Matrices Without Eigenvalues?


DavidB
10-04-2010, 09:11 PM
Hello.

I have recently been testing an updated program for computing the eigenvalues and eigenvectors of real, square matrices. I am trying to test it with matrices for which not all eigenvalues can be found. I had assumed that any matrix with two identical columns and/or two identical rows would cause the program to fail. For example, given a 6 x 6 matrix with two identical rows, I had expected the program to compute five eigenvalues and five eigenvectors and output a message to the effect that not all eigenvalues/eigenvectors could be computed for this matrix.

However, the program did compute 6 eigenvalues and 6 eigenvectors without outputting any errors. So, either my assumption was incorrect, or the program is incorrect.

Am I incorrect in assuming that an N x N matrix with two or more identical rows will have N–1 (or fewer) eigenvalues and eigenvectors?

If so, what would cause the matrix to have N–1 (or fewer) eigenvalues and eigenvectors? Could you please supply one or more example matrices; I would like to thoroughly test out the program with data that will cause it to fail--I want to ensure that the program fails gracefully.

.

ichbin
10-05-2010, 12:40 AM
All N X N square matrices have N eigenvalues; that's just the same as saying that an Nth order polynomial has N roots.

While a defective matrix still has N eigenvalues, it does not have N independent eigenvectors. This usually shows up (and I believe NR has a sentence to this effect) as the eigen-routine completing, but some of the equal or very close eigenvalues having linearly dependent or nearly linearly dependent eigenvectors.

A matrix having too few eigenvectors has nothing to do with it having too few independent rows or columns. The latter just makes its determinant zero, which means that at least one eigenvalue is zero.

Here is a simple example of a defective matrix (which, you will note, has entirely linearly independent rows and columns):

( 2 1 0 )
( 0 2 1 )
( 0 0 2 )

As I mentioned above, given a defective matrix, an eigen-routine will usually still complete (by returning linearly dependent eigenvectors). But there are matrices (often perfectly non-defective one) that do tend to cause eigen-routine convergence problems. One famous example is where the diagonal is "off-by-one":

( 0 1 0 0 0 )
( 0 0 1 0 0 )
( 0 0 0 1 0 )
( 0 0 0 0 1 )
( 1 0 0 0 0 )

The eigenvalues of the N X N form of this matrix are the Nth complex roots of unity. All have corresponding independent eigenvectors, so the matrix is not even close to defective. But many eigen-routines will never converge to this result.

DavidB
10-06-2010, 04:36 PM
Thank-you.

I even tried entering a matrix that was all 1's, hoping that would cause the program to fail--but it didn't. It just returned a bunch of 0 eigenvalues and identical eigenvectors. (Still haven't found a matrix that breaks the program.)

I guess I had confused the eigen properties of a matrix with its ability to be LU-Decomposed.