# Bandwidth reduction of multiple matrices

Suppose I have a symmetric matrix $A$ and several diagonal matrices $D_1,D_2,\dots$. Are there any matrix transformations such as $P^\top A P$ so that

$$P^\top A P, P^\top D_1 P, P^\top D_2 P, \dots$$

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. Apr 7, 2012 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. Apr 7, 2012 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. Apr 7, 2012 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). Apr 7, 2012 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.