Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
$\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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.