## thomas5267 one year ago Solve the following linear recurrence relations. $A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}$ This is a recurrence relations of the characteristic polynomial of a particular kind of matrix. EDIT: I need to prove that $$M_n$$ are always diagonalisable. I am only interested in $$n\geq3\text{ and odd}$$. $$M_n$$ is a tridiagonal nxn matrix. $$M_n$$ has 1/2 on all entries on the upper off-diagonal except the last entry, which is equal to 1. It also has 1/2 on all entries on the lower off-diagonal except the first entry, which is also equal to 1. All other entries are zero. For example: $M_5=\begin{pmatrix} 0&\frac{1}{2}&0&0&0\\ 1&0&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&0&1\\ 0&0&0&\frac{1}{2}&0 \end{pmatrix}\\ M_7=\begin{pmatrix} 0&\frac{1}{2}&0&0&0&0&0\\ 1&0&\frac{1}{2}&0&0&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\\ 0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\\ 0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&0&0&\frac{1}{2}&0&1\\ 0&0&0&0&0&\frac{1}{2}&0 \end{pmatrix}\\$ The characteristic equation of $$M_n$$ is $$-xA_{n-1}-\frac{1}{2}A_{n-2}, A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}$$. $$A_n$$ is the characteristic polynomial of the submatrix of $$M_n$$. The submatrix is generated by dropping the first row and first column of $$M_n$$. For example: M_5=\begin{pmatrix} 0&\frac{1}{2}&0&0&0\\ 1&0&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&0&1\\ 0&0&0&\frac{1}{2}&0 \end{pmatrix}\\ M_5-xI_5=\begin{pmatrix} -x&\frac{1}{2}&0&0&0\\ 1&-x&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&-x&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&-x&1\\ 0&0&0&\frac{1}{2}&-x \end{pmatrix}\\ \begin{align*} \det(M_5-xI_5)&= -x\begin{vmatrix} -x&\frac{1}{2}&0&0\\ \frac{1}{2}&-x&\frac{1}{2}&0\\ 0&\frac{1}{2}&-x&1\\ 0&0&\frac{1}{2}&-x \end{vmatrix}-\frac{1}{2} \begin{vmatrix} 1&\frac{1}{2}&0&0\\ 0&-x&\frac{1}{2}&0\\ 0&\frac{1}{2}&-x&1\\ 0&0&\frac{1}{2}&-x \end{vmatrix}\\ &=-xA_4-\frac{1}{2}\begin{vmatrix} -x&\frac{1}{2}&0\\ \frac{1}{2}&-x&1\\ 0&\frac{1}{2}&-x\\ \end{vmatrix}\\ &=-xA_4-\frac{1}{2}A_3 \end{align*} $$A_n$$ has a close form solution of $$A_n = \left( \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n + \left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$$ with the initial condition $$A_1=-x,\,A_2=x^2-\frac{1}{2}$$.

1. thomas5267

x is not related to n.

2. ganeshie8

characteristic eqn is $$r^2+xr+\frac{1}{4} = 0$$ $$\implies r = \dfrac{-x\pm\sqrt{x^2-1}}{2}$$

3. ganeshie8

