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.
Best Answer
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.)