Reduced Row Echelon Form of n by n Matrix – Proof

linear algebraproof-verificationproof-writing

I'm trying to prove the following proposition

Prove that the reduced row echelon form (rref) of an $n$ by $n$ matrix either is the identity matrix $\bf I$ or contains at least one row of zeroes.

Firstly, I will quote the definition of the rref from the same book where the proposition was given:

A matrix is in reduced row echelon form, normally abbreviated to rref,
if it satisfies all the following conditions:

  1. If there are any rows containing only zero entries then they are located in the bottom part of the matrix.

  2. If a row contains non-zero entries then the first non-zero entry is a 1. This 1 is called a leading 1.

  3. The leading 1’s of two consecutive non-zero rows go strictly from top left to bottom right of the matrix.

  4. The only non-zero entry in a column containing a leading 1 is the leading 1.

Now, my attempt:

Assume $\bf A$ is $n$ x $n$ matrix, where $\bf R$ is rref of $\bf A$.

Suppose $\bf R ≠ I$. Then $\bf R$ must have a leading $1$ (call it $x_{i,j}$) which is located in ith row and jth column and $j > i$. Since $\bf R$ is in rref, then all leading $1$ must go strictly to the bottom right of the matrix. We are left with the $n – j$ columns and $n – i$ rows. because $j > i$, then $n – i > n – j$ and thus there must be at least $j-i$ zero rows.

Now suppose $\bf R$ doesn't have row of zeros. In this case, if $x_{i,j}$ = 1, then $i = j$, because we've shown that if $j > i$ then $\bf R$ will have row of zeros. And by definition of the identity matrix, we can conclude that $\bf R = I$ $\Box$.

Although I have a lot of doubts, but I will ask: is it correct?

The proposition is kind of intuitive, however, it was a struggle for me to formalize my thoughts. If you have any remarks/suggestions about the proof above, I'd be glad to hear them!

Best Answer

It is correct but there are some nitpicks to make. For instance:

You write 'Suppose $\mathbf{R} \neq \mathbf{I}$. Then $\mathbf{R}$ must have a leading 1 (call it $x_{i,j}$) which is located in $i$th row and $j$th column and $j>i$.'

Strictly speaking there is a second possibility and that is when $\mathbf{R}$ doesn't contain any non-zero elements at all. Of course this case is easy to handle, but perhaps you should mention it.

Also, depending on your audience, it might not really be clear that (when $x_{i, j}$ exists) we have $j > i$. The fact that $\mathbf{R} \neq \mathbf{I}$ only implies that $j \neq i$ so you might want to elaborate a bit on why $j < i$ is ruled out.

In the converse direction there are two typos: 'if $x_{i,i} = 1$, then $i = j$' should probably read 'if $x_{i, j} = 1$ then $i = j$'. Just following that you write 'because we've shown that if $i > j$ then $\mathbf{R}$ will have row of zeros', but what we have shown is something else, namely that if $i < j$ then $\mathbf{R}$ will have row of zeros.

Of course, also at this point the reader might wonder what happens in the case that $i > j$ (i.e. the case I wrote about earlier). I recommend you include it.

There is something else: you write two proofs now one that not being the identity implies having a row of zeroes and one that not having a row of zeroes implies being the identity matrix. This is nice towards the reader, but since both are logically equivalent (to each other and to the statement of the proposition) strictly speaking you only need one. (This last issue is not a problem with your proof but something that it is good to be aware of)

Related Question