Page 207 - Matrix Analysis & Applied Linear Algebra

202 Chapter 4 Vector Spaces
Example 4.4.6

Rank and Connectivity. A set of points (or nodes), {N 1 ,N 2 ,...,N m } , to-
gether with a set of paths (or edges), {E 1 ,E 2 ,...,E n } , between the nodes is
called a graph.A connected graph is one in which there is a sequence of edges
linking any pair of nodes, and a directed graph is one in which each edge has been
assigned a direction. For example, the graph in Figure 4.4.1 is both connected
and directed.
1
E 1 E 2
E 5
2 E 4 4

E 3 E 6
3

Figure 4.4.1
The connectivity of a directed graph is independent of the directions assigned
to the edges—i.e., changing the direction of an edge doesn’t change the connec-
tivity. (Exercise 4.4.20 presents another type of connectivity in which direction
matters.) On the surface, the concepts of graph connectivity and matrix rank
seem to have little to do with each other, but, in fact, there is a close relationship.
The incidence matrix associated with a directed graph containing m nodes
and n edges is defined to be the m × n matrix E whose (k, j) -entry is


 1 if edge E j is directed toward node N k .
e kj = −1 if edge E j is directed away from node N k .
0 if edge E j neither begins nor ends at node N k .

For example, the incidence matrix associated with the graph in Figure 4.4.1 is

E 1 E 2 E 3 E 4 E 5 E 6
 
N 1 1 −1 0 0 −1 0
N 2  −1 0 −1 1 0 0 
E =   . (4.4.16)
N 3  0 0 1 0 1 1 
N 4 0 1 0 −1 0 −1
Each edge in a directed graph is associated with two nodes—the nose and the tail
of the edge—so each column in E must contain exactly two nonzero entries—a
(+1) and a (−1). Consequently, all column sums are zero. In other words, if

T
T
e =(1 1 ··· 1) , then e E = 0, so e ∈ N E T , and
T T
rank (E)= rank E = m − dim N E ≤ m − 1. (4.4.17)
This inequality holds regardless of the connectivity of the associated graph, but
marvelously, equality is attained if and only if the graph is connected.