Suppose $A$ is an order-$n$ matrix of zeroes and ones such that $A^2 = J$, the matrix of all ones. Show that $A$ has exactly $k$ ones along the diagonal, where $k^2 = n$.
I can show that $AJ=JA=kJ$, so in graph theoretic terms, $A$ is a regular graph of order $k$. And $A$ is connected, or else $A^2$ would have zeroes in it. I wonder if there's a theorem that can establish that the graph has exactly $k$ loops? Or perhaps it's more obvious from a matrix perspective.
I know that regularity and connectivity by itself isn't sufficient, since for example the matrix
$$A_\varnothing=\begin{bmatrix}1& & &1\\ &1&1& \\1& &1& \\&1&&1\end{bmatrix}$$
is $k$-regular and connected, but fails to satisfy $A_\varnothing^2 = J$ and fails to have $k$ ones along the diagonal.
An example that does exhibit this property is
$$A_\checkmark = \begin{bmatrix}1&1&&\\&&1&1\\1&1&&\\&&1&1\end{bmatrix}$$
I found I can prove it as a theorem using properties of eigenvalues(!).
The trick is that for a matrix of zeroes and ones, the number of ones along the diagonal is equal to the sum of the values along the diagonal (the trace of the matrix). But the trace of a matrix is also equal to the sum of its (generalized) eigenvalues. Hence it's enough to prove that $A$ has generalized eigenvalues $0$ (with multiplicity $n-1$) and $k$ (with multiplicity 1).
A nice aspect about this approach is that it generalizes to higher powers of $A$, and to matrices whose entries are not just zeroes and ones:
In detail:
Proof of (2): we note that the matrix $J$ computes the column/row sums of a matrix: For any order-$n$ matrix $M$, let $r_1, \ldots, r_n$ be its row sums. Note that by matrix multiplication rules, $MJ$ is the matrix of row sums: $$MJ = \begin{bmatrix}r_1 & r_1 & \ldots & r_1\\r_2 & r_2 & \ldots & r_2\\\vdots & \vdots & &\vdots\\ r_n & r_n & \ldots & r_n\\\end{bmatrix}$$ and similarly $JM$ is the matrix of column sums.
If $A^2 = J$ by hypothesis, then $A^3 = AJ = JA$. But $AJ$ is the matrix of row sums of $A$, and $JA$ is the matrix of column sums of $A$. If they're equal, then every row and column of $A$ must have the same sum— call it $k$.
Consequently, $AJ = JA = kJ$ (the matrix where every entry is $k$.)
As a corollary, we can prove that $k^2 = n$ (the order of the matrix) because $J^2 = nJ$ (the row sums of $J$ are all $n$) and $J^2 = JA^2 = (JA)A = kJA = k(JA) = k(kJ) = k^2J$, so $nJ = k^2 J$, which means that $k^2 = n$.
Proof of (5): The generalized eigenvalue formula is $$(A - \lambda I)^n v = 0.$$
From (3), above, we know that $k$ is an eigenvalue and hence a generalized eigenvalue. If $n=1$, this must be the only eigenvalue and we're done. Otherwise, we'll show that 0 is another generalized eigenvalue and that it has multiplicity $n-1$. Because there are exactly $n$ generalized eigenvalues, we can conclude that 0 is the only other eigenvalue, and that $k$ has multiplicity 1.
Considering the eigenvalue $\lambda = 0$, the generalized eigenvalue equation reduces to $A^n = 0$. But because $A^2 = J$ implies that $A^3 = kA^2$, we can prove by induction that $A^{r+2} = k^r A^2$ for integer $r \geq 0$. Hence $A^n = k^{n-2} A^2 = k^{n-2} J$. (Note: $n>2$ because $n$ is a perfect square and we're considering only the case $n>1$.)
Hence generalized eigenvectors of $A$ with eigenvalue 0 are vectors $v$ such that $$k^{n-2} J v = 0$$ or, eliminating the positive constant $k^{n-2}$, just $$Jv = 0.$$
But $Jv$ returns a vector where each entry is the sum of the entries in $v$:
$$Jv = (\sum_i v_i)\begin{bmatrix}1\\1\\\vdots \\ 1\end{bmatrix}$$
so $J$ sends to zero just those vectors whose entries sum to zero. The set of all such zero-sum vectors is a subspace of dimension $n-1$, so we have shown that $0$ is a generalized eigenvalue of $A$ with algebraic multiplicity $n-1$.
Because $k$ is an eigenvalue of $A$ and there are exactly $n$ generalized eigenvalues, it follows that $k$ is the only other generalized eigenvalue and that it has multiplicity 1. Q.E.D.