Eigenvalues of a certain combinatorially defined matrix

Question

Let $A_n$ be the matrix whose rows and columns are indexed by pairs $(i,j)$ with $1\leq i,j\leq n$ and $i\neq j$ (so $A$ is an $n(n-1)\times n(n-1)$ matrix), whose $((i,j),(k,l))$-entry is 0 if $i=k$ or $j=l$, and is 1 otherwise. Evidence suggests that the characteristic polynomial of $A$ (normalized to be monic) is given by $$ \det(xI-A_n)=(x-1)^{n^2-3n+1}(x+n-1)^{n-1}(x+n-3)^{n-1}(x-n^2+3n-3). $$ Is this a known result? If not, how can it be proved?

Answer 1

Let $E_m$ be the $m\times m$ all-ones matrix. We'll show that the spectrum of $$B_n:=I_{n(n-1)}+E_{n(n-1)}-A_n,$$ the matrix whose $((i,j),(k,\ell))$ entry is $1_{i=k}+1_{j=\ell}$, consists of $n^2-3n+1$ copies of zero, $n-1$ copies of $n-2$, $n-1$ copies of $n$, and one copy of $2n-2$. Since this one copy of $2n-2$ comes from the all-ones vector, it is easy to turn this into the desired description of the spectrum of $A_n$.

We do this by explicitly computing the eigenspaces. We will use the following description of the action of $B_n$ on a vector: $$(B_nv)_{ij}=\sum_{k\neq j}v_{kj}+\sum_{\ell\neq i}v_{i\ell}.\tag{$\star$}$$ Let $S=\{i,j\in[n]:i\neq j\}$. Let $\sigma:\mathbb R^S\to\mathbb R^S$ be the involution defined by $(\sigma v)_{ij}=v_{ji}$, define the subspace $$V=\left\{v\in\mathbb R^S:v_{ij}=v_{k\ell}\text{ whenever }i=k\right\};$$ we have that $\sigma V$ is the space of vectors $v$ for which $v_{ij}=v_{k\ell}$ whenever $j=\ell$. Note that $V\cap\sigma V$ consists only of the all-ones vector. As a result, the subspace $V+\sigma V$ has dimension $2\dim V-1=2n-1$. Property ($\star$) gives the description $$\frac1{n-1}B_n=\pi_V+\pi_{\sigma V},$$ where $\pi_W$ denotes the orthogonal projection onto a subspace $W$. From this, we learn the following:

• On the subspace $V^\perp\cap(\sigma V)^\perp=(V+\sigma V)^\perp$ of $\mathbb R^S$, which has dimension $n(n-1)-(2n-1)=n^2-3n+1$, the map $B_n$ evaluates to zero.
• On the subspace $V\cap\sigma V$, which is the span of the all-ones vector $\mathbf 1$, the map $B_n$ acts by $(2n-2)$ times the identity.
• Let $W=(V+\sigma V)\cap\mathbf 1^\perp$. This space has dimension $2n-2$, and as the intersection of two subspaces of $\mathbb R^S$ invariant under both $\sigma$ and $B_n$, $W$ is invariant under $B_n$.

The first two of the above properties give us the eigenvalues of zero and $2n-2$, and the third tells us that the remaining eigenvalues will be found in $B_n|_W$. Since $\sigma^2=1$ and $\sigma$ is symmetric, the space $W$ splits as the direct sum of the two orthogonal pieces $W_\pm$, defined as the $\pm1$-eigenspaces of $\sigma|_W$. We claim that $W_+$ is an $(n-2)$-eigenspace of $B_n$ and that $W_-$ is an $n$-eigenspace of $B_n$.

Take any $w\in W_\pm$; we can write $w=v\pm\sigma v$ for some $v\in V\cap \mathbf 1^\perp$. Write $a_1,\ldots,a_n$ so that $v_{ij}=a_i$ for each $i$ and $j\neq i$; we have $a_1+\cdots+a_n=0$ and $w_{ij}=v_{ij}\pm v_{ji}=a_i\pm a_j$ for each $i\neq j$. So, by ($\star$), \begin{align*} (B_nw)_{ij} &=\sum_{k\neq j}w_{kj}+\sum_{\ell\neq i}w_{i\ell}\\ &=\sum_{k\neq j}(a_k\pm a_j)+\sum_{\ell\neq i}(a_i\pm a_\ell)\\ &=\left(\sum_{k\neq j}a_k\right)\pm(n-1)a_j+(n-1)a_i\pm \left(\sum_{\ell\neq i}a_\ell\right)\\ &=-a_j\pm(n-1)a_j+(n-1)a_i\mp a_i\\ &=(n-1\mp 1)(a_i\pm a_j)=(n-1\mp 1)w_{ij}, \end{align*} as desired.