Let M be an $m \times n$ matrix whose rows are linearly independent. Suppose that $k$ columns $c_{i_1}, ... , c_{i_k}$of M span the column space of M. Let C be the matrix obtained from M by deleting all columns except $c_{i_1}, ... , c_{i_k}$. Show that the rows of C are also linearly independent.

Since the rows are linearly independent in M, we know that every row has a pivot position.

We know that the row rank is equal to the column rank. Since the row rank is at least m and the column space is at most k, we know that k is either equal to m or greater than it.

Case 1

Let k=m. Then $c_{i_1}, ... , c_{i_k}$ is both a linearly independent and a spanning set, so the rows must also be linearly independent.

Case 2

Let k>m. Since $c_{i_1}, ... , c_{i_k}$ is a spanning set, it must contain the linearly independent set. In other words, it must contain all columns in M that have a pivot position. So the rows of matrix C also have a pivot in every row, which implies that the rows are linearly independent.

Do you think my answer is correct?

Thanks in advance


1 Answer 1


I think your "proof by cases" works just fine, though I personally would do three cases, with first case "if $k < m \implies$ Contradiction", basically, then writing the very reasons you concluded that $k \geq m$.

Note: That's just how I'd do it, since you are already considering cases, we might as well exhaust them all, which you did (consider them all, just not explicitly so).

But my preference has nothing to do with the correctness of your proof. Your logic, which you included, for good reason, does the job.

  • $\begingroup$ Nice my dear friend. You really $\textbf{did}$ it. $\endgroup$
    – Mikasa
    Jun 26, 2013 at 4:48
  • $\begingroup$ @Babak: thank you, dear friend! Good to see you ;-) $\endgroup$
    – amWhy
    Jun 26, 2013 at 4:50

You must log in to answer this question.