Extending a full row rank matrix to a full rank square matrix

Question

Suppose I have a matrix $M$ over the reals, with $m$ rows and $n$ columns, where $n > m$. Suppose further that $M$ has full row rank.

Is it always possible to add $n-m$ unique standard basis elements (i.e. $(0,...,0,1,0,...,0)$) as fresh rows to the matrix to result in an $n$ by $n$ matrix of full rank?

For example, suppose we have the matrix:

\begin{matrix} 1 & 1 & 1\\ 1 & -1 & 1 \end{matrix}

The standard basis elements $(1,0,0)$ and $(0,0,1)$, when added as a row to the matrix, would result in a square matrix of full rank. (Note that the standard basis element $(0,1,0)$ would not work as the matrix

\begin{matrix} 0 & 1 & 0\\ 1 & 1 & 1\\ 1 & -1 & 1 \end{matrix}

does not have full rank.)

Answer 1

Yes, this always works, and the reason is the following lemma:

Lemma. Let $K$ be a field and $V$ a vector space over $K$. Given linearly independent vectors $v_1,\dots,v_k\in V$ and any $w\in V$, we have $$ \text{$v_1,\dots,v_k,w$ are linearly independent} \quad\Longleftrightarrow\quad w\notin\operatorname{span}(v_1,\dots,v_k). $$

In your situation $v_1,\dots,v_k$ are the rows of your $m\times n$ matrix. Since $m<n$, the rows don't span all of $\mathbb R^n$ so there must be at least one of the standard basis vectors not in the row space. By the above lemma you can add that vector as a row to obtain a new matrix with one more row and still linearly independent rows.

This can be repeated until you end up with a square matrix.

Answer 2

Yes you just need to continually add row vectors that aren't in the span of the previous ones until we have $n$ rows. This will always be possible as long as the previous row vectors don't span $\mathbb R^n$, which in our case won't happen since we have less than $n$ row vectors.

Each time we are adding $1$ to the dimension of the space generated by the rows. Sine we start out with $m$ and do it $n-m$ times at the end we get that the rows span a space of dimension $n$ as desired.