4

Let m and n be positive integers and let F be a field. Suppose W is a subspace of $ {F ^{n}}$ and $ dim W \le m$. Prove that there is precisely one m x n row-reduced echelon matrix over F which has W as its row space.

darkgbm
  • 1,810

2 Answers2

3

First, prove that if two $m\times n$ matrices in reduced row-echelon form are not identical, then they have different row spaces. Then it follows that all matrices whose rows have span $W$ have the same reduced row-echelon form.

Gerry Myerson
  • 179,216
  • Is there a rigorous way to show that 2 $m \times n$ rref matrices have different row spaces if they are not identical? If 2 $m \times n$ rref matrices have different row spaces, supposing that they have the same number of non-zero rows, it just means that they offer a different set of basis for their row space. Since it is possible for the same subspace to be spanned by many combinations of sets of bases, this does not prove anything... – darkgbm Oct 24 '13 at 09:10
  • 1
    Let $A$ and $B$ be in reduced row-echelon form, and not identical. Look at the first row where they differ. Prove that that gives you a vector which is in the row space of one of the matrices but not in the row space of the other. – Gerry Myerson Oct 24 '13 at 12:06
  • Ok I think I get what you mean. – darkgbm Oct 25 '13 at 13:16
1

Ok I think I get what Gerry meant.

First of all, the first non-zero entry of every row of an rref matrix must be 1. Also, all entries above and below the first non-zero entry of every row of an rref matrix must be 0.

Suppose that the rref of two matrices $A$ and $B$ are $R$ and $R'$ respectively. Also suppose the $i$th rows of $R$ and $R'$ first start to differ. There are two ways they can differ: a) the first non-zero entries are in different columns or b)the first non-zero entries are in the same column but the rest of the entries differ in some ways.

In the case of a, if the first non-zero entries are in different columns, suppose for $R$ it is at column $m$ and for $R'$ it is at column $n$ where without loss of generality $n > m$. Then, the row $i$ in $R$ cannot be spanned by any linear combinations of the row vectors in $R'$ because there is no non-zero entry in column $n$ in any of the rows in $R'$. Hence, $R$ and $R'$ do not have the same row space because a vector in $R$ is not in the row space of $R'$.

We have shown that the two rref matrices must have each row to have the first non-zero row to be in the same column for them to as least not be ruled out as not having the same row space.

Given any rref matrix with $r$ non-zero rows, $r$ scalars can determine the vector in the row space it maps to. Given two non-identical rref matrices (with the same number of non-zero rows and the same columns where the first non-zero entries for each row appear), a vector in each of their row spaces is mapped to when $r$ scalars are used. This vector cannot be mapped to by the other rref matrix's rows because it will impose a relation on the $r$ scalars, and this cannot happen because the $r$ scalars are supposed to be independent.

I cannot explain the bold part very clearly, the reader can try to work it out himself. Basically by getting $r$ vectors to determine the vector that is been mapped to, the entries of the vector not in the column of the first non-zero entry of the rref's row vectors will be determined by the $r$ scalars. By using these $r$ scalars on another rref vector (that passed part a's test), another relation between those entries and the $r$ vectors can be determined. Equating these relations, a relationship can be found between the $r$ scalars, which cannot happen.

darkgbm
  • 1,810