# Bandwidth reduction of multiple matrices

Suppose I have a symmetric matrix A, and several diagonal matrices $D_1,D_2,...$

Are there any matrix transformations, such as $P^\top A P$ so that $P^\top AP$, $P^\top D_1 P$, $P^\top D_2 P$, etc are either all tridiagonal, or all have minimimal bandwidth in some sense? If for example, I only had $D_1$ then solving the generalized eigenvalue problem for the matrix pencil $A,D_1$ would give me a basis that simultaneously diagonalizes both $A$ and $D_1$. Obviously, one basis will not simultaneously diagonalize more matrices in general, but a set of banded matrices would also be pretty nice.

I am aware of Tisseur and Garvey's papers on simultaneous tridiagonalization of two matrices.

-
Sorry, I should not have chosen the symbol $P$ in that case. $P$ is not a permutation matrix in my example, and $A$ is assumed to be full. As an example, suppose I have the generalized eigenvalue problems [ A V = V D_1 \Lambda_1 ] [ A U = U D_2 \Lambda_2 ] Now I have a matrice $V$ and $U$ such that the following matrices are diagonal: $V^\top A V$, $U^\top A U$, $V^\top D_1 V$, $U^\top D_2 U$ It seems, in general, impossible to find a single matrix that diagonalized $A$, $D_1$ and $D_2$, however, if it produced a banded matrix, that would still be useful for my purposes. –  Greg von Winckel Apr 7 '12 at 13:26
In general if $A$ is symmetric and $D$ is diagonal, it is not possible to simultaneously diagonalize them because this would imply that they commute. –  Chris Godsil Apr 7 '12 at 13:29
Yes. That is exactly what I said. That is precisely why I was asking if there was a way to reduce them both to banded form. –  Greg von Winckel Apr 7 '12 at 20:29
Additionally, it is possible to simultaneously diagonalize two matrices, but not with a similarity transformation. The matrix of eigenvectors to a symmetric definite matrix pencil $Ax=\lambda B x$ does diagonalize both $A$ and $B$, however, it is not an orthogonal matrix (see my first comment above). –  Greg von Winckel Apr 7 '12 at 20:33

If you use the typical reorderings (like reverse Cuthill-McKee ordering), $P^T A P$ will have a smaller bandwidth (in general, not tridiagonal though). Since $P$ is a permutation matrix, all $P^T D_i P$ will remain diagonal too.

Bart

-