# Show that every matrix can be in row-reduced echelon form

I would like to prove that every matrix can be in row-reduced echelon form. I started as follows:

It's easy to show that any $2\times2$ matrix can be in row-reduced echelon form. Now assume that for $n\in N$, we have that $n-1\times n-1$ matrices can be in row-reduced echelon form. Consider an $n\times n$ matrix $A:(A)_{ij}=a_{ij}$. Assume first that the first row of $A$ consists of a non-zero entry. Then put this entry via row-exchange in the first row. We can now turn all the remaining entries in the first column to zero through row addition with the first row. So we have the following: $$\begin{bmatrix} 1&*&\dots&*\\ 0&b_{12}&\dots&b_{1n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&b_{n2}&\dots&b_{nn} \end{bmatrix}$$ Now denote the $n-1\times n-1$ matrix with the $b_{ij}$ entries by $B$. We know that $B$ can be row-reduced. Assume $B$ can be row-reduced to $I_{n-1}$, then we know that we can turn the remaining entries on the first row to zeroes. Now assume $B$ can't be row-reduced to $I_{n-1}$.

Here I need that we have a zero row. But to prove that, I need that every matrix can be in row-reduced echelon form. So I'm hoping there's an elementary way to conclude that $B$ is row-equivalent to $B'$ that contains a zero row, without using invertibility and the like. I am looking for a very elementary approach.

EDIT

I know how I can do it. I can prove for this case, that the $n-1\times n-1$ matrix must contain a zero row, because I can use the fact that it is in row-echelon form. I would do this by contradiction:

Assume we have exactly $n-2^*$ leading ones and assume that the last row is not the zero row. We can turn all the entries of the last row that are below a leading one to zero. This means we can turn $n-2$ entries to zero. Now consider this last entry that is not below a leading one; if it is zero, we're done. If it is not zero, then obviously this entry must have been a leading one. End of proof.

This also finished our original proof, because if $B$ is row-equivalent to $B'$ that contains a zero row, then obviously our original matrix $A$ is row-equivalent to a matrix $A'$ that contains a zero row. We can turn $n-2$ entries of the first row of $A'$ (minus the first entry) to zeroes. The one entry that might not be equal to zero, isn't above a leading one anyway, so the requirements of RREF are met.

$^*$ I didn't consider the case of $<n-2$ leading ones, but actually I could have. The general case would be: Assume there are $\leq n-2$ leading ones. Assume the last row is not the zero-row. We know there is at least 1 entry in the last row that is not below a leading one. If there are more than one such entries, then consider the most left one (with the least column number). If this entry is zero, then we're done. If it's not zero, then it must have been a leading one itself. Contradiction.