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.
-
Is there some way to find the eigenvalues of this matrix?
-
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.
Best Answer
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.