Relationship between Row Space and Reduced Row Echelon Form

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.