# Eigenvalues of block Toeplitz matrix with Toeplitz blocks

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.

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 $$$$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}$$$$

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 $$$$\sigma(J_n)=\{(n,1),(0,n-1)\}.$$$$ 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 $$$$\sigma(C)=\{(m-1,1),(-1,m-1)\}.$$$$ 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$$.

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$$.

• I have made some edits based on your response (please see edit). However, the resulting sum of the Kronecker product and the diagonal matrix confuses me. How can I proceed?
– mgus
Mar 5 '20 at 3:35
• @mgus I'll add in what I had in mind when I have the chance Mar 5 '20 at 10:08
• See my latest edit Mar 5 '20 at 14:21
• Thanks for your response. Now it is clear to me except one thing: if the spectrums of $C$ and $J_n$ are indeed $\sigma(C)=\{(m-1,1),(-1,m-1)\}$ and $\sigma(J_n)=\{(n,1),(0,n-1)\}$, respectively then where is the eigenvalue $-n(m-1)$ of $C \otimes J$ is coming from? I thought it would be $n(m-1)$ with multiplicity $1$. After doing the remaining of the calculations for the eigenvalues of $A$ it seems that this should be true but how? Am I missing some plus or minus somewhere?
– mgus
Mar 5 '20 at 17:37
• @mgus You're right about $n(m-1)$; I just had an extra minus sign there. Mar 5 '20 at 17:39