Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a follow-up to a previous question. What graphs have incidence matrices of full rank?

Obvious members of the class: complete graphs.

Obvious counterexamples: Graph with more than two vertices but only one edge.

I'm tempted to guess that the answer is graphs that contain spanning trees as subgraphs. However, I haven't put much thought into this.

share|improve this question
add comment

5 Answers 5

up vote 18 down vote accepted

The first answer identifies "incidence matrix" with "adjacency matrix". The latter is the vertices-by-vertices matrix that Sciriha writes about. But the original question appears to concern the incidence matrix, which is vertices-by-edges. The precise answer is as follows.

Theorem: The rows of the incidence matrix of a graph are linearly independent over the reals if and only if no connected component is bipartite.

Proof. Some steps are left for the reader :-)

Note first that the sum of rows indexed by the vertices in one color class of a bipartite component is equal to the sum of the rows indexed by the other color class. Hence if some component is bipartite, the rows of the incidence matrix are linearly dependent.

For the converse, we have to show that the incidence matrix of a connected non-bipartite graph has full rank. Select a spanning tree $T$ of our graph $G$. Since $G$ is not bipartite, there is an edge $e$ of $G$ such that the subgraph $H$ formed by $T$ and $e$ is not bipartite.

The trick is to show that the columns of the incidence matrix indexed by the edges of H form an invertible matrix. We see that $H$ is built by "planting trees on an odd cycle". We complete the proof by induction on the number of edges not in the cycle.

The base case is when $H$ is an odd cycle. It is easy to show that its incidence matrix is invertible. Otherwise there is a vertex of valency one, $x$ say, such that $H \setminus x$ is connected and not bipartite. Then the incidence matrix of $H \setminus x$ is invertible and again it is easy to see this implies that the incidence matrix of $H$ is invertible.

Remark: I do not know who first wrote this result down. It is old, and is rediscovered at regular intervals.

share|improve this answer
    
Awesome, thanks! Do you have a reference for this? A graph theory textbook would be just fine. –  Jiahao Chen Nov 17 '09 at 20:15
1  
The earliest reference I could find in 30 minutes was: @article {MR0441791, AUTHOR = {Van Nuffelen, Cyriel}, TITLE = {On the incidence matrix of a graph}, JOURNAL = {IEEE Trans. Circuits and Systems}, YEAR = {1976}, NUMBER = {9}, PAGES = {572} It might be in Scheinermann's "Fractional Graph Theory", but I am travelling and cannot check this. It's surely in some of the texts on combinatorial optimization, but I am travelling... –  Chris Godsil Nov 19 '09 at 0:50
add comment

An interesting example of a class of graphs for which it not known when the adjacency matrix $A$ has full rank is the Hasse diagrams of the lattices $L(k,j)$. See pages 21-22 of arXiv:math/0501230. What makes this interesting is that explicit trigonometric formulas are known for the eigenvalues of $A$ and their multiplicities, but it is unclear from these formulas whether there is a zero eigenvalue of positive multiplicity.

share|improve this answer
add comment

As Chris pointed out, this answer is off the mark. The graphs with adjacency matrices (not incidence matrices) of non-full rank are called singular graphs. It seems that it is a known and difficult open problem to characterize them. See this paper by Sciriha.

share|improve this answer
add comment

I think I can find a graph with a spanning tree that does not have an adjacency matrix of full rank. Start with a path of length five join the first point to the fourth and the fifth two the secod. Then the first and the fifth will have the same adjacency row and that will be a dependency and that will be a graph with a spanning tree that does not have full rank. However the question is not about adjacency matrices but incidence matrices. However since any graph with a connected bipartite component does not have a incidence matrix of full rank as noted in another post we can take any connected tree and that graph will have a spanning tree and it will have bipartite component so it will not have a singular matrix of full rank.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.