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?


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


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

  • $\begingroup$ 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? $\endgroup$
    – mgus
    Mar 5 '20 at 3:35
  • $\begingroup$ @mgus I'll add in what I had in mind when I have the chance $\endgroup$ Mar 5 '20 at 10:08
  • $\begingroup$ See my latest edit $\endgroup$ Mar 5 '20 at 14:21
  • $\begingroup$ 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? $\endgroup$
    – mgus
    Mar 5 '20 at 17:37
  • $\begingroup$ @mgus You're right about $n(m-1)$; I just had an extra minus sign there. $\endgroup$ Mar 5 '20 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.