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
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 4, 2020 at 3:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .