6
$\begingroup$

I have a problem where I have $n$ commuting matrices $M_1,\dots,M_n$. It is a well-known fact that commuting matrices are simultaneously diagonalizable/triangularizable. I need to find the eigenvalues of these matrices, but I need to know the eigenvalues grouped up by the common eigenspaces.

In exact arithmetic, this would be as easy as Schur-factorizing $M_1 = UT_1U^*$, and then computing $T_i = U^*M_iU$. However, in floating-point arithmetic, it is my understanding that U may be computed inaccurately when the eigenspaces are poorly conditioned (i.e. when the eigenvalues are clustered).

Is there a stable numerical method for performing this computation?

$\endgroup$
4
$\begingroup$

For small Hermitian (or real symmetric) matrices, yes, but really this is a hard problem not fully solved. See [1,2] for algorithms. The Cardoso paper [2] looks at the non-commuting case, but in the commuting case should minimize the off diagonal errors with respect to the Frobeneius norm.

I don't know about about getting matrices simultaneously into upper triangular form. I would look at papers that cite these two papers.

[1] Bunse-Gerstner, Angelika, Ralph Byers, and Volker Mehrmann. "Numerical methods for simultaneous diagonalization." SIAM journal on matrix analysis and applications 14.4 (1993): 927-949.

[2] Cardoso, Jean-François, and Antoine Souloumiac. "Jacobi angles for simultaneous diagonalization." SIAM journal on matrix analysis and applications 17.1 (1996): 161-164.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Perhaps this will work. I have not read it. Oseledets, Ivan V., Dmitry V. Savostyanov, and Eugene E. Tyrtyshnikov. "Fast simultaneous orthogonal reduction to triangular matrices." SIAM Journal on Matrix Analysis and Applications 31.2 (2009): 316-330. $\endgroup$ – Terry Loring Jan 11 at 4:50
  • $\begingroup$ Didn't realize that it was such an open problem. Thank you for the references. In the meantime, I'm going to rely on the fact that the matrices at hand are generally quite small, and hope that a heuristic sort based on comparing the eigenvalues of $M_i$ to the diagonal of $U_1 M_i U_1^*$ will suffice. $\endgroup$ – Hayden Ringer Jan 11 at 23:40
  • $\begingroup$ Just to be clear, 1000-by-1000 should be small enough unless you have lots of multiplicity (or lots of near points) in the spectrum. The paper by Bunse-Gerstner explains how this quickly turns into a problem with almost commuting matrices. That's what makes it hard, I think. $\endgroup$ – Terry Loring Jan 12 at 1:13
  • 1
    $\begingroup$ A cheap trick is to do the Schur decomposition for a random linear combination of the matrices, then hope that unitary works rather well for all. Defeated by close point in the spectrum, but might work in your case. $\endgroup$ – Terry Loring Jan 12 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.