The Matrix-Tree Theorem without the matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T22:03:43Z http://mathoverflow.net/feeds/question/73385 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix The Matrix-Tree Theorem without the matrix Daniel Moskovich 2011-08-22T08:41:21Z 2011-10-02T18:13:50Z <p>I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me will be to teach the Matrix-Tree Theorem, which I think is the only place that linear algebra is used in the course.</p> <p>Let &#954;(G) denote the number of spanning trees of G (the <em>complexity</em> of G), and let L(G) denote the Laplacian matrix of G. Finally, for a vertex v of G, let L(v|v) denote the Laplacian matrix with the row and column corresponding to v deleted.</p> <blockquote> <b>Matrix-Tree Theorem:</b> &#954;(G)= det L(v|v). </blockquote> <p>It seems a shame for Linear Algebra to be a prerequisite for my course. Anyway, I don't expect most of my students to be great Linear Algebra experts. Because my students might not remember things like Cauchy-Binet, but mainly so that I myself feel that I can really understand what I'm teaching, I wonder how the Matrix-Tree Theorem could be proven without ever mentioning matrices. On a planet with strong combinatorics and where linear algebra had not been discovered, how would they prove the Matrix-Tree Theorem?</p> <p>The RHS of the Matrix-Tree Theorem makes sense without ever mentioning matrices, via the <a href="http://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma" rel="nofollow">Lindstr&ouml;m-Gessel-Viennot</a>(-Karlin-MacGregor) Lemma. Construct a graph H, with a source and a sink corresponding to each vertex of G, so that the signed sum of edge weights gives the entries of the Lagrangian matrix for G (surely there's a clever standard way to do this!) and define the determinant of H to be the signed sum of all n-tuples of non-intersecting paths from the sources to the sinks. This interpretation of the determinant seems a nice topic to teach. Maybe there's even an easier way.</p> <p>Cauchy-Binet becomes an elementary property of sets of non-intersecting paths in H, but I can't see how to free the rest of the proof of the Matrix-Tree Theorem from linear algebra.</p> <blockquote> <b>Question:</b> Is there a proof of the Matrix-Tree Theorem which makes no mention of matrices? Is it simple enough that one could teach it in an introductory graph theory course? </blockquote> <p><b>Note 1</b>: If the purpose of the Matrix-Tree Theorem is to efficiently calculate the complexity of a graph, then dodging linear algebra is surely counterproductive, because a determinant can efficiently be calculated in polynomial time. But, quite beside from my interest in "correctly-tooled" proofs and my teaching goals, I have vague dreams which are almost certainly nonsense about better understanding the Alexander polynomial as a quantum invariant along the lines of <a href="http://mathoverflow.net/questions/9847/why-is-the-alexander-polynomial-a-quantum-invariant" rel="nofollow">this question</a> which might conceivably factor through the Matrix-Tree Theorem (or rather some version of Kirchhoff's formula), and I think I clearly want to stay in the diagrammatic world.</p> <p><b>Note 2</b>: <a href="http://qchu.wordpress.com/2009/11/17/the-lindstrom-gessel-viennot-lemma/" rel="nofollow">This excellent post</a> by Qiaochu Yuan suggests that the answer to my question is in Aigner. I'm travelling right now, and the relevant section isn't on Google Books, so I don't have access to Aigner for the next few weeks. If memory serves, Aigner still uses linear algebra, but maybe I'm wrong... anyway, if the answer turns out to be "look in Aigner" then please downvote this question, or if you could summarize how it's done, I would be happier. The answer will surely turn out to be "look in [somewhere]" anyway, because surely this is easy and well-known (just I don't know it)...</p> http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix/73391#73391 Answer by Gjergji Zaimi for The Matrix-Tree Theorem without the matrix Gjergji Zaimi 2011-08-22T09:44:30Z 2011-08-22T09:44:30Z <p>Interesting question! There is an elementary way to prove the matrix tree theorem using only combinatorial reasoning and bijections. The result I'm referring to is: the number of spanning trees in a graph $G$ is the same as the number of $G$-parking functions. There is a bijective proof of this fact in <a href="http://arxiv.org/abs/math/0307292" rel="nofollow">"A family of bijections between G-parking functions and spanning trees"</a> by D. Chebikin and P. Pylyavskyy. Now what do these $G$-parking functions have to do with the determinant of the laplacian $L(G)$?</p> <p>It turns out that $G$-parking functions are representatives of the elements in the cokernel of the map $\mathbb Z^{n}\to \mathbb Z^n$ given by multiplication by $L(G)$, where $n$ is the number of vertices in $G$. This cokernel pops up in a lot of places and it's usually called the Critical group of $G$ or the sandpile group of $G$ (or by some authors, the Jacobian group or Picard group) and it is well known to have the same cardinality as the number of spanning trees of $G$. Any bijection between these will not be canonical because there is no canonical choice of spanning tree on $G$, so all bijections must make choices at some point.</p> <p>As far as bijections with other cokernels, like LGV or Kasteleyn-Percus, I don't know if it can be done neatly in great generality. I know that counting spanning trees can be translated to counting perfect matchings for planar graphs, for instance. Perhaps it extends to other nice classes.</p> <p>That said, even though this approach avoids mentioning matrices, Cauchy-Binet and all that, it would be awful for a first proof of the matrix tree theorem. I think this is similar to trying to teach the elementary proof of the prime number theorem in a first course of analytic number theory. Using less tools doesn't necessarily lead to more enlightenment. :)</p> http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix/73400#73400 Answer by Chris Godsil for The Matrix-Tree Theorem without the matrix Chris Godsil 2011-08-22T12:18:12Z 2011-08-22T12:18:12Z <p>You can do without Cauchy-Binet.</p> <p>If $e \in E(G)$, let $G/e$ denote the graph you get by contracting $e$ to a vertex. Let $t(G)$ denote the number of spanning trees in $G$. Then $$t(G) = t(G\setminus e) + t(G/e).$$ If $Q$ denotes the Laplacian of $G$ and $M[u]$ the matrix we get from the Laplacian by deleting the row and column with index $u$ from $M$, it is straightforward (using standard determinental operations) to show that $$\det Q(G)[u] = \det Q(G\setminus e)[u] +\det Q(G/e)[u]$$ So the result follows by induction.</p> <p>This proof is presented in Section 13.2 of one of my favorite books on algebraic graph theory :-) I am sure many other people have come up with it. It provides an excuse to talk about some of the other interesting graph parameters thatn can be computed by deletion-contraction (or is it deletion/contraction?)</p> http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix/73429#73429 Answer by Ira Gessel for The Matrix-Tree Theorem without the matrix Ira Gessel 2011-08-22T18:40:17Z 2011-08-22T18:40:17Z <p>A combinatorial proof of the matrix-tree theorem can be found in the paper by D. Zeilberger <a href="http://www.math.rutgers.edu/~zeilberg/mamarimY/Zeilberger_y1985_p61.pdf" rel="nofollow"> A combinatorial approach to matrix algebra,</a> Discrete Math. 56 (1985), 61–72. The proof uses only the interpretation of the determinant as an alternating sum over permutations. Each term corresponds to a digraph, and the digraphs that do not correspond to trees cancel.</p> http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix/76994#76994 Answer by Daniel Moskovich for The Matrix-Tree Theorem without the matrix Daniel Moskovich 2011-10-02T18:13:50Z 2011-10-02T18:13:50Z <p>I asked Daniel Spielman a related question, which was what the most conceptual proof of the matrix-tree theorem is, without appealing to the real numbers. He suggested <a href="http://www.cs.yale.edu/homes/spielman/561/lect18-09.pdf" rel="nofollow">these notes</a> by Nikhil Srivastava.</p> <p>Matrices are used, but really the linear algebra looks to me like it can be turned into combinatorics on graphs in a straightforward manner, so his answer constitutes a nice answer to this question as well. In any event, it's a nice short conceptual proof of the matrix-tree theorem which I hadn't known about.</p>