Why does Gaussian elimination not preserve similarity of a matrix?

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

• Do you know that the identity matrix is similar only to itself? Can you get the identity matrix from other matrix buy Gaussian eliminiation? Jan 30 '15 at 11:25
• As far as I know the max Gaussian can do is reduce to row echelon form, which will set elements below the diagonal to zero and leave the upper triangle part intact. So IMO you cant get an identity matrix unless you use it for computing the inverse and then multiply. Jan 30 '15 at 11:37
• Look at my (and pavel) answers below. Jan 30 '15 at 11:53

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.

• So if I'm not getting this wrong, you mean to say that to preserve similarly of a matrix, one must apply both the operation and its inverse operation on the matrix simultaneously? Jan 30 '15 at 11:49
• @SameerDeshmukh Yes, exactly. Note that adding a multiple of a row to another row is really easy to invert by just changing the sign of the scaling coefficient. Jan 30 '15 at 11:51
• @Algebraic Pavel Not exactly.He asks "must one apply both the operation and its inverse operation simultaneously?". When one applies $E$ on the left one should also multiply by $E^{-1}$ on the right. Jan 30 '15 at 12:28
• @PVanchinathan Of course on the right, where else should $E^{-1}$ be applied? Jan 30 '15 at 12:41
• I'm sorry to revive this old topic but I need the answer to a question related to this context: can I not perform row and column operations on a real symmetric matrix simultaneously (i.e. premultiplication by elementary matrix $E$ and immediate postmultiplication by matrix $E^{-1}$) to get a diagonal matrix? Why / why not? [The aim is to reduce a symmetric matrix to a diagonal form which , as one claims, cannot be done by row/column operations. Why is this true?] Mar 27 '15 at 13:05

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.

• but the question is why not an example.
– abel
Jan 30 '15 at 12:20
• @abel: To answer why something is not true, a counter example is a correct answer. To the question why a purported proof of a false statement is flawed requires a deeper analysis, but as far as I can tell OP does not give any reasons why Gaussian elimination should preserve similarity. Jan 30 '15 at 16:28

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.