1
$\begingroup$

I'm reading Artin's Algebra. There is the following theorem:

A square (reduced) row echelon matrix $M$ is either the identity matrix $I$, or else its bottom row is zero.

I am able to prove this statement by using induction, as in the following argument: this is clearly true for the 1 by 1 matrix. Let the inductive hypothesis be P(n): "a square row echelon matrix $Q \in R^{n \times n}$" is either the identity matrix, or else its bottom row is zero." I prove P(n+1). Consider any matrix $M \in R^{(n+1) \times (n+1)}$. Consider the first column of $M$. Split into two cases: either it is a pivot column (case 1), or not (case 2). In both cases, consider the smaller $n$ by $n$ matrix $J$, with top left corner located at $M_{22}$. $J$ is also in row echelon form, so the inductive hypothesis applies to $J$.

I prove Case 1. Suppose the first column is a pivot column with a 1 at $M_{11}$; then by hypothesis, $J$ is either the identity matrix (in which case $M$ is an identity matrix), or $J$ has bottom row full of zeros, and $M$ has a bottom row full of zeros. If the pivot in the first column is anywhere but in the first or last position, then the top row of $M$ will be zero if $J$ is the identity matrix, violating the fact that $M$ is in row echelon form, so this is impossible. But if $J$ has a zero bottom row, the bottom row of $M$ will be zero. If the pivot of the first column is at the last position, then it must be that the top row of $M$ is all zeros, else $M$ is not in row echelon form with its first column as a pivot column; so this is impossible. This proves case 1. Now, to prove case 2 observe that the only way for the first column to not be a pivot column is for it to be all 0's. By hypothesis, if $J$ is an identity matrix, then the top row is all 0's, violating the fact that $M$ is in row echelon form. If $J$ has a bottom row full of zeros, then $M$ has a row of zeros at the bottom.

However, Artin's proof seems to be much shorter: he includes the statement $S$: "if there are fewer than $n$ pivots, then some row is zero, and the bottom row is zero too."

Is it easy to prove that statement $S$ is true? I feel that my proof might be more complicated than it needs to be.

$\endgroup$
  • 1
    $\begingroup$ It is true that n a matrix in row echelon form (reduced or not), any row without a pivot must be a zero row. Is this the part that you're having trouble seeing? $\endgroup$ – Greg Martin Mar 24 '14 at 2:53
  • $\begingroup$ Yeah. Can you explain to me why that's true? $\endgroup$ – pyrrhic Mar 24 '14 at 3:09
  • $\begingroup$ Wait -- I don't see why it's obvious that with less than $n$ pivots, there exists a row without a pivot. $\endgroup$ – pyrrhic Mar 24 '14 at 3:14
  • $\begingroup$ Never mind; it is simply that since there are fewer than $n$ pivots, and that each pivot must be in a new row. But there are $n$ rows, so at least one row doesn't have a pivot. $\endgroup$ – pyrrhic Mar 24 '14 at 3:26
  • $\begingroup$ So, this is correct reasoning for square matrices. But my statement "in a matrix in row echelon form, any row without a pivot must be a zero row" is true for any size matrix, square or not. I think working out why it's always true will help you understand row echelon form a little more. $\endgroup$ – Greg Martin Mar 24 '14 at 3:59

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.