Derive characteristic equation recursion relation

  • #1
ognik
643
2

Homework Statement


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

Homework Equations


Pn(λ) = |A -λI |
Pn(λ) = (An,n - λ)Pn-1(λ) - A2n,n-1Pn-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, aij = Aii - λ (Given)
For j = i ± 1, aij = aji (symetric)
For i+1 < j < i-1, aij = aji = 0 (tri-diagonal)
Since then I've been going round in circles, only achieving:
P1(λ) = A11 - λ (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, aij = 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 Pn-1, but I'm just stuck for the next move?
 
  • #3
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.
 
  • #4
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)##.
 
  • Like
Likes ognik
  • #5
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 an,n and the off-diagonal, elements bi,j ( = bj,i). Mn,n = det[An,n]

P1(λ) = det [a1,1 - λ] = (a1,1 - λ). (I would need to stop the recursion here, to avoid dealing with P0 = det[] :-)

From directly writing out the 2x2 matrix, P2 = det[A2] = (a2,2 - λ).M1,1 = (a2,2 - λ).det [a1,1 - λ] = (a2,2 - λ).P1(λ)

Again, from directly writing out the 3x3 matrix A3, P3(λ) = (a3,3 - λ).M2,2 - (b3,2x b2,3).M1,1 + 0 = (a3,3 - λ).M2,2 - b23,2.P1(λ)

Here is where I'm not certain my proof is acceptable - I have extrapolated from P2 and P3 to write Pn(λ) = (an,n - λ).Pn-1((λ) - b2n,n-1.Pn-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 bn,n-1 = bn-1,n and b1,j=0 if i and j were separated by more than 1
 
  • #6
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)##.
 
  • Like
Likes ognik
  • #7
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 Ak+1, Mk, k = determinant of matrix remaining after deleting the highest, ie (k+1)'th, row and column. This is clearly |Ak|

2. We are given Pn(λ) = |An|. 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 ak+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} $$
 
  • #8
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 ...
 
Back
Top