Prove that any matrix can be reduced to echelon form by an appropriate sequence of elementary row operations.

I know the elementary row operations are:

$E_1$:Interchange the $i^{th}$ row and $j^{th}$ row

$E_2$: Multiply a row by a nonzero scalar $r\in k$

$E_3:$ Replace $i^{th}$ row by ($i^{th}$row) $+$ ($j^{th}$ row)

And I also know that an $n$x$n$ matrix $A = (a_{ij})$ is in echelon form if the number of zeros preceding the first nonzero entry in a row increases row by row, stopping this increase only when arriving at an all zero row (then succeeding row must be all zeros).

I can work out examples and see this to be true but I am unsure how to approach writing a proof for this.

  • $\begingroup$ Perhaps by induction. Prove for $2 \times 2$ and use induction on the size of the matrix? I remember seeing a proof of this in my first year Linear Algebra course but am not sure how the lecturer went about proving it. $\endgroup$ – ÍgjøgnumMeg Mar 30 '16 at 16:43
  • 1
    $\begingroup$ @Ed_4434 Same here, I also suppose that induction will help, but don't remember a proof at all. $\endgroup$ – YoTengoUnLCD Mar 30 '16 at 16:44
  • $\begingroup$ Actually, now that I think of it, it is easier to do it more directly. Take an arbitrary $m \times n$ matrix and show that you can reduce it to row echelon form. That is, use Gauß-Jordan to do so. $\endgroup$ – ÍgjøgnumMeg Mar 30 '16 at 16:48
  • $\begingroup$ Use the definition of rref and show exactly how you would achieve the conditions using these operations. $\endgroup$ – Klint Qinami Mar 30 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.