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).
Best Answer
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.