# Eigenvalues of a quasi-circulant matrix

The following matrix cropped up in a model I am building of a dynamical system:

$$A= \begin{bmatrix} 1 - \alpha & \alpha/2 & 0 & 0 &\cdots & 0 & 0 & \alpha/2\\ \alpha/2 & 1-\alpha & \alpha/2 & 0 &\cdots & 0 & 0 & 0\\ 0 & \alpha/2 & 1-\alpha & \alpha/2 &\cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 &\cdots & \alpha/2 & 1-\alpha & \alpha/2\\ \alpha/2 & 0 & 0 & 0 &\cdots & 0 & \alpha/2 & 1-\alpha\\ \end{bmatrix}$$

It is a stochastic matrix and a circulant matrix, and has equal values in the diagonal.

I am interested in the eigenvalues of this matrix, and it was easy to derive them from the properties listed here. It turns out that for size $n$,

$$\lambda_k = 1 - \alpha \left(1 - \cos\frac{\pi k (n-2)}{n}\right), \qquad k\in\{0,1,\dots,n-1\},$$

and in the limiting case,

$$\lim_{n\rightarrow\infty} \lambda_k = 1 - \alpha(1 + (-1)^k) = \begin{cases}1-2\alpha & k \textrm{ even}\\ 1 & k \textrm{ odd}\end{cases}$$

This is interesting for my study, because an eigenvalue of $1$ that is independent of $\alpha$ implies a marginally stable system that cannot be fully stabilized.

Now, I am interested in a slightly modified system, represented by the matrix below. This matrix is exactly like the one above save for the first and last rows, and is still a stochastic matrix with equal values in the diagonal.

I am wondering whether it is possible to derive the eigenvalues of this matrix, even if only for the limiting case.

$$A^\prime= \begin{bmatrix} 1 - \alpha & \color{red} \alpha & 0 & 0 &\cdots & 0 & 0 & \color{red} 0\\ \alpha/2 & 1-\alpha & \alpha/2 & 0 &\cdots & 0 & 0 & 0\\ 0 & \alpha/2 & 1-\alpha & \alpha/2 &\cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 &\cdots & \alpha/2 & 1-\alpha & \alpha/2\\ \color{red} 0 & 0 & 0 & 0 &\cdots & 0 & \color{red} \alpha & 1-\alpha\\ \end{bmatrix}$$

• That matrix is also tri-diagonal. It's not too difficult to write a recurrence relation for its characteristic determinant, solve it, set the result to zero, and solve for the eigenvalues. Look for proofs of the eigenvalues of tri-diagnoal Toeplitz matrices, which look similar, to see how it's done. Commented Aug 6, 2015 at 6:59
• I found this, as well, which may be the solution you're looking for. Commented Aug 6, 2015 at 7:01
• Still eigenvalue $1$ makes it marginally stable.
– A.Γ.
Commented Aug 6, 2015 at 8:47
• Expanding the determinant of $\lambda I-A$ along the first and then the last rows it is easy to express the characteristic polynomial of the matrix in terms of the central minors of size $n-2$ and $n-4$ that have no irregularity, i.e. the standard circulant matrices with known characteristic polynomials. I have no time now, but I believe you can fix it :)
– A.Γ.
Commented Aug 6, 2015 at 9:15

