two reduced row echelon matrices have the same nullspace, prove they are identical

Question

I am trying to prove if R and R' are two reduced row echelon matrices, and have the same nullspaces, they are identical. I have observed this when testing them, but I have trouble finding a formal proof.

I tried reading this question and extracting a general solution, but this question is focused on a particular 2 by 3 matrix whereas I am trying to find a formal proof for an m by n matrix.

I believe I should start by writing two general reduced row echelon matrices, writing Rx=R'x=0 and finding a general answer for each row, then proving they are equal, but I have trouble proving it generally and without presumptions.

Thank you in advance.

Answer 1

Here is an attempt at a direct proof (which is unfortunately more complicated than I would have hoped).

It suffices to show that the RREF can be recovered from the nullspace. Let $R$ denote an RREF matrix with $n$ columns; we proceed inductively over $n$. For the case of $n=1$, there are two possible RREF matrices corresponding to the two possible nullspaces.

For $n > 1$, let $U$ denote the nullspace of $R$. Let $R'$ denote the matrix obtained by deleting the last column of $R$. We note that the nullspace of $R'$ has the same dimension as (and is "essentially equal" to) $$ U' = U \cap \operatorname{span}\{e_1,\dots,e_{n-1}\}, $$ where $e_1,\dots,e_n$ denote the standard basis of $\Bbb R^n$. There are two possibilities: in the case that $U' = U$, the final column of $R$ must be linearly independent of the rest, which means that the final column must be a pivot column. For the case that $U' \subsetneq U$, let $p_1<\cdots<p_r$ denote the indexes of the pivot columns of $r$, so that $Re_{p_i} = e_i$ for each $i = 1,\dots,k$. It follows that the final column $Re_n$ of $R$ satisfies $$ Re_n = \sum_{i=1}^k r_{in} e_i = \sum_{i=1}^k r_{in} R e_{p_i} \implies\\ R\left[e_n - \sum_{i=1}^k r_{in} e_{p_i}\right] = 0. $$ That is, if $v = e_n - \sum_{i=1}^k r_{in} e_{p_i}$, then $U = U' + \operatorname{span}(v)$.

I claim that for any $w = e_n - \sum_{i = 1}^k s_{in} e_{p_i}$, we can only have $U' + \operatorname{span}(v) = U' + \operatorname{span}(w)$ if $r_{in} = s_{in}$ for all $i$. If this is proved, then the final column of $R$ is uniquely determined by $U$, which would allow us to finish the proof.

Answer 2

Perhaps there is an easier proof. I'll write it informally.

Consider the two system of equations defining the null spaces $$ R_Ax=0\quad\text{respectively}\quad R_Bx=0 $$ To have the same null space means that the solutions of the two systems are identical.

Now we start from the last row $m$ of the two rref. Suppose that the two rows differ, $r_{A,m}\ne r_{B_m}$ ($r_{A,m}$ is the $m$th row of $R_A$), then(*) there is $x$ such that $$ r_{A,m}\cdot x=0 \quad\text{and}\quad r_{B,m}\cdot x\ne 0 $$ (or the other way around) contradicting the equality of the two null spaces. Thus the two rows are equal. We proceed from row $m$ to row $1$ proving that all rows are identical.

(*) How to find such an $x$? We go back to the rules defining a rref. The two rows are different and cannot be both zero. If only one is zero the we have the whole $\mathbb{R}^n$ versus a strict subset of it. If both are not zero, the first element of the row is $1$; if the position of the $1$ is different, w.l.o.g $r_{A,m}$ has less zero on the left side of the $1$ positioned at $k$, then $x_k$ appears in $r_{A,m}\cdot x=0$ and not in $r_{B,m}\cdot x= 0$, thus $\cdots$