Return to Answer

The broadest 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.

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.

The broadest 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 $m\times n$ matrix representing our rank $n$ regular matroid $M$. In the case of a graph, this would be the vertex-edge incidence matrix. Then the analog of the Laplacian is $\mathbf{L}:=\mathbf{M}^T\mathbf{M}$. 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.

The broadest 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.

The broadest class of matroids for which you have a Matrix Tree theorem are the regular matroids: 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 our rank $n$ regular matroid $M$. In the case of a graph, this would be the vertex-edge incidence matrix. Then the analog of the Laplacian is $\mathbf{L}:=\mathbf{M}^T\mathbf{M}$. 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.

The broadest 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 $m\times n$ matrix representing our rank $n$ regular matroid $M$. In the case of a graph, this would be the vertex-edge incidence matrix. Then the analog of the Laplacian is $\mathbf{L}:=\mathbf{M}^T\mathbf{M}$. 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.