[Math] Prove every linearly independent set is contained in a basis

linear algebra

Suppose that linear space L has a basis with a finite number of points, B = {P1,
P2, P3, … Pn} Then every linearly independent set is contained in a
basis.

I'm not sure how to go about proving this. I know that no linearly independent set can be larger than basis B, but I'm not sure how to prove there isn't a linearly independent set outside of the basis.

Best Answer

You show this by simply adding vectors to some linearly independent set $X$ until you find a basis. You start with some linearly independent set $X = X_0$, and $k = 0$.

  1. Let $S_k = \textrm{span }X_k$.
  2. If $S_k = L$, we're done. By construction $X_k$ is linearly independent, and it spans $L$, so by definition it's a basis.
  3. Otherwise, pick an arbitrary $x_k \in L \setminus S_k$. Since $x_k \notin S_k$, $x_k$ is linearly independent from $X_k$.
  4. Set $X_{k+1} = X_k \cup \{x_k\}$, which by (3) is a linearly independent set
  5. Continue at (1), with $k := k + 1$

Since $L$ is finite-dimensional, this algorithm must stop at some point, because if $L$ has dimension $n$, no set with more than $n$ elements can be linearly independent. But if the algorithm stops during iteration $k$, then $X_k$ is a basis, and by construction $X_k \supset X$.

Therefore, whenever we're given a linearly independent set $X$, we can run this algorithm to find a basis $X_k$ which includes $X$.

Related Question