Consider this matrix: $$M:=\left[\begin{array}{r} 2&-2\\ -1&2&-1\\ &-1&2&-1\\ &&\ddots&\ddots&\ddots\\ &&&-1&2&-1\\ &&&&-1&2&-1\\ &&&&&-2&2 \end{array}\right].$$ Then your matrix $A'$ is given by $$A' = I -\frac{\alpha}{2} M.$$ Let $D:=\text{diag}(1/\sqrt{2}, 1, 1, \ldots, 1, 1, 1/\sqrt{2})$. Upon reading Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations (Britanak, Yip and Rao; $2006$), I found out (by trial and error, mostly) that the columns of this asymmetric matrix: $$P:=\left[\cos\left(\frac{jk\pi}{n-1}\right)\right]^{n-1}_{j,k=0} \cdot D$$ are eigenvectors of $M$, corresponding to (increasing) eigenvalues $$\left[4\sin^2\left(\frac{k}{n-0.5}\cdot\frac{\pi}{2}\right)\right]^{n-1}_{j=0}.$$ Let $\Lambda$ be the diagonal matrix of the eigenvalues of $M$. Then since $A'$ is so nicely defined, $$A'=I-\tfrac{\alpha}{2}M=PP^{-1}-\tfrac{\alpha}{2}P\Lambda P^{-1}=P(I-\tfrac{\alpha}{2}\Lambda)P^{-1},$$ so $A'$ has eigenvalues $$\left[1-2\alpha\sin^2\left(\frac{k}{n-0.5}\cdot\frac{\pi}{2}\right)\right]^{n-1}_{j=0}$$ (albeit decreasingly ordered, assuming $\alpha>0$; you may want to flip the $\cos(\ldots)$ columns left-to-right inside of $P$.)

Also, note that $D^2 M = L_{\text{path}}$, the Laplacian matrix of an undirected path graph with $n$ vertices, but you cannot use the eigendecomposition of $L_{\text{path}}(=Q_{\text{path}} \Lambda_{\text{path}} Q {}^{\text{T}}_{\text{path}}$ since $M \mapsto D^2 M$ is not a similarity transformation.

Oddly enough, spectral graph theory has the analytic solution for this problem.

Let $L$ be the graph Laplacian for the path graph. Then $L$ is tri-diagonal with $[1,2,2,...,2,1]$ on the diagonal and $-1$'s on the super and sub diagonals. Then the matrix $A'$ is given by $$A'=I-\frac{\alpha}2 L.$$ Now since every vector in $\mathbb{C}^N$ is an eigenfunction of $I$, every eigenfunction $\chi_j$ of $L$ with eigenvalue $\lambda_j$ will be an eigenfunction of $A'$ with eigenvalue $1-\frac{\alpha}{2}\lambda_j$. Thus, to solve the problem stated hereinbefore, one needs only to solve eigenvalue problem of the path graph. The derivation of which can be found here.

To summarize the results, the eigenvalues of $L$ are $\lambda_j = 2-2\cos(\frac{\pi j}{N})$ and may be obtained by mapping the cycle graph with $2N$ vertices to the path graph with $N$ vertices.

Interestingly, the cycle graph with $N$ vertices also yields a method for finding the eigenvalues and eigenvectors of $A$ as $$A=I-\frac{\alpha}2 L_c,$$ where $L_c$ is the graph Laplacian for the cycle graph with $N$ vertices. If you let $v_j=\frac{1}{\sqrt{N}}[\omega^{0j}, \omega^{1j}, ..., \omega^{(N-1)j}]^T$ for $\omega=e^{2\pi i/N}$ (i.e. $v_j$ is a column of the DFT matrix) then $$L_cv_j = (2\omega^{0}-\omega^{j}-\omega^{-j})v_j = (2-2\cos(2\pi j/N))v_j.$$ Hence, $Av_j = (1-\alpha(1-\cos(2\pi j/N)))v_j$ (so I think the indexing in the question might be a bit off) and the DFT matrix forms an orthonormal eigenbasis that diagonalizes $A$. To get a real orthonormal eigenbasis for $A$ (which is guaranteed to exist because $A$ is real and symmetric), taking combinations $w_j=1/2(v_j+v_{N-j})$ and $w_{N-j} = i/2 (v_j-v_{N-j})$ will do the trick.

• The matrix $L$ for which $A'=I-\frac{\alpha}{2}L$ is not the Laplacian for a graph path; look at the first and last rows of $A'$. Commented Mar 7, 2018 at 12:47
• On a side note, I prefer the change of basis matrix for real circulant symmetric matrices to be of cosines and sines rather than the DFT. Commented Mar 7, 2018 at 12:52
• Yeah, apparently I misread the original matrix. Oh well, it's just a bit of me rambling about the cycle graph Laplacian. I always like the DFT version as I'm an harmonic analyst at heart, but I'm not a fanatic about it. Commented Mar 15, 2018 at 13:57