4
$\begingroup$

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 \begin{equation} D_n=aD_{n-1}-bcD_{n-2} \end{equation} 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$?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Theo Bendit Sep 8 '18 at 12:18
  • $\begingroup$ "...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? $\endgroup$ – Radium Sep 8 '18 at 12:36
  • $\begingroup$ 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. $\endgroup$ – Theo Bendit Sep 8 '18 at 12:48
  • $\begingroup$ 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? $\endgroup$ – Radium Sep 8 '18 at 13:56
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Radium Sep 8 '18 at 15:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Andreas Sep 8 '18 at 15:16

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.