For a directed graph with vertices 
, 
, 
, the reachability matrix 
records whether one graph vertex
can be reached from another along a directed graph path.
With zero-length paths included, its entries are
 |
(1)
|
In particular, 
for every 
.
This matrix represents the reflexive
closure of the transitive closure of the
binary relation defined by the directed edges.
If 
is the adjacency matrix, with 
recording edges directed
from 
to 
,
then
 |
(2)
|
where 
is the identity matrix and the sign
function is applied to each entry separately. The powers count directed walks,
and a reachable pair of distinct vertices always
has a graph path of length at most 
. Other conventions require positive-length directed walks;
under those conventions, a diagonal entry is 1 only
when its graph vertex belongs to a directed graph
cycle.
In control theory, "reachability matrix" also denotes the controllability matrix of a finite-dimensional linear time-invariant system, whose column space consists of the states reachable from the zero state.
