3
$\begingroup$

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!

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

$$\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}$$

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Jong Howe Aug 24 '18 at 11:48
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo Aug 24 '18 at 12:11
  • $\begingroup$ 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. $\endgroup$ – Jong Howe Aug 27 '18 at 1:27
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo Aug 27 '18 at 4:41

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.