## Wednesday, May 24, 2006

### The Algebra Of Lines? Topic: Linear Algebra.

Note: See MathWorld for any necessary definitions.

--------------------

Problem: Let $\{v_1, v_2, \ldots, v_m\}$ be a linearly independent set of vectors in a nonzero subspace $S$ of $\mathbb{R}^n$ such that $span(v_1, v_2, \ldots, v_m) \subset S$. Then it can be extended by adding some more vectors to form a basis of $S$.

Solution: Take any vector $v_{m+1} \in S$ such that $v_{m+1}$ is not a linear combination of $\{v_1, v_2, \ldots, v_m\}$ (i.e. $v_{m+1}$ is not in the span of the original set of vectors). The existence of such a vector is guaranteed by the fact that the span is strictly contained within $S$ Since it is not a linear combination, the new set $\{v_1, v_2, \ldots, v_{m+1}\}$ is still linearly independent. Furthermore, it has a greater span than the original set. If the new span is still strictly contained within $S$, we may add another vector $v_{m+2} \in S$. Repeating this process allows us to keep increasing the span. But we also note that this process must terminate because a set of $n$ vectors that is linearly independent must span all of $\mathbb{R}^n$; therefore, after adding some vector $v_k$ with $m < k \le n$ we will have formed a basis $\{v_1, v_2, \ldots, v_k\}$ of $S$. QED.

--------------------

Comment: This is actually a lemma that leads to one of the most basic nontrivial results in Linear Algebra, that every subspace $S$ of $\mathbb{R}^n$ in fact has a basis. The idea is trivial in $\mathbb{R}^3$, for example, because a single vector is the basis for any line through the origin and two vectors are the basis for any plane through the origin. It is known that lines and planes through the origin (as well as $0$ and $\mathbb{R}^3$ itself) are the only subspaces in $\mathbb{R}^3$.

--------------------

Practice Problem: Any two bases of a subspace $S$ of $\mathbb{R}^n$ have the same number of elements (this number is called the dimension of $S$).