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!
 A: 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:


*

*$p_{j+1}=p_{j+1}'$

*the columns 1 to $p_{j+1}-1$ are equal in $E$ and $E'$

*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.
