15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hopefully needless to say: the term "graphs that contain spanning trees as subgraphs" occuring in the OP is equivalent to just "connected graphs". (By propositional logic alone, 'contains spanning tree=>is connected'. By a usual application of Zorn's lemma, and hence by virtue of AC, the converse 'is connected=>contains spanning tree' is true, too, see e.g. Chapter 2.3 of Stillwell's translation of Serre's 'Trees'.) (And for finite graphs, the stated equivalence holds in a logical framework much weaker than ZFC, though I sadly do not know its reverse-mathematical status.) $\endgroup$ – Peter Heinig Aug 17 '17 at 5:51
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Awesome, thanks! Do you have a reference for this? A graph theory textbook would be just fine. $\endgroup$ – Jiahao Chen Nov 17 '09 at 20:15
  • 2
    $\begingroup$ 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... $\endgroup$ – Chris Godsil Nov 19 '09 at 0:50
10
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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