# How do i prove that the reduced row echelon form is unique?

I don't like any definition of 'reduced row echelon form' using notions left and right since these are undefined notions.

Here is my definition.

A $m\times n$ matrix $A$ is in reduces row echelon form if:

$\forall 1≦i≦m, j=\min \{1≦p≦n\|A_{ij}\neq 0\} \Rightarrow [\forall 1≦k≦m,k≠i \Rightarrow A_{kj}=0]\bigwedge[A_{ij}=1\bigwedge \forall 1≦k<i, \exists 1≦\mu<j \text{ such that} A_{k\mu}≠0]$.

===========

This can be directly shown that this definition satisfies conditions of usual definition.

However, how do i show that reduced exchelon form of a matrix is unique?

Let $A$ be a $m\times n$ matrix such that $\text{rank}(A)=r$,and $B,C$ be two reduced row exchelon form of $A$.

I have proved (1)$\{1≦i≦m|\exists 1≦j≦n \text{ such that} B_{ij}\neq 0\}=\{1,...,r\}$ and (2)$\forall 1≦i≦r, j=\min\{1≦p≦n|B_{ip}\neq 0\} \Rightarrow e_i=Be_j$. (Analogously, this holds for $C$. And $e_i$'s are the standard ordered basis for x-tuple)

Let $\mu_j=\min\{1≦p≦n|B_{jp}\neq 0\}, \forall 1≦j≦r$.

Let $\xi_j=\min\{1≦p≦n|C_{jp}\neq 0\}, \forall 1≦j≦r$.

Then, i have proved $\sum_{j=1}^r B_{ji}Ae_{\mu_j}=\sum_{j=1}^r C_{ji} Ae_{\xi_j}$. Also, $\{Ae_{\mu_j}\}_{1≦j≦r}$ and $\{Ae_{\xi_j}\}_{1≦j≦r}$ are linearly independent.

I guess it should first be shown $\xi_j=\mu_j$ to prove $B=C$, but i have no idea how to prove this.. Please help!

-
You only defined the property of being in reduced row echelon form. This is a yes/no question. I cannot think of a natural definition for uniqueness from your question. –  akkkk Mar 19 '13 at 11:34
@akkk How come this is a yes/no question. I added my definition because i wanted ppl understand how my argument works. (That is, i wanted to justify why i'm proving a bit indirectly). I described a specific situation that is, showing $B=C$. If you want a definition for uniqueness, i would say, "Reduced row echelon form of any matrix $A$ is unique: if there are finite sequences $\{R_1,...,R_r\}$ and $\{S_1,...,S_\}$ of elementary matrices such that $R_1...R_rA$ and $S_1...S_sA$ are in reduced row echelon form, then they are equal". –  Jj- Mar 19 '13 at 11:41
In other words, if $m\times n$ matrix $A$ of rank $r$ is in reduced row echelon form, then at least one of two sentences "every leading coefficients are in odd columns" and "every leading coefficients are in even columns" must be false. But how do i prove this –  Jj- Mar 19 '13 at 11:59
By "question", I meant your definition of being in reduced row echelon form. I meant that you never defined what it means for $B$ to be the rref of $A$. –  akkkk Mar 19 '13 at 17:31

A colleague of mine was asking the same question last week ; I was able to find a few books where the fact was mentioned but none where it was proven, so I came up with the folllowing. I hope that will help.

First, having a matrix with two reduced row echelon forms means there are two reduced row echelon form matrices $E$ and $E'$ and an inversible matrix $P$ such that $E'=PE$. The goal is then to prove $E=E'$ (of size $m\times n$).

Now, first remark they must have the same rank $r$, which we can assume at least one or the result is obvious, so we have $r\geqslant1$. Denote by $p_1,\dots,p_r$ the indices of the pivot columns in $E$, and likewise $p_1',\dots,p_r'$ for $E'$, and complete by $p_{r+1}=p_{r+1}'=n$ for convenience. Define for $j$ such that $0\leqslant j\leqslant r$ the assertion $H_j$ by the following three conditions:

1. $p_{j+1}=p_{j+1}'$
2. the columns 1 to $p_{j+1}-1$ are equal in $E$ and $E'$
3. the first $j$ columns of $P$ are like those of the identity matrix

It is clear that $H_r$ gives $E=E'$. Now a simple finite induction proves everything. Before that, I must stress that the main idea is to put information about the $P$ matrix in the induction ; and the main tool is that if you know a matrix by its columns, $C_1,\dots, C_n$ and multiply (to the right!) by a column with all zero except a one in line $j$ (call it $k_j$), then you get $C_j$.

Let us start with $H_0$. If we multiply the relation $E'=PE$ with the matrix whose $p_1-1$ columns are $k_1,\dots,k_{p_1-1}$, we are in the part of $E$ where all columns are zero, and hence multiplying by $P$, we still get zero. So the first $p_1-1$ columns of $E'$ are zero too! That means $p_1'-1\geqslant p_1-1$. By reason of symmetry, the reverse equality is true, and $p_1=p_1'$. This is all we had to prove for $H_0$.

Now for the induction step, assume we know $H_j$ for some $j$ and let's work on $H_{j+1}$. First, since we know $H_j$, the $j+1$-th pivot column is the same in $E$ and $E'$, at index $p_{j+1}=p'_{j+1}$, so it is the same: $k_{j+1}$. Multiply $E'=PE$ on the right by $k_{p_{j+1}}$ and you get $Pk_{j+1}=k_{j+1}$, which tells you that $P$'s $j+1$-th column is what we expected. Now in $E$, all columns with index from $p_{j+1}+1$ to $p_{j+2}-1$ are linear combinations of $e_1,\dots, e_{j+1}$, so they are invariant by $P$. Multiply $E'=PE$ by the matrix whose columns are $k_{p_{j+1}},\dots,k_{p_{j+2}-1}$ and you'll find the corresponding columns are the same in $E$ and $E'$, which gives the part of $H_{j+1}$ about the columns of $E$ and $E'$, but also the inequality $p_{j+2}'\geqslant p_{j+2}$, which again by reason of symmetry must be an equality. $H_{j+1}$ is proven, end of the proof.

-