12
$\begingroup$

The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not see how to generalize it to general matroids. Also the graphs with isomorphic cycle matroids may have quite different Laplacian matrices. However, possibly there exists a known generalization?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

A broader class of matroids for which you have a Matrix Tree theorem are the regular matroids (those representable over every field): see, e.g., https://arxiv.org/abs/1404.3876.

EDIT: Let me actually try to give a very simple explanation of what's going on here.

Let $\mathbf{M}$ be an $n\times m$ matrix representing (i.e., its columns represent) our rank $n$ regular matroid $M$. In the case of a graph, this would be the vertex-edge incidence matrix (well, almost- we have to delete the first row of the incidence matrix to get a full rank matrix). Then the analog of the (reduced) Laplacian is given by $\mathbf{L}:=\mathbf{M}\mathbf{M}^T$. Now, the key (in fact, by a result of Tutte, equivalent) property of regular matroids is that we can choose $\mathbf{M}$ to be totally unimodular, meaning every minor is $=0, \pm 1$. Let's say we've done that. Then a routine application of the Cauchy-Binet formula shows that $\mathrm{det}(\mathbf{L})$ is equal to the number of $n$-tuples of linearly independent columns of $\mathbf{M}$, i.e., the number of bases of $M$.

Note that here we only used that the maximal minors of $\mathbf{M}$ are $0,\pm 1$, so maybe you can get away with slightly less than a regular matroid, I'm not sure.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ One way to do better than regular matroids is to allow complex matrices where all subdeterminants are zero or have modulus 1. The same Cauchy--Binet argument shows $\det(MM^*)$ counts bases. The matroids representable by this kind of matrix are the sixth-root-of-unity matroids. $\endgroup$
    – lambda
    Oct 2, 2020 at 22:18
  • 3
    $\begingroup$ Am I correct in assuming that there are complexity theoretic reasons for the lack of a general result of this sort? Google seems to suggest that counting bases is #P-complete in general. $\endgroup$
    – Gjergji Zaimi
    Oct 2, 2020 at 22:28
  • 3
    $\begingroup$ Regarding maximal vs nonmaximal minors: if the matrix has an $n \times n$ identity matrix as a submatrix then every subdeterminant is (up to sign) equal to a maximal one and the conditions are equivalent. But since you have some invertible $n \times n$ submatrix (with determinant $\pm 1$ by assumption) you can multiply on the left by the inverse to get such a submatrix while leaving the maximal minors unchanged up to sign. So the matroid is still regular in this case. $\endgroup$
    – lambda
    Oct 3, 2020 at 1:01
  • 1
    $\begingroup$ In general the number of bases is not the "right" invariant. The core example is the matroid represented by the columns of the top boundary map of the $d$-dimensional skeleton of the $n$-vertex simplex. In 1983 Kalai proved, using Binet-Cauchy, that the "count" of bases is $n^{\binom{n-2}{d}}$ (which reduces to Cayley's theorem for the case $d=1$) --- but you need to weight each basis by the square of the size of the codimension-1 homology of the simplicial complex it generates, and this group starts to be nontrivial at $n=6$ and $d=2$. $\endgroup$
    – Jeremy Martin
    Nov 4, 2020 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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