A question about the matrix tree theorem. How to compute the determinant of the following matrix?

Question

The problem is to determine the number of spanning trees in $K_{r,s}$. The Matrix tree theorem states that the answer is the determinant of the matrix $M_{ii}$, where $M_{ii}$ is the matrix obtained from deleting the first row and the first column of $X-A$, where $X$ is the diagonal matrix of degree of each vertex and $A$ is the adjacency matrix of $K_{r,s}$.

I have the desired matrix below, denoted as $M$, and its determinant is the answer of the graph theory question. However, I have difficulty in computing its determinant. The upper left corner is an $(r-1) \times (r-1)$ diagonal matrix with diagonal entry $s$, and the lower right corner is an $s \times s$ diagonal matrix with diagonal entry $r$. All the other entries are $-1$.

Though the matrix looks rather harmonic, I have no idea how to compute its determinant when $r$ and $s$ are arbitrary natural numbers. I appreciate any help from you guys.

Answer 1

You can grind it out using row and column operations, to end up with an upper diagonal matrix, from which the determinant is the product of the diagonals, or a quicker way is to use the formula \begin{align} \text{det} \begin{pmatrix} A & B \\ C & D \end{pmatrix} = \text{det}(A) \text{det}(D - CA^{-1}B) \end{align}

which is not so hard to compute, as A is diagonal, so the inverse has a nice form. I think the answer should be $r^{s-1}s^{r-1}$.

Answer 2

Here is a convenient trick for computing the determiant: instead of using any expansion formulas, find a full set of eigenvalues or eigenvectors for $M$. Then, use the fact that the determinant is the product of eigenvalues. This is often a good strategy when the matrix has "nice" symmetries, and the symmetries can be used to find all eigenvalues easily. Also, this is a good strategy when a large matrix has only a small number of (distinct) eigenvalues, which is the case here!

Now consider the Laplacian matrix of the graph $K_{r,s}$ (before deleting a row and column): the eigenvalues are $0$, $r$, $s$, and $r+s$. The $r$-eigenspace has multiplicity $s-1$, the $s$-eigenspace has multiplicity $r-1$, and the $(r+s)$-eigenspace and $0$-eigenspace have multiplicity $1$. Therefore the determinant of the reduced Laplacian (after deleting a row and column) is $$ \frac1{n} \prod (\text{non-zero eigenvalues}) = \frac1{r+s}r^{s-1}s^{r-1} (r+s) = r^{s-1} s^{r-1}. $$ (Once we know the eigenvalues are $r$, $s$, and $r+s$, it is straightforward to check their multiplicities. The part that requires some luck / insight is to guess that these are the correct eigenvalues.)