How to identify repeated eigenvalues?

I have a relatively large matrix (1771 x 1771), representing the laplacian of a graph. Looking at the eigenvalues of this matrix, I suspect that the multiplicity of some of the eigenvalues is greater than 1. However, because they are numerically computed all of the eigenvalues are numerically distinct. To make matters worse, the elements of this matrix are very small (on the order of eps). How can I determine if two (or more) numerically distinct eigenvalues are actually equivalent (i.e. how close do they have to be to be considered identical)?

I have attached a .mat file with the matrix in question. I compute the eigevalues and eigenvectors using

[U,lambda] = eig(full(L));

I am suspicious that the second and third (and maybe more) eigenvalues are actually degenerate, even though they are numerically distinct, but I don't know how to test this. Any suggestions?

Answer 1

[Star Strider]

I would use the uniquetol function if you have R2015a or later. you have to decide the tolerance you want to use to determine the difference between them. I would request all 3 outputs, so you can keep track of the positions of the unique values in the original vector (using the third output).

[Oliver]

@Star Strider: Thanks for the suggestion, I was unaware of this function. However, the fundamental issue is selecting the appropriate tolerance to determine whether two eigenvalues are the same or not, which I don't know a priori (the elements of the matrix I am considering vary by 7 orders of magnitude, so its not obvious how close is close enough). Is there some property of eigenvalues/eigenvectors that could be used to test whether two eigenvalues are equivalent (i.e. degenerate), even if they are numerically distinct?

[Star Strider]

I’m not certain what to suggest with respect to the tolerances. The only help with that I can offer is a way to visualize the eigenvalue magnitudes and the ‘gradient’ of the eigenvalue vector to determine the differences between them. (I used the gradient function because it produces a result the same size as the argument, making it easier to index to the original vector if you need to.) That may help you decide what you want to define as the tolerance.

This is the only way I can think of to approach this problem.

The Code:

in = load('Oliver LaplacianMaybeHasMultiplicities.mat');
Lv = in.Lv;

[U,lambda] = eig(full(Lv));

figure(1)
spy(Lv)
grid
title('Matrix Pattern')

Ls = eigs(Lv, size(Lv,1)-1);

figure(2)
semilogy(Ls)
grid
title('Eigenvalue Magnitudes')

dLs = gradient(Ls);
figure(3)
semilogy(dLs)
grid
title('Gradient (‘Derivative’) of Eigenvalues Vector')

There’s nothing special about my code. I offer it as the way I would approach this. Experiment with it to get the information you need from it.