Why does Gaussian elimination not preserve similarity of a matrix?

Question

I am trying to understand reduction of an unsymmetric real square matrix to Hessenberg form from Numerical Recipes Vol. 3.

In it, the author states that one does not use Gaussian elimination for reducing to Hessenberg form because the Gaussian elimination does not preserve similarity and hence ends up changing the eigenvalues of the matrix, which is undesirable.

Why does Gaussian elimination not preserve similarity?

Also, what conditions decide whether a particular matrix transformation preserves similarity?

Heres a Google Books link to where I found it. In case you cant view that, it's on page 594 of Numerical Recipes in C++ (Volume 3).

Answer 1

In the Gaussian elimination, given a matrix $A$, you apply a sequence of elementary row operations $E_1,\ldots,E_k$ in order to obtain a row echelon form $B$ of $A$: $$\tag{1} B=E_k\cdots E_1A=:EA. $$

Two matrices $A$ and $B$ are similar if and only if there is a nonsingular $X$ such that $$\tag{2}B=XAX^{-1}.$$ So there is no good reason why $A$ and $B$ in (1) should be similar (unless, of course, $E=I$).

If you want to preserve similarity using the elementary operations used in Gaussian elimination, you need to apply them "symmetrically", e.g., having an elementary operation $\tilde{E}$, $\tilde{E}A\tilde{E}^{-1}$ is a similarity transformation of the form (2) (note that the elementary row operations are easily invertible).

Considering the reduction to the Hessenberg form, while you zero out the part of the matrix below the first subdiagonal, each row operation has to be coupled by applying its inverse from the right.

Answer 2

You can use Gauss to take the matrix \begin{equation} \left( \begin{array}{cc} 1 & 0\\ 1 &1 \end{array} \right) \end{equation} To the identity matrix. Since the identity similar only to itself, Gauss elimination does not respect similarity.

Answer 3

Gauss Elimination preserves similarity if you right multiply EA by E^-1 as you can see from this example

it's not unitary similarity but similarity. This algorithm was in old EISPACK library but it has been left out of LAPACK. See the beautiful book of Watkins D.S. Fundamentals of matrix computations on page 358.