thomas5267
  • thomas5267
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}\).
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
thomas5267
  • thomas5267
x is not related to n.
ganeshie8
  • ganeshie8
characteristic eqn is \(r^2+xr+\frac{1}{4} = 0\) \(\implies r = \dfrac{-x\pm\sqrt{x^2-1}}{2}\)
ganeshie8
  • 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\]

Looking for something else?

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

More answers

thomas5267
  • 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\).
thomas5267
  • thomas5267
Is it possible to simplify \(A_n\)? Any identity relating to \((a+b)^n-(a-b)^n\)?
thomas5267
  • thomas5267
I mean \((a+b)^n+(a-b)^n\).
ganeshie8
  • 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
ganeshie8
  • ganeshie8
|dw:1441096564281:dw|
thomas5267
  • thomas5267
Any idea how to prove this polynomial has n distinct root?
thomas5267
  • thomas5267
I want to prove that matrix is always diagonalisable.
ganeshie8
  • ganeshie8
oh if you show that eigenvalues are distinct, then that essentially shows that enough eigenvectors are available
ganeshie8
  • ganeshie8
Is \(n\) the size of matrix here ?
thomas5267
  • thomas5267
Yes n is the size of the matrix.
ganeshie8
  • ganeshie8
and you want to prove that the polynomial eqn \(A_n=0\) always has \(n\) distinct roots ?
thomas5267
  • 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}\\ \]
thomas5267
  • thomas5267
Proving \(A_n\) always has n distinct solution would be a good start I think.
ganeshie8
  • ganeshie8
Ahh these are special matrices they are called tridiagonal matrices or something, very interesting ones..
thomas5267
  • 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.
ganeshie8
  • ganeshie8
Wow! cool stuff xD you found that recurrence relation by working 1x1, 2x2, 3x3, and then using induction is it ?
thomas5267
  • thomas5267
I didn't bother with induction. I expanded the matrix corresponded to \(A_4\) and found the empirical relations.
ganeshie8
  • ganeshie8
Ohk, I remember a nice simple way to get that earlier reccurrence relation let me pull that up quick
ganeshie8
  • ganeshie8
here it is https://en.wikipedia.org/wiki/Tridiagonal_matrix#Determinant
ganeshie8
  • ganeshie8
okay lets get back to proving that \(A_n=0\) has \(n\) distinct roots
thomas5267
  • 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\).
ganeshie8
  • ganeshie8
this looks interesting https://en.wikipedia.org/wiki/Tridiagonal_matrix#Eigenvalues
ganeshie8
  • ganeshie8
I thought \(A_n\) is the characteristic polynomial of nxn matrix ?
ganeshie8
  • ganeshie8
by that, i mean solutions of \(A_n=0\) are the eigenvalues that you're interested in
ganeshie8
  • ganeshie8
or did i get that whole thing wrong ?
thomas5267
  • thomas5267
\[ \det(M-xI_n)=-xA_{n-1}-\frac{1}{4}A_{n-2} \]
thomas5267
  • 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.
thomas5267
  • thomas5267
Sorry I didn't made it clear.
thomas5267
  • thomas5267
Actually the characteristic polynomial of \(M_n\) is not what I stated above.
thomas5267
  • thomas5267
The relationship should be \(\det(M_n-xI_n)=-xA_{n-1}-\frac{1}{2}A_{n-2}\)
ganeshie8
  • ganeshie8
Okay I think I'm beginning to understand.. looks more involved than I thought..
thomas5267
  • 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\]
ganeshie8
  • 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
thomas5267
  • 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.
ganeshie8
  • ganeshie8
something is wrong
ganeshie8
  • ganeshie8
nvm
thomas5267
  • 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*} \\ \]
thomas5267
  • thomas5267
\(A_n\) are all polynomials from 1 to 10.
ganeshie8
  • ganeshie8
right, i see..
ganeshie8
  • ganeshie8
thats really a clever derivation for determinant ! il give it a try in the evening again, right now i must go..
thomas5267
  • thomas5267
Thank you! It is not really that hard to find once you tried to find the characteristic polynomial of \(M_n\) by induction.
thomas5267
  • 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*} \]
thomas5267
  • 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.
thomas5267
  • thomas5267
@Kainui Help!

Looking for something else?

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