Eigenvalues of $n^2 \times n^2$ matrix with $(n-1)^2$ along diagonal and $1$ or $1-n$ elsewhere depending on adjacencies.

Question

I reduced a confounding and challenging problem to the task of proving an unweildy inequality. Luckily, I managed to reduce the inequality to proving that a certain quadratic form is positive semidefinite. This in turn, I observed was equivalent to a certain matrix having non-negative eigenvalues. Unfortunately, now I am stuck. The problem in its most reduced form is as such:

Write the integers $1, \dots, n^2$ in a square. Let $A_n$ be an $n^2 \times n^2$ matrix where $a_{ij} = \begin{cases} (n-1)^2, i = j \\ 1-n, \, i,j \text{ adjacent} \\ 1, else\end{cases}$ where "adjacent" is defined as being in the same row or column in the square that was constructed. Prove that all eigenvalues of $A_n$ are non-negative.

We have $A_2 = \begin{bmatrix} 1 & -1 & -1 & 1 \\ -1 & 1 & 1 & -1 \\ -1 & 1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}, A_3 = \begin{bmatrix} 4 & -2 & -2 & -2 & 1 & 1 & -2 & 1 & 1 \\ -2 & 4 & -2 & 1 & -2 & 1 & 1 & -2 & 1 \\ -2 & -2 & 4 & 1 & 1 & -2 & 1 & 1 & -2 \\ -2 & 1 & 1 & 4 & -2 & -2 & -2 & 1 & 1 \\ 1 & -2 & 1 & -2 & 4 & -2 & 1 & -2 & 1 \\ 1 & 1 & -2 & -2 & -2 & 4 & 1 & 1 & -2 \\ -2 & 1 & 1 & -2 & 1 & 1 & 4 & -2 & -2 \\ 1 & -2 & 1 & 1 & -2 & 1 & -2 & 4 & -2 \\ 1 & 1 & -2 & 1 & 1 & -2 & -2 & -2 & 4\end{bmatrix}.$ I'm not gonna bother writing out $A_4$ or any larger matrices. It would take too much time to even input the matrix into Wolfram-Alpha.

We see that $A_2$ has rank $1$ and trace $4,$ so its eigenvalues are $4,0,0,0.$ Unfortunately, $A_3$ is not so easy to analyze, although we can see it has rank $\le 8$ and trace $36.$ Using https://matrixcalc.org/en/vectors.html, I found that it had eigenvalues $0,9$ with multiplicity $5, 4$ respectively. How could we show that in general, $A_n$ has eigenvalues $0, n^2$ with multiplicity $2n-1, (n-1)^2$ respectively? Would there be any way of arriving at this conjecture without a computer?

Update: Some info about the structure of the eigenvalues of $A_3.$ We will represent eigenvalues as $3 \times 3$ matrices for simplicity. For $0,$ any row or column can be all $1$s with everything else being a $0.$ For $9,$ certain (not all) $2 \times 2$ rectangles with $1$ on one diagonal and $-1$ on the other will work. For example, $\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & -1 & 0 \\ 0 & 0 & 0 \\ -1 & 1 & 0 \end{bmatrix}$ correspond to eigenvalues of $0, 9$ respectively. It easy to generalize the eigenvalue of $0$ to obtain $2n-1$ eigenvectors, but I don't see how the $(n-1)^2$ eigenvectors for $n^2$ generalize, and the fact that the eigenvalues for $9$ actually work lacks a natural explanation.

Second update: Let $J_n$ be the all ones matrix. We can write $A_3 = \begin{bmatrix} -2J' & J' & J' \\ J' & -2J' & J' \\ J' & J' & -2J' \end{bmatrix} = J'' - 3K$ where $J' = J-3I, J''$ is the all $J'$s block matrix of appropriate size, and $K$ is the block diagonal matrix with $J'$ on the diagonal. The spectrum of $J_n$ is well-known to be $\{n^{(1)}, 0^{(n-1)} \},$ so the spectrum of $J-kI$ is also easily found. Perhaps there is some trick with block matrices that will allow for an easy solution.

Answer 1

Notice that the condition that $i$ and $j$ are adjacent is exactly the same thing as saying that either $\lceil i/n\rceil = \lceil j/n\rceil$ or $i\equiv j$ mod $n$. Let $I_n$ denote the identity matrix and $J_n$ denote the $n\times n$ matrix of all $1$s. It can be shown that $$ A_n=(J_n-nI_n)^{\otimes 2},$$ where $A^{\otimes 2}$ denotes the Kronecker square, i.e. the Kronecker product $A\otimes A$. It follows from properties of the Kronecker product that $A_n$ has eigenvalues equal to the square of eigenvalues of $(J_n-nI_n)$. The problem is thus reduced to showing that the eigenvalues of $(J_n-nI_n)$ are real, which follows from the fact that it is a symmetric matrix.

Answer 2

The eigenvectors of this matrix live in $\mathbb R^{n^2}$, but we should think of them as $n \times n$ matrices, because each component corresponds to a location in the $n \times n$ grid.

The $2n-1$ eigenvalues of $0$ correspond to eigenvectors that put all $1$'s in a single row, or single column, and $0$'s everywhere else. (There are actually $2n$ of these, but there's a single linear dependency between them: the sum of all the row-type eigenvectors equals the sum of all the column-type eigenvectors equals the $n \times n$ all-$1$ matrix.)

To see that these are all eigenvectors of $0$, note that these correspond to $n$ locations in the grid that are all pairwise adjacent. So when we multiply by your matrix, each nonzero entry gets a single contribution of $(n-1)^2$ from the diagonal, and $n-1$ contributions of $1-n$ from the other nonzero entries. Meanwhile, each zero entry gets a single contribution of $1-n$ from the nonzero entry adjacent to it, and contributions $n-1$ of $1$ from the other nonzero entries.

The other $(n-1)^2$ eigenvectors should be orthogonal to these, which means they correspond to matrices with all row sums and column sums $0$. There's a natural basis for these: put a $1$ in the $(i,j)$ entry for $1 \le i,j \le n-1$, a $-1$ in the $(i,n)$ and $(n,j)$ entry, and a $1$ in the $(n,n)$ entry.

When you turn one of these into an $n^2$-dimensional vector and multiply by your matrix:

• Each zero entry which is not adjacent to any of $(i,j), (i,n), (n,j), (n,n)$ stays $0$: $(i,j)$ and $(n,n)$ contribute $+1$ and $(i,n)$ and $(n,j)$ contribute $-1$.
• Each other zero entry is adjacent to exactly two of them (it's in the $i$-th row or $j$-th column or $n$-th row or $n$-th column) of the opposite sign, and non-adjacent to two of the opposite sign, and those contributions still cancel.
• Each of the four nonzero entries picks up $(n-1)^2$ from the diagonal, $-2(1-n)$ from the adjacent nonzero entries, and $1$ from the non-adjacent nonzero entry, for a total of $n^2$. This is negated for the negative entries.

So we confirm that all $(n-1)^2$ of these vectors are eigenvectors of $n^2$. They are linearly independent, because each of them has a nonzero entry $(i,j)$ not shared by any other such vector.

Now we've found $n^2$ linearly independent eigenvectors, so we're done.