Is There an Easier Way to Find the Signs of Eigenvalues for Sparse Matrices?

[JJ6]

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
http://g.imageshack.us/img249/10x10lo9.png/1/

Homework Equations

The Attempt at a Solution

I know that I can take the 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?

 

[blerg]

i would try to preform some elementary row/column operations on it.
try for the n=4,5,6

 

[JJ6]

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?

 

[Hurkyl]

I know that I can take the determinant and solve the characteristic equation, but I don't know how I would do that for an nxn matrix.

Surely you know an algorithm for computing the determinant of any matrix...

edit: bleh, the closed form solution is ugly.
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

 

[Defennder]

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.

 

[HallsofIvy]

Unfortunately, just row- reducing a matrix will NOT tell you its eigenvalues. If it did, finding eigenvalues would be a lot easier!

 

[JJ6]

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?

 

[Hurkyl]

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 A - \lambda I 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.

 

[Avodyne]

If you knew that \det(A-\lambda I) was an odd or even polynomial in \lambda, the answer would be immediately obvious.

 

[Hurkyl]

If you knew that \det(A-\lambda I) was an odd or even polynomial in \lambda, 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.

 

[Avodyne]

I was assuming the OP would have read the 3rd edit in your post #4.

 

[Dick]

Oh, I think we all know it has real eigenvalues, don't we?

 

[JJ6]

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?

 

[JJ6]

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.

 

[Avodyne]

Zero is a root only if your original matrix has zero determinant. Does it?

You don't need to solve \lambda^2-{1\over 4}=0 to see that if \lambda is a solution, so is -\lambda.

 

[JJ6]

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?

 

[Dick]

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.

 

[Avodyne]

The method I had in mind was to find a recursion relation for d_n = \det(A-\lambda I). Using cofactors, it's not too hard to express d_n in terms of d_{n-1} and d_{n-2}. Then, using d_1=-\lambda and d_0=1, it's pretty easy to show that d_n is an even (odd) function of \lambda if n is even (odd).

And yes, I'm a he!

 

[Dick]

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.

 

[JJ6]

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.

 

[HallsofIvy]

It seems to me that it is not all that difficult to find the general form for the characteristic equation. If we let P_n(\lambda) be the charactistic [polynomial, then expanding by the top row, P_n()\lambda) is just -\lambda times P_{n-1}(\lambda) minus 1/2 times 1/2 times P_{n-2}(\lambda). That is, P_{n}(\lambda)= -\lambda P_{n-1}(\lambda)+ (1/4)P_{n-2}(\lambda). 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 \lambda 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.

 

[dirk_mec1]

It seems to me that it is not all that difficult to find the general form for the characteristic equation. If we let P_n(\lambda) be the charactistic [polynomial, then expanding by the top row, P_n()\lambda) is just -\lambda times P_{n-1}(\lambda) minus 1/2 times 1/2 times P_{n-2}(\lambda). That is, P_{n}(\lambda)= -\lambda P_{n-1}(\lambda)+ (1/4)P_{n-2}(\lambda). 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 \lambda 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...

 

[Dick]

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.