12.4.2. Similarity Transformations

Similarity transformation is the fundamental tool for diagonalizing a matrix. Cauchy is credited with giving us our understanding of similar matrices and similarity transformations.

Similar Matrices

Two matrices are said to be similar if they have the same eigenvalues.

Aside from comparing the eigenvalues, there is a simple test to verify if two matrices are similar.

12.4.2.1. Similar Matrices

Theorem 12.5 (Similar Matrices)

Matrices \bf{A} and \bf{B} are similar if there exists a matrix \bf{M} for which the following relationship holds.

\mathbf{B} = \mathbf{M}^{-1}\,\mathbf{A\,M}

Proof. We will start with the eigenvalue equation for matrix \bf{A} and work toward the eigenvalue equation for the similar matrix \bf{B}. We can insert an identity matrix (\mathbf{M\,M}^{-1} = \bf{I}) into the eigenvalue equation.

\mathbf{A}\,(\mathbf{M\,M}^{-1})\,\bm{x} = \lambda\,\bm{x}

Now multiply both sides by \mathbf{M}^{-1} and substitute for \bf{B}.

\begin{aligned} (\mathbf{M}^{-1}\mathbf{A\,M})\,\mathbf{M}^{-1}\,\bm{x} &= \lambda\,\mathbf{M}^{-1}\,\bm{x} \\ \mathbf{B}\,(\mathbf{M}^{-1}\,\bm{x}) &= \lambda\,(\mathbf{M}^{-1}\,\bm{x}) \end{aligned}

Thus, an eigenvalue of \bf{B} is \lambda, the same as \bf{A}, and the corresponding eigenvector of \bf{B} is \mathbf{M}^{-1}\,\bm{x}.

\qed

Algorithms that compute the eigenvalues of a matrix must maintain similarity. Unitary transformation matrices in the form of Householder reflection matrices, \m{H}, or Givens rotation matrices, \m{G}, give a matrix a desired form by setting elements of the matrix to zero. When the unitary matrix is applied with multiplication from the left (\m{G}_i \m{A}), then the transpose of the unitary matrix is multiplied from the right to maintain similarity, \mathbf{B}_i = \m{G}_i \m{A\,G}_i^H. The transpose of each Householder or Givens unitary transform is what we call the similarity matrix, \m{Q}_i = \m{H}_i^H \text{ or } \m{G}_i^H. The factorization is then \m{A} = \m{Q\, B\, Q}^H.

A function that implements an algorithm could return matrices \bf{B}, which is the result of all of the similarity transformations, and \m{Q}, which is the product of the unitary similarity matrices, \m{Q} = \m{Q}_0 \times \m{Q}_1 \times \cdots \times \m{Q}_k.