Relationship between Row Space and Reduced Row Echelon Form Consider two matrices A and B having the same dimension. It is said that: if A and B have different reduced row echelon forms (RREFs), then their row spaces are different. 
Any one know how to prove this statement? Or, is there any reference (book) on this?
Thanks in advance.
 A: I think it is easier to prove the contrapositive instead: If two matrices have the same row space, then they have the same RREF.
Assume $A$ and $B$ have the same row space. Also, let's say they are both $n \times m$ matrices. This means for any $x \in \Bbb{R}^n$, there is a $y \in \Bbb{R}^n$ such that $x^tA=y^tB$.
Now, let $e_i \in \Bbb{R}^n$ for $1 \leq i \leq n$ be the sandard basis of $\Bbb{R}^n$ and let $y_i \in \Bbb{R}^n$ for $1 \leq i \leq n$ satisfy the equation $e_i^tA=y_i^tB$. Now, make a matrix such that the $i^{\text{th}}$ row of the matrix is $y_i^t$. Call this matrix $R$.
Note that there might be multiple possible $y_i$ for some $e_i$. We want $R$ to be nonsingular, so we need to choose these rows so they are linearly independent. If the rank of matrix $A$ is $k$, then there are $k$ rows of $A$ that are linearly independent. We will call these rows $e_{l_i}^tA$ for $1 \leq i \leq k$. We will call the other rows $e_{m_i}^tA$ for $1 \leq i \leq n-k$.


*

*For the rows with index $l_i$, find a solution $y_{l_i}$ and then write $y_{l_i}^t=u_{l_i}^t+v_{l_i}^t$ where the $u^t$s are in the left null space of $B$ and the $v^t$s are in the orthogonal complement of the left null space of $B$. Then, choose $v_{l_i}^t$ as the row for $R$. Since all of the $e_{l_i}^tA$ are linearly independent and $e_{l_i}^tA=v_{l_i}^tB$, all of the $v_{l_i}^tB$ are linearly independent, so all of the $v_{l_i}^t$ are linearly independent.

*For the rows with index $m_i$, find a solution $y_{m_i}$ and then write $y_{m_i}^t=u_{m_i}^t+v_{m_i}^t$ where the $u^t$s are in the left null space of $B$ and the $v^t$s are in the orthogonal complement of the left null space of $B$. Then, write a basis for the left null space of $B$. The row space of $B$ is equal to the row space of $A$, which has dimensionality $k$. Thus, by the Fundamental Theorem of Linear Algebra, the left null space has dimensionality $n-k$. Therefore, we can write a basis for the left null space of $B$ as $n_i$ for $1 \leq i \leq n-k$. Now, we will choose $v_{m_i}^t+n_i^t$ as the row for $R$. These are linearly independent from all of the $v_{l_i}^t$ since those were all in the orthogonal complement of the left null space and thus can not span $n_i^t$. Also, they are all independent from each other because they all have a different $n_i^t$, which are linearly independent from each other since they are a basis.


Clearly, we have $e_i^tR=y_i^t$, so we have $e_i^tRB=y_i^tB$, so by Transitive Property, we get $e_i^tRB=e_i^tA$. Now, $e_i^tM$ for any matrix $M$ represents the $i^{\text{th}}$ row of $M$. This means the $e_i^tRB=e_i^tA$ is the same as saying the $i^{\text{th}}$ row of $RB$ is equal to the $i^{\text{th}}$ row of $A$. Thus, since all of their rows are equal, we have $A=RB$. Since $R$ is nonsingular, this means $A$ is row equivalent to $B$, so $A$ and $B$ have the same RREF.
A: The row space of a matrix is the same as its row echelon form since you are performing elementary row operations. In RREF certain properties must be satisfied:


*

*The first non-zero entry of the row is $1$ (this is the pivot of the row)

*Every element below the pivot is a $0$.

*Each row that contains a leading 1 has zeros everywhere else.

*All rows of $0$ are in the bottom of the matrix.


Then if A and B have different RREF, then their row space are different too. Why? Let's put an example:
$M= \begin{bmatrix} -1&3&2 \\ -2&5&3 \\ -3&1&-2 \end{bmatrix}$
As you can notice $C_3 = C_1 + C_2$ then $rank(M) = 2$ and if you attempt to put in RREF is:
$\begin{bmatrix} 1&0&1 \\ 0&1&1 \\ 0&0&0 \end{bmatrix}$ but it doesn't satisfy the rule $3$.
If we work with a new matrix $M'$ with $rank(M')=3$ and we attempt to put in RREF then we will end up with:
$M'= \begin{bmatrix} -1&3&5 \\ -2&5&-7 \\ -3&1&11 \end{bmatrix}$
In RREF form : $\begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix}$
Thus both matrices $M$ and $M'$ have different row spaces and ranks.
