Bases and Dimension of Vector Spaces
Bases
Previously, I discussed span and linear independence. Essentially, the span of a list of vectors is the set of all possible linear combinations of those vectors, and a list of vectors is linearly independent if none of them can be expressed as a linear combination of the others.
Now I'll use these ideas to introduce one of the most important concepts in linear algebra:
Definition. A basis for a vector space $V$ is a linearly independent list of vectors which spans $V$.
This definition, combined with what we have already discussed, tells us three things:
- Every vector in $V$ can be expressed as a linear combination of basis vectors, since a basis must span $V$.
- This representation is unique, since the basis elements are linearly independent.
- $V$ is the direct sum of the spans of the basis vectors.
Stated more explictly, if $(e_1,\ldots,e_n)$ is a basis for a vector space $V$, then for every vector $v\in V$ there is a unique set of scalars $a_i\in\F$ for which
$$v=\sum_{i=1}^n a_ie_i.$$
Bases for vector spaces are similar to bases for topological spaces. The idea is that a basis is a small, easy to understand subset of vectors from which it is possible to extrapolate pretty much everything about the vector space as a whole.
Here are some examples and non-examples.
Example. The list $\big((1,0), (0,1)\big)$ is a basis for the vector space $\R^2$, since the list is linearly independent and for any vector $(x,y)\in\R^2$, we may write
$$(x,y) = x(1,0)+y(0,1).$$
Example. The list $\big((1,0), (1,1)\big)$ is also a basis for $\R^2$. To see that it is linearly independent, we must show that
$$a(1,0) + b(1,1) = (0,0) \tag{1}$$
only if $a=b=0$. Since in this vector space addition and scalar multiplication are done component-wise, equation $(1)$ reduces to the system of equations:
$$\begin{align}
a + b &= 0 \tag{2}\\
\phantom{a +} b &= 0. \tag{3}
\end{align}$$Equation $(2)$ implies that $a=-b$, from which equation $(3)$ implies that $a=b=0$, as desired.
To see that our list spans $\R^2$, we note that any vector $(x,y)\in\R^2$ can be written
$$(x,y) = (x-y)(1,0) + y(1,1).$$
Example. The list $\big((1,0),(-1,0)\big)$ is not a basis for $\R^2$ because it is linearly dependent and it does not span $\R^2$. To see that it is linearly dependent, note that
$$(1,0)+(-1,0)=(0,0).$$
That is, we have written the zero vector as a linear combination of vectors in the list with nonzero coefficients.
To see that it does not span $\R^2$, note that no vector in $\R^2$ with a nonzero second component can ever be written as a scalar multiple of these vectors, since both have a second component of zero.
Example. The list $\big((1,0),(0,1),(1,1)\big)$ is not a basis for $\R^2$ because it is linearly dependent. We can see this immediately from the linear dependence lemma, since it has length three and we have already exhibited a linearly dependent list of length two which spans $\R^2$.
Example. The list $\big(1,x,x^2,x^3)$ is a basis for $\P_3(\F)$, the vector space of polynomials over a field $\F$ with degree at most three. To justify this claim, note that this list is certainly linearly independent, and any polynomial of degree less than or equal three can be written
$$p(x)=a+b+cx^2+dx^3$$
for some choice of $a,b,c,d\in\F$.
The next theorem is fairly obvious, but without it we would be pretty much lost. Recall that a vector space is finite-dimensional if it is spanned by a finite list of vectors. For this next proof we will use this definition, as well the linear dependence lemma.
Theorem. Every finite-dimensional vector space has a basis.
Let $V$ denote a finite-dimensional vector space. Then $V$ is spanned by some finite list of vectors, not all zero, $(v_1,\ldots,v_n)$. If this list is linearly independent, then we are done. Otherwise, we can use the linear dependence lemma to remove a vector from this list and produce a new list of length $n-1$ which still spans $V$. We continue this process until we are left with a linearly independent list, which will take at most $n-1$ steps, since any list containing one nonzero vector is automatically linearly independent. This resulting list is, by definition, a basis for $V$.
This argument only works for finite-dimensional vector spaces, since it relies on the fact that we only have to apply the linear dependence lemma a finite number of times. Infinite-dimensional vector spaces, as I've mentioned before, are a lot grosser. It is possible to show that infinite-dimensional vector spaces are guaranteed to have bases if we accept the axiom of choice. Since most mathematicians much prefer to have bases for their vector spaces, this is just one more point in favor of accepting the axiom of choice. Luckily for us, we aren't currently interested in infinite-dimensional vector spaces and so we can simply ignore this icky business.
Dimension
Next comes a super important result which will finally settle the question I posed last time about how to define the dimension of a vector space. Its proof will employ the theorem I proved at the end of my last post, that the length of a list of spanning vectors is never shorter than any linearly independent list.
Theorem. All bases of a finite-dimensional vector space have the same length.
Proof. Let $V$ denote a finite dimensional vector space, and suppose $(e_1,\ldots,e_n)$ and $(f_1,\ldots,f_m)$ are both bases for $V$. Since $(e_1,\ldots,e_n)$ is linearly independent and $(f_1,\ldots,f_m)$ spans $V$, we have that $n\le m$. Similarly, since $(f_1,\ldots,f_m)$ is linearly independent and $(e_1,\ldots,e_n)$ spans $V$, we have that $m\le n$. It follows that $m=n$, as desired.
What we have really shown is that the length of a basis for a finite-dimensional vector space is an invariant of that space! And it's a particularly special invariant:
Definition. The dimension of a finite-dimensional vector space is the length of any basis for that space.
If the dimension of a vector space $V$ is $n$, we write
$$\dim V=n.$$
As a special case, recall that we defined $\span()=\set{0}$. That means that $\dim\set{0}=0$.
We've already shown that dimension is well-defined, since all bases for a vector space have the same length. But does this definition coincide with what we expect? For instance, we would certainly expect that $\dim\R^n=n$ for any positive integer $n$. And it turns out that this always the case, as we can see by the following definition.
Definition. Given a positive integer $n$, the standard basis for $\F^n$ is the list containing the vectors
$$\begin{eqnarray}
e_1 &=& (1,0,\ldots,0), \\
e_2 &=& (0,1,\ldots,0), \\
&\;\vdots& \\
e_n &=& (0,0,\ldots,1).
\end{eqnarray}$$That is, $e_i$ is the vector whose $i$th component is $1$ and every other component is zero.
It should be fairly obvious that for any $n$, the standard basis for $\F^n$ is, in fact, a basis. It is certainly linearly independent and it is easy to write any vector in $\F^n$ as a linear combination of basis vectors, implying it also spans $\F^n$. Since there are $n$ basis vectors in the standard basis, it follows that $\dim\F^n=n$, just like we would expect.
Some Useful Theorems
This first result tells use how to calculate the dimension of a sum of two subspaces. Recall that we previously showed that the intersection of two subspaces is itself a subspace.
Theorem. If $V_1$ and $V_2$ are subspaces of a finite-dimensional vector space, then
$$\dim(V_1+V_2) = \dim V_1 + \dim V_2 - \dim(V_1\cap V_2).$$
Proof. Since $V_1\cap V_2$ is a subspace of a finite-dimensional vector space, it is also finite-dimensional. Thus it has a basis, which we will denote $(e_1,\ldots,e_n)$.
This basis for $V_1\cap V_2$ is linearly independent, and thus we may extend it to a basis for $V_1$ by adding $m_1 = \dim V_1 - n$ new linearly independent vectors. That is, there is some basis $(e_1,\ldots,e_n,f_1,\ldots,f_{m_1})$ for $V_1$, and certainly $\dim V_1 = m_1+n$.
We may similarly extend $(e_1,\ldots,e_n)$ to a basis for $V_2$ by adding $m_2 = \dim V_2 - n$ new linearly independent vectors. That is, there is some basis $(e_1,\ldots,e_n,g_1,\ldots,g_{m_2})$ for $V_2$, and certainly $\dim V_2 = m_2+n$.
We argue that $(e_1,\ldots,e_n,f_1,\ldots,f_{m_1},g_1,\ldots,g_{m_2})$ is a basis for $V_1+V_2$. Certainly
$$V_1,V_2\subseteq\span(e_1,\ldots,e_n,f_1,\ldots,f_{m_1},g_1,\ldots,g_{m_2})$$
and thus
$$V_1+V_2=\span(e_1,\ldots,e_n,f_1,\ldots,f_{m_1},g_1,\ldots,g_{m_2}).$$
To see that this list is linearly independent, suppose that
$$\sum_{i=1}^n a_i e_i + \sum_{i=1}^{m_1} b_i f_i + \sum_{i=1}^{m_2} c_i g_i = 0 \tag{4}$$
for some scalars $\set{a_i}_{i=1}^n$, $\set{b_i}_{i=1}^{m_1}$ and $\set{c_i}_{i=1}^{m_2}$. We can rewrite $(4)$ as
$$\sum_{i=1}^{m_2} c_i g_i = -\sum_{i=1}^n a_i e_i - \sum_{i=1}^{m_1} b_i f_i,$$
from which we see that $\sum_{i=1}^{m_2} c_i g_i\in V_1\cap V_2$. Since $(e_1,\ldots,e_n)$ is a basis for $V_1\cap V_2$, it follows that we may write it uniquely as a linear combination of basis vectors,
$$\sum_{i=1}^{m_2} c_i g_i = \sum_{i=1}^n d_i e_i, \tag{5}$$
for some scalars ${d_i}_{i=1}^n$. But $(e_1,\ldots,e_n,g_1,\ldots,g_{m_2})$ is linearly independent, so it follows from equation $(5)$ that $c_i=0$ for all $i$. This means we may rewrite equation $(4)$ as
$$\sum_{i=1}^n a_i e_i + \sum_{i=1}^{m_1} b_i f_i = 0.$$
Since $(e_1,\ldots,e_n,f_1,\ldots,f_{m_1})$ is linearly independent, it follows that $a_i=0$ for all $1\le i\le n$ and $b_i=0$ for all $1\le i\le m_1$. Since all coefficients in equation $(4)$ have been shown to be zero, it follows that $(e_1,\ldots,e_n,f_1,\ldots,f_{m_1},g_1,\ldots,g_{m_2})$ is a basis for $V_1+V_2$.
It follows then that
$$\begin{align}
\dim(V_1+V_2) &= n + m_1 + m_2 \\
&= (n+m_1) + (n+m_2) - n \\
&= \dim V_1 + \dim V_2 - \dim(V_1\cap V_2),
\end{align}$$completing the proof.
If you think that proof was gross, try doing it for sums of three or more subspaces. Or don't, because as far as I know there is no general formula for such a thing.
The next result ties together our work from last post regarding direct sums, and follows immediately from the theorem we just proved. Recall that if a sum of two subspaces is direct, their intersection is trivial.
Theorem. If $U_1,\ldots,U_n$ are subspaces of a finite-dimensional vector space $V$ for which
$$V=\bigoplus_{i=1}^n U_i,$$
then
$$\dim V = \sum_{i=1}^n \dim U_i.$$
Proof. We first rewrite the sum as
$$V = (\cdots((U_1\oplus U_2) \oplus U_3) \oplus \cdots \oplus U_n).$$
We work outward, first considering the subspace $W_2 = U_1\oplus U_2$ and then the subspace $W_3 = W_2 \oplus U_3$, then the subspace $W_4 = W_3 \oplus U_4$, etc. This takes $n-1$ iterations, but eventually we reach $W_n = V$.
But $U_1\cap U_2=\set{0}$ since the sum is direct, and so by the previous theorem we see that
$$\begin{align}
\dim W_1 &= \dim (U_1 + U_2) \\
&= \dim U_1 + \dim U_2 - \dim (U_1\cap U_2) \\
&= \dim U_1 + \dim U_2 - \dim\set{0} \\
&= \dim U_1 + \dim U_2 - 0 \\
&= \dim U_1 + \dim U_2.
\end{align}$$And in general, since $W_j = W_{j-1} \oplus U_j$,
$$\begin{align}
\dim W_j &= \dim (W_{j-1} + U_j) \\[1em]
&= \dim W_{j-1} + \dim U_j \\
&= \sum_{i=1}^{j-1} \dim U_i + \dim U_j.
\end{align}$$Setting $j=n$, the result follows.
Next time I will introduce linear maps, which are (besides vector spaces themselves) the primary objects of study in linear algebra.