# Derive characteristic equation recursion relation

1. May 9, 2015

### ognik

1. The problem statement, all variables and given/known data
Given an NxN symetric tri-diagonal matrix, derive the recursion relation for the characteristic polynomial Pn(λ)

2. Relevant equations
Pn(λ) = |A -λI |
Pn(λ) = (An,n - λ)Pn-1(λ) - A2n,n-1Pn-2(λ)

3. 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?

2. May 15, 2015

### Greg Bernhardt

Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

3. May 15, 2015

### 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.

4. May 16, 2015

### vela

Staff Emeritus
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)$.

5. May 23, 2015

### 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 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. May 24, 2015

### vela

Staff Emeritus
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)$.

7. May 24, 2015

### 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... whats 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. May 26, 2015

### 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 ...