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

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.

• 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. – ÍgjøgnumMeg Mar 30 '16 at 16:43
• @Ed_4434 Same here, I also suppose that induction will help, but don't remember a proof at all. – YoTengoUnLCD Mar 30 '16 at 16:44
• 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. – ÍgjøgnumMeg Mar 30 '16 at 16:48
• Use the definition of rref and show exactly how you would achieve the conditions using these operations. – Klint Qinami Mar 30 '16 at 17:16