Are eigenvalues sorted, largest to smallest?

[GoogleCodeExporter]

Are the eigenvectors supposed to be sorted by eigenvalue, largest to smallest?  
When I try the eigen decomposition, it seems like the results are almost, but 
not quite, sorted.

Here is my test code:

public class EigTest {
    public static void main(String[] argv) {
        Random gen = new Random();

        int dim = 10;
        double[][] covArray = new double[dim][dim];
        for (int i1=0; i1<dim; i1++) {
            for (int i2=0; i2<=i1; i2++) {
                if (i1 == i2) {
                    covArray[i1][i2] = 1.0;
                }
                else{
                    covArray[i1][i2] = covArray[i2][i1] = 0.2 + 0.1*gen.nextDouble();
                }
            }
        }
        SimpleMatrix covMatrix = new SimpleMatrix(covArray);
        EVD evd = covMatrix.eig();
        for (int i=0; i<dim; i++) {
            System.out.println(i + " " + evd.getEigenvalue(i).getReal());
        }
    }
}

And here is the output:

0 3.199776985529203
1 0.6475744701287464
2 0.6179173072801434
3 0.6844364727875633
4 0.7209547852654137
5 0.7710224772493918
6 0.8081055762745701
7 0.8227425106373765
8 0.8738689128927779
9 0.8536005019548158

Original issue reported on code.google.com by senor.ca...@gmail.com on 24 Feb 2011 at 7:10

[GoogleCodeExporter]

The eigenvalues are not sorted, but because of how the QR algorithm works they 
tend to be returned semi-sorted.  Just did a quick search to see if returning 
sorted results was standard and I don't believe it is.  At least LAPACK does 
not sort by default but I think some functions provide the options to return 
sorted results.  MATLAB uses the order that LAPACK uses, according to a message 
board.

Do you think that having sorted results would be useful or was this more of a 
general comment?

Original comment by peter.ab...@gmail.com on 24 Feb 2011 at 12:34

• Changed state: Accepted
• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

The fact that they are almost sorted made me think that perhaps they were 
supposed to be sorted but something was not working right. It might be useful 
just to add a comment to the JavaDoc making it clear that the user will need to 
do any necessary sorting. (E.g., if someone is doing a PCA analysis they will 
generally just want the eigenvectors corresponding the largest N eigenvalues, 
so they will need to sort the results.)

Original comment by senor.ca...@gmail.com on 25 Feb 2011 at 12:18

[GoogleCodeExporter]

I'll add a comment making it clear that they are unsorted by default and add a 
sorting function to the wish list.

BTW If you are doing PCA you might want to considering using SVD rather than 
EVD because EVD forces you to explicitly compute the covariance matrix and that 
introduces numerical errors.

Original comment by peter.ab...@gmail.com on 25 Feb 2011 at 7:22

[GoogleCodeExporter]

Thanks!

Original comment by senor.ca...@gmail.com on 25 Feb 2011 at 9:01

[GoogleCodeExporter]

Original comment by peter.ab...@gmail.com on 26 Feb 2011 at 11:16

• Changed state: Done