1
$\begingroup$

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.)

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.