7
$\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.

Improve this question
$\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$
    – J. M. isn't a mathematician
    Commented 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$
    – J. M. isn't a mathematician
    Commented 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$
    – J. M. isn't a mathematician
    Commented Aug 24, 2010 at 14:03
  • $\begingroup$ I think unless the matrices commute, in general you cannot simultaneously transform them this way. $\endgroup$
    – Suvrit
    Commented Oct 9, 2011 at 9:10

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\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
    Commented Aug 26, 2010 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .