Eigenvalues of a matrix

  • Thread starter JJ6
  • Start date
  • #1
JJ6
13
0

Homework Statement



Hey guys, for my linear algebra class I need to find the signs of the eigenvalues (I just need to know how many are positive and how many are negative) of an nxn matrix with zeros everywhere except for the two diagonals directly above and directly below the main diagonal, which both have all entries 1/2. Here's a picture with n=10:

http://img249.imageshack.us/img249/9405/10x10lo9.png [Broken]
http://g.imageshack.us/img249/10x10lo9.png/1/ [Broken]

Homework Equations





The Attempt at a Solution



I know that I can take teh determinant and solve the characteristic equation, but I don't know how I would do that for an nxn matrix. Also, it seems like it shouldn't require so much work, since I need to know their signs but not their values. Can anybody point me in the right direction?
 
Last edited by a moderator:

Answers and Replies

  • #2
66
0
i would try to preform some elementary row/column operations on it.
try for the n=4,5,6
 
  • #3
JJ6
13
0
If I apply row/column operations on the matrix, will the eigenvalues be the same for the original matrix as they are for the echelon form?
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
I know that I can take teh determinant and solve the characteristic equation, but I don't know how I would do that for an nxn matrix.
:confused: Surely you know an algorithm for computing the determinant of any matrix....

edit: bleh, the closed form solution is ugly. :frown:
edit: but you can still find the roots of the closed form solution
edit: and there's a much easier trick if you already know the eigenvalues are real
 
Last edited:
  • #5
Defennder
Homework Helper
2,591
5
If I apply row/column operations on the matrix, will the eigenvalues be the same for the original matrix as they are for the echelon form?
Well I don't think so, since it's eigenvalues and not determinant. You can try it out for n=3,4.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,847
964
Unfortunately, just row- reducing a matrix will NOT tell you its eigenvalues. If it did, finding eigenvalues would be a lot easier!
 
  • #7
JJ6
13
0
I've been trying to come up with a "clever" solution for a while, but to no avail. In my book, we have the theorem:

Let A be a matrix, and let its eigenvalues all be real numbers. Then A is diagonalizable if and only if the geometric multiplicity of each eigenvalue equals its algebraic multiplicity.

This is the only theorem I could find in our book that deals with real eigenvalues. Is there a clever way of applying this that I'm missing?
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Unfortunately, just row- reducing a matrix will NOT tell you its eigenvalues. If it did, finding eigenvalues would be a lot easier!
However, row reducing [itex]A - \lambda I[/itex] does help you calculate the determinant, which gives you the characteristic polynomial of A.

But given that the matrix is so sparse, I wonder why not just apply the normal, general purpose algorithm that works to compute the determinant of any matrix.
 
  • #9
Avodyne
Science Advisor
1,396
88
If you knew that [itex]\det(A-\lambda I)[/itex] was an odd or even polynomial in [itex]\lambda[/itex], the answer would be immediately obvious.
 
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
If you knew that [itex]\det(A-\lambda I)[/itex] was an odd or even polynomial in [itex]\lambda[/itex], the answer would be immediately obvious.
Only if you also knew that the polynomial was totally real. Odd and even polynomials can still have complex roots, and so their sign would be undefined.
 
  • #11
Avodyne
Science Advisor
1,396
88
I was assuming the OP would have read the 3rd edit in your post #4. :smile:
 
  • #12
Dick
Science Advisor
Homework Helper
26,263
619
Oh, I think we all know it has real eigenvalues, don't we?
 
  • #13
JJ6
13
0
I have a quick question. If we have n = 2, then the matrix (after subtracting λ*I) has top row [-λ 1/2] and bottom row [1/2 -λ]. Then the characteristic equation is:

λ^2 - 1/4 = 0

But in this case, λ could be either positive or negative, right? If these λ that can be either + or - pop up, how do I tell what the matrix's eigenvalues are?

Edit: Wait, that was a really stupid question. We could factor to (λ - 1/2)(λ + 1/2), so our two eigenvalues would be 1/2 and -1/2, correct?
 
Last edited:
  • #14
JJ6
13
0
OK, I'm guessing from what you guys are saying that I need to use Decartes' rule of signs, but I'm not quite sure how I need to apply it. Assuming that I have a polynomial of degree n with all real roots, I should have number of positive roots + number of negative roots + multiplicity of 0 = n. But I don't know what 0's multiplicity will be, and I don't know how many sign changes there will be to calculate the number of positive roots.
 
  • #15
Avodyne
Science Advisor
1,396
88
Zero is a root only if your original matrix has zero determinant. Does it?

You don't need to solve [itex]\lambda^2-{1\over 4}=0[/itex] to see that if [itex]\lambda[/itex] is a solution, so is [itex]-\lambda[/itex].
 
  • #16
JJ6
13
0
OK, the original matrix will have determinant zero when n is odd. If n is even, det(A) = (-1/2)^n. So if n is even, we'll have n roots that are either odd or even, and if n is odd, we'll have n-1 roots that are either even or odd. Then can I say that if λ is a solution, -λ is a solution also, so we'll have the same number of even and odd roots?
 
  • #17
