# Matrix eigenvalues

Consider the matrix $$A_n=\begin{bmatrix} a & b & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ c & a & b & 0 & 0 & \dots & 0 & 0 & 0 \\ 0 & c & a & b & 0 & \dots & 0 & 0 & 0 \\ 0 & 0 & c & a & b & \dots & 0 & 0 & 0 \\ 0 & 0 & 0 & c & a & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \dots & a & b & 0 \\ 0 & 0 & 0 & 0 & 0 & \dots & c & a & b \\ 0 & 0 & 0 & 0 & 0 & \dots & 0 & c & a \end{bmatrix}_{n\times n}$$ The matrix with $a=2$ and $b=c=-1$ is encountered in finite difference discretization of $u_{xx}.$
(a) If $D_n = \det(A_n),$ show that $D_n = aD_{n-1}-bcD_{n-2}.$
(b) Solve the recurrence analytically to obtain $D_n$ as a function of $n.$ (and ofcourse $D_n$ will also depend on $a, b, c.$)
(c) Obtain the eigenvalues of $A_n.$ (Hint: Replace $a$ by $a-\lambda$)
 (a)Part can be shown easily by just simple Laplace expansion.
(b)We see that $D_0=1, D_1=a$.
Let $D_n=r^n$ be a solution of the recurrence relation $$D_n=aD_{n-1}-bcD_{n-2}$$ Then characteristic equation corresponding to (1) \begin{alignat*}{3} &\quad & r^n-ar^{n-1}+bcr^{n-2} &=0 \\&\implies &r^2-ar+bc &=0 \\&\implies &r_1=\tfrac{a-\sqrt{a^2-4bc}}{2}, r_2 &=\tfrac{a+\sqrt{a^2-4bc}}{2} \end{alignat*} Case 1: $a^2-4bc=0$
$r_1=r_2=\frac{a}{2}$
General solution of (1) :
$D_n=(C_1+nC_2)(\frac{a}{2})^n$, where $C_1$ and $C_2$ are arbitrary constants.

For $n=0$, we get $C_1=D_0=1$.
For $n=1$, we get $(C_1+C_2)\frac{a}{2}=D_1=a\implies C_2=1$

Hence $D_n=(1+n)(\frac{a}{2})^n$ Case 2: $a^2-4bc\neq0$
General solution of (1) :
$D_n=C_1r_1^n+C_2r_2^n$, with where $C_1$ and $C_2$ are arbitrary constants.
For $n=0$, we get $C_1+C_2=D_0=1$
For $n=1$, we get $C_1r_1+C_2r_2=D_1=a\implies (C_1+C_2)\frac{a}{2}+(C_2-C_1)\frac{\sqrt{a^2-4bc}}{2}=a \implies 2C_2-1=\frac{a}{\sqrt{a^2-4bc}} \implies C_2=\frac{r_2}{\sqrt{a^2-4bc}}$
$\therefore C_1=\frac{-r_1}{\sqrt{a^2-4bc}}$

Hence $D_n=\frac{r_2^{n+1}-r_1^{n+1}}{\sqrt{a^2-4bc}}=\frac{1}{2^{n+1}\sqrt{a^2-4bc}}[(a+\sqrt{a^2-4bc})^{n+1}-(a-\sqrt{a^2-4bc})^{n+1}]$ $$------------------------------------$$ I have done this far, but I'm stuck now.
Is there any simpler expression for $D_n$?
How to obtain eigenvalues, if we consider replacing $a$ by $a-\lambda$?

• For your first question, I'm going to say, "probably not". Sometimes these recurrence relation solutions come out to be this nasty. For your second question, replacing $a$ with $a - \lambda$ is equivalent to subtracting $\lambda I$ from your matrix. Make such a substitution, then solve for $\lambda$. – Theo Bendit Sep 8 '18 at 12:18
• "...replacing a with a−λ is equivalent to subtracting λI from your matrix." That I know. But I meant how to solve? If we replace a by a−λ in second case,it gets too complicated to solve, isn't it? – Radium Sep 8 '18 at 12:36
• It's not so bad. Putting $D_n = 0$ means you can dispose of the fraction out the front. Then rearranging will get you $r_1^{n+1} = r_2^{n+1}$, which you can then simplify by taking the $n+1$th roots of both sides (take care about odd and even cases). This makes solving not too difficult, requiring slightly different techniques for odd and even cases. – Theo Bendit Sep 8 '18 at 12:48
• Can you please explain the process? Since it is (n+1) th degree we would get n+1 solutions? But we can get atmost n values for $\lambda$. Also there is a square root function inside, how to avoid working with it ? since $(a-\lambda)^2$ is inside that square root? – Radium Sep 8 '18 at 13:56

