Eigenvalues of block Toeplitz matrix with Toeplitz blocks

eigenvalues-eigenvectorslinear algebramatricesspectral-theorytoeplitz-matrices

Consider integers $m,n$ and a $m \times m$-block Toeplitz matrix $A$ consisting of two different types of blocks as follows

\begin{align}
A_{mn \times mn}
&=
\begin{bmatrix}
B & C & C & \cdots & \cdots & C \\
C & B & C & C & \cdots & C \\
C & C & B & C & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & C \\
C & \cdots & \cdots & C & B & C \\
C & \cdots & \cdots & \cdots & C & B
\end{bmatrix}
_{mn \times mn}
,
\end{align}

where $B$'s are diagonal blocks with $B=\frac{1}{m}I_n$ and $C$'s are multiples of the all-ones matrix $J_n$, specifically $C=\frac{1}{mn}J_n$.

I want to compute the eigenvalues of $A$ (I am mainly interested in the value of the 2nd largest eigenvalue since it has a special meaning in graph expansion applications).

Note that in my problem the following conditions also hold for $m,n$:

  • $m$ is odd.
  • $n$ is prime.
  • $m<n$.

I have experimented with such matrices on the computer and I have observed a trend for the spectrum of $A$ which consists of the following eigenvalues:

  • $\lambda_1=0$ with algebraic multiplicity $m-1$.
  • $\lambda_2=1/m$ with algebraic multiplicity $m(n-1)$.
  • $\lambda_3=1$ with algebraic multiplicity $1$.

I do not claim that this is necessarily the answer but at least it was consistent for the pairs of $m,n$ I tried.

Can you suggest how one can go and prove the above claim (if correct) or pinpoint other known results?

EDIT

After Omnomnomnom's note that
\begin{equation}
A = \frac 1{mn}\underbrace{\pmatrix{
0&1&\cdots & 1\\
1&0&\ddots&\vdots\\
\vdots&\ddots&\ddots&1\\
1&\cdots&1&0}}_{= C_{m \times m}} \otimes J_n + \frac 1m I_{mn}
\end{equation}

I did some computation of the spectrums of the individual matrices. First, the characteristic polynomial of the all-ones $J_n$ is $(\lambda-n)\lambda^{n-1}$ and hence its spectrum (with the multiplicities) is
\begin{equation}
\sigma(J_n)=\{(n,1),(0,n-1)\}.
\end{equation}
For $C$, assume that $\lambda_1,\dots,\lambda_m$ are its eigenvalues. By the facts that $\mathrm{det}(C-(-1)I_m)=det(J_m)=0$, $C\mathbf{1}_m=(m-1)\mathbf{1}_m$ and $\mathrm{trace}(C)=\sum_i\lambda_i=0$ it turns out that
\begin{equation}
\sigma(C)=\{(m-1,1),(-1,m-1)\}.
\end{equation}
Suppose that $\mu_1,\dots,\mu_n$ are the eigenvalues of $J_n$ then by the Kronecker product's properties the spectrum of $CJ_n$ consists of the pairwise products $\lambda_i\mu_j, \forall i,j$.

Best Answer

Your observations are correct and hold for arbitrary $m,n$. It suffices to note that $$ A = \frac 1{mn}\pmatrix{ 0&1&\cdots & 1\\ 1&0&\ddots&\vdots\\ \vdots&\ddots&\ddots&1\\ 1&\cdots&1&0} \otimes J_n + \frac 1m I_{mn} $$ and use the properties of the Kronecker product.

In more detail: $C_{m \times m}$ is a rank 1 update of a scalar matrix, so we find that its eigenvalues are $-1$ with multiplicity $m-1$ and $m-1$ with multiplicity $1$. On the other hand, $J_n$ has eigenvalues $0$ with multiplicty $n-1$ and $n$ with multiplicity $1$.

It follows that $C \otimes J$ has eigenvalues $0$ with multiplicity $m(n-1)$, $-n$ with multiplicity $m-1$, and $n(m-1)$ with multiplicity $1$.

From there, it suffices to note that $\lambda$ is an eigenvalue of $A$ if and only if $c \lambda + d$ is an eigenvalue of $c A + dI$.

Related Question