Derive characteristic equation recursion relation

[ognik]

Homework Statement

Given an NxN symetric tri-diagonal matrix, derive the recursion relation for the characteristic polynomial P_n(λ)

Homework Equations

P_n(λ) = |A -λI |
P_n(λ) = (A_n,n - λ)P_n-1(λ) - A²_n,n-1P_n-2(λ)

The Attempt at a Solution

This was easy to do by induction, but I am always looking to strengthen my index notation, so I'd like to also do it using index notation. Please also point out anything wrong with my notation.
Starting with the generalised $$ |A| = \sum_{i=1}^{N} {(-1)}^{i+j}{a}_{ij}{M}_{ij} $$
When i = j, a_ij = A_ii - λ (Given)
For j = i ± 1, a_ij = a_ji (symetric)
For i+1 < j < i-1, a_ij = a_ji = 0 (tri-diagonal)
Since then I've been going round in circles, only achieving:
P₁(λ) = A₁₁ - λ (the recursion needs a starting value)
Expanding by the nth row (i=n, j from n to n-1 only, since for j=n-2, a_ij = 0):
$$ {P}_{n}\left(\lambda\right)=\sum_{i=n}^{i=n-1} {(-1)}^{i+j}{a}_{ij}{M}_{ij}= {\left(-1\right)}^{n+n}{a}_{n,n}{M}_{n,n}+{\left(-1\right)}^{n+n-1}{a}_{n,n-1}{M}_{n,n-1} $$
$$ =\left({A}_{n,n}-\lambda\right){M}_{n,n} - {a}_{n,n-1}{M}_{n,n-1} $$
I can see that I am almost there, the 2nd term looks similar to P_n-1, but I'm just stuck for the next move?

 

[ognik]

I have tried to think of anything else to add, but as far as I know, all the info is already there; I would really appreciate some help to finish this off, thanks.

 

[vela]

The induction hypothesis allows you to say that $M_{n,n} = P_{n-1}(\lambda)$.

Try sketching what $M_{n,n-1}$ looks like. You should be able to see that it's equal to $A_{n,n-1}P_{n-2}(\lambda)$.

 

[ognik]

Thanks Vela. After some thought, I am not so sure that my induction proof is 100%. Please comment on it below?
For clarity I will call the matrix A, the diagonal elements a_n,n and the off-diagonal, elements b_i,j ( = b_j,i). M_n,n = det[A_n,n]

P₁(λ) = det [a_1,1 - λ] = (a_1,1 - λ). (I would need to stop the recursion here, to avoid dealing with P₀ = det[] :-)

From directly writing out the 2x2 matrix, P₂ = det[A₂] = (a_2,2 - λ).M_1,1 = (a_2,2 - λ).det [a_1,1 - λ] = (a_2,2 - λ).P₁(λ)

Again, from directly writing out the 3x3 matrix A₃, P₃(λ) = (a_3,3 - λ).M_2,2 - (b_3,2x b_2,3).M_1,1 + 0 = (a_3,3 - λ).M_2,2 - b²_3,2.P₁(λ)

Here is where I'm not certain my proof is acceptable - I have extrapolated from P₂ and P₃ to write P_n(λ) = (a_n,n - λ).P_n-1((λ) - b²_n,n-1.P_n-2(λ) ... but induction normally requires proving the base case (done), assuming it correct for a general value n=k, and then proving it for k+1. Is my proof valid (for physics at least)?

Back to your "Try sketching what Mn,n−1 looks like. You should be able to see that it's equal to An,n−1Pn−2(λ)." Yes that is clear, though I was wondering if there was a way to do it using the general formula for |A| that I started with up top, and then feeding in b_n,n-1 = b_n-1,n and b_1,j=0 if i and j were separated by more than 1

 

[vela]

You should use n=3 as your base case because it's not clear what $P_{-1}$ and $P_0$ are.

For the n=k+1 case, you need to assume the relation holds for $n \le k$ and not just for $n=k$. You expand along the bottom row to get
$$P_{k+1}(\lambda) = \det(A-\lambda I) = (a_{k+1,k+1}-\lambda)\det(M_{k+1,k+1}) - a_{k+1,k}\det(M_{k+1,k}).$$ So far, all you've used is the definition of $P_n(\lambda)$ and what you know about determinants. Once you argue that $M_{k+1,k+1}$ has the correct form, you can invoke the induction hypothesis to replace $M_{k+1,k+1}$ by $P_k(\lambda)$. You follow similar steps when evaluating $\det(M_{k+1,k})$ and writing it in terms of $P_{k-1}(\lambda)$.

 

[ognik]

Thanks Vela, I see I was neglecting the other terms, careless me :-(. Incidentally I did research det [ ] and found conflicting views, most said it was 1, some said undefined... what's your view on det [ ]?

Please critique the 1st part below ... I have been struggling to get the 2nd term (that weakness working with index notation...), will come back to it once I know my approach is correct. Thanks.

1. For the (always square) matrix A_k+1, M_{k, k} = determinant of matrix remaining after deleting the highest, ie (k+1)'th, row and column. This is clearly |A_k|

2. We are given P_n(λ) = |A_n|. Expanding by the highest row (k+1), with c indicating columns, the definition of a determinant gives us
$$ {P}_{k+1}\left(\lambda\right)=det\left[{A}_{k+1}\right] = \sum_{c=k+1}^{1} {(-1)}^{k+1+c}.{a}_{k+1,c}.{M}_{k+1,c} $$
We know that a_k+1,c = 0 for c ≤ k+1 (tri-diagonal matrix), so the above sum can be written as:
$$ \left({a}_{k+1,k+1} - \lambda\right).{M}_{k+1,k+1} - {a}_{k+1,k}.{M}_{k+1,k} + 0 $$
3. From 1. and 2. above we can write the first term as :
$$ \left({a}_{k+1,k+1} - \lambda\right).{M}_{k,k} = \left({a}_{k+1,k+1} - \lambda\right).det({A}_{k}) = \left({a}_{k+1,k+1} - \lambda\right).{P}_{k}\left(\lambda\right) $$
Showing that $$ {P}_{k+1} (\lambda) = {M}_{k,k} $$

 

[ognik]

Hi again, hoping someone can verify my induction proof above - with the base case at n=3 proved, and the formula assumed correct for k, k-1 and k-2, in the part above I am trying to prove the k+1th case. I think its right, but it feels a little clumsy ...