# How to find "unique" eigenvalues when computed numerically?

I have a large sparse matrix, $L$, which represents the laplacian of a weighted graph: $L = \text{diag}(\sum_{j=1}^{N} w_{ij})-W$, where $W$ is the weighted adjacency matrix with $w_{ij}$ giving the non-negative weight of the edge connecting vertices $i$ and $j$, with $w_{ii} = 0$ (i.e. no self-loops). $L$ is symmetric. I would like to know the "unique" or "distinct" eigenvalues of $L$. I compute its eigenvalues and I get something like:

$$832.8374\\ 831.8227\\ 829.1944\\ 829.0325\\ 827.0706\\ 825.2424\\ 821.0557\\ 819.1499\\ 818.5737\\ 816.9287\\ \dots$$

I suspect that while numerically different, several of these really correspond to the same root of the characteristic polynomial, e.g. $\lambda_i' = 829.1944$ and $\lambda_i'' = 829.0325$ are probably the same root, $\lambda_i$, but due to numerical artifacts they appear different.

When computing eigenvalues numerically, how can I determine which eigenvalues are actually distinct roots of the characteristic polynomial (i.e. I want to know the unique eigenvalues and their geometric multiplicity)?

I am computing these using Matlab's eigs function, which uses the Arnoldi algorithm.

• This problem is basically intractable, unless you can say something completely analytical (using some sort of structure of the matrix).
– Ian
Jan 15 '16 at 22:43
• @Ian: See the edits, L is a graph laplacian and is symmetric and real valued. Does that help?
– okj
Jan 17 '16 at 2:27
• @okj Not really. Arbitrarily small perturbations of a matrix with a double eigenvalue will have single eigenvalues, which makes this kind of problem extremely numerically unsntable. The fact that your matrix has integer entries might help, though.
– Ian
Jan 17 '16 at 3:02