10

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!

chaohuang
  • 6,257

2 Answers2

18

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

Arturo Magidin
  • 398,050
3

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.

Gerry Myerson
  • 179,216
  • I know this answer was posted a long time ago, but I would be grateful if you could clarify something in your response. By leftmost non-zero entry, do you mean leading 1? Or can it be any number? @Arturo Magidin mentions "identify the columns that contain the leading 1's". – Agent 0 Jun 05 '18 at 20:14
  • 1
    If all you want to do is find a maximal linearly independent subset of a given set of vectors (as in the original question), then it doesn't matter what the leftmost non-zero entry is. But in the usual definition of "reduced row-echelon matrix", yes, that entry has to be a 1. – Gerry Myerson Jun 05 '18 at 23:24
  • 1
    Right, makes sense, in my case, I am going to do RREF matrix so that's why I was wondering if it would matter. I appreciate you for getting back to me, +1 :) – Agent 0 Jun 06 '18 at 01:50