# Can the eigenvalues of this block circulant matrix be found?

I have a matrix of the form

$$M = \begin{pmatrix} A & A^T & & & I\\ I & A & A^T & & \\ & I & A & \ddots &\\ & & \ddots & \ddots & A^T\\ A^T & & & I & A \end{pmatrix}$$

where $$I$$ is an $$n \times n$$ identity matrix and $$A$$ is an $$n \times n$$-matrix given by

$$A = \begin{pmatrix} 0 & 1 & 0 & \dots & 0\\ \vdots & \ddots& \ddots & \ddots & \vdots\\ 0 & \dots & 0 & 1 & 0\\ 0 & \dots & & 0 & 1\\ 0 & \dots & & & 0 \end{pmatrix}$$

that is a matrix which has ones on the super diagonal and zeros everywhere else.

1. Is there some way to find the eigenvalues of this matrix?

2. If there is, can it be generalized to a more complicated $$A$$?

Since $$A$$ and $$A^T$$ don't commute, one cannot diagonalize them simultaneously (also, they are not even diagonalizable), otherwise that would have been a straightforward way to do it. I have tried computing the characteristic polynomial, but I cannot seem to find a way to simplify the determinant.

• If $A$ is $n\times n$ with only $1$s in the superdiagonal, then the bottom row of $A$ should be zeros, right? If $A$ had a $1$ in the bottom left corner, it would be [circulant], and that would make $M$ circulant as well. Those matrices are nice since they're diagonalized by the discrete Fourier transform. The eigenvalues can be computed using the entries of $M$ and the roots of unity. The formula is provided in the link, under "eigenvectors and eigenvalues" section. You may be able to leverage this result to get something close. : en.wikipedia.org/wiki/Circulant_matrix – Zim Jul 15 at 16:40
• Ah, yes, that's right! I have solved the case where A is circulant. Then you can use that A and A^T commute, which simplifies the problem a lot. Unfortunately this is not the case here... – ECA18 Jul 15 at 17:11
• Another partial result (assuming everywhere else in your matrix are zeros): The Gershgorin disk theorem shows that the magnitude of each eigenvalue is bounded above by $3$. – Zim Jul 15 at 18:27
• @RodrigodeAzevedo Yes! – ECA18 Jul 16 at 9:23
• Unfortunately no. The other "trick" I know is also based on circulant matrices and relies on the fact that $M$ is banded. you can make a surrogate $2n\times 2n$ matrix with $M$ in the leading principal minor. All of the other entries of the surrogate are constructed so that it is circulant. Then you can directly calculate the eigenvalues of the surrogate, and use the fact that $M$ is a leading principal minor to gain insights on the eigenvalues of $M$. – Zim Jul 16 at 17:00

The eigenvalues and eigenvectors can be found exactly. Let the number of block rows in $$M$$ be $$K$$. Let's write the eigenproblem as $$MX = \lambda X$$ where $$X$$ is a block vector $$X = \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_K \end{pmatrix}$$

Each block row eigenvalue equation can now be written as $$Ax_k + A^\top x_{k+1} + x_{k-1} = \lambda x_k, \quad k= 1, \dots, K.$$ Here $$x_k$$ are assumed to be periodical, so $$x_{K+1} \equiv x_1$$ and $$x_0 \equiv x_K$$. Each $$x_k$$ is a vector of length $$n$$. Let's apply discrete Fourier transform, just like it is done for regular circulant matrices. $$x_k = \sum_{m=0}^{K-1} \omega^{m(k-1)} z_m$$ Here $$\omega = \exp \frac{2 \pi i} {K}$$ and each $$z_m$$ is a vector of length $$n$$.

Let's call $$X^{(m)} = \begin{pmatrix} z_m\\ \omega^m z_m\\ \vdots\\ \omega^{m(k-1)} z_m\\ \vdots\\ \omega^{m(K-1)} z_m \end{pmatrix} = f_m \otimes z_m.$$ the $$m$$-th harmonic of the solution $$X$$. Here $$f_m$$ is the $$m$$-th column of the $$DFT$$-like matrix and $$\otimes$$ denotes Kronecker product.

