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.)
Best Answer
Yes, this always works, and the reason is the following lemma:
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.