3

There is a theorem in Algebraic graph theory which state: "Let X be a graph with n vertices and $c_o$ bipartite connected components. If B is the incidence matrix of X, then its rank is given by rk(B) = n - $c_o$."

This is what I think should be the way of proving this theorem. If a graph has $c_o$ bipartite components then the incidence matrix has $2c_o$ zero block matrices and therefore the row echelon form will contain $c_0$ free variables and hence the result.

Can someone provide a better proof otherwise I have lost interest in the proof in Godsil chapter 8? Is my logic okay here?

Christian Prince
  • 1,388

1 Answers1

3

First we consider that you know that any binary matrix for which the sum of row vectors modulo 2 is zero is linearly dependent otherwise it is independent.

Now the suppose it has one binary component then the sum of the rows modulo 2 is a zero matrix, because we will be adding two ones in one column and there are only two of these hence the rank of this matrix will be atmost $n-1$.

Considering any set of $n-1$ rows of the matrix any of their some modulo 2 is some $e_i$ and hence the rank of this matrix is atmost $n-1$

It follows here that the rank is $n-1$

Suppose the graph has $c_o$ components which are connected and bipartite then the incidence matrix can be reordered so that the incidence matrices of each component is aligned along the major diagonal and from our analysis above each has rank $n_i - 1$. The rank of the whole matrix is $\displaystyle \sum _{i=1}^{c_o} (n_i - 1 )=n-c_o$. It is difficult to understand profs like Godsil. Good luck