It is obvious that $$X = X^{(0)} + \dots + X^{(K-1)}.$$

I state that all eigenvectors $$X$$ of the original problem can be found as pure harmonics, that is all $$X^{(m)} = 0$$ except for some $$m = m_0$$. Harmonics are linearly independent since they are orthogonal: $$(X^{(m)}, X^{(m')}) = (f_m \otimes z_m, f_{m'} \otimes z_{m'}) = (f_m, f_{m'}) (z_m, z_{m'}) = K \delta_{mm'} (z_m, z_{m'}).$$

Each harmonic $$X^{(m)}$$ gives $$n$$ eigenvalues govern by $$[A + \omega^m A^\top + \omega^{-m}] z_m = \lambda z_m. \tag{*}$$ We may introduce $$B_m = \omega^{-m/2} A + \omega^{m/2} A^\top$$ which for real matrices $$A$$ is hermitian. $$B_m z_m = \mu z_m, \quad \mu \in \mathbb R. \tag{**}$$ Eigenvalues of (*) and (**) are related by $$\lambda = \omega^{-m} + \omega^{m/2} \mu.$$

This is probably best we can do for the second question.

For the $$A$$ being upper shift matrix we may proceed. $$B_m = \begin{pmatrix} 0 & \omega^{-m/2} \\ \omega^{m/2} & 0 & \omega^{-m/2} \\ &\ddots&\ddots&\ddots\\ &&\omega^{m/2} & 0 & \omega^{-m/2} \\ &&&\omega^{m/2} & 0 \end{pmatrix}$$ Let's introduce $$q = \omega^{m/2} = \exp \frac{\pi i m}{K}$$. Then $$\omega^{-m/2} = q^{-1} = \bar q$$. Again, rewriting the eigenproblem $$B_m u = \mu u$$ as a tridiagonal system of equations we get $$u_0 = 0\\ q u_{p-1} + \bar q u_{p+1} = \mu u_p, \qquad p = 1, \dots, n\\ u_{n+1} = 0.$$ Plugging $$u_p = e^{i \alpha p}$$ as a general solution for the middle equations we get $$q e^{-i \alpha} + \bar q e^{i \alpha} = \mu \implies \mu = 2 \cos (\alpha - \arg q) = 2 \cos \left(\alpha - \frac{m \pi}{K}\right)$$ Note that sole $$e^{i \alpha p}$$ cannot satisfy the boundary conditions $$u_0 = u_{n+1} = 0$$. We might combine two $$e^{i \alpha p} - e^{i \alpha' p}$$ with different $$\alpha$$ provided that $$\mu_\alpha = \mu_{\alpha'}$$. Let's take $$\alpha - \frac{m \pi}{K} = -\alpha' + \frac{m \pi}{K} \implies \alpha' = -\alpha + \frac{2 m \pi}{K}.$$ Satisfying $$u_{n+1} = 0$$ gives an equation for $$\alpha$$ $$0 = u_{n+1} = e^{i\alpha (n+1)} - e^{i \alpha' (n+1)} = e^{i \alpha' (n+1)} \left( e^{i (\alpha - \alpha') (n+1)} - 1 \right).$$ $$\left(2\alpha - \frac{2m\pi}{K} \right) (n + 1) = 2\pi d, \qquad d = 1, \dots, n\\ \alpha = \frac{m \pi}{K} + \frac{\pi d}{n + 1}.$$ This gives $$n$$ solutions for each of $$K$$ harmonics ($$m = 0, \dots, K-1; d = 1,\dots,n$$): $$\alpha_{m,d} = \frac{m \pi}{K} + \frac{\pi d}{n + 1}\\ \mu_{m,d} = 2\cos \left(\frac{\pi d}{n + 1}\right)\\ \lambda_{m,d} = \omega^{-m} + \omega^{m/2} \mu_{m,d}\\ (z_{m,d})_p = \exp \left(i \alpha_{m,d} p\right) - \omega^{mp}\exp \left(-i \alpha_{m,d} p\right)$$

Here's a small verification in Python.

I can't hold myself from posting a plot of the eigenvalues for $$K=16, n=24$$. The eigenvalues are contained in a deltoid. 