# How to remove linearly dependent rows/cols

How would one remove linearly dependent rows/columns from a rank-deficient matrix.

For example, (from wikipedia):

$$A = \begin{bmatrix} 2 & 4 & 1 & 3 \\ -1 & -2 & 1 & 0 \\ 0 & 0 & 2 & 2 \\ 3 & 6 & 2 & 5 \end{bmatrix}.$$

If you convert it to row-echelon-form, you get:

$$A = \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

This demonstrates that there are two linearly independent columns. As noted in the wikipedia article, "We see that the second column is twice the first column, and that the fourth column equals the sum of the first and the third". How can one extract the linearly independent columns (or rows) and get a result like:

$$A = \begin{bmatrix} 2 & 1 \\ -1 & 1 \\ 0 & 2 \\ 3 & 2 \end{bmatrix}.$$

-

## 1 Answer

Look at the row-echelon form. Each non-zero row has a "leading 1" (that is, the first non-zero entry in each such row is a 1). The columns with a leading 1 are the 1st and the 3rd. It follows that the 1st and 3rd columns of the original matrix are linearly independent, indeed, are a basis for the vector space spanned by the columns.

-
Cool, and why is it not possible to reduce the rows instead? Since row-rank and column-rank are equal? –  Realz Slaw Sep 19 '12 at 13:23
For the rows, you have two choices. One, the nonzero rows of the row-echelon form are a basis for the row space of the original matrix, so you can just use them. Two, if you insist on using only rows from the original matrix, you can do this if you modify the row-reduction procedure by never swapping two rows. Then if, say, the 3rd, 7th, and 16th rows in the (quasi-)reduced form are nonzero, you keep the 3rd, 7th, and 16th rows of the original. –  Gerry Myerson Sep 19 '12 at 13:52
"It follows that the 1st and 3rd columns of the original matrix are linearly independent, indeed, are a basis for the vector space spanned by the columns." - BOOM! –  Karl Morrison Oct 22 '14 at 11:39