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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I think it's highly unlikely that an $O(n^2)$ algorithm exists unless that is the complexity of matrix multiplication, unless the matrices have special structure. Why don't you want to use the characteristic polynomials? $\endgroup$– Geoffrey IrvingCommented Dec 25, 2015 at 5:42
-
1$\begingroup$ Is evaluating the characteristic polynomials at a couple values out of bounds? $\endgroup$– Geoffrey IrvingCommented Dec 25, 2015 at 5:46
-
$\begingroup$ @GeoffreyIrving Yes. $\endgroup$– TurboCommented Dec 25, 2015 at 7:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.
answered Dec 25, 2015 at 5:17
-
$\begingroup$ Why cannot I use $x=0$ and how many $i$ do we need? This is likely the only easy way right? $\endgroup$– TurboCommented Dec 25, 2015 at 7:03
-
$\begingroup$ Why doesn't computing power of trace suffice? Why do you do full test also? $\endgroup$– TurboCommented Dec 25, 2015 at 7:11
-
$\begingroup$ Worst case, you'll need $n$ powers (vs $O(1)$ random characteristic polynomial checks). $\endgroup$ Commented Dec 25, 2015 at 7:27
-
$\begingroup$ @Turbo: When heuristics are concerned, it is hard to predict what will be faster for your application. Doing a complete check by traces is way more expensive than using an actual eigenvalue computation (esp. for symmetric matrices) but in practice the traces of one or two powers might be enough to end most comparisons. If more than a handful of powers are needed on average, Geoffrey's method is going to be faster and more precise. If you are dealing with a practical application with lots of matrices, you should experiment with different approaches first. $\endgroup$ Commented Dec 25, 2015 at 23:54
$\begingroup$
$\endgroup$
1
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).
-
$\begingroup$ @geoffreyIrvine $det(\lambda-A)$ is evaluating char poly at $x=\lambda$. $\endgroup$– TurboCommented Dec 25, 2015 at 7:00