3
$\begingroup$

On the wikipedia page for the Kirchoff matrix theorem, they state a souped up version of the theorem:

Let $G$ be a finite undirected loopless graph and let us form the square matrix $L$ indexed by the vertices of the graph $G$ so that $L_{vv} = \sum_{e = (v,w)}x_e$ and $L_{vw} = -x_{(v,w)}$ where $e = (v,w)$ is an edge between vertices $v,w$ and we have variables $x_e$ for each edge in the graph.

Note that each row and column sum is zero so that each minor of $L$ gotten by deleting one row/column has the same determinant and this determinant turns out to be: $$\det'(L) = \sum_{T}\prod_{e\in T}x_e$$ where we sum over spanning trees $T$. I can prove this last statement in a hands on way but it seems like it should have a conceptual explanation.

In particular, this reminds me a lot of the quiver algebra, is there a way to interpret Kirchoff's theorem using quiver algebras (or perhaps the representation theory of some similar ring)?

As an example of what I mean by a conceptual explanation, the Frobenius determinant theorem is along the lines of what I am aiming for. It is a very explicit statement about determinants of some matrix associated to any finite group but secretly, it's a statement about the irreducible representation decomposition of the group algebra $k[G]$. Is there some similar statement here with respect to the ring $k[x_e : e = (v,w)]$?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ There are many known proofs of the Matrix-Tree theorem; I find your description of what qualifies as "conceptual" a little unclear. But for instance determinants are related to volumes, and there are thus connections between the M-T theorem and polyhedral/tropical geometry- see for instance arxiv.org/abs/1304.4259. $\endgroup$
    – Sam Hopkins
    Commented Jul 3, 2021 at 17:24
  • $\begingroup$ @SamHopkins I guess I really do have something fairly concrete in mind by "conceptual" and I edited the question to include this. I would really like an explanation in terms of representations of the ring $k[x_e : e = (v,w)]$ and also perhaps an interpretation of this ring? $\endgroup$
    – Asvin
    Commented Jul 3, 2021 at 18:04
  • $\begingroup$ Well the ring $k[x_e]$ knows nothing about the structure of $G$ so I don't see much hope there. (Though somewhat similar, and definitely related to M-T stuff, is the notion of cut and cycle spaces of a graph, which are subspaces of the vs of formal linear combinations of edges.) Whether there is any connection between path algebras of a quiver and the M-T theorem is a quite interesting question, I have no idea about that... $\endgroup$
    – Sam Hopkins
    Commented Jul 3, 2021 at 18:15
  • $\begingroup$ Right, we would definitely like to impose more structure on $k[x_e]$ before trying to use it - I am just not sure what structure to impose. $\endgroup$
    – Asvin
    Commented Jul 3, 2021 at 18:24
  • $\begingroup$ One more possible place to look for associating an algebraic structure to a graph and getting the M-T theorem out of it: in arxiv.org/abs/1303.1148 it is explained how to obtain the chromatic polynomial of a graph from its associated Kac-Moody algebra. Now, the chromatic polynomial does not contain knowledge of the number of spanning trees- but the closely related Tutte polynomial does. And, even if we could get to number of spanning trees this way, not clear at all where a determinant would come in. But again, it's along the lines of what you were inquiring about... $\endgroup$
    – Sam Hopkins
    Commented Jul 3, 2021 at 18:43

0

Reset to default

You must log in to answer this question.