Suppose we are given a matrix $M_{n*2n}$ of $n$ linearly independent row vectors. Then I am trying to find an algorithmic way to add $n$ more linearly independent row vectors to this matix resulting in to a matrix $M_{2n*2n}$.

Consider this easy example, if the given matrix $M_{2*4}$ is \begin{bmatrix}0&1&0&0\\1&0&0&0\end{bmatrix} then we can add $[0,0,0,1]$ and $[0,0,1,0]$ to obtain the matrix $M_{4*4}$ \begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1 \\0&0&1&0 \end{bmatrix}

EDIT 1: Which approach I should use for a given general matrix? Can I use row reduced echelon form (rref) here?

Thank you for your help.


Take some basis for $\mathbb R^{2n}$, such as the standard basis, and consider each of the basis vectors in sequence. If it is linearly independent of the rows of the matrix so far, then append it to the matrix; otherwise discard it and move on to the next basis vector.

At the end of this process you know that

  • The rows of the extended matrix are linearly independent, by construction.
  • Every basis vector is either a row of the extended matrix or a linear combination of rows. Therefore every linear combination of basis vectors (that is, every vector) is also a linear combination of rows.

These two facts can only be true at the same time if the extended matrix is square, so exactly $n$ of the $2n$ basis vectors will have been added.

  • $\begingroup$ Thanks for your answer. I can understand what you are saying. But I am thinking of a more straightforward approach that might use rref of the given matrix. Do you have any suggestions on that? $\endgroup$ – schzan Nov 16 '15 at 11:19
  • $\begingroup$ @shzan: If you already have a row echelon form of the matrix (it doesn't need to be reduced), just add a standard basis vector for each of the pivot-less columns (with 1 in the chosen column and 0 in the other columns). $\endgroup$ – hmakholm left over Monica Nov 16 '15 at 11:31

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.