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

matricesmatrix-rank

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:

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.

Related Question