Page 208 - Matrix Analysis & Applied Linear Algebra

4.4 Basis and Dimension 203

Rank and Connectivity
Let G be a graph containing m nodes. If G is undirected, arbitrarily
assign directions to the edges to make G directed, and let E be the
corresponding incidence matrix.

• G is connected if and only if rank (E)= m − 1. (4.4.18)

Proof. Suppose G is connected. Prove rank (E)= m − 1 by arguing that
T T T
dim N E =1, and do so by showing e =(1 1 ··· 1) is a basis N E .
T T
To see that e spans N E , consider an arbitrary x ∈ N E , and focus on
any two components x i and x k in x along with the corresponding nodes N i
and N k in G. Since G is connected, there must exist a subset of r nodes,
} , where and k = j r ,
{N j 1 ,N j 2 ,...,N j r i = j 1
for each p =1, 2,...,r − 1.
such that there is an edge between N j p and N j p+1

Therefore, corresponding to each of the r − 1 pairs N j p ,N j p+1 , there must
exist a column c p in E (not necessarily the p th column) such that components
j p and j p+1 in c p are complementary in the sense that one is (+1) while the
T
other is (−1) (all other components are zero). Because x E = 0, it follows that
T
x c p =0, and hence x j p = x j p+1 . But this holds for every p =1, 2,...,r − 1,
so x i = x k for each i and k, and hence x = αe for some scalar α. Thus {e}
T T
spans N E . Clearly, {e} is linearly independent, so it is a basis N E ,
T
and, therefore, dim N E = 1 or, equivalently, rank (E)= m−1. Conversely,
suppose rank (E)= m−1, and prove G is connected with an indirect argument.
If G is not connected, then G is decomposable into two nonempty subgraphs
G 1 and G 2 in which there are no edges between nodes in G 1 and nodes in G 2 .
This means that the nodes in G can be ordered so as to make E have the form

0
E 1
E = ,
0 E 2
where E 1 and E 2 are the incidence matrices for G 1 and G 2 , respectively. If
G 1 and G 2 contain m 1 and m 2 nodes, respectively, then (4.4.17) insures that

E 1 0
rank (E)=rank =rank (E 1 )+rank (E 1 )≤(m 1 −1)+(m 2 −1)=m−2.
0E 2
But this contradicts the hypothesis that rank (E)= m − 1, so the supposition
that G is not connected must be false.