Proving Trigonometric E-Values for a Symmetric Tridiagonal Matrix

[Nusc]

Homework Statement

A = [ b c ... 0000000000000000000 ]
[ c b c ... .000000000000000 0]
[ ... ]
[ 000000000000000000 c b c ]
[ 000000000000000000 b c ]
where a,b are real. This matrix is tridigonal and symmetric.

I need to show that this matrix has e-values lamda_i = b +2cos((i * pi)/(N+1))
and e-vectors x_i = [sin ((i* pi)/(N+1), sin ((2*i*pi)/(N+1)), ..., sin((N*i*pi)/(N+1))]

Homework Equations

The Attempt at a Solution

I could find the deterministic equation to find the e-values but i don't see how that gives rise to trigonometric functions.

 

[HallsofIvy]

The matrix you've shown is not symmetric. The right bottom corner is
\left[\begin{array}{cc}b &amp; c \\ b &amp; c\end{array}\right][/itex]<br /> which is not symmetric.<br /> Do you mean for the bottom row to end with &quot;c b&quot; rather than &quot;b c&quot;?<br /> <br /> For problems like this it is always a good idea to look at simple cases- If n= 3 this is<br /> \left[\begin{array}{ccc}b &amp;amp; c &amp;amp; 0 \\ c &amp;amp; b &amp;amp; c \\ 0 &amp;amp; b &amp;amp; c\end{array}\right]<br /> where I have altered the matrix as I suggested to make it symmetric.<br /> <br /> The characteristic equation is (b-\lambda)^3- 2c^2(b- \lambda)= (b- \lambda)((b-\lambda^2- 2c^20)= 0 which has the obvious solutions \lambda= b, \lambda= b+ c\sqrt{2}, and \lambda= b- c\sqrt{2}. Of course, here N= 3 so N+1= 4 and \pi/(N+1)= \pi/4. <br /> According to your formula, \lambda_1= b+ 2cos(\pi/4)= b+ \sqrt{2}, /lamba_2= b+ 2cos(2\pi/4)= b and \lambda_3= b+ 2cos(3\pi/4)= b- \sqrt{2}<br /> (Your formula seems to be missing a &quot;c&quot;.)

 

[tiny-tim]

… (N+1)-th roots of -1 …

I could find the deterministic equation to find the e-values but i don't see how that gives rise to trigonometric functions.

Hi Nusc!

(I haven't looked at the matrix aspect of this, but …)

cos(nπ/(N+1)) and sin(nNπ/(N+1)) aren't really trigonometric - they're part of:

e^{i\pi\left(\frac{n}{N+1}<br /> \right)}\,,\,=\,\cos\left(\frac{n\pi}{N+1}<br /> \right)\,+\,i\sin\left(\frac{n\pi}{N+1}<br /> \right)\,,​

which is one of the (N+1)-th roots of -1.

 

[Nusc]

For the tridiagonal matrix we have, b elements are along the diagonal. c elements are on the upper and lower diagonal.

I could not write the matrix using latex

 

[Nusc]

The matrix you've shown is not symmetric. The right bottom corner is
\left[\begin{array}{cc}b &amp; c \\ b &amp; c\end{array}\right][/itex]<br /> which is not symmetric.<br /> Do you mean for the bottom row to end with &quot;c b&quot; rather than &quot;b c&quot;?<br /> <br /> For problems like this it is always a good idea to look at simple cases- If n= 3 this is<br /> \left[\begin{array}{ccc}b &amp;amp; c &amp;amp; 0 \\ c &amp;amp; b &amp;amp; c \\ 0 &amp;amp; b &amp;amp; c\end{array}\right]<br /> where I have altered the matrix as I suggested to make it symmetric.<br /> <br /> The characteristic equation is (b-\lambda)^3- 2c^2(b- \lambda)= (b- \lambda)((b-\lambda^2- 2c^20)= 0 which has the obvious solutions \lambda= b, \lambda= b+ c\sqrt{2}, and \lambda= b- c\sqrt{2}. Of course, here N= 3 so N+1= 4 and \pi/(N+1)= \pi/4. <br /> According to your formula, \lambda_1= b+ 2cos(\pi/4)= b+ \sqrt{2}, /lamba_2= b+ 2cos(2\pi/4)= b and \lambda_3= b+ 2cos(3\pi/4)= b- \sqrt{2}<br /> (Your formula seems to be missing a &quot;c&quot;.)

<br /> <br /> That matrix is incorrect. How would i find the deterministic equation for nxn matrix in this case? Would doing that suffice to prove that the matrix always has e-values \lambda_i = b +2ccos(ipi/(n+1)) ?

 

[tiny-tim]

… wrong answer …

The expected answer is wrongly stated.

It should have a factor 2c.cos, not 2cos.

Then the eigenvalues are b + 2c.cos(nπ/(N+1)), for n = 1 … N;
and an eigenvector for the nth eigenvalue is:

(sin(nπ/(N+1)), sin(2nπ/(N+1)), … , sin(Nnπ/(N+1))).​

Hint: sin((m-1)nπ/(N+1)) + sin((m+1)nπ/(N+1)) = … ? ​

(And note that sin(0nπ/(N+1)) and sin((N+1)nπ/(N+1)) are both 0.)

 

[Nusc]

So the actual characteristic equation for a 3x3 matrix in this case is
<br /> (b-\lambda)^3- 2c^2(b- \lambda) +c^2 = 0<br />
What tricks can i use to solve for lamdba

 

[tiny-tim]

… recurrence relation …

Hi Nusc!

Hint: if the characteristic equation of the n x n matrix is Pn = 0, find a recurrence relation expressing the polynomial Pn in terms of Pn-1 and Pn-2.

Then either solve that recurrence relation by normal methods, or (since the question gives us the solution) define ∆ by: lambda = b + 2c.cos∆.

You should find that Pn = cos(n∆).

And then … ?

 

[Nusc]

I'm not familiar with recurrence relations and so I don't know how that process works.

 

[tiny-tim]

I'm not familiar with recurrence relations and so I don't know how that process works.

ok, I'll rephrase it without recurrence relations …

Look for constants p and q which do not depend on n and for which there is a formula P_n\,=\,pP_{n-1}\,+\,qP_{n-2}\,.

(Do it by starting with the b - lambda in the top left corner, and then starting again with the two c's next to it.)

Then put Pn = cos(n∆) into the formula, and check that that works.

 

[Nusc]

I feel like I should know this elementary concept. lol sadly i do not

 

[tiny-tim]

… finding the determinant …

ok, I'll rephrase it without recurrence relations …

Look for constants p and q which do not depend on n and for which there is a formula P_n\,=\,pP_{n-1}\,+\,qP_{n-2}\,.

(Do it by starting with the b - lambda in the top left corner, and then starting again with the two c's next to it.)

Then put Pn = cos(n∆) into the formula, and check that that works.

Right: the object is to find the determinant (which we're calling Pn) of the tridiagonl n x n matrix with b - µ along the diagonal and c along the off-diagonals.

Do you know how the determinant is defined? Basically, you multiply n terms, chosen so that there's one in each of the n rows and one in each of the n columns, and then add all such possible products (some of them multiplied by minus-one).

So start with the b - µ in the top left corner - what is the sum of all the possible products with that b - µ? Can it be written (b - µ)Pm, for some m?

Then start again, with the two c's next to the top left corner. Can you have one without the other in any product? If not, why not? Then do the same as before … can the result, or part of the result, be written cPm, or (c^2)Pm, for some m?

Has that left anything out?

How have you got on so far … ?

 

[Nusc]

P_n = (b-lambda)P_n-1 - c^2 P_n-2
Are you sure Pn = Cos(n*nabla) ?

(b-lambda)P_n-1 = c^2 P_n-1

which gives

lambda = b - c^2 Pn-2/Pn-1

HOw does that equal b + 2 c.cos(n*pi/(N+1) ?

 

[tiny-tim]

… cos((n+1)∆) + cos((n-1)∆) = 2.cos∆.cos(n∆) …

Hi Nusc!

P_n = (b-lambda)P_n-1 - c^2 P_n-2​

Excellent!

(b-lambda)P_n-1 = c^2 P_n-1

erm … where does that come from?

Are you sure Pn = Cos(n*nabla) ?

(Actually, its a Delta … a nabla is an upside-down ∆ … ∆ is a standard letter in all civilsed fonts, so if you copy-and-paste from this post, it should work. )

Yup. Just define ∆ by lambda = b + 2c.cos∆, which gives you:

P_n = 2c.cos∆P_n-1 - c^2 P_n-2​

(or P_n+1 = 2c.cos∆P_n - c^2 P_n-1, which is probably slightly neater.)

and plug P_n = 2.(c^n).cos(n∆) into it, and divide by 2.c^n.

( oops! … I left out the 2.c^n before … )​

In other words, use standard trig formulas to check that:

cos((n+1)∆) + cos((n-1)∆) = 2.cos∆.cos(n∆). ​

and combine that with the obvious P_1 = b - lambda = 2.c.cos∆ and P_2 = (b - lambda)^2 - c^2 = (c^2)(4(cos∆)^2 - 1) = (c^2)(2(cos∆)^2 - 2(sin∆)^2) = 2.(c^2).cos(2∆) to confirm that we have the right factor and the right starting-point for n.​

And finally … since the characteristic equation is now 2.(c^n).cos(n∆) = 0 … what are the eigenvalues (the lambdas) … ?

(oh … and the value for the angle in my post #6 was wrong … )

 

[Nusc]

Hi Nusc!


Excellent!


erm … where does that come from?
YOu said Pn = 0

 

[Nusc]

Where did this come from
P_n = 2.(c^n).cos(n∆) into it, and divide by 2.c^n.
?

 

[Nusc]

And you forgot a negative sign it shojld be pn = -2ccos(del*n(

 

[tiny-tim]

Hi nusc!

YOu said Pn = 0

ah … I said that the characteristic equation of the matrix is Pn = 0.

Pn is a polynomial in lambda, and we find all the lambdas by finding all n solutions of Pn = 0.

But first we have to find Pn … and it isn't zero when we find it!

So we found it by induction (or recurrence).

Where did this come from
P_n = 2.(c^n).cos(n∆) into it, and divide by 2.c^n.
?

Well, that's the official answer (more or less), so I just plugged it into confirm that it was the right answer (and, incidentally found that I'd got the wrong factor originally!).

We could have solved for P_n using standard recurrence relation methods, of course, but you said you hadn't done that, so I just went straight to the answer.

And you forgot a negative sign it shojld be pn = -2ccos(del*n(

ooh … you're right … well spotted!

Soo … since the eigenvalues (the lambdas) must satisfy cos(n∆) = 0 … what are they … ?

 

[Nusc]

I'm lost:

<br /> P_n\,=\,-2c*ccos(m*pi/(N+1))P_{n-1}\,-\,c^2P_{n-2}\,.<br />

That does not give you:
<br /> P_n = -2c^n \cos(n*del)<br />

 

[tiny-tim]

… sorry … !

I'm lost:
<br /> P_n\,=\,-2c*ccos(m*pi/(N+1))P_{n-1}\,-\,c^2P_{n-2}\,.<br />

That does not give you:
<br /> P_n = -2c^n \cos(n*del)<br />

ah … yes … I made a stupid trig mistake in P_2 ! … ​

I wrote:

P_2 = (b - lambda)^2 - c^2 = (c^2)(4(cos∆)^2 - 1) = (c^2)(2(cos∆)^2 - 2(sin∆)^2) = 2.(c^2).cos(2∆),​

which is rubbish.

4(cos∆)^2 - 1 isn't 2(cos∆)^2 - 2(sin∆)^2, it's 2(cos∆)^2 + cos(2∆).

So P_2 should have been (c^2)(2.(cos∆)^2 + cos(2∆)) = (c^2).sin(3∆)/sin∆.

My original P_1 = 2c.cos∆ was correct, but it can also be written P_1 = c.sin(2∆)/sin∆.

So the middle of my post #14 (it's just too late for me to edit it) should read:

P_n = -2c.cos∆P_n-1 - c^2 P_n-2.

​

So plug P_n = ((-c)^n).sin((n+1)∆)/sin∆ into it, and multiply by sin∆/c^n.

In other words, use standard trig formulas to check that:

sin((n+1)∆) + sin((n-1)∆) = 2.cos∆.sin(n∆),​

and combine that with:

P_1 = b - lambda = -2.c.cos∆ = -sin(2∆)/sin∆,

and P_2 = (b - lambda)^2 - c^2 = (c^2)(4(cos∆)^2 - 1) = (c^2)(2.(cos∆)^2 + cos(2∆)) = (c^2).sin(3∆)/sin∆,​

to confirm that P_n = ((-c)^n).sin((n+1)∆)/sin∆ gives us the right factor, and also the right starting-point for n.

Sorry! ​

So … back to the plot … since … with a little help from you … the correct characteristic equation is now ((-c)^n).sin((n+1)∆)/sin∆ = 0 … what are the eigenvalues (the lambdas) … ?

 

[Nusc]

These should have negative signs:
My original P_1 = 2c.cos∆ was correct, but it can also be written P_1 = c.sin(2∆)/sin∆.

 

[Nusc]

Don't oyu mean
So plug P_n = ((-c)^n).sin((n+1)∆)/sin∆ into it, and multiply by sin∆/(-c)^n.

 

[Nusc]

1) P_n = -2c.cos∆P_n-1 - c^2 P_n-2.
2) P_n = ((-c)^n).sin((n+1)∆)/sin∆

(1) = (2)

-2c.cos∆P_n-1 - c^2 P_n-2 = ((-c)^n).sin((n+1)∆)/sin∆

How did u get sin((n+1)∆) + sin((n-1)∆) = 2.cos∆.sin(n∆)?

sin((n+1)∆ = -2c.cos∆ sin∆ P_n-1/(-c)^n) - c^2 sin∆ P_n-2/(-c)^n)

Why is showing this necessary?

 

[tiny-tim]

Hi Nusc!

"P_n = ((-c)^n).sin((n+1)∆)/sin∆" means that that is true for all values of n.

For example, it also means that P_n+1 = ((-c)^+1).sin((n+2)∆)/sin∆.

How did u get sin((n+1)∆) + sin((n-1)∆) = 2.cos∆.sin(n∆)?

Hint: you can sing this to the tune of The Battle Hymn of the Republic:

Sin A plus B equals sin A cos B plus cos A sin B

Cos A plus B equals cos A cos B minus sin A sin B

Sin A minus B equals sin A cos B minus cos A sin B

CosAminusB equals cos A cos B plus sin A sin B! ​

It's your patriotic duty to learn it!
© tiny-tim ...​

(1) = (2)

No … (2) is only one of the infinitely many solutions to (1).

The solutions to (1) are of the form A.cos((n+1)∆) + B.sin((n+1)∆), for any constants A and B.

To find those constants, we check any two P_ns (obviously, we do the two easiest ones, P_1 and P_2!), and solve for A and B … in this case we get A = (-c)^n/sin∆.

You haven't done recurrence relations in class, so you really shouldn't be worrying about this detail … the only important thing is that you understand how to check that (2) is a solution of (1) … not how to find it in the first place.

Why is showing this necessary?

Because P_n = 0 is the characteristic equation of the eigenvalues of the matrix (you have done that in class, haven't you?), and so we need to know what P_n is so that we can solve the equation and find the eigenvalues.

 

[Nusc]

If (1) does not equate to (2) then

plug P_n = ((-c)^n).sin((n+1)∆)/sin∆ into where ? and multiply by sin∆/c^n.

 

[tiny-tim]

plug P_n = ((-c)^n).sin((n+1)∆)/sin∆ (and similarly for P_n-1 and P_n-2) into P_n = -2c.cos∆P_n-1 - c^2 P_n-2.

 

[Nusc]

DOne. Doing that gives me:
sin((n+1)∆) + sin((n-1)∆) = 2.cos∆.sin(n∆),

And i got this after substituting Pn and Pn-1 and Pn-2. not through standard trig. Is this correct? So once I've shown this what does this mean? how does this verify that these are the e-values? Then I have to show that the e-vectors are as stated in the first post

 

[tiny-tim]

And i got this after substituting Pn and Pn-1 and Pn-2. not through standard trig. Is this correct?

Yes, you got it from substitution. Then you still have to use standard trig to check that that equation is right!

If you put any old P_n in, you'd still get some trig equation … but it would be rubbish! Only a valid P_n will give a valid trig equation!

how does this verify that these are the e-values?

I've been assuming that you've done, in class, solution of eigengvalues λ of a matrix M by "characteristic equation" … that is by the equation M - λ.I = 0.

Have you?

 

[Nusc]

yeah

 

[Nusc]

So recap, I found a general characteristic equation for this nxn symmetric -tridiagonal matrix.

we assumed that lamdba = b+2c.cos(theta) is an e-value but I need to prove this and I don't see how what we did proved this at all.

we stuck lambda back in P_n and it gave us a solution to the general characteristic equation i don't know what this represents.

One could have just avoided this method completely and solved
AX=Lambda*B but since I'm this far I might as well finish it off

Eventually we have

sin((n+1)∆) + sin((n-1)∆) = 2.cos∆.sin(n∆) now I need to verify this with standard trig. How do I do this?
Then I stil have to find the e-vectors.
Was there not a more concise way of doing this problem?