You got questions (a) and (b) already. For (c) the eigenvalues, you need the characteristic equation $\det (A_n - \lambda I) = 0$. This is the same as $D_n = \det (A_n) = 0$, if in there $a$ is replaced by $a-\lambda$. From your result,

$$0 = D_n({\rm a \; replaced}) =\frac{1}{2^{n+1}\sqrt{(a-\lambda)^2-4bc}}[(a-\lambda+\sqrt{(a-\lambda)^2-4bc})^{n+1}-(a-\lambda-\sqrt{(a-\lambda)^2-4bc})^{n+1}]$$

i.e. for $(a-\lambda)^2-4bc \ne 0$ (denominator $\ne 0$) we have

$$(a-\lambda+\sqrt{(a-\lambda)^2-4bc})^{n+1}=(a-\lambda-\sqrt{(a-\lambda)^2-4bc})^{n+1}$$

or (be careful to obtain all the roots in $\sqrt[n+1]{1}$) $$a-\lambda+\sqrt{(a-\lambda)^2-4bc}=(a-\lambda-\sqrt{(a-\lambda)^2-4bc})\exp{(2\pi i k/(n+1))}$$

for $k = 0,1,\cdots,n$. Indexing the $\lambda_k$ with $k$, you get the results. E.g. $\lambda_0 = a \pm 2 \sqrt{bc}$ but that contradicts the above condition $(a-\lambda)^2-4bc \ne 0$.

Since $k=0$ is excluded, the general result is $\lambda_k = a \pm 2 \sqrt{bc} \cos(\frac{\pi k}{n+1})$ for $k = 1,2,\cdots,n$. Since $\cos(x) = -\cos(\pi -x)$, one of the two signs in $\pm$ actually suffices: $\lambda_k = a - 2 \sqrt{bc} \cos(\frac{\pi k}{n+1}) = a + 2 \sqrt{bc} \cos(\pi - \frac{\pi k}{n+1}) \\= a + 2 \sqrt{bc} \cos(\frac{\pi (n+1-k)}{n+1}) =a + 2 \sqrt{bc} \cos(\frac{\pi m}{n+1})$

where $1 \le m = n+1-k \le n$, so the results with the positive sign are reproduced with the same range of the counting variable $m$.

We show the general result by plugging $\lambda_k = a + 2 \sqrt{bc} \cos(\frac{\pi k}{n+1})$ (plugging $\lambda_k = a - 2 \sqrt{bc} \cos(\frac{\pi k}{n+1})$ works as well ) in the determining equation for the eigenvalues. Indeed

$$2 \sqrt{bc} [\cos(\frac{\pi k}{n+1})+\sqrt{\cos^2(\frac{\pi k}{n+1})-1}]=2 \sqrt{bc} [\cos(\frac{\pi k}{n+1})-\sqrt{\cos^2(\frac{\pi k}{n+1})-1}]\exp{(2\pi i k/(n+1))}$$ or $$\cos(\frac{\pi k}{n+1}) + i \sin(\frac{\pi k}{n+1})=[\cos(\frac{\pi k}{n+1}) - i \sin(\frac{\pi k}{n+1})]\exp{(2\pi i k/(n+1))}$$ or $$\exp{(\pi i k/(n+1))}=\exp{(-\pi i k/(n+1))}\exp{(2\pi i k/(n+1))}$$ which is an identity.

By the way, technically, what you have here is a tridiagonal Toeplitz matrix, where references can be found easily.

• Thanks for the detailed explanation. But we get $n+1$ solutions. While $\lambda_k,$ for k=1,2,...,n are eigenvalues of the matrix $A_n$, $\lambda_0$ is not. For example n=1 eigenvalue=a=$\lambda_1$, for n=2 eigenvalues=a$\pm\sqrt{bc}$=$\lambda_1,\lambda_2$ etc – Radium Sep 8 '18 at 15:00
• You are right: $k=0$ must be excluded. I put the expanation why this is so in the main text. Now we have n solutions. – Andreas Sep 8 '18 at 15:16