# 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
That's a good point Cameron. However, I'm assuming (perhaps incorrectly, perhaps not), that the OP is a beginning student of linear algebra, in which case it's useful to point out why one might do row exchanges. If this is not what I'm reading between the lines of OP's question, then so be it. At any rate, it would be good for you to add your comment as an answer. –  Shaun Ault Aug 26 '12 at 12:39

Not every matrix can be converted to REF without row exchanges. A well known necessary condition is for every leading principal minor to be non-zero.

-
Could you cite a source for this condition, please? Pehaps I'm off base, but iirc, one can always eschew row exchanges (if working in matrices with entries in a field). –  Cameron Buie Aug 26 '12 at 4:26
@CameronBuie I think you're right. This result is simply from the the existence of the LU decomposition without pivoting, I hadn't considering the procedure you gave above. I think I ought to change it to sufficient but not necessary. –  EuYu Aug 26 '12 at 4:31