# Simultaneously orthogonally transform two SPD matrices to tridiagonal form?

Supposing you have two SPD matrices $A,B\in\mathbb{R}^{n\times n}$ are there any known results on the existence or non-existence of a unitary matrix $Q$ such that $Q^\top A Q=T_A$ and $Q^\top B Q=T_B$ are both tridiagonal. If such a transformation exists in general, it is not required for my purposes that it be computable in finitely many steps.

I am aware of non-orthogonal congruence transformations which tridiagonalize two matrices.

Thanks!

Edit:

Thanks for the response. I am familiar with the papers of Tisseur and Garvey et. al, but they are using non-orthogonal transformations. In one paper they use alternating 1D Householder reflectors and matrices of the form $L=I+xy^\top$ to force portions of the leading columns to be in the same space.

I tried finding a counter-example from the 3x3 case, but it looks like I have plenty of degrees of freedom to play with and higher dimensions become treacherously difficult to manage individual elements.

Maybe this question is equivalent to finding a $Q$ such that for an arbitrary matrix $V$ that $Q^\top V$ is bidiagonal, which certainly looks hopeless to me.

-
Oh wow... as I recall this is one of the "Holy Grails" of numerical linear algebra; this is related to the search for much better algorithms for the "symmetric definite generalized eigenproblem", where the usual approach is to diagonalize one at the expense of making the other full (after which the usual methods for symmetric eigenproblems like QR are applied). This: maths.manchester.ac.uk/~ftisseur/reports/trd1.pdf is one result, but as Greg says, this isn't what he wants. – J. M. Aug 24 '10 at 12:02
For the benefit of search engines: this can also be referred to as the tridiagonalization of a symmetric-definite pencil. – J. M. Aug 24 '10 at 12:17
It's noteworthy to add that attempts to simplify the QZ algorithm (the standard method for the generalized eigenproblem) for symmetric definite pencils have all failed; this has something to do with the fact that the product of two symmetric matrices need not be symmetric. – J. M. Aug 24 '10 at 14:03
I think unless the matrices commute, in general you cannot simultaneously transform them this way. – Suvrit Oct 9 '11 at 9:10

## 1 Answer

To elaborate on what I said in the comments... the reason I feel there might not be a way to do this is as follows: the problem of simultaneously tridiagonalizing two SPD matrices $A$ and $B$ is equivalent to tridiagonalizing either of $AB^{-1}$ or $A^{-1}B$; unfortunately both of these can be unsymmetric (the product of two symmetric matrices need not be symmetric), and orthogonal (unitary) similarity transformations of an unsymmetric matrix only manage to reduce to Hessenberg form.

-
Thanks for the responses. It looks like it should not be possible in general. I will see if it's possible to make a clean proof or at least a counter-example and focus my efforts on generalizing the Garvey-Tisseur concept to simultaneous congruence transforms of more matrices with wider resulting bandwidth. – Greg Aug 26 '10 at 6:21