therefore the general solution of recurrence relation is $A_n = c_1\left( \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n + c_2\left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$

4. thomas5267

Okay. The initial condition is $$A_1=-x,\,A_2=x^2-\frac{1}{2}$$. I plugged $$n=1$$ and $$x=1$$ and $$x=\sqrt{2}$$ to get $$c_1=c_2=1$$.

5. thomas5267

Is it possible to simplify $$A_n$$? Any identity relating to $$(a+b)^n-(a-b)^n$$?

6. thomas5267

I mean $$(a+b)^n+(a-b)^n$$.

7. ganeshie8

it looks good the way it is now i don't see any easy way to simplify it further recall the formula for fibonacci sequence

8. ganeshie8

|dw:1441096564281:dw|

9. thomas5267

Any idea how to prove this polynomial has n distinct root?

10. thomas5267

I want to prove that matrix is always diagonalisable.

11. ganeshie8

oh if you show that eigenvalues are distinct, then that essentially shows that enough eigenvectors are available

12. ganeshie8

Is $$n$$ the size of matrix here ?

13. thomas5267

Yes n is the size of the matrix.

14. ganeshie8

and you want to prove that the polynomial eqn $$A_n=0$$ always has $$n$$ distinct roots ?

15. thomas5267

I want to prove these matrices are always diagonalisable. $M_5=\begin{pmatrix} 0&\frac{1}{2}&0&0&0\\ 1&0&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&0&1\\ 0&0&0&\frac{1}{2}&0 \end{pmatrix}\\ M_7=\begin{pmatrix} 0&\frac{1}{2}&0&0&0&0&0\\ 1&0&\frac{1}{2}&0&0&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\\ 0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\\ 0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&0&0&\frac{1}{2}&0&1\\ 0&0&0&0&0&\frac{1}{2}&0 \end{pmatrix}\\ M_7-xI_7=\begin{pmatrix} -x&\frac{1}{2}&0&0&0&0&0\\ 1&-x&\frac{1}{2}&0&0&0&0\\ 0&\frac{1}{2}&-x&\frac{1}{2}&0&0&0\\ 0&0&\frac{1}{2}&-x&\frac{1}{2}&0&0\\ 0&0&0&\frac{1}{2}&-x&\frac{1}{2}&0\\ 0&0&0&0&\frac{1}{2}&-x&1\\ 0&0&0&0&0&\frac{1}{2}&-x \end{pmatrix}\\$ $$A_n$$ is the first entry of the cofactor expansion of $$M_n-xI_n$$. $A_6=\begin{vmatrix} -x&\frac{1}{2}&0&0&0&0\\ \frac{1}{2}&-x&\frac{1}{2}&0&0&0\\ 0&\frac{1}{2}&-x&\frac{1}{2}&0&0\\ 0&0&\frac{1}{2}&-x&\frac{1}{2}&0\\ 0&0&0&\frac{1}{2}&-x&1\\ 0&0&0&0&\frac{1}{2}&-x \end{vmatrix}\\$

16. thomas5267

Proving $$A_n$$ always has n distinct solution would be a good start I think.

17. ganeshie8

Ahh these are special matrices they are called tridiagonal matrices or something, very interesting ones..

18. thomas5267

It is a transition matrix of a Markov chain. I used this matrix to model the gunplay of a first person shooter called Planetside 2 XD.

19. ganeshie8

Wow! cool stuff xD you found that recurrence relation by working 1x1, 2x2, 3x3, and then using induction is it ?

20. thomas5267

I didn't bother with induction. I expanded the matrix corresponded to $$A_4$$ and found the empirical relations.

21. ganeshie8

Ohk, I remember a nice simple way to get that earlier reccurrence relation let me pull that up quick

22. ganeshie8
23. ganeshie8

okay lets get back to proving that $$A_n=0$$ has $$n$$ distinct roots

24. thomas5267

I am only interested in the diagonalisability of $$M_n,\,n\geq3 \text{ and is odd}$$. Actually proving $$A_n$$ has n distinct roots is not that useful since $$\det(M_n-xI_n)$$ is not $$A_n$$.

25. ganeshie8

this looks interesting https://en.wikipedia.org/wiki/Tridiagonal_matrix#Eigenvalues

26. ganeshie8

I thought $$A_n$$ is the characteristic polynomial of nxn matrix ?

27. ganeshie8

by that, i mean solutions of $$A_n=0$$ are the eigenvalues that you're interested in

28. ganeshie8

or did i get that whole thing wrong ?

29. thomas5267

$\det(M-xI_n)=-xA_{n-1}-\frac{1}{4}A_{n-2}$

30. thomas5267

I am only interested in the diagonalisability of $$M_n, n\geq3\text{ and is odd}$$. $$A_n$$ is the characteristic polynomial of the submatrix of $$M_{n+1}$$ with the first row and first column removed.

31. thomas5267

Sorry I didn't made it clear.

32. thomas5267

Actually the characteristic polynomial of $$M_n$$ is not what I stated above.

33. thomas5267

The relationship should be $$\det(M_n-xI_n)=-xA_{n-1}-\frac{1}{2}A_{n-2}$$

34. ganeshie8

Okay I think I'm beginning to understand.. looks more involved than I thought..

35. thomas5267

Just to reiterate. $A_n = \left( \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n + \left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$

36. ganeshie8

not so sure how you got that relation but it seems you want to show $$-xA_{n-1}-\frac{1}{2}A_{n-2}=0$$ has $$n$$ distinct solutions

37. thomas5267

Yes. I want to show $$\det(M_n-xI_n)=-xA_{n-1}-\frac{1}{2}A_{n-2}=0$$ has n distinct solution.

38. ganeshie8

something is wrong

39. ganeshie8

nvm

40. thomas5267

M_5=\begin{pmatrix} 0&\frac{1}{2}&0&0&0\\ 1&0&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&0&1\\ 0&0&0&\frac{1}{2}&0 \end{pmatrix}\\ M_5-xI_5=\begin{pmatrix} -x&\frac{1}{2}&0&0&0\\ 1&-x&\frac{1}{2}&0&0\\ 0&\frac{1}{2}&-x&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&-x&1\\ 0&0&0&\frac{1}{2}&-x \end{pmatrix}\\ \begin{align*} \det(M_5-xI_5)&= -x\begin{vmatrix} -x&\frac{1}{2}&0&0\\ \frac{1}{2}&-x&\frac{1}{2}&0\\ 0&\frac{1}{2}&-x&1\\ 0&0&\frac{1}{2}&-x \end{vmatrix}-\frac{1}{2} \begin{vmatrix} 1&\frac{1}{2}&0&0\\ 0&-x&\frac{1}{2}&0\\ 0&\frac{1}{2}&-x&1\\ 0&0&\frac{1}{2}&-x \end{vmatrix}\\ &=-xA_4-\frac{1}{2}\begin{vmatrix} -x&\frac{1}{2}&0\\ \frac{1}{2}&-x&1\\ 0&\frac{1}{2}&-x\\ \end{vmatrix}\\ &=-xA_4-\frac{1}{2}A_3 \end{align*} \\

41. thomas5267

$$A_n$$ are all polynomials from 1 to 10.

42. ganeshie8

right, i see..

43. ganeshie8

thats really a clever derivation for determinant ! il give it a try in the evening again, right now i must go..

44. thomas5267

Thank you! It is not really that hard to find once you tried to find the characteristic polynomial of $$M_n$$ by induction.

45. thomas5267

\begin{align*} \det(M_n-x I_n)&=-xA_{n-1}-\frac{1}{2}A_{n-2}\\ &=A_n-\frac{1}{4}A_{n-2} \end{align*}

46. thomas5267

The eigenvalues of $$M_{n},\,n\geq3 \text{ and odd}$$ are symmetric (x and -x are both eigenvalues.) and distinct. 0 is always one of the eigenvalues. The characteristic polynomial is also odd.

47. thomas5267

@Kainui Help!