Chapter 10Vector Spaces (Linear Spaces)
In Chapter 8 we studied matrices and determinants, and in Chapter 9 we studied methods for solving systems of linear equations (the adjugate matrix, the inverse matrix, rank, and degrees of freedom). The vectors we dealt with there were always “numbers arranged in a column,” that is, elements of $\R^n$. In this chapter we change our viewpoint drastically. In general, a “set in which, as with vectors, we can add elements and multiply them by scalars” is called a vector space (or linear space), and we build an abstract framework in which it does not matter whether the elements are tuples of numbers. The concepts of “independence,” “basis,” “dimension,” and “subspace” obtained in this way become powerful tools that can be reused not only inside $\R^n$ but also for sets of polynomials, sets of functions, sets of matrices, and so on—for virtually anything “that allows addition and scalar multiplication.”
There are two central questions in this chapter. First: “Do the given vectors carry independent information without redundancy, or can some of them be written as combinations of the others (that is, are they dependent)?”—this is the idea of linear independence and linear dependence. Second: “How many vectors are needed, at minimum, to describe a given vector space with neither too many nor too few?”—this is basis and dimension. We then call a small vector space that fits entirely inside a vector space a subspace, and we go on to treat the intersection and sum of two subspaces, all the way to the dimension theorem. All of these form the foundation for “linear maps,” which we study in Chapter 11, and for “eigenvalues and diagonalization,” which we study in Chapter 12. This is the most abstract chapter of linear algebra—and also the one with the widest range of applications.
- Definition of a vector space (linear space): a set closed under addition and scalar multiplication, and the two sets of axioms, the properties (I) of addition and the properties (II) of scalar multiplication
- Definitions of a linear combination and a linear relation (relation of linear dependence)
- Definitions of linear independence and linear dependence, and a test using determinants and rank: $a_1,\ldots,a_n$ are linearly independent $\iff$ $\rank[a_1\,\cdots\,a_n]=n$
- Definition of a basis (linearly independent and spanning the whole space), the dimension $\dim W=n$, and the two faces of dimension, “the maximum number of linearly independent vectors = the minimum number of vectors that span”
- Definition of a subspace (contains $0$ and is closed under addition and scalar multiplication), and the fact that this definition can be simplified to two conditions
- The subspace $\langle a_1,\ldots,a_r\rangle$ spanned by given vectors, and the solution space of a homogeneous system of linear equations, $\dim W=n-\rank A$
- The intersection $W_1\cap W_2$, the sum $W_1+W_2$, and the direct sum $W_1\oplus W_2$ of subspaces, and the dimension theorem for subspaces, $\dim W_1+\dim W_2=\dim(W_1+W_2)+\dim(W_1\cap W_2)$
Source notes: Yasuhide Mochizuki, Mathematics Notes: Linear Algebra, pp. 15–24.
10.1 Definition and Axioms of Vector Spaces
The “vectors in the plane” that you learned about in high school mathematics are arrows, and we can add them (by the parallelogram law) and multiply them by scalars (operations that stretch or shrink an arrow, or reverse its direction). In this case, the sum of two plane vectors, or a real multiple of a vector, again lies inside the set of “vectors in the plane”; it never jumps outside the set. The vector space that we are about to define is obtained by extracting only this property—“adding and taking scalar multiples never leads out of the original set”—and abstracting it without assuming in any way that the elements are arrows.
Definition 10.1: Vector space (linear space)
Suppose that for any elements $a,b$ of a set $V$ (an element is also called a “gen” in Japanese), a sum $a+b$ and a scalar multiple $ka$ ($k$ is a real number) are defined, and that they are always elements of $V$. If, furthermore, this sum and scalar multiple satisfy properties (I) and (II) below, then $V$ is called a vector space (or linear space) over the set $\R$ of all real numbers.
(I) Properties of the sum
$$ \begin{array}{ll} (\mathrm{i})\ \ (a+b)+c=a+(b+c) & \text{(associative law)}\\[2pt] (\mathrm{ii})\ \ a+b=b+a & \text{(commutative law)}\\[2pt] (\mathrm{iii})\ \ a+0=0+a=a\ \text{holds for some}\ 0\in V\ \text{(and this element is unique)} & \text{(existence of the zero vector)}\\[2pt] (\mathrm{iv})\ \ \text{for every}\ a\in V\ \text{the equation}\ a+x=x+a=0\ \text{has a solution}\ x\in V\ \text{(and the solution is unique)} & \text{(existence of the inverse vector)} \end{array} $$(II) Properties of scalar multiplication
$$ \begin{array}{ll} (\mathrm{i})\ \ 1\cdot a=a & (\mathrm{iii})\ \ (k+l)a=ka+la\\[2pt] (\mathrm{ii})\ \ k(a+b)=ka+kb & (\mathrm{iv})\ \ (kl)a=k(la) \end{array} $$We call the $0$ in (I)(iii) the zero vector, and the $x$ in (I)(iv) the inverse vector of $a$, which we write as $-a$. Thanks to the commutative law in (I)(ii), conditions (iii) and (iv) can each be written as a single equation saying that “the result is the same whether we add from the right or from the left.” Of the properties in (II), (iii) and (iv) are the “distributive law and associative law for scalars”: they say that the addition and multiplication inside the parentheses may be carried out first on the scalar side. The property $1\cdot a=a$ in (II)(i) looks obvious at first sight, but unless it is stated explicitly as an axiom, the definition would no longer guarantee, for example, what kind of element $0\cdot a$ is (in fact, $0\cdot a=0$ can be derived from the properties in (II) alone, but the proof requires (i)).
Intuition: The essence of vector spaces
Nothing in this definition tells us what the elements of $V$ concretely are. As long as the definition of a vector space (a sum and a scalar multiple are defined, and they satisfy (I) and (II)) is satisfied, its elements need not be numerical vectors in $\R^n$; they may be matrices, or “functions” such as polynomials or continuous functions. For example, the set of all $m\times n$ matrices is a vector space under the sum of matrices and multiplication of matrices by real numbers (the zero vector is the zero matrix, and the inverse vector is the matrix multiplied by $-1$). As soon as we can verify the property that “we can add and take scalar multiples, and the objects behave just like ordinary numbers,” we may treat anything whatsoever as an element of a vector space. In Example 10.1, we check that a set of polynomials really is a vector space.
From this chapter onward, unless stated otherwise, our main stage is $V=\R^n$ (the set of numerical vectors consisting of $n$ real numbers arranged in a column), but please remember that whenever the words “vector space” appear, we can always return to this general definition. Figure 10.1 shows how the sum and scalar multiplication look in the most familiar vector space, $\R^2$.
(A note on notation: In this chapter we do not put arrows or boldface on the letters $a,b,x,\ldots$ that denote elements of a vector space. In Chapter 8 we denoted column vectors by arrows, $\vec x$, and in Chapter 9 by boldface, $\bm x$; from this chapter on, however, we deliberately use undecorated letters in order to emphasize the abstractness expressed by “the elements need not be numerical vectors (they may be polynomials, matrices, or functions).” In Chapters 11 and 12, where we again confine our discussion to concrete transformations of $\R^n,\R^m$, we return to the boldface notation $\bm x$.)
10.1.1 Linear combinations and linear relations
The most basic way of combining elements of a vector space is the linear combination.
Definition 10.2: Linear combination
Given elements $a_1,a_2,a_3,\ldots,a_n$ of a vector space $V$ and real numbers $c_1,c_2,c_3,\ldots,c_n$, the expression $$ c_1a_1+c_2a_2+c_3a_3+\cdots+c_na_n $$ is called a linear combination of the elements $a_1,a_2,\ldots,a_n$ of $V$.
A linear combination is what we obtain by “stretching, shrinking, or reversing each of $a_1,\ldots,a_n$ by whatever factors $c_1,\ldots,c_n$ we like, and then adding everything up.” For example, in $\R^2$, if $a_1=(1,0)$ and $a_2=(0,1)$, then every $(x,y)\in\R^2$ can be expressed as the linear combination $x\,a_1+y\,a_2$. Next we consider the case in which a linear combination is exactly $0$ (the zero vector).
Definition 10.3: Linear relation
A relation of the form $$ c_1a_1+c_2a_2+\cdots+c_na_n=0 \qquad (c_i\in\R,\ i=1,2,\ldots,n) $$ among elements $a_1,a_2,a_3,\ldots,a_n$ of a vector space $V$ is called a linear relation (or relation of linear dependence) of $a_1,a_2,\ldots,a_n$.
For any $a_1,\ldots,a_n$, this relation always holds for at least one choice of coefficients—just take all the coefficients to be $c_1=c_2=\cdots=c_n=0$ (we call this the trivial linear relation). What we really need to ask is: “Can this relation hold even when the coefficients are not all $0$?” This is the theme of the next section, linear independence and linear dependence.
Example 10.1: Verifying that a set of polynomials is a vector space
Consider the set $P_2=\{a_0+a_1x+a_2x^2 \mid a_0,a_1,a_2\in\R\}$ of all polynomials of degree at most 2 with real coefficients. Verify that $P_2$ is a vector space (under addition of polynomials and multiplication of polynomials by scalars).
Solution. Let $p(x)=a_0+a_1x+a_2x^2$ and $q(x)=b_0+b_1x+b_2x^2$ be any two elements of $P_2$. Computing the sum, we get $$ p(x)+q(x)=(a_0+b_0)+(a_1+b_1)x+(a_2+b_2)x^2 $$ The coefficients $a_0+b_0,\ a_1+b_1,\ a_2+b_2$ are all sums of real numbers and hence real, and the degree in $x$ is still at most 2. Hence $p(x)+q(x)\in P_2$, which means that the set is closed under addition. Also, for any real number $k$ we have $$ k\,p(x)=(ka_0)+(ka_1)x+(ka_2)x^2 $$ and since the coefficients are all real and the degree is at most 2, $k\,p(x)\in P_2$, so the set is closed under scalar multiplication as well. The associative, commutative, and distributive laws are based on the addition and multiplication of the real-number coefficients of the polynomials, so they hold directly by the laws of operations for real numbers. The zero vector is the zero polynomial $0+0\cdot x+0\cdot x^2$, and the inverse vector of $p(x)$ is $-p(x)=(-a_0)+(-a_1)x+(-a_2)x^2$. Therefore all the properties in (I) and (II) are satisfied, and $P_2$ is a vector space. (In this way, the “Intuition” box after Definition 10.1, which says that the elements of a vector space are not limited to numerical vectors, finds a concrete instance here.)
10.2 Linear Independence and Linear Dependence
We now give a formal name to the question left at the end of the previous section—“does the linear relation $c_1a_1+\cdots+c_na_n=0$ hold only when all the coefficients are $0$ (the trivial case), or does it also hold for a set of coefficients that are not all $0$?” (In the margin of the original notes there is a remark added later by the author himself, “The order is not desirable. Vector space → basis and dimension would be better,” that is, a suggestion that it would be better to place basis and dimension immediately after the definition of a vector space. However, the definition of a basis (Definition 10.5(i)) uses the very words “linearly independent,” so unless independence and dependence are defined first, the definition of a basis itself cannot be written. In this book, therefore, we adopt as is the order actually written in the body of the notes—independence and dependence first, basis and dimension afterward.)
Definition 10.4: Linear independence and linear dependence
Consider elements $a_1,a_2,\ldots,a_n$ of a vector space $V$ and their linear relation $$ c_1a_1+c_2a_2+\cdots+c_na_n=0 \qquad\cdots① \qquad (c_i\in\R) $$ Exactly one of the following holds.
(i) There is only one way to express it, that is, ① holds only when $c_1=c_2=\cdots=c_n=0$ $\Longrightarrow$ $a_1,a_2,\ldots,a_n$ are said to be linearly independent of one another.
(ii) There are several ways to express it, that is, ① holds even when at least one of $c_1,c_2,\ldots,c_n$ is not $0$ $\Longrightarrow$ $a_1,a_2,\ldots,a_n$ are said to be linearly dependent.
In words, linear independence is the state in which “no single vector can be built from a linear combination of the others (there is no redundant information),” and linear dependence is the state in which “at least one vector can be written as a linear combination of the other vectors (the information is duplicated).” We check concretely that this rephrasing is correct after Illustration 10.2. First, let us see how to decide this in practice, using an example in $\R^3$.
Illustration 10.1: Testing $a_1,a_2,a_3$ for linear independence
Determine whether the vectors $$ a_1=\begin{bmatrix}1\\2\\-1\end{bmatrix},\qquad a_2=\begin{bmatrix}2\\3\\1\end{bmatrix},\qquad a_3=\begin{bmatrix}1\\3\\4\end{bmatrix} $$ are linearly independent or linearly dependent.
Solution. We form the linear relation of $a_1,a_2,a_3$. $$ c_1a_1+c_2a_2+c_3a_3=0 $$ This can be rewritten as the product of the matrix whose columns are the three vectors and the vector whose components are the coefficients arranged in a column (we are using in reverse the viewpoint learned in Chapter 8 that “the product of a matrix and a vector is a linear combination of the column vectors of the matrix”). $$ [a_1\ a_2\ a_3]\begin{bmatrix}c_1\\c_2\\c_3\end{bmatrix} =\begin{bmatrix}1&2&1\\2&3&3\\-1&1&4\end{bmatrix}\begin{bmatrix}c_1\\c_2\\c_3\end{bmatrix} =\begin{bmatrix}0\\0\\0\end{bmatrix} \qquad\cdots② $$ Let $[a_1\ a_2\ a_3]=A$. Computing the determinant by Sarrus's rule gives $$ |A|=1\cdot3\cdot4+2\cdot3\cdot(-1)+1\cdot2\cdot1-1\cdot3\cdot(-1)-1\cdot3\cdot1-2\cdot2\cdot4=12-6+2+3-3-16=-8 $$ so $|A|\neq0$. Hence, by Theorem 9.5 of Chapter 9 (conditions for invertibility of a matrix), “$A$ is invertible ($|A|\neq0$) $\iff$ $\rank A=n$ $\iff$ its row echelon matrix is the identity matrix,” $A$ is invertible and has an inverse matrix $A^{-1}$. Multiplying both sides of ② on the left by $A^{-1}$ gives $$ \begin{bmatrix}c_1\\c_2\\c_3\end{bmatrix} =A^{-1}\begin{bmatrix}0\\0\\0\end{bmatrix} =\begin{bmatrix}0\\0\\0\end{bmatrix} $$ (the product of $A^{-1}$ and the zero vector is always the zero vector). Hence ② is satisfied only by $c_1=c_2=c_3=0$, so by Definition 10.4(i), $a_1,a_2,a_3$ are linearly independent. (This also means that the rephrasing “no single vector can be written as a linear combination of the other two” holds. Suppose, for the sake of argument, that $a_1$ could be written as $a_1=k_2a_2+k_3a_3$ ($k_2,k_3\in\R$). Moving terms to one side gives $1\cdot a_1+(-k_2)a_2+(-k_3)a_3=0$, which is a linear relation whose coefficients ($1,-k_2,-k_3$) are not all $0$. But we have just found that the only coefficients satisfying ② are $c_1=c_2=c_3=0$, so this is a contradiction. Hence $a_1$ cannot be written as a linear combination of $a_2,a_3$. The same holds for $a_2,a_3$.)
Figure 10.2 shows $a_1,a_2,a_3$ as arrows drawn from the origin. However we combine two of the three arrows, we cannot produce the remaining one, and the arrows spread out in $\R^3$ in directions that “do not lie in a single plane”—this is the geometric meaning of linear independence.
Next, in the same $\R^3$, we examine another set of three vectors.
Illustration 10.2: Linear dependence of $b_1,b_2,b_3$ and its geometric meaning
Determine whether the vectors $$ b_1=\begin{bmatrix}1\\2\\4\end{bmatrix},\qquad b_2=\begin{bmatrix}2\\-1\\3\end{bmatrix},\qquad b_3=\begin{bmatrix}-1\\3\\1\end{bmatrix} $$ are linearly independent or linearly dependent.
Solution. As in Illustration 10.1, we rewrite the linear relation $C_1b_1+C_2b_2+C_3b_3=0$ in the form of a matrix–vector product. $$ [b_1\ b_2\ b_3]\begin{bmatrix}C_1\\C_2\\C_3\end{bmatrix} =\begin{bmatrix}1&2&-1\\2&-1&3\\4&3&1\end{bmatrix}\begin{bmatrix}C_1\\C_2\\C_3\end{bmatrix} =\begin{bmatrix}0\\0\\0\end{bmatrix} \qquad\cdots③ $$ Letting $[b_1\ b_2\ b_3]=B$ and computing the determinant, we get $$ |B|=1\cdot(-1)\cdot1+2\cdot3\cdot4+(-1)\cdot2\cdot3-(-1)\cdot(-1)\cdot4-2\cdot2\cdot1-1\cdot3\cdot3=-1+24-6-4-4-9=0 $$ so $|B|=0$. Hence $B$ has no inverse matrix, so ③ has solutions $\begin{bmatrix}C_1&C_2&C_3\end{bmatrix}^{\mathsf T}$ other than $\begin{bmatrix}0&0&0\end{bmatrix}^{\mathsf T}$ as well (since $B^{-1}$ does not exist, the procedure of Illustration 10.1, in which we multiply both sides by $B^{-1}$ to derive $C_i=0$, cannot be used). Therefore, by Definition 10.4(ii), $b_1,b_2,b_3$ are linearly dependent.
To see why we call this “dependent,” let us look closely at $b_1,b_2,b_3$ themselves. $$ b_2+b_3=\begin{bmatrix}2\\-1\\3\end{bmatrix}+\begin{bmatrix}-1\\3\\1\end{bmatrix}=\begin{bmatrix}1\\2\\4\end{bmatrix}=b_1 $$ That is, $b_1=b_2+b_3$ holds. $b_1$ can be written as a linear combination of $b_2,b_3$ (in the simple form in which both coefficients are $1$)—$b_1$ is dependent on $b_2,b_3$. (This is the nontrivial solution that corresponds to setting $C_1=1,C_2=-1,C_3=-1$ in ③.)
The fact that $b_1=b_2+b_3$ holds means that all three of $b_1,b_2,b_3$ lie in the plane spanned by the two vectors $b_2$ and $b_3$ alone. Figure 10.3 shows this plane and the three arrows, and Figure 10.4 shows the parallelogram in that plane viewed head-on (with rectangular coordinates re-chosen within the plane). The diagonal of the parallelogram is $b_1$—this is exactly the fact seen in Figure 10.1 that “the sum of vectors is the diagonal of a parallelogram.”
Example 10.7: Reading independence and dependence from the figures alone
Compare Figure 10.2 ($a_1,a_2,a_3$) and Figure 10.3 ($b_1,b_2,b_3$) without using the numerical values of the components or computations by Sarrus's rule. Which set can be judged linearly independent, and which linearly dependent? State the reason, based on the figures. Furthermore, from the shape of the parallelogram in Figure 10.4, read off one nontrivial linear relation for the dependent set (without computing any components).
Solution. In Figure 10.2, the three arrows $a_1,a_2,a_3$ appear to spread out through the whole space, in such a way that, whichever two of them we choose, the remaining one does not lie in the same plane as those two. That the three do not appear to fit into any single plane means that none of them can be written as a linear combination of the other two (= a point in the plane), so from the figure alone we can judge these three to be linearly independent. On the other hand, in Figure 10.3, $b_1$ (red) is drawn lying exactly within the plane spanned by $b_2,b_3$ (the two bluish arrows). That the three lie in the same plane means that $b_1$ can be written as a linear combination of $b_2,b_3$, which span that plane, so we can judge these three to be linearly dependent.
Figure 10.4 shows exactly the plane of Figure 10.3 viewed head-on, with a parallelogram having $b_2,b_3$ as two of its sides drawn in it. As we confirmed in Figure 10.1, a diagonal of a parallelogram represents “the sum of the vectors of the two sides.” Since this diagonal is $b_1$, we can read off the following just by looking at the figure: $$ b_1=b_2+b_3 $$ Moving the terms to one side gives $1\cdot b_1+(-1)\cdot b_2+(-1)\cdot b_3=0$, and this is a nontrivial linear relation, in which the coefficients are not all $0$. (Checking with components, we get $b_2+b_3=(2,-1,3)+(-1,3,1)=(1,2,4)=b_1$, which agrees with the relation read off from the figure.)
The procedure of Illustrations 10.1 and 10.2—compute the determinant, and judge the vectors independent if it is not $0$ and dependent if it is $0$—can be used only for square matrices (the case where the number of vectors equals the number of components of each vector). So we now state, in terms of the rank from Chapter 9, a criterion that can also be used in the general case where the number of vectors and the number of components differ.
Theorem 10.1: Relation between linear independence and rank
For elements $a_1,a_2,\ldots,a_n$ of $\R^n$, $$ [a_1\ a_2\ \cdots\ a_n]\begin{bmatrix}c_1\\c_2\\\vdots\\c_n\end{bmatrix}=0\ \text{has the trivial solution}\ (c_1=\cdots=c_n=0)\ \text{and no other} \iff \rank[a_1\ a_2\ \cdots\ a_n]=n $$ holds. Therefore, $$ a_1,a_2,\ldots,a_n\ \text{are linearly independent}\iff \rank[a_1\ \cdots\ a_n]=n, $$ and otherwise (that is, if $\rank[a_1\ \cdots\ a_n]\lt n$) they are linearly dependent.
Proof (review of Chapter 9)
$A=[a_1\ \cdots\ a_n]$ is an $n\times n$ square matrix. As we learned in Chapter 9, the solution space of the homogeneous system of linear equations $Ax=0$ ($n$ unknowns) has $n-\rank A$ degrees of freedom. The degrees of freedom are $0$, that is, the only solution is the trivial solution $x=0$, exactly when $\rank A=n$ (and only then). This is directly the condition that “the coefficients of a linear relation can only be all $0$,” which is the same as “linearly independent.” (Even when $a_1,\ldots,a_n$ are elements of $\R^m$ and the number of vectors $n$ differs from the number of components $m$, the same argument holds; $A$ simply becomes an $m\times n$ matrix.)
In Illustration 10.1 we had $\rank A=3=(\text{number of vectors})$, so the vectors were independent; in Illustration 10.2 we had $\rank B=2\lt3$, so they were dependent—Theorem 10.1 is a more general criterion that encompasses the determinant test (for the square case). In the next example, we use this theorem to confirm the important fact that “if the number of vectors exceeds the dimension, they are necessarily dependent.”
Example 10.2: Any four vectors in $\R^3$ are linearly dependent
The vectors $$ d_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\quad d_2=\begin{bmatrix}0\\1\\1\end{bmatrix},\quad d_3=\begin{bmatrix}1\\1\\2\end{bmatrix},\quad d_4=\begin{bmatrix}2\\-1\\1\end{bmatrix} $$ are elements of $\R^3$. Determine whether they are linearly independent or linearly dependent, and if they are dependent, find one explicit linear relation.
Solution. $D=[d_1\ d_2\ d_3\ d_4]$ is a $3\times4$ matrix. Applying elementary row operations to $D$ (we omit the computation; it suffices to count the steps of the row echelon matrix), we obtain $\rank D=2$. Applying the number-of-vectors version of Theorem 10.1 (the case $a_1,\ldots,a_n\in\R^m$), we have $\rank D=2\lt4=(\text{number of vectors})$, so $d_1,d_2,d_3,d_4$ are linearly dependent.
Indeed, comparing the components, we find that $$ d_1+d_2=\begin{bmatrix}1\\0\\1\end{bmatrix}+\begin{bmatrix}0\\1\\1\end{bmatrix}=\begin{bmatrix}1\\1\\2\end{bmatrix}=d_3 $$ holds. Hence $d_1+d_2-d_3+0\cdot d_4=0$ is a linear relation whose coefficients are not all $0$.
As this example shows, in $\R^3$ it is fundamentally impossible, no matter how hard we try, to make four or more vectors linearly independent. This is because the rank of a $3\times4$ matrix, unlike that of a $4\times4$ matrix, cannot exceed the number of rows ($=3$). (The rank can never exceed the number of rows or the number of columns; it is always at most both.) In general, “in an $n$-dimensional space, at most $n$ vectors can be linearly independent”—this fact is the very meaning of “dimension” in the next section.
10.3 Basis and Dimension
In high school mathematics, when we represent a point of $\R^2$ by coordinates $(x,y)$, we are in fact unconsciously using two reference vectors $e_1=(1,0)$ and $e_2=(0,1)$ (called the standard basis) and expressing the point as the linear combination $(x,y)=x\,e_1+y\,e_2$. For $\R^3$ we need three vectors $e_1,e_2,e_3$, and for general $\R^n$ we need $n$ of them. The naive sense of “how many coordinate axes are needed” can be made precise in terms of linear independence, and the result is the basis and the dimension that we are about to study. Figure 10.5 shows the standard bases of $\R^2,\R^3$.
We now give a formal definition of these two conditions, “independent and spanning the whole space,” for a general vector space.
Definition 10.5: Basis of a vector space
If elements $\{a_1,a_2,\ldots,a_n\}$ of a vector space $W$ satisfy the following two properties, they are called a basis of $W$.
(i) $a_1,a_2,a_3,\ldots,a_n$ are linearly independent.
(ii) Every element $x$ of $W$ can be written as a linear combination of $a_1,a_2,\ldots,a_n$ (a sum of scalar multiples of them).
Definition 10.6: Dimension of a vector space
The number $n$ of elements that make up a basis of a vector space $W$ (the number of basis vectors) is called the dimension of $W$ and is written $\dim W=n$.
For example, by Figure 10.5 we have $\dim\R^2=2$ and $\dim\R^n=n$. Moreover, in Example 10.2 of the previous section we saw that “in $\R^3$, four or more vectors are always linearly dependent.” This is a concrete instance of the general fact that a set of vectors whose number exceeds the dimension 3 cannot be independent. In general, more vectors than the dimension are always linearly dependent, and conversely fewer vectors than the dimension can never span the whole vector space (spanning will be treated again in Definition 10.8). The following theorem summarizes these two facts.
Theorem 10.2: The meaning of $\dim W$
Let $W$ be a vector space. Then $\dim W$ is equal to each of the following two numbers.
(i) The maximum number of linearly independent vectors contained in $W$
(ii) The minimum number of vectors that span $W$ (that is, whose linear combinations produce all of $W$)
Idea of the proof
Let $a_1,\ldots,a_n$ ($n=\dim W$) be a basis of $W$. For (i): since a basis consists of $n$ independent vectors, the “maximum number of independent vectors” is at least $n$. Conversely, if we take $n+1$ vectors $x_1,\ldots,x_{n+1}$ from $W$, each $x_i$ can be written as a linear combination of the basis, $x_i=\sum_{j=1}^n c_{ij}a_j$. The matrix formed by arranging the coefficients $c_{ij}$ is an $n\times(n+1)$ matrix, so its rank is at most $n$. This means (by the same reasoning as in Example 10.2) that there exists a nontrivial linear relation among $x_1,\ldots,x_{n+1}$, so these $n+1$ vectors cannot be independent. Hence the “maximum number of independent vectors” is exactly $n$. For (ii): the $n$ basis vectors already span all of $W$ by Definition 10.5(ii), so the “minimum number of spanning vectors” is at most $n$. Conversely, suppose that $n-1$ or fewer vectors could span all of $W$ (which is $n$-dimensional). Then the coefficient matrix expressing each of the $n$ basis vectors as a linear combination of those vectors would be an $(n-1)\times n$ matrix, and its rank would be at most $n-1$; this in turn would make the $n$ basis vectors themselves not independent, a contradiction. Hence the “minimum number of spanning vectors” is also exactly $n$.
Another basic fact about dimension, concerning inclusion relations, is the following theorem.
Theorem 10.3: A theorem on dimension
If vector spaces $W_1,W_2$ satisfy $W_1\subset W_2$ ($W_1$ is a subset of $W_2$), then
(I) $\dim W_1\le\dim W_2$
(II) Moreover, if $\dim W_1=\dim W_2$, then $W_1=W_2$
Proof
(I) Let $a_1,\ldots,a_m$ ($m=\dim W_1$) be a basis of $W_1$. These are $m$ independent vectors, and since $W_1\subset W_2$ they are at the same time elements of $W_2$. By Theorem 10.2(i), the maximum number of independent vectors contained in $W_2$ is $\dim W_2$, so $m\le\dim W_2$, that is, $\dim W_1\le\dim W_2$.
(II) Suppose $\dim W_1=\dim W_2=n$. As in the argument for (I), a basis $a_1,\ldots,a_n$ of $W_1$ consists of $n$ independent vectors lying in $W_2$. If $W_1\neq W_2$, there would exist an element $x$ of $W_2$ that cannot be written as a linear combination of $a_1,\ldots,a_n$. Then $a_1,\ldots,a_n,x$ would be $n+1$ independent vectors in $W_2$, but this contradicts Theorem 10.2(i) (the maximum number of independent vectors in $W_2$ is $\dim W_2=n$). Hence we must have $W_1=W_2$.
In the next example we actually work out, by hand, the dimension and a basis of subspaces of $\R^4$ given by conditions (the formal definition of “subspace” is given in Section 10.4, but here you may read on with the intuitive understanding of “the set of all vectors satisfying the conditions”).
Illustration 10.3: Dimension and bases of subspaces of $\R^4$
Find the dimension and a basis of each of the following subspaces of $\R^4$.
(i) $\displaystyle W=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ x+y+z+w=0\right\}$
(ii) $\displaystyle W=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ \begin{aligned}x+y-z+w&=0\\-2x-y\phantom{-z}+w&=0\\3x+y+z-3w&=0\end{aligned}\right\}$
Solution. (i) Solving the condition $x+y+z+w=0$ for $x$ gives $x=-y-z-w$. Since $y,z,w$ are variables that can be chosen freely (they are not constrained), an element of $W$ can be written as $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix} =\begin{bmatrix}-y-z-w\\y\\z\\w\end{bmatrix} =y\begin{bmatrix}-1\\1\\0\\0\end{bmatrix}+z\begin{bmatrix}-1\\0\\1\\0\end{bmatrix}+w\begin{bmatrix}-1\\0\\0\\1\end{bmatrix} $$ that is, as a linear combination of three vectors (with $y,z,w$ as the coefficients). These three vectors are linearly independent of one another (for example, from the combination of the first component and the second, third, and fourth components, looking at the positions of the $1$s, each of which appears in only one of the vectors, shows that all the coefficients of a linear relation must be $0$). Hence these three vectors form a basis of $W$, and $$ \dim W=4-1=3,\qquad \text{basis }\begin{bmatrix}-1\\1\\0\\0\end{bmatrix},\begin{bmatrix}-1\\0\\1\\0\end{bmatrix},\begin{bmatrix}-1\\0\\0\\1\end{bmatrix} $$ (Since there is only one conditional equation, $1$ of the $4$ variables is dependent and the remaining $4-1=3$ can move freely—this is why the dimension is $3$.)
(ii) We collect the coefficients of the three conditional equations into a matrix and reduce it to a row echelon matrix by elementary row operations (Chapter 9). $$ \begin{bmatrix}1&1&-1&1\\-2&-1&0&1\\3&1&1&-3\end{bmatrix} \xrightarrow[R_3\to R_3-3R_1]{R_2\to R_2+2R_1} \begin{bmatrix}1&1&-1&1\\0&1&-2&3\\0&-2&4&-6\end{bmatrix} \xrightarrow{R_3\to R_3+2R_2} \begin{bmatrix}1&1&-1&1\\0&1&-2&3\\0&0&0&0\end{bmatrix} \xrightarrow{R_1\to R_1-R_2} \begin{bmatrix}1&0&1&-2\\0&1&-2&3\\0&0&0&0\end{bmatrix} $$ (In the first step, we added $2$ times $R_1$ to $R_2$ and $-3$ times $R_1$ to $R_3$, eliminating the entries $2,3$ in the first column. In the second step, we added $2$ times $R_2$ to $R_3$ to eliminate the $-2$ in the second column. In the third step, we subtracted $R_2$ from $R_1$ to eliminate the $1$ in the second column, tidying up so that the leading entry of each step is a $1$ and nothing else in its column is nonzero.) Since the last matrix has two rows that are not $0$, $\rank=2$, and $$ \dim W=4-\rank=4-2=2 $$ From the final form, the original system of equations is equivalent to $$ \begin{cases}x\phantom{+y}+z-2w=0\\ \phantom{x+}y-2z+3w=0\end{cases} $$ Taking $z,w$ as free variables and solving, we get $x=-z+2w$, $y=2z-3w$, so $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix}-z+2w\\2z-3w\\z\\w\end{bmatrix}=z\begin{bmatrix}-1\\2\\1\\0\end{bmatrix}+w\begin{bmatrix}2\\-3\\0\\1\end{bmatrix} $$ and a basis is $\begin{bmatrix}-1\\2\\1\\0\end{bmatrix},\begin{bmatrix}2\\-3\\0\\1\end{bmatrix}$.
A basis is not determined in only one way for a given vector space—indeed, $\R^2$ has countless bases other than the standard basis $e_1,e_2$. In the next example we work through the computation of expressing the same vector in different bases (change of basis).
Example 10.3: Expressing a vector in different bases
The vector $v=(5,3)$ of $\R^2$ can be written in the standard basis as $v=5e_1+3e_2$. Now take $f_1=(1,1)$, $f_2=(1,-1)$ as a basis (after also confirming that $f_1,f_2$ really are a basis), and find $c_1,c_2$ satisfying $v=c_1f_1+c_2f_2$.
Solution. First we confirm that $f_1,f_2$ form a basis. Setting $F=[f_1\ f_2]=\begin{bmatrix}1&1\\1&-1\end{bmatrix}$, we have $\det F=1\cdot(-1)-1\cdot1=-2\neq0$, so by Theorem 10.1, $f_1,f_2$ are linearly independent. Now $\R^2$ is two-dimensional, and two independent vectors automatically form a basis (stated as the converse of Theorem 10.2(ii): $\dim\R^2=2$ independent vectors always span all of $\R^2$). Hence $f_1,f_2$ form a basis of $\R^2$.
Writing $v=c_1f_1+c_2f_2$ in components, we get $$ \begin{bmatrix}5\\3\end{bmatrix}=c_1\begin{bmatrix}1\\1\end{bmatrix}+c_2\begin{bmatrix}1\\-1\end{bmatrix}=\begin{bmatrix}c_1+c_2\\c_1-c_2\end{bmatrix} $$ that is, we need only solve the system $c_1+c_2=5,\ c_1-c_2=3$. Adding the two equations side by side gives $2c_1=8$, so $c_1=4$; subtracting them side by side gives $2c_2=2$, so $c_2=1$. As a check, $4f_1+1f_2=4(1,1)+1(1,-1)=(4+1,4-1)=(5,3)=v$, which is correct. Hence $v=4f_1+f_2$.
The same vector $v$ is represented by the pair of coefficients $(5,3)$ in the basis $\{e_1,e_2\}$ and by the pair of coefficients $(4,1)$ in the basis $\{f_1,f_2\}$—the “vector itself” does not change, but its coordinates (the pair of coefficients) change depending on “which basis is used for measuring.” This is the essence of a change of basis.
10.4 Subspaces
In Illustration 10.3 we considered, inside $\R^4$, “the set of vectors satisfying the conditional equations.” The important point is that such a set is itself again a vector space (while remaining inside the original space). We now formally define such a “small vector space sitting entirely inside a vector space” as a subspace.
Definition 10.7: Subspace
Let $W$ be a subset of $\R^n$. Suppose that it contains the zero vector $0$ and is closed under addition and scalar multiplication in $\R^n$, that is, suppose that
(I) $0\in W$
(II) $a,b\in W \implies a+b\in W$
(III) $a\in W,\ k\in\R \implies ka\in W$
hold. Then $W$ is called a subspace of $\R^n$.
The two conditions (II) and (III) can be combined into the single statement “$k a+\ell b\in W$ ($a,b\in W$, $k,\ell\in\R$)” (taking $k=\ell=1$ recovers (II), and taking $\ell=0$ recovers (III)). In short, a subspace is “a set that you cannot leave by taking linear combinations.”
Incidentally, consider the one-dimensional subspace $\langle a\rangle=\{ca\mid c\in\R\}$ spanned by a single vector $a$ other than $0$ (the formal definition of a spanned subspace is given in Definition 10.8). Each choice of a real number $c$ determines exactly one element of it. That is, moving around inside a one-dimensional subspace is essentially the same as “choosing one scalar (a real constant)”—the naive intuition that a one-dimensional vector space corresponds exactly to the information of a single constant (real number) is the simplest concrete example of the idea that we will learn later: “dimension = number of basis vectors = number of freely choosable parameters.”
10.4.1 A simplified criterion for subspaces
The conditions for a subspace actually have exactly the same form as the conditions for a vector space (Definition 10.1)—it suffices to be closed under sums and scalar multiples. Therefore, to check whether a given set is a subspace we would in principle have to verify all of (I), (II), and (III), but the conditions can be simplified as follows.
Theorem 10.4: Simplified criterion for subspaces
For a nonempty subset $W$ of a vector space $V$ to be a subspace of $V$, the following two conditions alone suffice.
[1] If $x,y\in W$, then $x+y\in W$
[2] If $x\in W,\ c\in\R$, then $cx\in W$
Proof
It suffices to assume [1] and [2] and show that all of (I), (II), (III) of Definition 10.7 hold. (II) is exactly [1], and (III) is exactly [2]. What remains is $0\in W$ in (I). Now, since $W$ is nonempty (by the hypothesis of the theorem), we can pick at least one element $x\in W$. Setting $c=0$ in [2] gives $0\cdot x\in W$. Here, let us confirm from the axioms of a vector space (Definition 10.1(II)) that $0\cdot x=0$ (the zero vector). By (II)(iii), $0\cdot x=(0+0)\cdot x=0\cdot x+0\cdot x$. Adding the inverse vector $-(0\cdot x)$ of $0\cdot x$ to both sides from the right, the left side becomes $0\cdot x+(-(0\cdot x))=0$ (the zero vector), and the right side becomes $0\cdot x+0\cdot x+(-(0\cdot x))=0\cdot x$, so $0=0\cdot x$, that is, $0\cdot x=0$. Hence, together with $0\cdot x\in W$, we get $0\in W$, that is, (I) holds. Conversely, if (I), (II), (III) are assumed, it is clear from the definition that [1] and [2] hold.
Figures 10.6 and 10.7 show examples of sets that are, and are not, subspaces. In either of the spaces $\R^2,\R^3$, lines and planes through the origin are subspaces, whereas lines not passing through the origin and figures not containing the origin (such as a sphere) are not subspaces—this is the first rule of thumb to check (however, there are sets that are not subspaces even though they pass through the origin; $W_2$ in Illustration 10.4 below is such an example).
In Illustration 10.4 below, for concrete subsets of $\R^2$, we actually determine whether each is a subspace, using the simplified conditions [1] and [2] of Theorem 10.4.
Illustration 10.4: Determining whether a set is a subspace
Are $W_1=\left\{\begin{bmatrix}x\\y\end{bmatrix}\ \middle|\ x+y=0\right\}$ and $W_2=\left\{\begin{bmatrix}x\\y\end{bmatrix}\ \middle|\ x^2+y^2\le1\right\}$ subspaces of $\R^2$?
Solution. We use the simplified condition of Theorem 10.4: “if $a,b\in W$ and $k,\ell\in\R$, then $ka+\ell b\in W$.”
(i) For $W_1$. Let $a=\begin{bmatrix}a_1\\a_2\end{bmatrix},\ b=\begin{bmatrix}b_1\\b_2\end{bmatrix}\in W_1$. Since $a,b\in W_1$, we have $a_1+a_2=0$ and $b_1+b_2=0$. For $k,\ell\in\R$, writing $ka+\ell b=\begin{bmatrix}ka_1+\ell b_1\\ka_2+\ell b_2\end{bmatrix}$, we obtain $$ (ka_1+\ell b_1)+(ka_2+\ell b_2)=k(a_1+a_2)+\ell(b_1+b_2)=k\cdot0+\ell\cdot0=0 $$ so $ka+\ell b\in W_1$. Hence $W_1$ is a subspace of $\R^2$.
(ii) For $W_2$. Let $c=\begin{bmatrix}c_1\\c_2\end{bmatrix},\ d=\begin{bmatrix}d_1\\d_2\end{bmatrix}\in W_2$. Since $c,d\in W_2$, we have $c_1^2+c_2^2\le1$ and $d_1^2+d_2^2\le1$. Writing $kc+\ell d=\begin{bmatrix}kc_1+\ell d_1\\kc_2+\ell d_2\end{bmatrix}$, we obtain $$ (kc_1+\ell d_1)^2+(kc_2+\ell d_2)^2=k^2(c_1^2+c_2^2)+\ell^2(d_1^2+d_2^2)+2k\ell(c_1d_1+c_2d_2) $$ Now take $k\gt1,\ \ell\gt1$ and choose, for example, $c=\begin{bmatrix}1\\0\end{bmatrix}$ and $d=\begin{bmatrix}0\\1\end{bmatrix}$ (both lie on the unit circle and are elements of $W_2$). Then $kc+\ell d=\begin{bmatrix}k\\ \ell\end{bmatrix}$, and the square of its norm is $k^2+\ell^2\gt1^2+1^2=2\gt1$, so $kc+\ell d\notin W_2$. Hence $W_2$ is not a subspace of $\R^2$.
Example 10.4: Determining whether a set is a subspace by conditions [1] and [2] (another example)
Are $W_3=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\ \middle|\ x-2y+z=0\right\}$ and $W_4=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\ \middle|\ x+y+z=1\right\}$ subspaces of $\R^3$?
Solution. For $W_3$. Let $a=(a_1,a_2,a_3),\ b=(b_1,b_2,b_3)\in W_3$. Then $a_1-2a_2+a_3=0$ and $b_1-2b_2+b_3=0$. For $k,\ell\in\R$, $$ (ka_1+\ell b_1)-2(ka_2+\ell b_2)+(ka_3+\ell b_3)=k(a_1-2a_2+a_3)+\ell(b_1-2b_2+b_3)=k\cdot0+\ell\cdot0=0 $$ so $ka+\ell b\in W_3$. Thus conditions [1] and [2] (in the combined form $ka+\ell b\in W$) hold, and $W_3$ is a subspace.
For $W_4$. For a set to be a subspace, first of all, the condition $0\in W_4$ of Definition 10.7(I) is necessary. Substituting the zero vector $0=(0,0,0)$ into the conditional equation gives $0+0+0=0\neq1$, so it does not satisfy the condition $x+y+z=1$. Hence $0\notin W_4$, which already violates (I), so $W_4$ is not a subspace. (Whereas $W_2$ contained the origin but failed to be a subspace because it was not closed, $W_4$ is an example that fails to be a subspace for the more basic reason that it does not contain the origin at all.)
10.5 Spanned Subspaces, Solution Spaces, Intersections, and Sums of Subspaces
Each of the sets $W_1,W_3$ in Illustration 10.3 and Illustration 10.4 had the common form “the set of all linear combinations of finitely many vectors.” We generalize this construction and confirm that it always yields a subspace.
Theorem 10.5: Spanned subspaces
Let $a_1,a_2,\ldots,a_r\in\R^n$. Then $$ W=\{x_1a_1+x_2a_2+\cdots+x_ra_r \mid x_1,x_2,\ldots,x_r\in\R\} $$ is a subspace of $\R^n$.
Proof
Let $x=x_1a_1+\cdots+x_ra_r$ and $y=y_1a_1+\cdots+y_ra_r$ ($x_1,\ldots,x_r,y_1,\ldots,y_r\in\R$) be two arbitrary elements of $W$, and let $k,\ell\in\R$. Then $$ kx+\ell y=k(x_1a_1+\cdots+x_ra_r)+\ell(y_1a_1+\cdots+y_ra_r)=(kx_1+\ell y_1)a_1+(kx_2+\ell y_2)a_2+\cdots+(kx_r+\ell y_r)a_r $$ (we collected the coefficients of each $a_i$ by the distributive law for scalars). The coefficients $kx_1+\ell y_1,\ kx_2+\ell y_2,\ldots,kx_r+\ell y_r$ are all real numbers, so $kx+\ell y$ again has the form of a linear combination of $a_1,\ldots,a_r$; that is, $kx+\ell y\in W$. Hence, by the simplified condition of Theorem 10.4, $W$ is a subspace of $\R^n$.
Definition 10.8: Spanned subspace and spanning set
The subspace $W$ of Theorem 10.5 is called the subspace spanned by $a_1,a_2,\ldots,a_r$ and is denoted by $\langle a_1,a_2,\ldots,a_r\rangle$. That is, $$ \langle a_1,a_2,\ldots,a_r\rangle=\{x_1a_1+x_2a_2+\cdots+x_ra_r \mid x_1,x_2,\ldots,x_r\in\R\} $$ Moreover, when $W=\langle a_1,a_2,\ldots,a_r\rangle$, the set of vectors $\{a_1,a_2,\ldots,a_r\}$ is called a spanning set of $W$.
A spanning set is very similar to a basis, but unlike a basis it need not be linearly independent (it may contain duplicates or redundant information). If we select only the linearly independent vectors from a spanning set, they form a basis—this idea is treated in Exercise 10.6.
10.5.1 Solution space of a homogeneous system of linear equations
The set of all solutions of the homogeneous system of linear equations $Ax=0$, which you learned about in Chapter 9, is in fact also a subspace.
Definition 10.9: Solution space of a homogeneous system of linear equations
Let $A$ be an $m\times n$ matrix. Then $W=\{x\in\R^n \mid Ax=0\}$ is a subspace of $\R^n$. It is called the solution space of the homogeneous system of linear equations $Ax=0$.
(That $W$ is indeed a subspace can be confirmed with the simplified condition of Theorem 10.4: if $Ax=0,\ Ay=0$ and $k,\ell\in\R$, then by the distributive law for the product of a matrix and a vector, $A(kx+\ell y)=kAx+\ell Ay=k\cdot0+\ell\cdot0=0$, so $kx+\ell y$ is again a solution of $Ax=0$.)
Theorem 10.6: Dimension of the solution space
Let $A$ be an $m\times n$ matrix. Then the dimension of the solution space $W$ of the homogeneous system of linear equations $Ax=0$ is given by $$ \dim W=n-\rank A \qquad\cdots④ $$
This is merely a restatement of the “degrees of freedom” you learned about in Chapter 9—of the $n$ unknowns, $\rank A$ are constrained, and the remaining $n-\rank A$ are free to vary. In Illustration 10.3(i) we have $n=4,\ \rank A=1$ (one conditional equation) and $\dim W=3$, and in Illustration 10.3(ii) we have $n=4,\ \rank A=2$ and $\dim W=2$; both agree with ④.
10.5.2 Intersection and sum of subspaces
Here we collect the ways of constructing new subspaces from two subspaces.
Definition 10.10: Intersection, sum, and direct sum
For two subspaces $W_1,W_2$ of $\R^n$, we define (i), (ii), and (iii) below.
(i) $W_1\cap W_2=\{x\in\R^n \mid x\in W_1\ \text{and}\ x\in W_2\}$ is called the intersection of $W_1$ and $W_2$.
(ii) $W_1+W_2=\{x+y \mid x\in W_1,\ y\in W_2\}$ is called the sum of $W_1$ and $W_2$.
(iii) The condition that every element of $W$ can be written uniquely (in exactly one way) as the sum of an element of $W_1$ and an element of $W_2$—that is, that $W_1\cap W_2=\{0\}$—is expressed by writing $W=W_1\oplus W_2$, and $W$ is said to be the direct sum of $W_1$ and $W_2$.
Proof: “Uniquely expressible” is equivalent to “$W_1\cap W_2=\{0\}$”
Definition 10.10(iii) joins the two conditions “uniquely expressible” and “$W_1\cap W_2=\{0\}$” with “that is,” but this is not an unconditional restatement of the same thing; it is a claim that can be proved as follows.
(Uniqueness $\Longrightarrow$ the intersection is $\{0\}$) Suppose that an element $x$ of $W=W_1+W_2$ could be written in two ways, $x=w_1+w_2=w_1'+w_2'$ ($w_1,w_1'\in W_1,\ w_2,w_2'\in W_2$). Moving terms to the other side, we obtain $w_1-w_1'=w_2'-w_2$. The left-hand side $w_1-w_1'=w_1+(-1)w_1'$ is an element of $W_1$ because $W_1$ is a subspace (closed under sums and scalar multiples), and likewise the right-hand side $w_2'-w_2$ is an element of $W_2$. Since both sides are the same vector, this vector belongs to both $W_1$ and $W_2$; that is, it is an element of $W_1\cap W_2$. If $W_1\cap W_2=\{0\}$, this element can only be $0$, so $w_1-w_1'=0$, that is, $w_1=w_1'$, and similarly $w_2=w_2'$; thus the two seemingly different representations were in fact the same one. Hence the representation is unique.
(The contrapositive of “if the intersection is not $\{0\}$, uniqueness fails”) Conversely, suppose that $W_1\cap W_2$ contains an element $v$ other than $0$. Since $v\in W_1\cap W_2$, we have $v\in W_1$ and $v\in W_2$, and since $W_2$ is a subspace, also $-v\in W_2$. Therefore the zero vector $0\in W$ can be written in two ways: as $0=v+(-v)$ ($v\in W_1,\ -v\in W_2$), and as $0=0+0$ ($0\in W_1,\ 0\in W_2$). Since $v\neq0$, these two representations are different, so uniqueness fails.
Combining the two arguments above, “uniquely expressible” and “$W_1\cap W_2=\{0\}$” are indeed equivalent.
This direct-sum condition $W_1\cap W_2=\{0\}$ can be viewed as an extension of the idea of linear independence of vectors to a relation between subspaces. Just as the essence of linear independence was that a single vector $a_1$ cannot be written as a linear combination of the other vectors $a_2,\ldots,a_n$, the fact that $W_1$ shares no element of $W_2$ (other than $0$) puts us, so to speak, in a situation where $W_1$ and $W_2$ are independent, in the sense that “$W_1$ and $W_2$ point in independent directions, neither of which can be built from the information in the other.” (The precise formulation of this intuition is the dimension theorem for subspaces, which is proved as Theorem 10.8 in Section 10.6; there we will see that the discrepancy of “counting the intersection twice” disappears exactly in the case of a direct sum (when there is no overlap).)
Caution: Differences among $W_1\cap W_2$, $W_1\cup W_2$, and $W_1+W_2$
$W_1\cap W_2$ and $W_1+W_2$ are always subspaces, but the union $W_1\cup W_2$ (the set of all elements belonging to $W_1$ or $W_2$) is in general not a subspace. For example, in $\R^2$ let $W_1$ be the $x$-axis and $W_2$ the $y$-axis. Then $(1,0)\in W_1\subset W_1\cup W_2$ and $(0,1)\in W_2\subset W_1\cup W_2$, but their sum $(1,0)+(0,1)=(1,1)$ lies on neither axis and hence does not belong to $W_1\cup W_2$—the union is not closed under addition. Rigorous proofs of the three statements are given in Section 10.6 (Theorem 10.7).
Figure 10.8 shows two planes $W_1,W_2$ in $\R^3$ (two-dimensional subspaces through the origin) meeting in a single line. This line of intersection is exactly $W_1\cap W_2$.
Example 10.5: Intersection and sum in $\R^3$
For $U_1=\left\langle\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix}\right\rangle$ (the $xy$-plane) and $U_2=\left\langle\begin{bmatrix}0\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix}\right\rangle$ (the $yz$-plane), find $\dim U_1,\ \dim U_2,\ \dim(U_1\cap U_2),\ \dim(U_1+U_2)$.
Solution. Both $U_1,U_2$ are spanned by two linearly independent vectors, so $\dim U_1=\dim U_2=2$.
$U_1\cap U_2$ is the set of points lying on both the $xy$-plane ($z=0$) and the $yz$-plane ($x=0$), so it is given by $x=0,z=0$; that is, it is the $y$-axis $\{(0,t,0)\mid t\in\R\}$. This is spanned by the single vector $(0,1,0)$, so $\dim(U_1\cap U_2)=1$.
$U_1+U_2$ is the subspace spanned by the spanning sets of $U_1,U_2$ combined, namely $\left\{\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix}\right\}$. These three vectors are exactly the standard basis of $\R^3$ (linearly independent of one another), so $U_1+U_2=\R^3$ and $\dim(U_1+U_2)=3$.
In summary, $\dim U_1+\dim U_2=2+2=4$ and $\dim(U_1+U_2)+\dim(U_1\cap U_2)=3+1=4$, so the two agree. This agreement is no accident; it is precisely the content of the dimension theorem for subspaces (Theorem 10.8), which is proved in the next section.
10.6 Theorems on Subspaces and the Dimension Theorem
We now prove carefully the three claims announced in the Caution of the previous section—$W_1\cap W_2$ is a subspace, $W_1\cup W_2$ is not necessarily a subspace, and $W_1+W_2$ is a subspace.
Theorem 10.7: Theorem on subspaces
For subspaces $W_1,W_2$ of $\R^n$, the following hold.
(Ⅰ) $W_1\cap W_2$ is a subspace of $\R^n$.
(Ⅱ) In general, $W_1\cup W_2$ is not necessarily a subspace.
(Ⅲ) $W_1+W_2$ is a subspace of $\R^n$.
(Ⅳ) $W_1\cup W_2\subset W_1+W_2$.
Proof
(Ⅰ) Suppose $a,b\in W_1\cap W_2$. Then $a,b\in W_1$ and $a,b\in W_2$. Since $W_1$ is a subspace (Theorem 10.4), $a+b\in W_1$, and likewise, since $W_2$ is a subspace, $a+b\in W_2$. Hence $a+b\in W_1$ and $a+b\in W_2$, that is, $a+b\in W_1\cap W_2$. The same holds for scalar multiples: if $a\in W_1\cap W_2,\ k\in\R$, then $ka\in W_1$ and $ka\in W_2$, so $ka\in W_1\cap W_2$. Thus conditions [1] and [2] of Theorem 10.4 are satisfied, and therefore $W_1\cap W_2$ is a subspace.
(Ⅱ) To show that something “does not hold in general,” it suffices to give a single counterexample. As we saw in the Caution in Section 10.5, take $W_1=\{(t,0)\mid t\in\R\}$ (the $x$-axis) and $W_2=\{(0,t)\mid t\in\R\}$ (the $y$-axis) in $\R^2$. The sum $(1,0)+(0,1)=(1,1)$ of $(1,0)\in W_1\subset W_1\cup W_2$ and $(0,1)\in W_2\subset W_1\cup W_2$ lies on neither the $x$-axis nor the $y$-axis, so it does not belong to $W_1\cup W_2$. That is, $W_1\cup W_2$ is not closed under addition and fails condition [1] for a subspace. Hence $W_1\cup W_2$ is not a subspace in general.
(Ⅲ) By the definition of $W_1+W_2$ (Definition 10.10(ii)), its elements may be regarded as the collection of all elements of the form $kx_1+\ell x_2$ ($x_1\in W_1,\ x_2\in W_2,\ k,\ell\in\R$) (indeed, for any two elements $x_1+y_1$, $x_2+y_2$ of $W_1+W_2$ ($x_1,x_2\in W_1,\ y_1,y_2\in W_2$), their linear combination $k(x_1+y_1)+\ell(x_2+y_2)=(kx_1+\ell x_2)+(ky_1+\ell y_2)$ satisfies $kx_1+\ell x_2\in W_1$ because $W_1$ is a subspace and $ky_1+\ell y_2\in W_2$ because $W_2$ is a subspace, so it is again an element of the form that defines $W_1+W_2$). Substituting $k=0,\ell=0$ gives $0+0=0\in W_1+W_2$, which also confirms (I). Therefore $W_1+W_2$ satisfies the conditions of Theorem 10.4 and is a subspace.
(Ⅳ) If $x\in W_1$, then we can write $x=x+0$ ($0\in W_2$), so $x\in W_1+W_2$. Hence $W_1\subset W_1+W_2$. Similarly, $W_2\subset W_1+W_2$. Therefore $W_1\cup W_2\subset W_1+W_2$. (In fact, $W_1+W_2$ is the smallest of the subspaces containing $W_1\cup W_2$.)
Finally, we prove the most important theorem concerning the dimension of subspaces, announced at the end of Example 10.5.
Theorem 10.8: Dimension theorem for subspaces
For subspaces $W_1,W_2$ of $\R^n$, the equation $$ \dim W_1+\dim W_2=\dim(W_1+W_2)+\dim(W_1\cap W_2) \qquad\cdots⑤ $$ holds (this is also called the dimension formula for subspaces).
Proof
Let $\dim(W_1\cap W_2)=r$, and let $c_1,\ldots,c_r$ be a basis of $W_1\cap W_2$. Since $W_1\cap W_2\subset W_1$, these $r$ independent vectors can be extended, by adding further vectors $a_1,\ldots,a_p$, to a basis $c_1,\ldots,c_r,a_1,\ldots,a_p$ of all of $W_1$ ($\dim W_1=r+p$). (A set of independent vectors can be enlarged one vector at a time until it spans the whole space by itself—this is a general fact about the existence of bases. Let us confirm why this is so. If $c_1,\ldots,c_r$ do not yet span all of $W_1$, then there exists a vector $a_1\in W_1$ that cannot be written as a linear combination of them. In that case $c_1,\ldots,c_r,a_1$ remain independent. Indeed, suppose a nontrivial linear relation $\delta_1c_1+\cdots+\delta_rc_r+\varepsilon a_1=0$ (the coefficients are not all $0$) held. Then we must first have $\varepsilon\neq0$ (if $\varepsilon=0$, this would be a nontrivial linear relation among $c_1,\ldots,c_r$ themselves, contradicting the independence of $c_1,\ldots,c_r$). It then follows that $a_1=-\varepsilon^{-1}(\delta_1c_1+\cdots+\delta_rc_r)$, so $a_1$ could be written as a linear combination of $c_1,\ldots,c_r$, which contradicts the choice of $a_1$ (a vector that cannot be written as such a linear combination). Hence $c_1,\ldots,c_r,a_1$ is independent. If they still do not span all of $W_1$, we can repeat the same argument with $a_2,a_3,\ldots$ and increase the number of vectors one at a time; but the number of independent vectors cannot exceed the maximum number of vectors that can be independent in $W_1$ ($\dim W_1$, by Theorem 10.2(i)), so this procedure must stop after finitely many steps, and we obtain an independent set that spans all of $W_1$.) Similarly, since $W_1\cap W_2\subset W_2$, the basis of the intersection can also be extended to a basis $c_1,\ldots,c_r,b_1,\ldots,b_q$ ($\dim W_2=r+q$) of the subspace that contains it.
Now we show that the combined $r+p+q$ vectors $c_1,\ldots,c_r,a_1,\ldots,a_p,b_1,\ldots,b_q$ form a basis of $W_1+W_2$.
(Spanning) Every element of $W_1+W_2$ has the form $x_1+x_2$ ($x_1\in W_1,\ x_2\in W_2$). Since $x_1$ can be expressed as a linear combination of $c_1,\ldots,c_r,a_1,\ldots,a_p$ and $x_2$ as a linear combination of $c_1,\ldots,c_r,b_1,\ldots,b_q$, their sum $x_1+x_2$ can also be expressed as a linear combination of these $r+p+q$ vectors. Hence this set spans $W_1+W_2$.
(Independence) Consider the linear relation $$ \underbrace{\sum_{i=1}^r \alpha_ic_i}_{=:u}+\underbrace{\sum_{j=1}^p \beta_ja_j}_{=:v}+\underbrace{\sum_{k=1}^q \gamma_kb_k}_{=:w}=0 \qquad\cdots⑥ $$ ($\alpha_i,\beta_j,\gamma_k\in\R$). Rewrite ⑥ as $v=-u-w$. Since $u,w$ are both linear combinations of $c_1,\ldots,c_r,b_1,\ldots,b_q$ (a basis of $W_2$), we have $v=-u-w\in W_2$. On the other hand, $v=\sum\beta_ja_j$ is already a linear combination of part of the basis of $W_1$, so $v\in W_1$. Hence $v\in W_1\cap W_2$, and $v$ can be expressed as a linear combination of $c_1,\ldots,c_r$ (in exactly one way, since they form a basis of $W_1\cap W_2$): there exist $\delta_i$ such that $v=\sum_{i=1}^r\delta_ic_i$. Then $$ \sum_{j=1}^p\beta_ja_j-\sum_{i=1}^r\delta_ic_i=0 $$ holds, but since $c_1,\ldots,c_r,a_1,\ldots,a_p$ form a basis of $W_1$ (that is, are independent), all the coefficients of this linear relation are $0$; in particular, $\beta_1=\cdots=\beta_p=0$. Hence $v=0$, and ⑥ reduces to $u+w=0$. Since $u,w$ are linear combinations of $c_1,\ldots,c_r,b_1,\ldots,b_q$ (a basis of $W_2$), independence again gives $\alpha_1=\cdots=\alpha_r=0,\ \gamma_1=\cdots=\gamma_q=0$. Thus all the coefficients in ⑥ are $0$, and $c_1,\ldots,c_r,a_1,\ldots,a_p,b_1,\ldots,b_q$ are linearly independent.
It follows that these $r+p+q$ vectors form a basis of $W_1+W_2$, and $\dim(W_1+W_2)=r+p+q$. On the other hand, $\dim W_1+\dim W_2=(r+p)+(r+q)=2r+p+q$, and since $\dim(W_1\cap W_2)=r$, we obtain $$ \dim(W_1+W_2)+\dim(W_1\cap W_2)=(r+p+q)+r=2r+p+q=\dim W_1+\dim W_2 $$ which proves ⑤.
We check how to use the dimension theorem with a concrete numerical example from the original notes.
Illustration 10.5: Numerical example of the dimension theorem
For $W_1=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ \begin{aligned}x+y&=0\\z-w&=0\end{aligned}\right\}$ and $W_2=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ x+y+z+w=0\right\}$, find $\dim W_1,\ \dim W_2,\ \dim(W_1\cap W_2),\ \dim(W_1+W_2)$.
Solution. $W_1$ is defined by two conditional equations ($x+y=0$, $z-w=0$), so by Theorem 10.6, $\dim W_1=4-2=2$. $W_2$ is defined by one conditional equation, so $\dim W_2=4-1=3$.
$W_1\cap W_2$ is the set of vectors that simultaneously satisfy the three conditional equations $x+y=0,\ z-w=0,\ x+y+z+w=0$. Substituting the first equation $x+y=0$ into the third equation $x+y+z+w=0$ (we simply replace $x+y$ by $0$) gives $0+z+w=0$, hence $z+w=0$. Combining this with the second equation $z-w=0$: adding the two equations side by side gives $2z=0$, so $z=0$, and subtracting them side by side gives $2w=0$, so $w=0$. Hence the conditions are effectively the three (independent) equations $x+y=0,\ z=0,\ w=0$, and $\dim(W_1\cap W_2)=4-3=1$ (a basis is $(1,-1,0,0)$).
By the dimension theorem ⑤, we have $$ \dim(W_1+W_2)=\dim W_1+\dim W_2-\dim(W_1\cap W_2)=2+3-1=4 $$ Since $\dim(W_1+W_2)=4=\dim\R^4$, we also see that in fact $W_1+W_2=\R^4$ (all of $\R^4$).
Example 10.6: Another numerical example of the dimension theorem
For $W_1=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ \begin{aligned}x-y&=0\\z+w&=0\end{aligned}\right\}$ and $W_2=\left\{\begin{bmatrix}x\\y\\z\\w\end{bmatrix}\ \middle|\ x+2y-z+w=0\right\}$, find $\dim W_1,\ \dim W_2,\ \dim(W_1\cap W_2),\ \dim(W_1+W_2)$.
Solution. $W_1$ is defined by two conditional equations, so $\dim W_1=4-2=2$ (from $x=y,\,z=-w$, a basis is $(1,1,0,0),(0,0,1,-1)$), and $W_2$ is defined by one conditional equation, so $\dim W_2=4-1=3$.
$W_1\cap W_2$ is determined by the system of the three equations $x-y=0,\ z+w=0,\ x+2y-z+w=0$. We examine the rank of the coefficient matrix $$ M=\begin{bmatrix}1&-1&0&0\\0&0&1&1\\1&2&-1&1\end{bmatrix} $$ by elementary row operations. Applying $R_3\to R_3-R_1$ makes the first-column entry of $R_3$ equal to $1-1=0$, and we obtain $$ M\ \xrightarrow{R_3\to R_3-R_1}\ \begin{bmatrix}1&-1&0&0\\0&0&1&1\\0&3&-1&1\end{bmatrix} $$ Now swapping the second and third rows gives $$ \begin{bmatrix}1&-1&0&0\\0&3&-1&1\\0&0&1&1\end{bmatrix} $$ which is already a row echelon matrix (the first, second, and third rows have nonzero leading entries in the first, second, and third columns, respectively). Since none of the three rows has become $0$, $\rank M=3$. Hence $\dim(W_1\cap W_2)=4-\rank M=4-3=1$.
By the dimension theorem, we have $$ \dim(W_1+W_2)=\dim W_1+\dim W_2-\dim(W_1\cap W_2)=2+3-1=4 $$ so in this case, too, $W_1+W_2=\R^4$.
10.7 Summary and Exercises
10.7.1 Summary
- Vector space (linear space): a set on which addition and scalar multiplication are defined and which satisfies axioms (I) and (II) (associativity, commutativity, the existence of the zero vector and of inverse vectors; distributivity and associativity for scalars). Its elements are not limited to numerical vectors; they may be matrices or polynomials.
- Linear combinations and linear relations: an equation stating that $c_1a_1+\cdots+c_na_n$ (a linear combination) equals $0$ is called a linear relation. The dividing line between independence and dependence is whether there is any solution other than the trivial solution (all coefficients $0$).
- Linear independence and linear dependence: the vectors are independent if the linear relation holds only when all the coefficients are $0$; otherwise (that is, if at least one vector can be written as a linear combination of the others) they are dependent. The criterion is $\rank[a_1\ \cdots\ a_n]=n$ (Theorem 10.1).
- Basis and dimension: a set of vectors that is independent and spans the whole space is a basis. The number of vectors in it is the dimension $\dim W$, and “the maximum number of independent vectors” equals “the minimum number of vectors that span” (Theorem 10.2). $W_1\subset W_2\Rightarrow\dim W_1\le\dim W_2$, and if equality holds then $W_1=W_2$ (Theorem 10.3).
- Subspaces: a subset that contains $0$ and is closed under addition and scalar multiplication. The simplified conditions are “$x,y\in W\Rightarrow x+y\in W$” and “$x\in W,c\in\R\Rightarrow cx\in W$” (Theorem 10.4).
- Spanned subspaces and solution spaces: $\langle a_1,\ldots,a_r\rangle$ is always a subspace (Theorem 10.5). The solution space of the homogeneous system of linear equations $Ax=0$ satisfies $\dim W=n-\rank A$ (Theorem 10.6).
- Intersections, sums of subspaces, direct sums, and the dimension theorem: $W_1\cap W_2,\ W_1+W_2$ are always subspaces, whereas $W_1\cup W_2$ is in general not a subspace (Theorem 10.7). Furthermore, $$ \dim W_1+\dim W_2=\dim(W_1+W_2)+\dim(W_1\cap W_2) $$ (Theorem 10.8, the dimension theorem).
In Chapter 11, on the stage built in this chapter from “vector spaces,” “bases,” and “dimension,” we study the maps that connect two vector spaces—linear maps. The image (Im) and the kernel (Ker) of a linear map are none other than the subspaces studied in this chapter, and the relation concerning their dimensions (the map version of the dimension theorem) is proved using the same idea as in Theorem 10.8.
10.7.2 Exercises
Exercise 10.1: Determining linear independence
Determine whether $g_1=\begin{bmatrix}1\\2\\0\end{bmatrix},\ g_2=\begin{bmatrix}0\\1\\3\end{bmatrix},\ g_3=\begin{bmatrix}2\\0\\-1\end{bmatrix}$ are linearly independent or linearly dependent.
Hint: As in Illustration 10.1, compute the determinant of the matrix formed by placing the three vectors side by side (Theorem 10.1).
Exercise 10.2: Dimension and basis of a subspace
Find the dimension and a basis of the subspace $W=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\ \middle|\ 2x-y+3z=0\right\}$ of $\R^3$.
Hint: Use Theorem 10.6 ($\dim W=n-\rank A$), or, as in Illustration 10.3(i), express one variable in terms of the other two.
Exercise 10.3: Determining whether a sum is direct
In $\R^3$, let $U_1=\left\langle\begin{bmatrix}1\\1\\0\end{bmatrix},\begin{bmatrix}0\\1\\1\end{bmatrix}\right\rangle$ and $U_2=\left\langle\begin{bmatrix}1\\0\\0\end{bmatrix}\right\rangle$. Determine whether $\R^3=U_1\oplus U_2$ (a direct sum) holds.
Hint: By Definition 10.10(iii), it suffices to examine whether $U_1\cap U_2=\{0\}$. Confirm that the three vectors obtained by putting together the spanning sets of $U_1,U_2$ are independent ($\rank=3$).
Exercise 10.4: Working backward with the dimension theorem
In $\R^5$, suppose that subspaces $W_1,W_2$ satisfy $\dim W_1=3,\ \dim W_2=3,\ \dim(W_1+W_2)=5$. Find $\dim(W_1\cap W_2)$.
Hint: Just solve the formula of Theorem 10.8 (the dimension theorem) for $\dim(W_1\cap W_2)$.
Exercise 10.5: Checking the subspace axioms (a counterexample)
Is the first quadrant of $\R^2$, $W=\{(x,y)\mid x\ge0,\ y\ge0\}$, a subspace of $\R^2$? If it is not a subspace, show which condition fails by giving a concrete example.
Hint: Test Definition 10.7(III) (whether the set is closed under scalar multiplication) with a negative scalar.
Exercise 10.6: Choosing a basis from a spanning set
The vectors $h_1=\begin{bmatrix}1\\0\\0\end{bmatrix},\ h_2=\begin{bmatrix}0\\1\\0\end{bmatrix},\ h_3=\begin{bmatrix}1\\1\\0\end{bmatrix},\ h_4=\begin{bmatrix}0\\0\\1\end{bmatrix}$ form a spanning set of $\R^3$ (the four vectors span $\R^3$, but since $\dim\R^3=3$, one of them is redundant). From these four vectors, choose three that form a basis of $\R^3$.
Hint: Among the four vectors there is one that can be written as a linear combination of two of the other vectors (see the discussion of spanning sets in Section 10.5). Remove it and check whether the remaining three are independent.
10.7.3 References
- Yasuhide Mochizuki, Mathematics Notes: Linear Algebra (handwritten lecture notes, in Japanese). The source of this chapter.
- Masahiko Saito, Senkei Daisū Nyūmon [Introduction to Linear Algebra], University of Tokyo Press, 1966 (in Japanese).
- Ichiro Satake, Senkei Daisūgaku [Linear Algebra], Shōkabō, 1958 (in Japanese).