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

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.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

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
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

x is not related to n.
characteristic eqn is \(r^2+xr+\frac{1}{4} = 0\) \(\implies r = \dfrac{-x\pm\sqrt{x^2-1}}{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\]

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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

Not the answer you are looking for?

Search for more explanations.

Ask your own question