For which $m,n$ is the graph $K_{m,n}$ integral?

Question

A graph is integral if the eigenvalues of its adjacency matrix are all integers. For which integers $m$ and $n$ is $K_{m,n}$, the complete bipartite graph on $m$ and $n$ vertices, integral?

Answer 1

Let $A$ denote the adjacency matrix of $K_{m,n}$. Now up to reordering of rows and columns $A$ must look like \begin{equation*} A = \begin{bmatrix} 0&\dots&0&1&\dots&1 \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&\dots&0&1&\dots&1 \\ 1&\dots&1&0&\dots&0 \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 1&\dots&1&0&\dots&0 \\ \end{bmatrix} \end{equation*} where the blocks of ones have dimension $m \times n$. Now let's calculate some successive powers of $A$. This can done quickly by recalling that the $(i,j)$ entry of $A^n$ represents the number of distinct paths of length $n$ from vertex $i$ to vertex $j$. \begin{equation*} A^2 = \begin{bmatrix} m&\dots&m&0&\dots&0 \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ m&\dots&m&0&\dots&0 \\ 0&\dots&0&n&\dots&n \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&\dots&0&n&\dots&n \\ \end{bmatrix} \quad A^3 = \begin{bmatrix} 0&\dots&0&mn&\dots&mn \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&\dots&0&mn&\dots&mn \\ mn&\dots&mn&0&\dots&0 \\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ mn&\dots&mn&0&\dots&0 \\ \end{bmatrix} \end{equation*} So from this we see that $A$ has minimal polynomial $A^3-mnA$. The minimal polynomial divides the characteristic polynomial, and all the roots of the characteristic polynomial (eigenvalues) are roots of this minimum polynomial too (Cayley-Hamilton theorem), so $A$ has integer eigenvalues exactly when the roots of $A^3-mnA$ are integers. The roots of $A^3-mnA$ are $0$ and $\pm\sqrt{mn}$, so we can conclude that $K_{m,n}$ is integral exactly when the product $mn$ is a square.