Simultaneous tridiagonalization of two symmetric matrices

We show how to simultaneously reduce a pair of symmetric matrices to tridiagonal form by congruence transformations. No assumptions are made on the non‐singularity or definiteness of the two matrices. The reduction follows a strategy similar to the one used for the tridiagonalization of a single symmetric matrix via Householder reflectors. Two algorithms are proposed, one using non‐orthogonal rank‐one modifications of the identity matrix and the other, more costly but more stable, using a combination of Householder reflectors and non‐orthogonal rank‐one modifications of the identity matrix with minimal condition numbers. Each of these tridiagonalization processes requires O(n³) arithmetic operations and respects the symmetry of the problem. We illustrate and compare the two algorithms with some numerical experiments. Copyright © 2003 John Wiley & Sons, Ltd.