# When is row exchange necessary in gaussian elimination?

How do we know that matrix needs to do row exchange when doing Gaussian elimination to obtain row echelon form, and when is row exchange necessary in Gaussian elimination?

Can every matrix be converted under Gaussian elimination to row echelon form without row exchange?

-

One important case is when the $(1,1)$ entry of the matrix is $0$. We would row-exchange with a row whose first entry is non-zero, if such exists.
$\begin{eqnarray*} \left(\begin{array}{cc}0&1\\1&0\end{array}\right) & \to & \left(\begin{array}{cc}1&1\\1&0\end{array}\right)\\ & \to & \left(\begin{array}{cc}1&1\\0&-1\end{array}\right)\\ & \to & \left(\begin{array}{cc}1&0\\0&-1\end{array}\right)\\ & \to & \left(\begin{array}{cc}1&0\\0&1\end{array}\right). \end{eqnarray*}$ – Cameron Buie Aug 26 '12 at 4:22
Observe that row-exchange is accomplished here indirectly with $4$ other elementary row operations. Turns out that this generalizes, so that any row exchange can be accomplished by using (at most) $4$ other elementary row operations, instead. – Cameron Buie Aug 26 '12 at 4:23