I've found a proof of uniqueness of reduced row echelon form. I have certian doubts with regard to this sentence: "It follows that R' and S' are (row) equivalent since deletion of columns does not affect row equivalence, and that they are reduced but not equal." But wait a second, we have chosen R' and S' matrices such that they are identical in all but the last column. So the matrices are NOT row equivalent. Could anyone explain what I'm missing here?

  • $\begingroup$ This is what I think they meant: if $R'$ and $S'$ are row-equivalent, then they'll still be row-equivalent after deleting a column from each (so deleting a column doesn't "get rid of" row equivalence). However, if $R'$ and $S'$ are not row equivalent, we may be able to delete a column to make them row equivalent. $\endgroup$ – Omnomnomnom Sep 10 '14 at 16:25
  • $\begingroup$ But $R'$ and $S'$ are defined to be different. Proof by contradiction is about assuming opposite, and by sticking to your assumptions + using correct logic on the way arrive at contradiction. I either don't understand this particular example or its just wrong. $\endgroup$ – user107986 Sep 10 '14 at 16:43

The way it's written is kind of confusing and I think incorrect, but I also think the main idea works. First of all, your question:

$R$ and $S$ are row-equivalent because they both come from row-reducing the same matrix (call this original matrix $A$). Thus, $R'$ and $S'$ are row-equivalent because they can be seen as coming from a matrix $A'$ which is defined by deleting exactly the same columns that you deleted from $R'$ (or $S'$) via the same sets of row operations.

The confusing part comes in at the end. The possibilities are:

(i) the augmented systems are both uniquely solvable, which implies that $r' = s'$ (implying that $R'$ = $S'$, which is a contradiction);

(ii) $R'$ is consistent but $S'$ is not (or vice versa), which happens when $R$ and $S$ first disagree at a place where the column of one matrix is a pivot but the corresponding column of the other matrix isn't. But this is also a contradiction since $R'$ and $S'$ are row-equivalent (and thus share the same solution set).

The pdf refers to a possibility that "both $R'$ and $S'$ are inconsistent" but I don't think that makes sense, because of the way $R'$ and $S'$ are defined-- you wouldn't have chosen those columns to define $R'$ and $S'$ in the first place since they are obviously equal. The only 'interesting' choices are the two above.

  • $\begingroup$ The proof in the PDF has at least one further gap: What if the leftmost column in which $R$ and $S$ differ is a pivot column in $R$ but a non-pivot column in $S$ ? (Then, $R'$ does not have the shape indicated, because the $\mathbf{0}$ isn't the zero vector anymore.) This isn't hard to deal with, but should be done too. (Also, the word "inconsistent" seems out of place, since we are hopefully talking about homogeneous systems.) $\endgroup$ – darij grinberg Sep 5 '17 at 19:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.