Which graphs have incidence matrices of full rank? - MathOverflow

Which graphs have incidence matrices of full rank?

2009-11-14T19:04:14Z

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.

Answer by Kristal Cantwell for Which graphs have incidence matrices of full rank?

2009-11-14T19:20:05Z

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.

Answer by Konrad Swanepoel for Which graphs have incidence matrices of full rank?

2009-11-14T19:34:04Z

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.

Answer by Chris Godsil for Which graphs have incidence matrices of full rank?

2009-11-15T14:54:29Z

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.

Answer by Richard Stanley for Which graphs have incidence matrices of full rank?

2009-11-24T04:03:36Z

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.

Answer by lucas for Which graphs have incidence matrices of full rank?

2011-05-25T10:50:15Z

http://books.google.com/books?id=Yr2pJA950iAC&pg=PA140&lpg=PA140&dq=incidence+matrix+rank+of+a+graph&source=bl&ots=9expNEXB_S&sig=5qb8FNhNPFbAEi3taFMxN1WKHR4&hl=en&ei=cNzcTfD4N8vJsgbaleTpDg&sa=X&oi=book_result&ct=result&resnum=6&ved=0CDAQ6AEwBQ#v=onepage&q=incidence%20matrix%20rank%20of%20a%20graph&f=false