Dick
Science Advisor
Homework Helper
26,263
619
Avodyne is saying that for even n det(A-lambda*I) has only terms of even power in lambda and for odd, only odd powers. I don't think this follows from what you are saying. I know he's right, but it seems like it should have a lot easier proof than anything I've come up with. And it's not Descartes rule of signs. It's just that if lambda and -lambda both have to be eigenvalues and you know you have n real eigenvalues, it's pretty easy to count the positive ones. I hope Avodyne is a he. Correct me if I'm wrong.
 
Last edited:
  • #18
Avodyne
Science Advisor
1,396
88
The method I had in mind was to find a recursion relation for [itex]d_n = \det(A-\lambda I)[/itex]. Using cofactors, it's not too hard to express [itex]d_n[/itex] in terms of [itex]d_{n-1}[/itex] and [itex]d_{n-2}[/itex]. Then, using [itex]d_1=-\lambda[/itex] and [itex]d_0=1[/itex], it's pretty easy to show that [itex]d_n[/itex] is an even (odd) function of [itex]\lambda[/itex] if [itex]n[/itex] is even (odd).

And yes, I'm a he!
 
  • #19
Dick
Science Advisor
Homework Helper
26,263
619
That sounds promising. I've just started to realize I haven't been paying enough attention to showing that there aren't multiple zero roots which something like that could give you. And actually Descartes rule of signs does come in pretty handy. I forgot to look up exactly what it was before dismissing it. Sorry JJ6.
 
Last edited:
  • #20
JJ6
13
0
Oh, I finally understand this. I got the recursion to work out fine, and I managed to find the signs of the eigenvalues. Thank you very much, everyone.
 
  • #21
HallsofIvy
Science Advisor
Homework Helper
41,847
964
It seems to me that it is not all that difficult to find the general form for the characteristic equation. If we let [itex]P_n(\lambda)[/itex] be the charactistic [polynomial, then expanding by the top row, [itex]P_n()\lambda)[/itex] is just [itex]-\lambda[/itex] times [itex]P_{n-1}(\lambda)[/itex] minus 1/2 times 1/2 times [itex]P_{n-2}(\lambda)[/itex]. That is, [itex]P_{n}(\lambda)= -\lambda P_{n-1}(\lambda)+ (1/4)P_{n-2}(\lambda)[/itex]. Calculating a few of those, I see what Hurkyl meant: "bleh, the closed form solution is ugly." but I think we can conjecture:
If n is even, the signs alternate. If n is odd, we have [itex]\lambda[/itex] times a polymomial with alternating signs.

You ought to be able to prove that, say, by induction. I would be inclined to conjecture: if n is even half the eigenvalues are positive and half negative. If n is odd, 0 is an eigenvalue and half the remaining eigenvalues are positive, half negative. Again, you might be able to prove that by induction on the size of the determinant.
 
  • #22
761
13
It seems to me that it is not all that difficult to find the general form for the characteristic equation. If we let [itex]P_n(\lambda)[/itex] be the charactistic [polynomial, then expanding by the top row, [itex]P_n()\lambda)[/itex] is just [itex]-\lambda[/itex] times [itex]P_{n-1}(\lambda)[/itex] minus 1/2 times 1/2 times [itex]P_{n-2}(\lambda)[/itex]. That is, [itex]P_{n}(\lambda)= -\lambda P_{n-1}(\lambda)+ (1/4)P_{n-2}(\lambda)[/itex]. Calculating a few of those, I see what Hurkyl meant: "bleh, the closed form solution is ugly." but I think we can conjecture:
If n is even, the signs alternate. If n is odd, we have [itex]\lambda[/itex] times a polymomial with alternating signs.

You ought to be able to prove that, say, by induction. I would be inclined to conjecture: if n is even half the eigenvalues are positive and half negative. If n is odd, 0 is an eigenvalue and half the remaining eigenvalues are positive, half negative. Again, you might be able to prove that by induction on the size of the determinant.

Yes but given the fact that this matrix is sparse shouldn't there be an easier way of finding the signs of the eigenvalues? In a lot of algorithms row reducing big (and in general sparse) matrices much has been discovered about the eigenvalues. I wonder if there is a much easier way...
 
  • #23
Dick
Science Advisor
Homework Helper
26,263
619
Yes but given the fact that this matrix is sparse shouldn't there be an easier way of finding the signs of the eigenvalues? In a lot of algorithms row reducing big (and in general sparse) matrices much has been discovered about the eigenvalues. I wonder if there is a much easier way...

Yes there is. It's the method Avodyne suggested. If you take the recursion relation it's pretty easy to see the alternating nature of the coefficients.
 
Last edited:

Related Threads on Eigenvalues of a matrix

Replies
3
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
11
Views
10K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
9
Views
33K
Replies
5
Views
3K
  • Last Post
Replies
4
Views
710
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
4
Views
824
  • Last Post
Replies
0
Views
1K
Top