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.
 A: Assuming that the Arnoldi iteration appears to have converged, then given two eigenvalues, it is possible to determine if they are different. However, it is impossible to determine whether they are the same.
Given the entries of the matrix and the initial vector and the number of iterations in your eigensolver, it is possible to determine the maximum amount of error that has accrued from floating point operations as a function of the machine precision. Unfortunately, this floating error analysis might be quite tricky depending on exactly how you're implementing your iterative solver (it would be far easier, for example, to analyze power iteration).
At the end of the day, you'll have an upper bound on the relative error possible, in which case if any two eigenvalues have a ratio that exceeds that value, then they can be concluded to be different. If the two eigenvalues have a ratio below this threshold, then no conclusion can be made, as it is impossible to decide if the eigenvalues are the same, or just closer than the finite precision of the computer can resolve.
