how to find maximal linearly independent subsets

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!

Solution 1:

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

Solution 2:

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.