A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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}\).

  • This Question is Closed
  1. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    x is not related to n.

  2. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  6. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  7. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1441096564281:dw|

  9. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  10. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I want to prove that matrix is always diagonalisable.

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Is \(n\) the size of matrix here ?

  13. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes n is the size of the matrix.

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  15. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Proving \(A_n\) always has n distinct solution would be a good start I think.

  17. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  18. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  20. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  21. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  22. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    here it is https://en.wikipedia.org/wiki/Tridiagonal_matrix#Determinant

  23. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    okay lets get back to proving that \(A_n=0\) has \(n\) distinct roots

  24. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  26. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I thought \(A_n\) is the characteristic polynomial of nxn matrix ?

  27. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  28. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    or did i get that whole thing wrong ?

  29. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Sorry I didn't made it clear.

  32. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Actually the characteristic polynomial of \(M_n\) is not what I stated above.

  33. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  35. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    something is wrong

  39. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    nvm

  40. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \[ 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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \(A_n\) are all polynomials from 1 to 10.

  42. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    right, i see..

  43. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  44. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \[ \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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @Kainui Help!

  48. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.