Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}. $$

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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