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.

Given a set of vectors, we can compute the number of independent vectors by calculating the rank of the set, but my question is how to find a maximal linearly independent subset. Thanks!

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

One method is:

  1. Place the vectors as columns of a matrix. Call this matrix $A$.
  2. Use Gaussian elimination to reduce the matrix to row-echelon form, $B$.
  3. Identify the columns of $B$ that contain the leading $1$s (the pivots).
  4. The columns of $A$ that correspond to the columns identified in step 3 form a maximal linearly independent set of our original set of vectors.

Another method is:

  1. Let $A$ be your multiset of vectors, and let $B=\varnothing$, the empty set.
  2. Remove from $A$ any repetitions and all zero vectors.
  3. If $A$ is empty, stop. This set is a maximal linearly independent subset of $A$. Otherwise, go to step 4.
  4. Pick a vector $\mathbf{v}$ from $A$ and test to see if it lies in the span of $B$.
  5. If $\mathbf{v}$ is in the span of $B$, replace $A$ with $A-\{\mathbf{v}\}$, and do not modify $B$; then go back to step 3.
  6. If $\mathbf{v}$ is not in the span of $B$, replace $A$ with $A-\{\mathbf{v}\}$ and replace $B$ with $B\cup\{\mathbf{v}\}$. Then go back to step 3.

When step 3 instructs you to stop, $B$ contains a maximal linearly independent subset of $A$.

share|improve this answer
add comment

Form a matrix whose columns are the given vectors. Do row reduction to bring it to reduced form. In each non-zero row of the reduced form, circle the leftmost non-zero entry. The columns in the original matrix that correspond to columns in the reduced matrix with a circled entry - they form a maximal linearly independent set.

share|improve this answer
add comment

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.