Definitions A matrix is said to be in reduced row echelon form if it satisfies the following: (1) Any row made up of entirely zeroes is preceded by a nonzero row. (2) The first nonzero entry in each nonzero row is the only nonzero entry in its column. (3) The first nonzero entry in each row occurs to the right of the first nonzero entry in the previous row[s]. (4) The first non zero entry in each row is 1.
I aim to prove the uniqueness of this reduced row echelon form, and first prove a result that (atleast to me) isn't obviously related. I would like if someone could check my proof for this result and also see if the result itself can be described more concisely. The rest of the proof follows simply from this result, and I don't need it checked.
Result 1: Let $T$ denote the bijection that transforms a rank $r$ matrix $A$ into it's reduced row echelon form $A_E$. Let $A_i$ denote the $i$th column of $A$. The following always holds: The ordered set of columns that $T$ will map to $\{e_1,\cdots,e_r\}$ is the set found by choosing the first most linearly independant columns of $A$, including the first column. That is, starting with $A_1$, choose the first column that is lineraly independant to $A_1$, then choose the next that is lineraly independant to both $A_1$ and the previous one you chose, and so on until you have a set of $r$ linearly independant columns of $A$.
Proof. Assume for a contradiction that the result did not hold: assume there exists some linear transformation $T$ transforming a matrix $A$ into it's row echelon form $B$ such that there exists $A_k$ that satisfies the following: (1) $A_k$ comes after a column that $T$ maps to $e_n$ and before a column that $T$ maps to $e_{n+1}$ for the first time. (2) $A_k$ is linearly independant to all the columns that first map to $\{e_1,\cdots e_n\}$.
Call $S$ the set of columns of $A$ that first map to $e_1,\cdots, e_n$. By the assumption and definition of bijection $T(S)\cup T(A_k)$ must be linearly independant. That is $\{e_1,\cdots,e_n,T(A_k)\}$ is linearly independant, meaning $T(A_k)$ must have a nonzero entry in a row higher than $n$, by the definition of row echelon form, this contradicts the assumption that $A_k$ comes before the first column that maps to $e_{n+1}$. Proving Result 1