A community for students.
Here's the question you clicked on:
 0 viewing
thomas5267
 one year ago
Solve the following linear recurrence relations.
\[
A_n=x A_{n1}\frac{1}{4}A_{n2}
\]
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 offdiagonal except the last entry, which is equal to 1. It also has 1/2 on all entries on the lower offdiagonal 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_{n1}\frac{1}{2}A_{n2}, A_n=x A_{n1}\frac{1}{4}A_{n2}\). \(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_5xI_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_5xI_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^21}}{2}\right)^n + \left(\dfrac{x\sqrt{x^21}}{2}\right)^n\) with the initial condition \(A_1=x,\,A_2=x^2\frac{1}{2}\).
thomas5267
 one year ago
Solve the following linear recurrence relations. \[ A_n=x A_{n1}\frac{1}{4}A_{n2} \] 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 offdiagonal except the last entry, which is equal to 1. It also has 1/2 on all entries on the lower offdiagonal 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_{n1}\frac{1}{2}A_{n2}, A_n=x A_{n1}\frac{1}{4}A_{n2}\). \(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_5xI_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_5xI_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^21}}{2}\right)^n + \left(\dfrac{x\sqrt{x^21}}{2}\right)^n\) with the initial condition \(A_1=x,\,A_2=x^2\frac{1}{2}\).

This Question is Closed

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1x is not related to n.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2characteristic eqn is \(r^2+xr+\frac{1}{4} = 0\) \(\implies r = \dfrac{x\pm\sqrt{x^21}}{2}\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2therefore the general solution of recurrence relation is \[A_n = c_1\left( \dfrac{x+\sqrt{x^21}}{2}\right)^n + c_2\left(\dfrac{x\sqrt{x^21}}{2}\right)^n\]

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Okay. 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
 one year ago
Best ResponseYou've already chosen the best response.1Is it possible to simplify \(A_n\)? Any identity relating to \((a+b)^n(ab)^n\)?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I mean \((a+b)^n+(ab)^n\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2it 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
 one year ago
Best ResponseYou've already chosen the best response.2dw:1441096564281:dw

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Any idea how to prove this polynomial has n distinct root?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I want to prove that matrix is always diagonalisable.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2oh if you show that eigenvalues are distinct, then that essentially shows that enough eigenvectors are available

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Is \(n\) the size of matrix here ?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Yes n is the size of the matrix.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2and you want to prove that the polynomial eqn \(A_n=0\) always has \(n\) distinct roots ?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I 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_7xI_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_nxI_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
 one year ago
Best ResponseYou've already chosen the best response.1Proving \(A_n\) always has n distinct solution would be a good start I think.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Ahh these are special matrices they are called tridiagonal matrices or something, very interesting ones..

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1It 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
 one year ago
Best ResponseYou've already chosen the best response.2Wow! cool stuff xD you found that recurrence relation by working 1x1, 2x2, 3x3, and then using induction is it ?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I didn't bother with induction. I expanded the matrix corresponded to \(A_4\) and found the empirical relations.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Ohk, I remember a nice simple way to get that earlier reccurrence relation let me pull that up quick

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2here it is https://en.wikipedia.org/wiki/Tridiagonal_matrix#Determinant

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2okay lets get back to proving that \(A_n=0\) has \(n\) distinct roots

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I 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_nxI_n)\) is not \(A_n\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2this looks interesting https://en.wikipedia.org/wiki/Tridiagonal_matrix#Eigenvalues

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2I thought \(A_n\) is the characteristic polynomial of nxn matrix ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2by that, i mean solutions of \(A_n=0\) are the eigenvalues that you're interested in

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2or did i get that whole thing wrong ?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1\[ \det(MxI_n)=xA_{n1}\frac{1}{4}A_{n2} \]

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1I 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
 one year ago
Best ResponseYou've already chosen the best response.1Sorry I didn't made it clear.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Actually the characteristic polynomial of \(M_n\) is not what I stated above.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1The relationship should be \(\det(M_nxI_n)=xA_{n1}\frac{1}{2}A_{n2}\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Okay I think I'm beginning to understand.. looks more involved than I thought..

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Just to reiterate. \[ A_n = \left( \dfrac{x+\sqrt{x^21}}{2}\right)^n + \left(\dfrac{x\sqrt{x^21}}{2}\right)^n\]

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2not so sure how you got that relation but it seems you want to show \(xA_{n1}\frac{1}{2}A_{n2}=0\) has \(n\) distinct solutions

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Yes. I want to show \(\det(M_nxI_n)=xA_{n1}\frac{1}{2}A_{n2}=0\) has n distinct solution.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.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_5xI_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_5xI_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
 one year ago
Best ResponseYou've already chosen the best response.1\(A_n\) are all polynomials from 1 to 10.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2thats really a clever derivation for determinant ! il give it a try in the evening again, right now i must go..

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1Thank you! It is not really that hard to find once you tried to find the characteristic polynomial of \(M_n\) by induction.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1\[ \begin{align*} \det(M_nx I_n)&=xA_{n1}\frac{1}{2}A_{n2}\\ &=A_n\frac{1}{4}A_{n2} \end{align*} \]

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.1The 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.
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.