6
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 24, 2010 at 12:02
  • 1
    $\begingroup$ For the benefit of search engines: this can also be referred to as the tridiagonalization of a symmetric-definite pencil. $\endgroup$ Aug 24, 2010 at 12:17
  • $\begingroup$ 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. $\endgroup$ Aug 24, 2010 at 14:03
  • $\begingroup$ I think unless the matrices commute, in general you cannot simultaneously transform them this way. $\endgroup$
    – Suvrit
    Oct 9, 2011 at 9:10

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Greg
    Aug 26, 2010 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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