Quick tests to differentiate eigenvalues Given two real square symmetric matrices $A$ and $B$ are there any quick tests to make sure at least one of their eigenvalues differ without computing the eigenvalues and likely more robust or looking at the characteristic polynomials presumably with $O(n^2)$ arithmetic operations?
 A: When I had to do this with a couple of billion matrices, I computed the traces of some powers before going for the full test. A good method is to compute $\mathrm{tr} \,((A+xI)^{2^i})$ for $i=1,2,\ldots$ by repeated squaring, where $x$ is some random-ish value. 
A: This violates the terms of the question, but I'll write it down since I think it's the best you can do.  
This can done in time $O(d)$, where $d$ is the cost of evaluating determinants of matrices of either matrix plus a diagonal.  Namely, pick a random $\lambda$ and compute
$$\det(\lambda-A)-\det(\lambda-B)$$
which is the difference of the two characteristic polynomials at $\lambda$.  A nonzero value means at least one eigenvalue differs. 
This has the complexity of matrix multiplication for general sense matrices, but can be faster in special cases: it's quadratic for Toeplitz matrices and often faster for sparse matrices (https://scicomp.stackexchange.com/questions/20573/calculating-the-log-determinant-of-a-large-sparse-matrix). 
