A question about the matrix tree theorem. How to compute the determinant of the following matrix? 
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.
 A: 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}$.
A: 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.)
