# Eigenvalues of an imperfect circulant matrix

For the circulant matrix, for example, $$\begin{bmatrix} a & b & 0 & & 0 \\ 0 & a & b & \cdots & 0 \\ 0 & 0 & a & & 0 \\ & \vdots & &\ddots & \vdots\\ b & 0 & 0 & \cdots & a \end{bmatrix},$$ we can obtain its eigenvalues analytically using the property of circulant matrix. Is it still possible to get the eigenvalues of the following "impefect circulant matrix" analytically? $$\begin{bmatrix} c & d & 0 & & 0 \\ 0 & a & b & \cdots & 0 \\ 0 & 0 & a & & 0 \\ & \vdots & &\ddots & \vdots\\ b & 0 & 0 & \cdots & a \end{bmatrix},$$ Thank you!

• @RodrigodeAzevedo Sorry, I made a mistake in the original problem. I have edited the problem to correct the mistake. Thank you very much. – Jong Howe Aug 16 '18 at 14:36
• Are you only interested in exact solutions, or also in perturbation bounds assuming $c$ and $d$ are not too far from $a$ and $b$ ? – ippiki-ookami Aug 16 '18 at 14:48
• @ippiki-ookami Thank you for the comment. I am interested in exact solutions. – Jong Howe Aug 24 '18 at 11:45

$$\begin{bmatrix} c & d & 0 & \dots & 0 & 0\\ 0 & a & b & \dots & 0 & 0\\ 0 & 0 & a & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & a & b\\ b & 0 & 0 & \dots & 0 & a \end{bmatrix} = \mathrm U + b \, \mathrm e_n \mathrm e_1^\top =: \mathrm M$$

where $\rm U$ is an $n \times n$ upper triangular and bidiagonal matrix. Using the matrix determinant lemma, the characteristic polynomial of matrix $\rm M$ is

\begin{aligned} \det (s \mathrm I_n - \mathrm M) &= \det \big( (s \mathrm I_n - \mathrm U) - b \, \mathrm e_n \mathrm e_1^\top \big) \\ &= \det (s \mathrm I_n - \mathrm U) - b \, \mathrm e_1^\top \mbox{adj} \big( s \mathrm I_n - \mathrm U \big) \,\mathrm e_n\\ &= \det (s \mathrm I_n - \mathrm U) - b \, \mathrm e_n^\top \mbox{adj}^\top \big( s \mathrm I_n - \mathrm U \big) \,\mathrm e_1 \\ &= \det (s \mathrm I_n - \mathrm U) - b \, \mbox{cofactor}_{n,1}\big( s \mathrm I_n - \mathrm U \big) \end{aligned}

Since $\rm U$ is upper triangular,

$$\det (s \mathrm I_n - \mathrm U) = (s-a)^{n-1} (s-c)$$

The $(n,1)$-th cofactor is

$$(-1)^{n+1} (-b)^{n-2} (-d) = (-1)^{2n} b^{n-2} d = b^{n-2} d$$

and, thus,

$$\det (s \mathrm I_n - \mathrm M) = \color{blue}{(s-a)^{n-1} (s-c) - b^{n-1} d}$$

• Thanks very much. I still wonder whether it is possible to get a closed form solution like $s_i = f(a,b,c,d,n,i)$. – Jong Howe Aug 24 '18 at 11:48
• @JongHowe Aren't you operating under the assumption that it's possible to find the roots of any polynomial in terms of arithmetic operations and radicals? It has been known for almost 2 centuries that it is not possible for polynomials of degree $5$ or higher. Take a look at this. However, finding the exact characteristic polynomial is possible, which is what I did. Just forget about finding its exact roots. – Rodrigo de Azevedo Aug 24 '18 at 12:11
• Thanks for the answer. I know that it is impossible to find the root of any general polynomial in terms of arithmetic operations and radicals. But I was not sure whether it was possible for the characterisitc polynomial you gave, which has a somehowe special form, has exact solution. But maybe it is still impossible. Thank you very much. – Jong Howe Aug 27 '18 at 1:27
• @JongHowe I wouldn't use such strong words. For example, if $d=0$, then we have eigenvalues $a$ with multiplicity $n-1$ and $c$ with multiplicity $1$. However, if $d \neq 0$, the eigenvalues are not so obvious. – Rodrigo de Azevedo Aug 27 '18 at 4:41