Proof that there is precisely one row-reduced matrix per row space

linear algebramatrices

This theorem and proof comes from Hoffman & Kunze (2ed) section 2.5 theorem 11.

I do not understand how the information preceding "It is now clear that R is uniquely determined by W" makes this theorem clear. Because I cannot quite pin point what I am missing, I will explain my understanding of the theorem up to the point where I cannot.

I think I understand that we start with a matrix whose row space is W. Then, we take the row-reduced echelon matrix. Then, we consider any (an arbitrary) row-reduced echelon matrix whose row space is W. Then, we know that the RREM row vectors form a basis for W. Thus, an arbitrary vector can be written as a linear combination of the basis vectors. After this point, however, I am lost as to how the information contributes to proving the theorem.

Any help would be greatly appreciated!

enter image description here

enter image description here

Best Answer

The proof.

I think you got the existence right:

I think I understand that we start with a matrix whose row space is W. Then, we take the row-reduced echelon matrix.

As for the uniqueness, I will reformulate the proof slightly, hopefully, it will be easier to follow.

Then, we consider any (an arbitrary) row-reduced echelon matrix whose row space is W. Then, we know that the RREM row vectors form a basis for W. Thus, an arbitrary vector can be written as a linear combination of the basis vectors.

The rest relies on the properties of the RREF $R$: the position of the first non-zero entry of row $\rho_i$ is $k_i$, and its value is $1$. I shall call $\{k_i\}$ the basic positions.

As you said, $\beta\in W$ can be written as a linear combination of $\{\rho_i\}$. There are $r$ coefficients, which determine $\beta$. Because $\{\rho_i\}$ is such a special basis, these coefficients equal $b_{k_i}$. In particular, if an arbitrarily chosen $\beta \in W$ happens to satisfy $b_{k_s}=1$ and $b_{k_i}=0$ for $i\neq s$, then $\beta = \rho_s$.

This begs the following questions.

  1. Can we recover the set $\{\rho_i\}$ by "fishing" the row-space $W$ for vectors that satisfy $b_{k_s}=1$ and $b_{k_i}=0,\,\forall i\neq s$?

    • Yes, we will certainly "catch" all $\{\rho_i\}$. But we also don't want to "catch" anything else.

  2. Even if we "catch" $\{\rho_i\}$ and nothing more, does this prove the uniqueness of RREF?

    • Not yet, because there is an element of circular reasoning. We "filter" $\beta\in W$ using the basic positions we extracted from a particular RREM. We haven't ruled out that a different set $\{\rho_i\}$ can be obtained by using a different set of $\{k_i\}$.

The following observation removes the remaining obstacles.

If $\beta\in W$, $\beta\neq0$, then its first non-zero entry must be at a basic position (otherwise we contradict the expansion of $\beta$ in $\{\rho_i\}$). Conversely, for all basic positions, there exists a $\beta\in W$ with its first non-zero entry at this position (e.g., take $\beta=\rho_s$). In other words, the set of possible positions of the first non-zero entry of $\beta\in W$ is precisely the set of basic positions defined by the given RREM. This means that the set of basic positions $\{k_i\}$ is a property of $W$ and is the same for all RREMs.

We are certain we will "catch" $\{\rho_i\}$, nothing but $\{\rho_i\}$, and there is no ambiguity in defining $\{k_i\}$.

On a side note:

I do not understand how the information preceding "It is now clear that R is uniquely determined by W" makes this theorem clear.

Because it does not!

The key thing to understand here is how the text is structured and how it should be read:

  • some paragraphs are "level-0", they are part of the "global" narrative of the proof and develop ideas sequentially, from a premise to an intermediate conclusion;
  • some paragraphs are "level-1", they are like little lemmas or subroutines you enter in a programme, they state a conclusion first, and only then proceed to explaining it. This conclusion can be an intermediate idea within the scope of the proof, but the final destination within the scope of the paragraph.

In general, the boundaries between these two types of paragraphs can be blurred, but in this text they are quite clear. Here, the only level-0 paragraph is

Now let $R$ be any row-reduced...

All other paragraphs are level-1:

There is at least one $m\times n$...

Suppose $\beta$ is ... . We claim the first non-zero coordinate occurs ...

It is now clear that $R$ is uniquely determined by $W$. ...

So to answer your question, the information preceding "It is now clear ..." does not make it clear. You should look at the sentences that follow. I hope this helps!

Related Question