Basis and Dimension

The prior section ends with the observation that a spanning set is minimal when it is linearly independent and a linearly independent set is maximal when it spans the space. So the notions of minimal spanning set and maximal independent set coincide. In this section we will name this idea and study its properties.

Basis

Definition 1.1 A basis for a vector space is a sequence of vectors that is linearly independent and that spans the space.

Because a basis is a sequence, meaning that bases are different if they contain the same elements but in different orders, we denote it with angle brackets $⟨ {\vec{β}}_{1}, {\vec{β}}_{2}, \dots ⟩$ .¹ (A sequence is linearly independent if the multiset consisting of the elements of the sequence is independent. Similarly, a sequence spans the space if the set of elements of the sequence spans the space.)

Example 1.2 This is a basis for $ℝ^{2}$ .

$⟨ (\begin{matrix} 2 \\ 4 \end{matrix}), (\begin{matrix} 1 \\ 1 \end{matrix}) ⟩$

It is linearly independent

$c_{1} (\begin{matrix} 2 \\ 4 \end{matrix}) + c_{2} (\begin{matrix} 1 \\ 1 \end{matrix}) = (\begin{matrix} 0 \\ 0 \end{matrix}) ⟹ \begin{array}{rcrcr} 2 c_{1} & + & 1 c_{2} & = & 0 \\ 4 c_{1} & + & 1 c_{2} & = & 0 \end{array} ⟹ c_{1} = c_{2} = 0$

and it spans $ℝ^{2}$ .

$\begin{array}{rcrcr} 2 c_{1} & + & 1 c_{2} & = & x \\ 4 c_{1} & + & 1 c_{2} & = & y \end{array} ⟹ c_{2} = 2 x - y and c_{1} = (y - x) / 2$

Example 1.3 This basis for $ℝ^{2}$ differs from the prior one

$⟨ (\begin{matrix} 1 \\ 1 \end{matrix}), (\begin{matrix} 2 \\ 4 \end{matrix}) ⟩$

because it is in a different order. The verification that it is a basis is just as in the prior example.

Example 1.4 The space $ℝ^{2}$ has many bases. Another one is this.

$⟨ (\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \end{matrix}) ⟩$

The verification is easy.

Definition 1.5 For any $ℝ^{n}$

$ℰ_{n} = ⟨ (\begin{matrix} 1 \\ 0 \\ ⋮ \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ ⋮ \\ 0 \end{matrix}), \dots, (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 1 \end{matrix}) ⟩$

is the standard (or natural) basis. We denote these vectors ${\vec{e}}_{1}, \dots, {\vec{e}}_{n}$ .

Calculus books denote $ℝ^{2}$ ’s standard basis vectors as $\vec{ı}$ and $\vec{ȷ}$ instead of ${\vec{e}}_{1}$ and ${\vec{e}}_{2}$ and they denote to $ℝ^{3}$ ’s standard basis vectors as $\vec{ı}$ , $\vec{ȷ}$ , and $\vec{k}$ instead of ${\vec{e}}_{1}$ , ${\vec{e}}_{2}$ , and ${\vec{e}}_{3}$ . Note that ${\vec{e}}_{1}$ means something different in a discussion of $ℝ^{3}$ than it means in a discussion of $ℝ^{2}$ .

Example 1.6 Consider the space ${a \cdot \cos θ + b \cdot \sin θ ∣ a, b \in ℝ}$ of functions of the real variable $θ$ . This is a natural basis $⟨ \cos θ, \sin θ ⟩ = ⟨ 1 \cdot \cos θ + 0 \cdot \sin θ, 0 \cdot \cos θ + 1 \cdot \sin θ ⟩$ . A more generic basis for this space is $⟨ \cos θ - \sin θ, 2 \cos θ + 3 \sin θ ⟩$ . Verification that these two are bases is Exercise 1.29.

Example 1.7 A natural basis for the vector space of cubic polynomials $𝒫_{3}$ is $⟨ 1, x, x^{2}, x^{3} ⟩$ . Two other bases for this space are $⟨ x^{3}, 3 x^{2}, 6 x, 6 ⟩$ and $⟨ 1, 1 + x, 1 + x + x^{2}, 1 + x + x^{2} + x^{3} ⟩$ . Checking that each is linearly independent and spans the space is easy.

Example 1.8 The trivial space ${\vec{0}}$ has only one basis, the empty one $⟨ ⟩$ .

Example 1.9 The space of finite-degree polynomials has a basis with infinitely many elements $⟨ 1, x, x^{2}, \dots ⟩$ .

Example 1.10 We have seen bases before. In the first chapter we described the solution set of homogeneous systems such as this one

$\begin{array}{rcrcrcrcr} x & + & y & - & w & = & 0 \\ z & + & w & = & 0 \end{array}$

by parametrizing.

${(\begin{matrix} - 1 \\ 1 \\ 0 \\ 0 \end{matrix}) y + (\begin{matrix} 1 \\ 0 \\ - 1 \\ 1 \end{matrix}) w ∣ y, w \in ℝ}$

Thus the vector space of solutions is the span of a two-element set. This two-vector set is also linearly independent, which is easy to check. Therefore the solution set is a subspace of $ℝ^{4}$ with a basis comprised of these two vectors.

Example 1.11 Parametrization finds bases for other vector spaces, not just for solution sets of homogeneous systems. To find a basis for this subspace of $ℳ_{2 \times 2}$

${(\begin{matrix} a & b \\ c & 0 \end{matrix}) ∣ a + b - 2 c = 0}$

we rewrite the condition as $a = - b + 2 c$ .

${(\begin{matrix} - b + 2 c & b \\ c & 0 \end{matrix}) ∣ b, c \in ℝ} = {b (\begin{matrix} - 1 & 1 \\ 0 & 0 \end{matrix}) + c (\begin{matrix} 2 & 0 \\ 1 & 0 \end{matrix}) ∣ b, c \in ℝ}$

Thus, this is a natural candidate for a basis.

$⟨ (\begin{matrix} - 1 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} 2 & 0 \\ 1 & 0 \end{matrix}) ⟩$

The above work shows that it spans the space. Linear independence is also easy.

Consider again Example 1.2. To verify that the set spans the space we looked at linear combinations that total to a member of the space $c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} = (\binom{x}{y})$ . We only noted in that example that such a combination exists, that for each $x, y$ there exists a $c_{1}, c_{2}$ , but in fact the calculation also shows that the combination is unique: $c_{1}$ must be $(y - x) / 2$ and $c_{2}$ must be $2 x - y$ .

Theorem 1.12 In any vector space, a subset is a basis if and only if each vector in the space can be expressed as a linear combination of elements of the subset in one and only one way.

We consider linear combinations to be the same if they have the same summands but in a different order, or if they differ only in the addition or deletion of terms of the form ‘ $0 \cdot \vec{β}$ ’.

Proof A sequence is a basis if and only if its vectors form a set that spans and that is linearly independent. A subset is a spanning set if and only if each vector in the space is a linear combination of elements of that subset in at least one way. Thus we need only show that a spanning subset is linearly independent if and only if every vector in the space is a linear combination of elements from the subset in at most one way.

Consider two expressions of a vector as a linear combination of the members of the subset. Rearrange the two sums, and if necessary add some $0 \cdot {\vec{β}}_{i}$ terms, so that the two sums combine the same $\vec{β}$ ’s in the same order: $\vec{v} = c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} + \dots + c_{n} {\vec{β}}_{n}$ and $\vec{v} = d_{1} {\vec{β}}_{1} + d_{2} {\vec{β}}_{2} + \dots + d_{n} {\vec{β}}_{n}$ . Now

$c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} + \dots + c_{n} {\vec{β}}_{n} = d_{1} {\vec{β}}_{1} + d_{2} {\vec{β}}_{2} + \dots + d_{n} {\vec{β}}_{n}$

holds if and only if

$(c_{1} - d_{1}) {\vec{β}}_{1} + \dots + (c_{n} - d_{n}) {\vec{β}}_{n} = \vec{0}$

holds. So, asserting that each coefficient in the lower equation is zero is the same thing as asserting that $c_{i} = d_{i}$ for each $i$ , that is, that every vector is expressible as a linear combination of the $\vec{β}$ ’s in a unique way.

QED

Definition 1.13 In a vector space with basis $B$ the representation of $\vec{v}$ with respect to $B$ is the column vector of the coefficients used to express $\vec{v}$ as a linear combination of the basis vectors:

${Rep}_{B} (\vec{v}) = {(\begin{matrix} c_{1} \\ c_{2} \\ ⋮ \\ c_{n} \end{matrix})}_{B}$

where $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ and $\vec{v} = c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} + \dots + c_{n} {\vec{β}}_{n}$ . The $c$ ’s are the coordinates of $\vec{v}$ with respect to $B$ .

Example 1.14 In $𝒫_{3}$ , with respect to the basis $B = ⟨ 1, 2 x, 2 x^{2}, 2 x^{3} ⟩$ , the representation of $x + x^{2}$ is

${Rep}_{B} (x + x^{2}) = {(\begin{matrix} 0 \\ 1 / 2 \\ 1 / 2 \\ 0 \end{matrix})}_{B}$

because $x + x^{2} = 0 \cdot 1 + (1 / 2) \cdot 2 x + (1 / 2) \cdot 2 x^{2} + 0 \cdot 2 x^{3}$ . With respect to a different basis $D = ⟨ 1 + x, 1 - x, x + x^{2}, x + x^{3} ⟩$ , the representation is different.

${Rep}_{D} (x + x^{2}) = {(\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix})}_{D}$

Remark 1.15 Definition 1.1 requires that a basis be a sequence so that we can write these coordinates in an order.

When there is only one basis around, we often omit the subscript naming that basis.

Example 1.16 In $ℝ^{2}$ , to find the coordinates of the vector $\vec{v} = (\binom{3}{2})$ with respect to the basis

$B = ⟨ (\begin{matrix} 1 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ 2 \end{matrix}) ⟩$

solve

$c_{1} (\begin{matrix} 1 \\ 1 \end{matrix}) + c_{2} (\begin{matrix} 0 \\ 2 \end{matrix}) = (\begin{matrix} 3 \\ 2 \end{matrix})$

and get that $c_{1} = 3$ and $c_{2} = - 1 / 2$ .

${Rep}_{B} (\vec{v}) = (\begin{matrix} 3 \\ - 1 / 2 \end{matrix})$

Writing the representation as a column generalizes the familiar case: in $ℝ^{n}$ and with respect to the standard basis $ℰ_{n}$ , the vector starting at the origin and ending at $(v_{1}, \dots, v_{n})$ has this representation.

${Rep}_{ℰ_{n}} ((\begin{matrix} v_{1} \\ ⋮ \\ v_{n} \end{matrix})) = {(\begin{matrix} v_{1} \\ ⋮ \\ v_{n} \end{matrix})}_{ℰ_{n}}$

This is an example.

${Rep}_{ℰ_{n}} ((\begin{matrix} - 1 \\ 1 \end{matrix})) = (\begin{matrix} - 1 \\ 1 \end{matrix})$

Remark 1.17 The ${Rep}_{B} (\vec{v})$ notation is not standard. The most common notation is $[\vec{v}]_{B}$ but one advantage that ${Rep}_{B} (\vec{v})$ has is that it is harder to misinterpret or overlook.

The column represents the vector in the sense that a linear relationship holds among a set of vectors if and only if that relationship holds among the set of representations.

Lemma 1.18 Where $B$ is a basis with $n$ elements, for any set of vectors, $a_{1} {\vec{v}}_{1} + \dots + a_{k} {\vec{v}}_{k} = {\vec{0}}_{V}$ if and only if $a_{1} {Rep}_{B} ({\vec{v}}_{1}) + \dots + a_{k} {Rep}_{B} ({\vec{v}}_{k}) = {\vec{0}}_{ℝ^{n}}$ .

Proof Fix a basis $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ and suppose

${Rep}_{B} ({\vec{v}}_{1}) = (\begin{matrix} c_{1, 1} \\ ⋮ \\ c_{n, 1} \end{matrix}) \dots {Rep}_{B} ({\vec{v}}_{k}) = (\begin{matrix} c_{1, k} \\ ⋮ \\ c_{n, k} \end{matrix})$

so that ${\vec{v}}_{1} = c_{1, 1} {\vec{β}}_{1} + \dots + c_{n, 1} {\vec{β}}_{n}$ , etc. Then $a_{1} {\vec{v}}_{1} + \dots + a_{k} {\vec{v}}_{k} = \vec{0}$ is equivalent to these.

$\begin{aligned} \vec{0} & = a_{1} \cdot (c_{1, 1} {\vec{β}}_{1} + \dots + c_{n, 1} {\vec{β}}_{n}) + \dots + a_{k} \cdot (c_{1, k} {\vec{β}}_{1} + \dots + c_{n, k} {\vec{β}}_{n}) \\ = (a_{1} c_{1, 1} + \dots + a_{k} c_{1, k}) \cdot {\vec{β}}_{1} + \dots + (a_{1} c_{n, 1} + \dots + a_{k} c_{n, k}) \cdot {\vec{β}}_{n} \end{aligned}$

Obviously the bottom equation is true if the coefficients are zero. But, because $B$ is a basis, Theorem 1.12 says that the bottom equation is true if and only if the coefficients are zero. So the relation is equivalent to this.

$\begin{aligned} a_{1} c_{1, 1} + \dots + a_{k} c_{1, k} & = 0 \\ ⋮ \\ a_{1} c_{n, 1} + \dots + a_{k} c_{n, k} & = 0 \end{aligned}$

This is the equivalent recast into column vectors.

$a_{1} (\begin{matrix} c_{1, 1} \\ ⋮ \\ c_{n, 1} \end{matrix}) + \dots + a_{k} (\begin{matrix} c_{1, k} \\ ⋮ \\ c_{n, k} \end{matrix}) = (\begin{matrix} 0 \\ ⋮ \\ 0 \end{matrix})$

Note that not only does a relationship hold for one set if and only if it holds for the other, but it is the same relationship—the $a_{i}$ are the same.

QED

Example 1.19 Example 1.14 finds the representation of $x + x^{2} \in 𝒫_{3}$ with respect to $B = ⟨ 1, 2 x, 2 x^{2}, 2 x^{3} ⟩$ .

${Rep}_{B} (x + x^{2}) = {(\begin{matrix} 0 \\ 1 / 2 \\ 1 / 2 \\ 0 \end{matrix})}_{B}$

This relationship

$2 \cdot (x + x^{2}) - 1 \cdot (2 x) - 2 \cdot (x^{2}) = 0 + 0 x + 0 x^{2} + 0 x^{3}$

is represented by this one.

$2 \cdot {Rep}_{B} (x + x^{2}) - {Rep}_{B} (2 x) - 2 \cdot {Rep}_{B} (x^{2}) = 2 \cdot (\begin{matrix} 0 \\ 1 / 2 \\ 1 / 2 \\ 0 \end{matrix}) - (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}) - 2 \cdot (\begin{matrix} 0 \\ 0 \\ 1 / 2 \\ 0 \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix})$

Our main use of representations will come later but the definition appears here because the fact that every vector is a linear combination of basis vectors in a unique way is a crucial property of bases, and also to help make a point. For calculation of coordinates among other things, we shall restrict our attention to spaces with bases having only finitely many elements. That will start in the next subsection.

Exercises

Exercise 1.20 Worked answer

Recommended. Decide if each is a basis for $𝒫_{2}$ .
1. $⟨ x^{2} - x + 1, 2 x + 1, 2 x - 1 ⟩$
2. $⟨ x + x^{2}, x - x^{2} ⟩$
Back to Exercise 1.20

Answer.
1. This is a basis for $𝒫_{2}$ . To show that it spans the space we consider a generic $a_{2} x^{2} + a_{1} x + a_{0} \in 𝒫_{2}$ and look for scalars $c_{1}, c_{2}, c_{3} \in ℝ$ such that $a_{2} x^{2} + a_{1} x + a_{0} = c_{1} \cdot (x^{2} - x + 1) + c_{2} \cdot (2 x + 1) + c_{3} (2 x - 1)$ . The resulting linear system is this.
  
  $\begin{array}{rcrcrcr} c_{1} & = & a_{2} \\ 2 c_{2} & + & 2 c_{3} & = & a_{1} \\ c_{2} & - & c_{3} & = & a_{0} \end{array} ⟶_{\begin{array}{l} \end{array}}^{(- 1 / 2) ρ_{2} + ρ_{3}} \begin{array}{rcrcrcr} c_{1} & = & a_{2} \\ 2 c_{2} & + & 2 c_{3} & = & a_{1} \\ - 2 c_{3} & = & a_{0} - (1 / 2) a_{1} \end{array}$
  
  Thus, given any triple of $a_{i}$ ’s, we can compute the $c_{j}$ ’s as $c_{1} = a_{2}$ , $c_{2} = (1 / 4) a_{1} + (1 / 2) a_{0}$ , and $c_{3} = (1 / 4) a_{1} - (1 / 2) a_{0}$ . Therefore each element of $𝒫_{2}$ is a combination of the given $x^{2} - x + 1$ , $2 x + 1$ , and $2 x - 1$ .
  
  To prove that the set of the given three is linearly independent we can set up the equation $0 x^{2} + 0 x + 0 = c_{1} \cdot (x^{2} - x + 1) + c_{2} \cdot (2 x + 1) + c_{3} (2 x - 1)$ and solve, and it will give that $c_{1} = 0$ , $c_{2} = 0$ , and $c_{3} = 0$ . Or, we can instead observe that the solution in the prior paragraph is unique, and cite Theorem 1.12.
2. This is not a basis. It does not span the space since no combination of the two $c_{1} \cdot (x + x^{2}) + c_{2} \cdot (x - x^{2})$ will sum to the polynomial $3 \in 𝒫_{2}$ .
Exercise 1.21 Worked answer

Recommended. Decide if each is a basis for $ℝ^{3}$ .
1. $⟨ (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}), (\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) ⟩$
2. $⟨ (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}), (\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}) ⟩$
3. $⟨ (\begin{matrix} 0 \\ 2 \\ - 1 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 2 \\ 5 \\ 0 \end{matrix}) ⟩$
4. $⟨ (\begin{matrix} 0 \\ 2 \\ - 1 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 1 \\ 3 \\ 0 \end{matrix}) ⟩$
Back to Exercise 1.21

Answer. By Theorem 1.12, each is a basis if and only if we can express each vector in the space in a unique way as a linear combination of the given vectors.
1. Yes this is a basis. The relation
  
  $c_{1} (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) + c_{2} (\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}) + c_{3} (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) = (\begin{matrix} x \\ y \\ z \end{matrix})$
  
  gives
  
  $(\begin{array}{cccc} 1 & 3 & 0 & x \\ 2 & 2 & 0 & y \\ 3 & 1 & 1 & z \end{array}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{3}} (\begin{array}{cccc} 1 & 3 & 0 & x \\ 0 & - 4 & 0 & - 2 x + y \\ 0 & 0 & 1 & x - 2 y + z \end{array})$
  
  which has the unique solution $c_{3} = x - 2 y + z$ , $c_{2} = x / 2 - y / 4$ , and $c_{1} = - x / 2 + 3 y / 4$ .
2. This is not a basis. Setting it up as in the prior item
  
  $c_{1} (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) + c_{2} (\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}) = (\begin{matrix} x \\ y \\ z \end{matrix})$
  
  gives a linear system whose solution
  
  $(\begin{array}{ccc} 1 & 3 & x \\ 2 & 2 & y \\ 3 & 1 & z \end{array}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{3}} (\begin{array}{ccc} 1 & 3 & x \\ 0 & - 4 & - 2 x + y \\ 0 & 0 & x - 2 y + z \end{array})$
  
  is possible if and only if the three-tall vector’s components $x$ , $y$ , and $z$ satisfy $x - 2 y + z = 0$ . For instance, we can find the coefficients $c_{1}$ and $c_{2}$ that work when $x = 1$ , $y = 1$ , and $z = 1$ . However, there are no $c$ ’s that work for $x = 1$ , $y = 1$ , and $z = 2$ . Thus this is not a basis; it does not span the space.
3. Yes, this is a basis. Setting up the relationship leads to this reduction
  
  $(\begin{array}{cccc} 0 & 1 & 2 & x \\ 2 & 1 & 5 & y \\ - 1 & 1 & 0 & z \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- (1 / 3) ρ_{2} + ρ_{3}} (\begin{array}{cccc} - 1 & 1 & 0 & z \\ 0 & 3 & 5 & y + 2 z \\ 0 & 0 & 1 / 3 & x - y / 3 - 2 z / 3 \end{array})$
  
  which has a unique solution for each triple of components $x$ , $y$ , and $z$ .
4. No, this is not a basis. The reduction
  
  $(\begin{array}{cccc} 0 & 1 & 1 & x \\ 2 & 1 & 3 & y \\ - 1 & 1 & 0 & z \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{(- 1 / 3) ρ_{2} + ρ_{3}} (\begin{array}{cccc} - 1 & 1 & 0 & z \\ 0 & 3 & 3 & y + 2 z \\ 0 & 0 & 0 & x - y / 3 - 2 z / 3 \end{array})$
  
  which does not have a solution for each triple $x$ , $y$ , and $z$ . Instead, the span of the given set includes only those three-tall vectors where $x = y / 3 + 2 z / 3$ .
Exercise 1.22 Worked answer

Recommended. Represent the vector with respect to the basis.
1. $(\begin{matrix} 1 \\ 2 \end{matrix})$ , $B = ⟨ (\begin{matrix} 1 \\ 1 \end{matrix}), (\begin{matrix} - 1 \\ 1 \end{matrix}) ⟩ \subseteq ℝ^{2}$
2. $x^{2} + x^{3}$ , $D = ⟨ 1, 1 + x, 1 + x + x^{2}, 1 + x + x^{2} + x^{3} ⟩ \subseteq 𝒫_{3}$
3. $(\begin{matrix} 0 \\ - 1 \\ 0 \\ 1 \end{matrix})$ , $ℰ_{4} \subseteq ℝ^{4}$
Back to Exercise 1.22

Answer.
1. We solve
  
  $c_{1} (\begin{matrix} 1 \\ 1 \end{matrix}) + c_{2} (\begin{matrix} - 1 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix})$
  
  with
  
  $(\begin{array}{ccr} 1 & - 1 & 1 \\ 1 & 1 & 2 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} (\begin{array}{ccr} 1 & - 1 & 1 \\ 0 & 2 & 1 \end{array})$
  
  and conclude that $c_{2} = 1 / 2$ and so $c_{1} = 3 / 2$ . Thus, the representation is this.
  
  ${Rep}_{B} ((\begin{matrix} 1 \\ 2 \end{matrix})) = {(\begin{matrix} 3 / 2 \\ 1 / 2 \end{matrix})}_{B}$
2. The relationship $c_{1} \cdot (1) + c_{2} \cdot (1 + x) + c_{3} \cdot (1 + x + x^{2}) + c_{4} \cdot (1 + x + x^{2} + x^{3}) = x^{2} + x^{3}$ is easily solved by eye to give that $c_{4} = 1$ , $c_{3} = 0$ , $c_{2} = - 1$ , and $c_{1} = 0$ .
  
  ${Rep}_{D} (x^{2} + x^{3}) = {(\begin{matrix} 0 \\ - 1 \\ 0 \\ 1 \end{matrix})}_{D}$
3. ${Rep}_{ℰ_{4}} ((\begin{matrix} 0 \\ - 1 \\ 0 \\ 1 \end{matrix})) = {(\begin{matrix} 0 \\ - 1 \\ 0 \\ 1 \end{matrix})}_{ℰ_{4}}$
Exercise 1.23 Worked answer

Represent the vector with respect to each of the two bases.

$\vec{v} = (\begin{matrix} 3 \\ - 1 \end{matrix}) B_{1} = ⟨ (\begin{matrix} 1 \\ - 1 \end{matrix}), (\begin{matrix} 1 \\ 1 \end{matrix}) ⟩, B_{2} = ⟨ (\begin{matrix} 1 \\ 2 \end{matrix}), (\begin{matrix} 1 \\ 3 \end{matrix}) ⟩$

Back to Exercise 1.23

Answer. Solving

$(\begin{matrix} 3 \\ - 1 \end{matrix}) = (\begin{matrix} 1 \\ - 1 \end{matrix}) \cdot c_{1} + (\begin{matrix} 1 \\ 1 \end{matrix}) \cdot c_{2}$

gives $c_{1} = 2$ and $c_{2} = 1$ .

${Rep}_{B_{1}} ((\begin{matrix} 3 \\ - 1 \end{matrix})) = {(\begin{matrix} 2 \\ 1 \end{matrix})}_{B_{1}}$

Similarly, solving

$(\begin{matrix} 3 \\ - 1 \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix}) \cdot c_{1} + (\begin{matrix} 1 \\ 3 \end{matrix}) \cdot c_{2}$

gives this.

${Rep}_{B_{2}} ((\begin{matrix} 3 \\ - 1 \end{matrix})) = {(\begin{matrix} 10 \\ - 7 \end{matrix})}_{B_{2}}$
Exercise 1.24 Worked answer

Find a basis for $𝒫_{2}$ , the space of all quadratic polynomials. Must any such basis contain a polynomial of each degree: degree zero, degree one, and degree two?

Back to Exercise 1.24

Answer. A natural basis is $⟨ 1, x, x^{2} ⟩$ . There are bases for $𝒫_{2}$ that do not contain any polynomials of degree one or degree zero. One is $⟨ 1 + x + x^{2}, x + x^{2}, x^{2} ⟩$ . (Every basis has at least one polynomial of degree two, though.)
Exercise 1.25 Worked answer

Find a basis for the solution set of this system.

$\begin{array}{rcrcrcrcr} x_{1} & - & 4 x_{2} & + & 3 x_{3} & - & x_{4} & = & 0 \\ 2 x_{1} & - & 8 x_{2} & + & 6 x_{3} & - & 2 x_{4} & = & 0 \end{array}$

Back to Exercise 1.25

Answer. The reduction

$(\begin{array}{ccccr} 1 & - 4 & 3 & - 1 & 0 \\ 2 & - 8 & 6 & - 2 & 0 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{ccccr} 1 & - 4 & 3 & - 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array})$

gives that the only condition is that $x_{1} = 4 x_{2} - 3 x_{3} + x_{4}$ . The solution set is

$\begin{matrix} {(\begin{matrix} 4 x_{2} - 3 x_{3} + x_{4} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}) ∣ x_{2}, x_{3}, x_{4} \in ℝ} \\ = {x_{2} (\begin{matrix} 4 \\ 1 \\ 0 \\ 0 \end{matrix}) + x_{3} (\begin{matrix} - 3 \\ 0 \\ 1 \\ 0 \end{matrix}) + x_{4} (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) ∣ x_{2}, x_{3}, x_{4} \in ℝ} \end{matrix}$

and so the obvious candidate for the basis is this.

$⟨ (\begin{matrix} 4 \\ 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} - 3 \\ 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) ⟩$

We’ve shown that this spans the space, and showing it is also linearly independent is routine.
Exercise 1.26 Worked answer

Recommended. Find a basis for $ℳ_{2 \times 2}$ , the space of $2 \times 2$ matrices.

Back to Exercise 1.26

Answer. There are many bases. This is a natural one.

$⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ⟩$
Exercise 1.27 Worked answer

Recommended. Find a basis for each.
1. The subspace ${a_{2} x^{2} + a_{1} x + a_{0} ∣ a_{2} - 2 a_{1} = a_{0}}$ of $𝒫_{2}$
2. The space of three-wide row vectors whose first and second components add to zero
3. This subspace of the $2 \times 2$ matrices
  
  ${(\begin{matrix} a & b \\ 0 & c \end{matrix}) ∣ c - 2 b = 0}$
Back to Exercise 1.27

Answer. For each item, many answers are possible.
1. One way to proceed is to parametrize by expressing the $a_{2}$ as a combination of the other two $a_{2} = 2 a_{1} + a_{0}$ . Then $a_{2} x^{2} + a_{1} x + a_{0}$ is $(2 a_{1} + a_{0}) x^{2} + a_{1} x + a_{0}$ and
  
  $\begin{matrix} {(2 a_{1} + a_{0}) x^{2} + a_{1} x + a_{0} ∣ a_{1}, a_{0} \in ℝ} \\ = {a_{1} \cdot (2 x^{2} + x) + a_{0} \cdot (x^{2} + 1) ∣ a_{1}, a_{0} \in ℝ} \end{matrix}$
  
  suggests $⟨ 2 x^{2} + x, x^{2} + 1 ⟩$ . This only shows that it spans, but checking that it is linearly independent is routine.
2. Parametrize ${(\begin{matrix} a & b & c \end{matrix}) ∣ a + b = 0}$ to get ${(\begin{matrix} - b & b & c \end{matrix}) ∣ b, c \in ℝ}$ , which suggests using the sequence $⟨ (\begin{matrix} - 1 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 1 \end{matrix}) ⟩$ . We’ve shown that it spans, and checking that it is linearly independent is easy.
3. Rewriting
  
  ${(\begin{matrix} a & b \\ 0 & 2 b \end{matrix}) ∣ a, b \in ℝ} = {a \cdot (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) + b \cdot (\begin{matrix} 0 & 1 \\ 0 & 2 \end{matrix}) ∣ a, b \in ℝ}$
  
  suggests this for the basis.
  
  $⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ 0 & 2 \end{matrix}) ⟩$
Exercise 1.28 Worked answer

Find a basis for each space, and verify that it is a basis.
1. The subspace $M = {a + b x + c x^{2} + d x^{3} ∣ a - 2 b + c - d = 0}$ of $𝒫_{3}$ .
2. This subspace of $ℳ_{2 \times 2}$ .
  
  $W = {(\begin{matrix} a & b \\ c & d \end{matrix}) ∣ a - c = 0}$
Back to Exercise 1.28

Answer.
1. Parametrize $a - 2 b + c - d = 0$ as $a = 2 b - c + d$ , $b = b$ , $c = c$ , and $d = d$ to get this description of $M$ as the span of a set of three vectors.
  
  $M = {(2 + x) \cdot b + (- 1 + x^{2}) \cdot c + (1 + x^{3}) \cdot d ∣ b, c, d \in ℝ}$
  
  To show that this three-vector set is a basis, what remains is to verify that it is linearly independent.
  
  $0 + 0 x + 0 x^{2} + 0 x^{3} = (2 + x) \cdot c_{1} + (- 1 + x^{2}) \cdot c_{2} + (1 + x^{3}) \cdot c_{3}$
  
  From the $x$ terms we see that $c_{1} = 0$ . From the $x^{2}$ terms we see that $c_{2} = 0$ . The $x^{3}$ terms give that $c_{3} = 0$ .
2. First parametrize the description (note that the fact that $b$ and $d$ are not mentioned in the description of $W$ does not mean they are zero or absent, it means that they are unrestricted).
  
  $W = {(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) \cdot b + (\begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix}) \cdot c + (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) \cdot d ∣ b, c, d \in ℝ}$
  
  That gives $W$ as the span of a three element set. We will be done if we show that the set is linearly independent.
  
  $(\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) \cdot c_{1} + (\begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix}) \cdot c_{2} + (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) \cdot c_{3}$
  
  Using the upper right entries we see that $c_{1} = 0$ . The upper left entries give that $c_{2} = 0$ , and the lower left entries show that $c_{3} = 0$ .
Exercise 1.29 Worked answer

Check Example 1.6.

Back to Exercise 1.29

Answer. We will show that the second is a basis; the first is similar. We will show this straight from the definition of a basis, because this example appears before Theorem 1.12.

To see that it is linearly independent, we set up $c_{1} \cdot (\cos θ - \sin θ) + c_{2} \cdot (2 \cos θ + 3 \sin θ) = 0 \cos θ + 0 \sin θ$ . Taking $θ = 0$ and $θ = π / 2$ gives this system

$\begin{array}{rcrcr} c_{1} \cdot 1 & + & c_{2} \cdot 2 & = & 0 \\ c_{1} \cdot (- 1) & + & c_{2} \cdot 3 & = & 0 \end{array} ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{2}} \begin{array}{rcrcr} c_{1} & + & 2 c_{2} & = & 0 \\ + & 5 c_{2} & = & 0 \end{array}$

which shows that $c_{1} = 0$ and $c_{2} = 0$ .

The calculation for span is also easy; for any $x, y \in ℝ$ , we have that $c_{1} \cdot (\cos θ - \sin θ) + c_{2} \cdot (2 \cos θ + 3 \sin θ) = x \cos θ + y \sin θ$ gives that $c_{2} = x / 5 + y / 5$ and that $c_{1} = 3 x / 5 - 2 y / 5$ , and so the span is the entire space.
Exercise 1.30 Worked answer

Recommended. Find the span of each set and then find a basis for that span.
1. ${1 + x, 1 + 2 x}$ in $𝒫_{2}$
2. ${2 - 2 x, 3 + 4 x^{2}}$ in $𝒫_{2}$
Back to Exercise 1.30

Answer.
1. Asking which $a_{0} + a_{1} x + a_{2} x^{2}$ can be expressed as $c_{1} \cdot (1 + x) + c_{2} \cdot (1 + 2 x)$ gives rise to three linear equations, describing the coefficients of $x^{2}$ , $x$ , and the constants.
  
  $\begin{array}{rcrcr} c_{1} & + & c_{2} & = & a_{0} \\ c_{1} & + & 2 c_{2} & = & a_{1} \\ 0 & = & a_{2} \end{array}$
  
  Gauss’s Method with back-substitution shows, provided that $a_{2} = 0$ , that $c_{2} = - a_{0} + a_{1}$ and $c_{1} = 2 a_{0} - a_{1}$ . Thus, with $a_{2} = 0$ , we can compute appropriate $c_{1}$ and $c_{2}$ for any $a_{0}$ and $a_{1}$ . So the span is the entire set of linear polynomials ${a_{0} + a_{1} x ∣ a_{0}, a_{1} \in ℝ}$ . Parametrizing that set ${a_{0} \cdot 1 + a_{1} \cdot x ∣ a_{0}, a_{1} \in ℝ}$ suggests a basis $⟨ 1, x ⟩$ (we’ve shown that it spans; checking linear independence is easy).
2. With
  
  $a_{0} + a_{1} x + a_{2} x^{2} = c_{1} \cdot (2 - 2 x) + c_{2} \cdot (3 + 4 x^{2}) = (2 c_{1} + 3 c_{2}) + (- 2 c_{1}) x + (4 c_{2}) x^{2}$
  
  we get this system.
  
  $\begin{array}{rcrcr} 2 c_{1} & + & 3 c_{2} & = & a_{0} \\ - 2 c_{1} & = & a_{1} \\ 4 c_{2} & = & a_{2} \end{array} ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{(- 4 / 3) ρ_{2} + ρ_{3}} \begin{array}{rcrcr} 2 c_{1} & + & 3 c_{2} & = & a_{0} \\ 3 c_{2} & = & a_{0} + a_{1} \\ 0 & = & (- 4 / 3) a_{0} - (4 / 3) a_{1} + a_{2} \end{array}$
  
  Thus, the only quadratic polynomials $a_{0} + a_{1} x + a_{2} x^{2}$ with associated $c$ ’s are the ones such that $0 = (- 4 / 3) a_{0} - (4 / 3) a_{1} + a_{2}$ . Hence the span is this.
  
  ${(- a_{1} + (3 / 4) a_{2}) + a_{1} x + a_{2} x^{2} ∣ a_{1}, a_{2} \in ℝ}$
  
  Parametrizing gives ${a_{1} \cdot (- 1 + x) + a_{2} \cdot ((3 / 4) + x^{2}) ∣ a_{1}, a_{2} \in ℝ}$ , which suggests $⟨ - 1 + x, (3 / 4) + x^{2} ⟩$ (checking that it is linearly independent is routine).
Exercise 1.31 Worked answer

Recommended. Find a basis for each of these subspaces of the space $𝒫_{3}$ of cubic polynomials.
1. The subspace of cubic polynomials $p (x)$ such that $p (7) = 0$
2. The subspace of polynomials $p (x)$ such that $p (7) = 0$ and $p (5) = 0$
3. The subspace of polynomials $p (x)$ such that $p (7) = 0$ , $p (5) = 0$ , and $p (3) = 0$
4. The space of polynomials $p (x)$ such that $p (7) = 0$ , $p (5) = 0$ , $p (3) = 0$ , and $p (1) = 0$
Back to Exercise 1.31

Answer.
1. The subspace is this.
  
  ${a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} ∣ a_{0} + 7 a_{1} + 49 a_{2} + 343 a_{3} = 0}$
  
  Rewriting $a_{0} = - 7 a_{1} - 49 a_{2} - 343 a_{3}$ gives this.
  
  ${(- 7 a_{1} - 49 a_{2} - 343 a_{3}) + a_{1} x + a_{2} x^{2} + a_{3} x^{3} ∣ a_{1}, a_{2}, a_{3} \in ℝ}$
  
  On breaking out the parameters, this suggests $⟨ - 7 + x, - 49 + x^{2}, - 343 + x^{3} ⟩$ for the basis (it is easily verified).
2. The given subspace is the collection of cubics $p (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}$ such that $a_{0} + 7 a_{1} + 49 a_{2} + 343 a_{3} = 0$ and $a_{0} + 5 a_{1} + 25 a_{2} + 125 a_{3} = 0$ . Gauss’s Method
  
  $\begin{array}{rcrcrcrcr} a_{0} & + & 7 a_{1} & + & 49 a_{2} & + & 343 a_{3} & = & 0 \\ a_{0} & + & 5 a_{1} & + & 25 a_{2} & + & 125 a_{3} & = & 0 \end{array} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} \begin{array}{rcrcrcrcr} a_{0} & + & 7 a_{1} & + & 49 a_{2} & + & 343 a_{3} & = & 0 \\ - 2 a_{1} & - & 24 a_{2} & - & 218 a_{3} & = & 0 \end{array}$
  
  gives that $a_{1} = - 12 a_{2} - 109 a_{3}$ and that $a_{0} = 35 a_{2} + 420 a_{3}$ . Rewriting $(35 a_{2} + 420 a_{3}) + (- 12 a_{2} - 109 a_{3}) x + a_{2} x^{2} + a_{3} x^{3}$ as $a_{2} \cdot (35 - 12 x + x^{2}) + a_{3} \cdot (420 - 109 x + x^{3})$ suggests this for a basis $⟨ 35 - 12 x + x^{2}, 420 - 109 x + x^{3} ⟩$ . The above shows that it spans the space. Checking it is linearly independent is routine. (Comment. A worthwhile check is to verify that both polynomials in the basis have both seven and five as roots.)
3. Here there are three conditions on the cubics, that $a_{0} + 7 a_{1} + 49 a_{2} + 343 a_{3} = 0$ , that $a_{0} + 5 a_{1} + 25 a_{2} + 125 a_{3} = 0$ , and that $a_{0} + 3 a_{1} + 9 a_{2} + 27 a_{3} = 0$ . Gauss’s Method
  
  $\begin{array}{rcrcrcrcr} a_{0} & + & 7 a_{1} & + & 49 a_{2} & + & 343 a_{3} & = & 0 \\ a_{0} & + & 5 a_{1} & + & 25 a_{2} & + & 125 a_{3} & = & 0 \\ a_{0} & + & 3 a_{1} & + & 9 a_{2} & + & 27 a_{3} & = & 0 \end{array} ⟶_{\begin{array}{l} - ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{3}} \begin{array}{rcrcrcrcr} a_{0} & + & 7 a_{1} & + & 49 a_{2} & + & 343 a_{3} & = & 0 \\ - 2 a_{1} & - & 24 a_{2} & - & 218 a_{3} & = & 0 \\ 8 a_{2} & + & 120 a_{3} & = & 0 \end{array}$
  
  yields the single free variable $a_{3}$ , with $a_{2} = - 15 a_{3}$ , $a_{1} = 71 a_{3}$ , and $a_{0} = - 105 a_{3}$ . The parametrization is this.
  
  $\begin{matrix} {(- 105 a_{3}) + (71 a_{3}) x + (- 15 a_{3}) x^{2} + (a_{3}) x^{3} ∣ a_{3} \in ℝ} \\ = {a_{3} \cdot (- 105 + 71 x - 15 x^{2} + x^{3}) ∣ a_{3} \in ℝ} \end{matrix}$
  
  Therefore, a natural candidate for the basis is $⟨ - 105 + 71 x - 15 x^{2} + x^{3} ⟩$ . It spans the space by the work above. It is clearly linearly independent because it is a one-element set (with that single element not the zero object of the space). Thus, any cubic through the three points $(7, 0)$ , $(5, 0)$ , and $(3, 0)$ is a multiple of this one. (Comment. As in the prior question, a worthwhile check is to verify that plugging seven, five, and three into this polynomial yields zero each time.)
4. This is the trivial subspace of $𝒫_{3}$ . Thus, the basis is empty $⟨ ⟩$ .
Remark. Alternatively, we could have derived the polynomial in the third item by multiplying out $(x - 7) (x - 5) (x - 3)$ .
Exercise 1.32 Worked answer

We’ve seen that the result of reordering a basis can be another basis. Must it be?

Back to Exercise 1.32

Answer. Yes. Linear independence and span are unchanged by reordering.
Exercise 1.33 Worked answer

Can a basis contain a zero vector?

Back to Exercise 1.33

Answer. No linearly independent set contains a zero vector.
Exercise 1.34 Worked answer

Recommended. Let $⟨ {\vec{β}}_{1}, {\vec{β}}_{2}, {\vec{β}}_{3} ⟩$ be a basis for a vector space.
1. Show that $⟨ c_{1} {\vec{β}}_{1}, c_{2} {\vec{β}}_{2}, c_{3} {\vec{β}}_{3} ⟩$ is a basis when $c_{1}, c_{2}, c_{3} \neq 0$ . What happens when at least one $c_{i}$ is $0$ ?
2. Prove that $⟨ {\vec{α}}_{1}, {\vec{α}}_{2}, {\vec{α}}_{3} ⟩$ is a basis where ${\vec{α}}_{i} = {\vec{β}}_{1} + {\vec{β}}_{i}$ .
Back to Exercise 1.34

Answer.
1. To show that it is linearly independent, note that if $d_{1} (c_{1} {\vec{β}}_{1}) + d_{2} (c_{2} {\vec{β}}_{2}) + d_{3} (c_{3} {\vec{β}}_{3}) = \vec{0}$ then $(d_{1} c_{1}) {\vec{β}}_{1} + (d_{2} c_{2}) {\vec{β}}_{2} + (d_{3} c_{3}) {\vec{β}}_{3} = \vec{0}$ , which in turn implies that each $d_{i} c_{i}$ is zero. But with $c_{i} \neq 0$ that means that each $d_{i}$ is zero. Showing that it spans the space is much the same; because $⟨ {\vec{β}}_{1}, {\vec{β}}_{2}, {\vec{β}}_{3} ⟩$ is a basis, and so spans the space, we can for any $\vec{v}$ write $\vec{v} = d_{1} {\vec{β}}_{1} + d_{2} {\vec{β}}_{2} + d_{3} {\vec{β}}_{3}$ , and then $\vec{v} = (d_{1} / c_{1}) (c_{1} {\vec{β}}_{1}) + (d_{2} / c_{2}) (c_{2} {\vec{β}}_{2}) + (d_{3} / c_{3}) (c_{3} {\vec{β}}_{3})$ .
  
  If any of the scalars are zero then the result is not a basis, because it is not linearly independent.
2. Showing that $⟨ 2 {\vec{β}}_{1}, {\vec{β}}_{1} + {\vec{β}}_{2}, {\vec{β}}_{1} + {\vec{β}}_{3} ⟩$ is linearly independent is easy. To show that it spans the space, assume that $\vec{v} = d_{1} {\vec{β}}_{1} + d_{2} {\vec{β}}_{2} + d_{3} {\vec{β}}_{3}$ . Then, we can represent the same $\vec{v}$ with respect to $⟨ 2 {\vec{β}}_{1}, {\vec{β}}_{1} + {\vec{β}}_{2}, {\vec{β}}_{1} + {\vec{β}}_{3} ⟩$ in this way $\vec{v} = (1 / 2) (d_{1} - d_{2} - d_{3}) (2 {\vec{β}}_{1}) + d_{2} ({\vec{β}}_{1} + {\vec{β}}_{2}) + d_{3} ({\vec{β}}_{1} + {\vec{β}}_{3})$ .
Exercise 1.35 Worked answer

Find one vector $\vec{v}$ that will make each into a basis for the space.
1. $⟨ (\begin{matrix} 1 \\ 1 \end{matrix}), \vec{v} ⟩$ in $ℝ^{2}$
2. $⟨ (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}), \vec{v} ⟩$ in $ℝ^{3}$
3. $⟨ x, 1 + x^{2}, \vec{v} ⟩$ in $𝒫_{2}$
Back to Exercise 1.35

Answer. Each forms a linearly independent set if we omit $\vec{v}$ . To preserve linear independence, we must expand the span of each. That is, we must determine the span of each (leaving $\vec{v}$ out), and then pick a $\vec{v}$ lying outside of that span. Then to finish, we must check that the result spans the entire given space. Those checks are routine.
1. Any vector that is not a multiple of the given one, that is, any vector that is not on the line $y = x$ will do here. One is $\vec{v} = {\vec{e}}_{1}$ .
2. By inspection, we notice that the vector ${\vec{e}}_{3}$ is not in the span of the set of the two given vectors. The check that the resulting set is a basis for $ℝ^{3}$ is routine.
3. For any member of the span ${c_{1} \cdot (x) + c_{2} \cdot (1 + x^{2}) ∣ c_{1}, c_{2} \in ℝ}$ , the coefficient of $x^{2}$ equals the constant term. So we expand the span if we add a quadratic without this property, say, $\vec{v} = 1 - x^{2}$ . The check that the result is a basis for $𝒫_{2}$ is easy.
Exercise 1.36 Worked answer

Recommended. Consider $2 + 4 x^{2}, 1 + 3 x^{2}, 1 + 5 x^{2} \in 𝒫_{2}$ .
1. Find a linear relationship among the three.
2. Represent them with respect to $B = ⟨ 1 - x, 1 + x, x^{2} ⟩$ .
3. Check that the same linear relationship holds among the representations, as in Lemma 1.18.
Back to Exercise 1.36

Answer.
1. $1 \cdot (2 + 4 x^{2}) - 3 \cdot (1 + 3 x^{2}) + 1 \cdot (1 + 5 x^{2}) = 0 + 0 x + 0 x^{2}$
2. Simple calculation gives this.
  
  ${Rep}_{B} (2 + 4 x^{2}) = (\begin{matrix} 1 \\ 1 \\ 4 \end{matrix}) {Rep}_{B} (1 + 3 x^{2}) = (\begin{matrix} 1 / 2 \\ 1 / 2 \\ 3 \end{matrix}) {Rep}_{B} (1 + 5 x^{2}) = (\begin{matrix} 1 / 2 \\ 1 / 2 \\ 5 \end{matrix})$
3. The check is straightforward.
  
  $1 \cdot (\begin{matrix} 1 \\ 1 \\ 4 \end{matrix}) - 3 \cdot (\begin{matrix} 1 / 2 \\ 1 / 2 \\ 3 \end{matrix}) + 1 \cdot (\begin{matrix} 1 / 2 \\ 1 / 2 \\ 5 \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix})$
Exercise 1.37 Worked answer

Recommended. Where $⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ is a basis, show that in this equation

$c_{1} {\vec{β}}_{1} + \dots + c_{k} {\vec{β}}_{k} = c_{k + 1} {\vec{β}}_{k + 1} + \dots + c_{n} {\vec{β}}_{n}$

each of the $c_{i}$ ’s is zero. Generalize.

Back to Exercise 1.37

Answer. To show that each scalar is zero, simply subtract $c_{1} {\vec{β}}_{1} + \dots + c_{k} {\vec{β}}_{k} - c_{k + 1} {\vec{β}}_{k + 1} - \dots - c_{n} {\vec{β}}_{n} = \vec{0}$ . The obvious generalization is that in any equation involving only the $\vec{β}$ ’s, and in which each $\vec{β}$ appears only once, each scalar is zero. For instance, an equation with a combination of the even-indexed basis vectors (i.e., ${\vec{β}}_{2}$ , ${\vec{β}}_{4}$ , etc.) on the right and the odd-indexed basis vectors on the left also gives the conclusion that all of the coefficients are zero.
Exercise 1.38 Worked answer

A basis contains some of the vectors from a vector space; can it contain them all?

Back to Exercise 1.38

Answer. No; no linearly independent set contains the zero vector.
Exercise 1.39 Worked answer

Theorem 1.12 shows that, with respect to a basis, every linear combination is unique. If a subset is not a basis, can linear combinations be not unique? If so, must they be?

Back to Exercise 1.39

Answer. Here is a subset of $ℝ^{2}$ that is not a basis, and two different linear combinations of its elements that sum to the same vector.

${(\begin{matrix} 1 \\ 2 \end{matrix}), (\begin{matrix} 2 \\ 4 \end{matrix})} 2 \cdot (\begin{matrix} 1 \\ 2 \end{matrix}) + 0 \cdot (\begin{matrix} 2 \\ 4 \end{matrix}) = 0 \cdot (\begin{matrix} 1 \\ 2 \end{matrix}) + 1 \cdot (\begin{matrix} 2 \\ 4 \end{matrix})$

Thus, when a subset is not a basis, it can be the case that its linear combinations are not unique.

But just because a subset is not a basis does not imply that its combinations must be not unique. For instance, this set

${(\begin{matrix} 1 \\ 2 \end{matrix})}$

does have the property that

$c_{1} \cdot (\begin{matrix} 1 \\ 2 \end{matrix}) = c_{2} \cdot (\begin{matrix} 1 \\ 2 \end{matrix})$

implies that $c_{1} = c_{2}$ . The idea here is that this subset fails to be a basis because it fails to span the space; the proof of the theorem establishes that linear combinations are unique if and only if the subset is linearly independent.
Exercise 1.40 Worked answer

A square matrix is symmetric if for all indices $i$ and $j$ , entry $i, j$ equals entry $j, i$ .
1. Find a basis for the vector space of symmetric $2 \times 2$ matrices.
2. Find a basis for the space of symmetric $3 \times 3$ matrices.
3. Find a basis for the space of symmetric $n \times n$ matrices.
Back to Exercise 1.40

Answer.
1. Describing the vector space as
  
  ${(\begin{matrix} a & b \\ b & c \end{matrix}) ∣ a, b, c \in ℝ}$
  
  suggests this for a basis.
  
  $⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) ⟩$
  
  Verification is easy.
2. This is one possible basis.
  
  $⟨ (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) ⟩$
3. As in the prior two questions, we can form a basis from two kinds of matrices. First are the matrices with a single one on the diagonal and all other entries zero (there are $n$ of those matrices). Second are the matrices with two opposed off-diagonal entries are ones and all other entries are zeros. (That is, all entries in $M$ are zero except that $m_{i, j}$ and $m_{j, i}$ are one.)
Exercise 1.41 Worked answer

We can show that every basis for $ℝ^{3}$ contains the same number of vectors.
1. Show that no linearly independent subset of $ℝ^{3}$ contains more than three vectors.
2. Show that no spanning subset of $ℝ^{3}$ contains fewer than three vectors. Hint: recall how to calculate the span of a set and show that this method cannot yield all of $ℝ^{3}$ when we apply it to fewer than three vectors.
Back to Exercise 1.41

Answer.
1. Any four vectors from $ℝ^{3}$ are linearly related because the vector equation
  
  $c_{1} (\begin{matrix} x_{1} \\ y_{1} \\ z_{1} \end{matrix}) + c_{2} (\begin{matrix} x_{2} \\ y_{2} \\ z_{2} \end{matrix}) + c_{3} (\begin{matrix} x_{3} \\ y_{3} \\ z_{3} \end{matrix}) + c_{4} (\begin{matrix} x_{4} \\ y_{4} \\ z_{4} \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix})$
  
  gives rise to a linear system
  
  $\begin{array}{rcrcrcrcr} x_{1} c_{1} & + & x_{2} c_{2} & + & x_{3} c_{3} & + & x_{4} c_{4} & = & 0 \\ y_{1} c_{1} & + & y_{2} c_{2} & + & y_{3} c_{3} & + & y_{4} c_{4} & = & 0 \\ z_{1} c_{1} & + & z_{2} c_{2} & + & z_{3} c_{3} & + & z_{4} c_{4} & = & 0 \end{array}$
  
  that is homogeneous (and so has a solution) and has four unknowns but only three equations, and therefore has nontrivial solutions. (Of course, this argument applies to any subset of $ℝ^{3}$ with four or more vectors.)
2. We shall do just the two-vector case. Given $x_{1}$ , …, $z_{2}$ ,
  
  $S = {(\begin{matrix} x_{1} \\ y_{1} \\ z_{1} \end{matrix}), (\begin{matrix} x_{2} \\ y_{2} \\ z_{2} \end{matrix})}$
  
  to decide which vectors
  
  $(\begin{matrix} x \\ y \\ z \end{matrix})$
  
  are in the span of $S$ , set up
  
  $c_{1} (\begin{matrix} x_{1} \\ y_{1} \\ z_{1} \end{matrix}) + c_{2} (\begin{matrix} x_{2} \\ y_{2} \\ z_{2} \end{matrix}) = (\begin{matrix} x \\ y \\ z \end{matrix})$
  
  and row reduce the resulting system.
  
  $\begin{array}{rcrcr} x_{1} c_{1} & + & x_{2} c_{2} & = & x \\ y_{1} c_{1} & + & y_{2} c_{2} & = & y \\ z_{1} c_{1} & + & z_{2} c_{2} & = & z \end{array}$
  
  There are two variables $c_{1}$ and $c_{2}$ but three equations, so when Gauss’s Method finishes, on the bottom row there will be some relationship of the form $0 = m_{1} x + m_{2} y + m_{3} z$ . Hence, vectors in the span of the two-element set $S$ must satisfy some restriction. Hence the span is not all of $ℝ^{3}$ .
Exercise 1.42 Worked answer

One of the exercises in the Subspaces subsection shows that the set

${(\begin{matrix} x \\ y \\ z \end{matrix}) ∣ x + y + z = 1}$

is a vector space under these operations.

$(\begin{matrix} x_{1} \\ y_{1} \\ z_{1} \end{matrix}) + (\begin{matrix} x_{2} \\ y_{2} \\ z_{2} \end{matrix}) = (\begin{matrix} x_{1} + x_{2} - 1 \\ y_{1} + y_{2} \\ z_{1} + z_{2} \end{matrix}) r (\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} r x - r + 1 \\ r y \\ r z \end{matrix})$

Find a basis.

Back to Exercise 1.42

Answer. We have (using these oddball operations with care)

$\begin{matrix} {(\begin{matrix} 1 - y - z \\ y \\ z \end{matrix}) ∣ y, z \in ℝ} = {(\begin{matrix} - y + 1 \\ y \\ 0 \end{matrix}) + (\begin{matrix} - z + 1 \\ 0 \\ z \end{matrix}) ∣ y, z \in ℝ} \\ = {y \cdot (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}) + z \cdot (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) ∣ y, z \in ℝ} \end{matrix}$

and so a natural candidate for a basis is this.

$⟨ (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) ⟩$

To check linear independence we set up

$c_{1} (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}) + c_{2} (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix})$

(the vector on the right is the zero object in this space). That yields the linear system

$\begin{array}{rcrcrcr} (- c_{1} + 1) & + & (- c_{2} + 1) & - & 1 & = & 1 \\ c_{1} & = & 0 \\ c_{2} & = & 0 \end{array}$

with only the solution $c_{1} = 0$ and $c_{2} = 0$ . Checking the span is similar.

Dimension

The previous subsection defines a basis of a vector space and shows that a space can have many different bases. So we cannot talk about “the” basis for a vector space. True, some vector spaces have bases that strike us as more natural than others, for instance, $ℝ^{2}$ ’s basis $ℰ_{2}$ or $𝒫_{2}$ ’s basis $⟨ 1, x, x^{2} ⟩$ . But for the vector space ${a_{2} x^{2} + a_{1} x + a_{0} ∣ 2 a_{2} - a_{0} = a_{1}}$ , no particular basis leaps out at us as the natural one. We cannot, in general, associate with a space any single basis that best describes it.

We can however find something about the bases that is uniquely associated with the space. This subsection shows that any two bases for a space have the same number of elements. So with each space we can associate a number, the number of vectors in any of its bases.

Before we start, we first limit our attention to spaces where at least one basis has only finitely many members.

Definition 2.1 A vector space is finite-dimensional if it has a basis with only finitely many vectors.

One space that is not finite-dimensional is the set of polynomials with real coefficients, Example 1.11. This is not spanned by any finite subset since that would contain a polynomial of largest degree but this space has polynomials of all degrees. Such spaces are interesting and important but we will focus in a different direction. From now on we will study only finite-dimensional vector spaces. In the rest of this book we shall take ‘vector space’ to mean ‘finite-dimensional vector space’.

To prove the main theorem we shall use a technical result, the Exchange Lemma. We first illustrate it with an example.

Example 2.2 Here is a basis for $ℝ^{3}$ and a vector given as a linear combination of members of that basis.

$B = ⟨ (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix}) ⟩ (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}) = (- 1) \cdot (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + 2 (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}) + 0 \cdot (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix})$

Two of the basis vectors have non-zero coefficients. Pick one, for instance the first. Replace it with the vector that we’ve expressed as the combination

$\hat{B} = ⟨ (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix}) ⟩$

and the result is another basis for $ℝ^{3}$ .

Lemma 2.3 (Exchange Lemma) Assume that $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ is a basis for a vector space, and that for the vector $\vec{v}$ the relationship $\vec{v} = c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} + \dots + c_{n} {\vec{β}}_{n}$ has $c_{i} \neq 0$ . Then exchanging ${\vec{β}}_{i}$ for $\vec{v}$ yields another basis for the space.

Proof Call the outcome of the exchange $\hat{B} = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{i - 1}, \vec{v}, {\vec{β}}_{i + 1}, \dots, {\vec{β}}_{n} ⟩$ .

We first show that $\hat{B}$ is linearly independent. Any relationship $d_{1} {\vec{β}}_{1} + \dots + d_{i} \vec{v} + \dots + d_{n} {\vec{β}}_{n} = \vec{0}$ among the members of $\hat{B}$ , after substitution for $\vec{v}$ ,

$\begin{matrix} d_{1} {\vec{β}}_{1} + \dots + d_{i} \cdot (c_{1} {\vec{β}}_{1} + \dots + c_{i} {\vec{β}}_{i} + \dots + c_{n} {\vec{β}}_{n}) + \dots + d_{n} {\vec{β}}_{n} = \vec{0} & (*) \end{matrix}$

gives a linear relationship among the members of $B$ . The basis $B$ is linearly independent so the coefficient $d_{i} c_{i}$ of ${\vec{β}}_{i}$ is zero. Because we assumed that $c_{i}$ is nonzero, $d_{i} = 0$ . Using this in equation $(*)$ gives that all of the other $d$ ’s are also zero. Therefore $\hat{B}$ is linearly independent.

We finish by showing that $\hat{B}$ has the same span as $B$ . Half of this argument, that $[\hat{B}] \subseteq [B]$ , is easy; we can write any member $d_{1} {\vec{β}}_{1} + \dots + d_{i} \vec{v} + \dots + d_{n} {\vec{β}}_{n}$ of $[\hat{B}]$ as $d_{1} {\vec{β}}_{1} + \dots + d_{i} \cdot (c_{1} {\vec{β}}_{1} + \dots + c_{n} {\vec{β}}_{n}) + \dots + d_{n} {\vec{β}}_{n}$ , which is a linear combination of linear combinations of members of $B$ , and hence is in $[B]$ . For the $[B] \subseteq [\hat{B}]$ half of the argument, recall that if $\vec{v} = c_{1} {\vec{β}}_{1} + \dots + c_{n} {\vec{β}}_{n}$ with $c_{i} \neq 0$ then we can rearrange the equation to ${\vec{β}}_{i} = (- c_{1} / c_{i}) {\vec{β}}_{1} + \dots + (1 / c_{i}) \vec{v} + \dots + (- c_{n} / c_{i}) {\vec{β}}_{n}$ . Now, consider any member $d_{1} {\vec{β}}_{1} + \dots + d_{i} {\vec{β}}_{i} + \dots + d_{n} {\vec{β}}_{n}$ of $[B]$ , substitute for ${\vec{β}}_{i}$ its expression as a linear combination of the members of $\hat{B}$ , and recognize, as in the first half of this argument, that the result is a linear combination of linear combinations of members of $\hat{B}$ , and hence is in $[\hat{B}]$ .

QED

Theorem 2.4 In any finite-dimensional vector space, all bases have the same number of elements.

Proof Fix a vector space with at least one finite basis. Choose, from among all of this space’s bases, one $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ of minimal size. We will show that any other basis $D = ⟨ {\vec{δ}}_{1}, {\vec{δ}}_{2}, \dots ⟩$ also has the same number of members, $n$ . Because $B$ has minimal size, $D$ has no fewer than $n$ vectors. We will argue that it cannot have more than $n$ vectors.

The basis $B$ spans the space and ${\vec{δ}}_{1}$ is in the space, so ${\vec{δ}}_{1}$ is a nontrivial linear combination of elements of $B$ . By the Exchange Lemma, we can swap ${\vec{δ}}_{1}$ for a vector from $B$ , resulting in a basis $B_{1}$ , where one element is ${\vec{δ}}_{1}$ and all of the $n - 1$ other elements are $\vec{β}$ ’s.

The prior paragraph forms the basis step for an induction argument. The inductive step starts with a basis $B_{k}$ (for $1 \leq k < n$ ) containing $k$ members of $D$ and $n - k$ members of $B$ . We know that $D$ has at least $n$ members so there is a ${\vec{δ}}_{k + 1}$ . Represent it as a linear combination of elements of $B_{k}$ . The key point: in that representation, at least one of the nonzero scalars must be associated with a ${\vec{β}}_{i}$ or else that representation would be a nontrivial linear relationship among elements of the linearly independent set $D$ . Exchange ${\vec{δ}}_{k + 1}$ for ${\vec{β}}_{i}$ to get a new basis $B_{k + 1}$ with one $\vec{δ}$ more and one $\vec{β}$ fewer than the previous basis $B_{k}$ .

Repeat that until no $\vec{β}$ ’s remain, so that $B_{n}$ contains ${\vec{δ}}_{1}, \dots, {\vec{δ}}_{n}$ . Now, $D$ cannot have more than these $n$ vectors because any ${\vec{δ}}_{n + 1}$ that remains would be in the span of $B_{n}$ (since it is a basis) and hence would be a linear combination of the other $\vec{δ}$ ’s, contradicting that $D$ is linearly independent.

QED

Definition 2.5 The dimension of a vector space is the number of vectors in any of its bases.

Example 2.6 Any basis for $ℝ^{n}$ has $n$ vectors since the standard basis $ℰ_{n}$ has $n$ vectors. Thus, this definition of ‘dimension’ generalizes the most familiar use of term, that $ℝ^{n}$ is $n$ -dimensional.

Example 2.7 The space $𝒫_{n}$ of polynomials of degree at most $n$ has dimension $n + 1$ . We can show this by exhibiting any basis— $⟨ 1, x, \dots, x^{n} ⟩$ comes to mind—and counting its members.

Example 2.8 The space of functions ${a \cdot \cos θ + b \cdot \sin θ ∣ a, b \in ℝ}$ of the real variable $θ$ has dimension $2$ since this space has the basis $⟨ \cos θ, \sin θ ⟩$ .

Example 2.9 A trivial space is zero-dimensional since its basis is empty.

Again, although we sometimes say ‘finite-dimensional’ for emphasis, from now on we take all vector spaces to be finite-dimensional. So in the next result the word ‘space’ means ‘finite-dimensional vector space’.

Corollary 2.10 No linearly independent set can have a size greater than the dimension of the enclosing space.

Proof The proof of Theorem 2.4 never uses that $D$ spans the space, only that it is linearly independent.

QED

Example 2.11 Recall the diagram from Example I.2.19 showing the subspaces of $ℝ^{3}$ . Each subspace is described with a minimal spanning set, a basis. The whole space has a basis with three members, the plane subspaces have bases with two members, the line subspaces have bases with one member, and the trivial subspace has a basis with zero members.

In that section we could not show that these are $ℝ^{3}$ ’s only subspaces. We can show it now. The prior corollary proves that There are no, say, five-dimensional subspaces of three-space. Further, by Definition 2.5 the dimension of every space is a whole number so there are no subspaces of $ℝ^{3}$ that are somehow $1.5$ -dimensional, between lines and planes. Thus the list of subspaces that we gave is exhaustive; the only subspaces of $ℝ^{3}$ are either three-, two-, one-, or zero-dimensional.

Corollary 2.12 Any linearly independent set can be expanded to make a basis.

Proof If a linearly independent set is not already a basis then it must not span the space. Adding to the set a vector that is not in the span will preserve linear independence by Lemma II.1.15. Keep adding until the resulting set does span the space, which the prior corollary shows will happen after only a finite number of steps.

QED

Corollary 2.13 Any spanning set can be shrunk to a basis.

Proof Call the spanning set $S$ . If $S$ is empty then it is already a basis (the space must be a trivial space). If $S = {\vec{0}}$ then it can be shrunk to the empty basis, thereby making it linearly independent, without changing its span.

Otherwise, $S$ contains a vector ${\vec{s}}_{1}$ with ${\vec{s}}_{1} \neq \vec{0}$ and we can form a basis $B_{1} = ⟨ {\vec{s}}_{1} ⟩$ . If $[B_{1}] = [S]$ then we are done. If not then there is a ${\vec{s}}_{2} \in [S]$ such that ${\vec{s}}_{2} \notin [B_{1}]$ . Let $B_{2} = ⟨ {\vec{s}}_{1}, \vec{s_{2}} ⟩$ ; by Lemma II.1.15 this is linearly independent so if $[B_{2}] = [S]$ then we are done.

We can repeat this process until the spans are equal, which must happen in at most finitely many steps.

QED

Corollary 2.14 In an $n$ -dimensional space, a set composed of $n$ vectors is linearly independent if and only if it spans the space.

Proof First we will show that a subset with $n$ vectors is linearly independent if and only if it is a basis. The ‘if’ is trivially true—bases are linearly independent. ‘Only if’ holds because a linearly independent set can be expanded to a basis, but a basis has $n$ elements, so this expansion is actually the set that we began with.

To finish, we will show that any subset with $n$ vectors spans the space if and only if it is a basis. Again, ‘if’ is trivial. ‘Only if’ holds because any spanning set can be shrunk to a basis, but a basis has $n$ elements and so this shrunken set is just the one we started with.

QED

The main result of this subsection, that all of the bases in a finite-dimensional vector space have the same number of elements, is the single most important result in this book. As Example 2.11 shows, it describes what vector spaces and subspaces there can be.

One immediate consequence brings us back to when we considered the two things that could be meant by the term ‘minimal spanning set’. At that point we defined ‘minimal’ as linearly independent but we noted that another reasonable interpretation of the term is that a spanning set is ‘minimal’ when it has the fewest number of elements of any set with the same span. Now that we have shown that all bases have the same number of elements, we know that the two senses of ‘minimal’ are equivalent.

Exercises

Assume that all spaces are finite-dimensional unless otherwise stated.

Exercise 2.15 Worked answer

Recommended. Find a basis for, and the dimension of, $𝒫_{2}$ .

Back to Exercise 2.15

Answer. One basis is $⟨ 1, x, x^{2} ⟩$ , and so the dimension is three.
Exercise 2.16 Worked answer

Find a basis for, and the dimension of, the solution set of this system.

$\begin{array}{rcrcrcrcr} x_{1} & - & 4 x_{2} & + & 3 x_{3} & - & x_{4} & = & 0 \\ 2 x_{1} & - & 8 x_{2} & + & 6 x_{3} & - & 2 x_{4} & = & 0 \end{array}$

Back to Exercise 2.16

Answer. The solution set is

${(\begin{matrix} 4 x_{2} - 3 x_{3} + x_{4} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}) ∣ x_{2}, x_{3}, x_{4} \in ℝ}$

so a natural basis is this

$⟨ (\begin{matrix} 4 \\ 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} - 3 \\ 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) ⟩$

(checking linear independence is easy). Thus the dimension is three.
Exercise 2.17 Worked answer

Recommended. Find a basis for, and the dimension of, each space.
1. ${(\begin{matrix} x \\ y \\ z \\ w \end{matrix}) \in ℝ^{4} ∣ x - w + z = 0}$
2. the set of $5 \times 5$ matrices whose only nonzero entries are on the diagonal (e.g., in entry $1, 1$ and $2, 2$ , etc.)
3. ${a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} ∣ a_{0} + a_{1} = 0 and a_{2} - 2 a_{3} = 0} \subseteq 𝒫_{3}$
Back to Exercise 2.17

Answer.
1. Parametrize to get this description of the space.
  
  ${(\begin{matrix} w - z \\ y \\ z \\ w \end{matrix}) = (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}) y + (\begin{matrix} - 1 \\ 0 \\ 1 \\ 0 \end{matrix}) z + (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) w ∣ y, z, w \in ℝ}$
  
  That gives the space as the span of the three-vector set. To show the three vector set makes a basis we check that it is linearly independent.
  
  $(\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix}) = (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}) c_{1} + (\begin{matrix} - 1 \\ 0 \\ 1 \\ 0 \end{matrix}) c_{2} + (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) c_{3}$
  
  The second components give that $c_{1} = 0$ , and the third and fourth components give that $c_{2} = 0$ and $c_{3} = 0$ . So one basis is this.
  
  $⟨ (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} - 1 \\ 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}) ⟩$
  
  The dimension is the number of vectors in a basis: $3$ .
2. The natural parametrization is this.
  
  $\begin{matrix} {(\begin{matrix} a & 0 & 0 & 0 & 0 \\ 0 & b & 0 & 0 & 0 \\ 0 & 0 & c & 0 & 0 \\ 0 & 0 & 0 & d & 0 \\ 0 & 0 & 0 & 0 & e \end{matrix}) ∣ a, \dots, e \in ℝ} \\ {(\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) \cdot a + (\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) \cdot b + \dots ∣ a, \dots, e \in ℝ} \end{matrix}$
  
  Checking that the five-element set is linearly independent is trivial. So this is a basis; the dimension is $5$ .
  
  $⟨ (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}), \dots, (\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) ⟩$
3. The restrictions form a two-equations, four-unknowns linear system. Parametrizing that system to express the leading variables in terms of those that are free gives $a_{0} = - a_{1}$ , $a_{1} = a_{1}$ , $a_{2} = 2 a_{3}$ , and $a_{3} = a_{3}$ .
  
  $\begin{matrix} {- a_{1} + a_{1} x + 2 a_{3} x^{2} + a_{3} x^{3} ∣ a_{1}, a_{3} \in ℝ} \\ = {(- 1 + x) \cdot a_{1} + (2 x^{2} + x^{3}) \cdot a_{3} ∣ a_{1}, a_{3} \in ℝ} \end{matrix}$
  
  That description shows that the space is the span of the two-element set ${- 1 + x, x^{2} + x^{3}}$ . We will be done if we show the set is linearly independent. This relationship
  
  $0 + 0 x + 0 x^{2} + 0 x^{3} = (- 1 + x) \cdot c_{1} + (2 x^{2} + x^{3}) \cdot c_{2}$
  
  gives that $c_{1} = 0$ from the constant terms, and $c_{2} = 0$ from the cubic terms. One basis for the space is $⟨ - 1 + x, 2 x^{2} + x^{3} ⟩$ . This is a two-dimensional space.
Exercise 2.18 Worked answer

Find a basis for, and the dimension of, $ℳ_{2 \times 2}$ , the vector space of $2 \times 2$ matrices.

Back to Exercise 2.18

Answer. For this space

$\begin{matrix} {(\begin{matrix} a & b \\ c & d \end{matrix}) ∣ a, b, c, d \in ℝ} \\ = {a \cdot (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) + \dots + d \cdot (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ∣ a, b, c, d \in ℝ} \end{matrix}$

this is a natural basis.

$⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ⟩$

The dimension is four.
Exercise 2.19 Worked answer

Find the dimension of the vector space of matrices

$(\begin{matrix} a & b \\ c & d \end{matrix})$

subject to each condition.
1. $a, b, c, d \in ℝ$
2. $a - b + 2 c = 0$ and $d \in ℝ$
3. $a + b + c = 0$ , $a + b - c = 0$ , and $d \in ℝ$
Back to Exercise 2.19

Answer.
1. As in the prior exercise, the space $ℳ_{2 \times 2}$ of matrices without restriction has this basis
  
  $⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ⟩$
  
  and so the dimension is four.
2. For this space
  
  $\begin{matrix} {(\begin{matrix} a & b \\ c & d \end{matrix}) ∣ a = b - 2 c and d \in ℝ} \\ = {b \cdot (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) + c \cdot (\begin{matrix} - 2 & 0 \\ 1 & 0 \end{matrix}) + d \cdot (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ∣ b, c, d \in ℝ} \end{matrix}$
  
  this is a natural basis.
  
  $⟨ (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} - 2 & 0 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ⟩$
  
  The dimension is three.
3. Gauss’s Method applied to the two-equation linear system gives that $c = 0$ and that $a = - b$ . Thus, we have this description
  
  ${(\begin{matrix} - b & b \\ 0 & d \end{matrix}) ∣ b, d \in ℝ} = {b \cdot (\begin{matrix} - 1 & 1 \\ 0 & 0 \end{matrix}) + d \cdot (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ∣ b, d \in ℝ}$
  
  and so this is a natural basis.
  
  $⟨ (\begin{matrix} - 1 & 1 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) ⟩$
  
  The dimension is two.
Exercise 2.20 Worked answer

Recommended. Find the dimension of this subspace of $ℝ^{2}$ .

$S = {(\begin{matrix} a + b \\ a + c \end{matrix}) ∣ a, b, c \in ℝ}$

Back to Exercise 2.20

Answer. We cannot simply count the parameters. That is, the answer is not $3$ . Instead, observe that we can express every member $(\binom{x}{y}) \in ℝ^{2}$ in the form

$(\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} a + b \\ a + c \end{matrix})$

with the choice of $a = 0$ , $b = x$ , and $c = y$ (other choices are possible). So $S$ is the set $S = ℝ^{2}$ . It has dimension $2$ .
Exercise 2.21 Worked answer

Recommended. Find the dimension of each.
1. The space of cubic polynomials $p (x)$ such that $p (7) = 0$
2. The space of cubic polynomials $p (x)$ such that $p (7) = 0$ and $p (5) = 0$
3. The space of cubic polynomials $p (x)$ such that $p (7) = 0$ , $p (5) = 0$ , and $p (3) = 0$
4. The space of cubic polynomials $p (x)$ such that $p (7) = 0$ , $p (5) = 0$ , $p (3) = 0$ , and $p (1) = 0$
Back to Exercise 2.21

Answer. The bases for these spaces are developed in the answer set of the prior subsection.
1. One basis is $⟨ - 7 + x, - 49 + x^{2}, - 343 + x^{3} ⟩$ . The dimension is three.
2. One basis is $⟨ 35 - 12 x + x^{2}, 420 - 109 x + x^{3} ⟩$ so the dimension is two.
3. A basis is ${- 105 + 71 x - 15 x^{2} + x^{3}}$ . The dimension is one.
4. This is the trivial subspace of $𝒫_{3}$ and so the basis is empty. The dimension is zero.
Exercise 2.22 Worked answer

What is the dimension of the span of the set ${\cos^{2} θ, \sin^{2} θ, \cos 2 θ, \sin 2 θ}$ ? This span is a subspace of the space of all real-valued functions of one real variable.

Back to Exercise 2.22

Answer. First recall that $\cos 2 θ = \cos^{2} θ - \sin^{2} θ$ , and so deletion of $\cos 2 θ$ from this set leaves the span unchanged. What’s left, the set ${\cos^{2} θ, \sin^{2} θ, \sin 2 θ}$ , is linearly independent (consider the relationship $c_{1} \cos^{2} θ + c_{2} \sin^{2} θ + c_{3} \sin 2 θ = Z (θ)$ where $Z$ is the zero function, and then take $θ = 0$ , $θ = π / 4$ , and $θ = π / 2$ to conclude that each $c$ is zero). It is therefore a basis for its span. That shows that the span is a dimension three vector space.
Exercise 2.23 Worked answer

Find the dimension of $ℂ^{47}$ , the vector space of $47$ -tuples of complex numbers.

Back to Exercise 2.23

Answer. Here is a basis

$⟨ (1 + 0 i, 0 + 0 i, \dots, 0 + 0 i), (0 + 1 i, 0 + 0 i, \dots, 0 + 0 i), (0 + 0 i, 1 + 0 i, \dots, 0 + 0 i), \dots ⟩$

and so the dimension is $2 \cdot 47 = 94$ .
Exercise 2.24 Worked answer

What is the dimension of the vector space $ℳ_{3 \times 5}$ of $3 \times 5$ matrices?

Back to Exercise 2.24

Answer. A basis is

$⟨ (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}), \dots, (\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) ⟩$

and thus the dimension is $3 \cdot 5 = 15$ .
Exercise 2.25 Worked answer

Recommended. Show that this is a basis for $ℝ^{4}$ .

$⟨ (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}) ⟩$

(We can use the results of this subsection to simplify this job.)

Back to Exercise 2.25

Answer. In a four-dimensional space a set of four vectors is linearly independent if and only if it spans the space. The form of these vectors makes linear independence easy to show (look at the equation of fourth components, then at the equation of third components, etc.).
Exercise 2.26 Worked answer

Decide if each is a basis for $𝒫_{2}$ .
1. ${1, x^{2}, x^{2} - x}$
2. ${x^{2} + x, x^{2} - x}$
3. ${2 x^{2} + x + 1, 2 x + 1, 2}$
4. ${3 x^{2}, - 1, 3 x, x^{2} - x}$
Back to Exercise 2.26

Answer. By the results of this section, because $𝒫_{2}$ has dimension $3$ , to show that a linearly independent set is a basis we need only observe that it has three members. To show a set is not a basis we need only observe that it does not have three members (in this case we don’t have to worry about linear independence).
1. This is a basis; it is linearly independent by inspection (the first element has no quadratic or linear term, the second has a quadratic but no linear term, and the third has a linear term) and it has three elements.
2. This is not a basis as it has only two elements.
3. This three-element set is a basis.
4. This is not a basis as it has four elements.
Exercise 2.27 Worked answer

Refer to Example 2.11.
1. Sketch a similar subspace diagram for $𝒫_{2}$ .
2. Sketch one for $ℳ_{2 \times 2}$ .
Back to Exercise 2.27

Answer.
1. The diagram for $𝒫_{2}$ has four levels. The top level has the only three-dimensional subspace, $𝒫_{2}$ itself. The next level contains the two-dimensional subspaces (not just the linear polynomials; any two-dimensional subspace, like those polynomials of the form $a x^{2} + b$ ). Below that are the one-dimensional subspaces. Finally, of course, is the only zero-dimensional subspace, the trivial subspace.
2. For $ℳ_{2 \times 2}$ , the diagram has five levels, including subspaces of dimension four through zero.
Exercise 2.28 Worked answer

Recommended. Where $S$ is a set, the functions $f : S \to ℝ$ form a vector space under the natural operations: the sum $f + g$ is the function given by $f + g (s) = f (s) + g (s)$ and the scalar product is $r \cdot f (s) = r \cdot f (s)$ . What is the dimension of the space resulting for each domain?
1. $S = {1}$
2. $S = {1, 2}$
3. $S = {1, \dots, n}$
Back to Exercise 2.28

Answer.
1. One
2. Two
3. $n$
Exercise 2.29 Worked answer

(See Exercise 2.28.) Prove that this is an infinite-dimensional space: the set of all functions $f : ℝ \to ℝ$ under the natural operations.

Back to Exercise 2.29

Answer. We need only produce an infinite linearly independent set. One is such sequence is $⟨ f_{1}, f_{2}, \dots ⟩$ where $f_{i} : ℝ \to ℝ$ is

$f_{i} (x) = {\begin{cases} 1 & if x = i \\ 0 & otherwise \end{cases}$

the function that has value $1$ only at $x = i$ .
Exercise 2.30 Worked answer

(See Exercise 2.28.) What is the dimension of the vector space of functions $f : S \to ℝ$ , under the natural operations, where the domain $S$ is the empty set?

Back to Exercise 2.30

Answer. A function is a set of ordered pairs $(x, f (x))$ . So there is only one function with an empty domain, namely the empty set. A vector space with only one element a trivial vector space and has dimension zero.
Exercise 2.31 Worked answer

Show that any set of four vectors in $ℝ^{2}$ is linearly dependent.

Back to Exercise 2.31

Answer. Apply Corollary 2.10.
Exercise 2.32 Worked answer

Show that $⟨ {\vec{α}}_{1}, {\vec{α}}_{2}, {\vec{α}}_{3} ⟩ \subset ℝ^{3}$ is a basis if and only if there is no plane through the origin containing all three vectors.

Back to Exercise 2.32

Answer. A plane has the form ${\vec{p} + t_{1} {\vec{v}}_{1} + t_{2} {\vec{v}}_{2} ∣ t_{1}, t_{2} \in ℝ}$ . (The first chapter also calls this a ‘ $2$ -flat’, and contains a discussion of why this is equivalent to the description often taken in Calculus as the set of points $(x, y, z)$ subject to a condition of the form $a x + b y + c z = d$ ). When the plane passes through the origin we can take the particular vector $\vec{p}$ to be $\vec{0}$ . Thus, in the language we have developed in this chapter, a plane through the origin is the span of a set of two vectors.

Now for the statement. Asserting that the three are not coplanar is the same as asserting that no vector lies in the span of the other two—no vector is a linear combination of the other two. That’s simply an assertion that the three-element set is linearly independent. By Corollary 2.14, that’s equivalent to an assertion that the set is a basis for $ℝ^{3}$ (more precisely, any sequence made from the set’s elements is a basis).
Exercise 2.33 Worked answer

Prove that any subspace of a finite dimensional space is finite dimensional.

Back to Exercise 2.33

Answer. Let the space $V$ be finite dimensional and let $S$ be a subspace of $V$ .

If $S$ is not finite dimensional then it has a linearly independent set that is infinite (start with the empty set and iterate adding vectors that are not linearly dependent on the set; this process can continue for infinitely many steps or else $S$ would be finite dimensional). But any linearly independent subset of $S$ is a linearly independent subset of $V$ , contradicting Corollary 2.10
Exercise 2.34 Worked answer

Where is the finiteness of $B$ used in Theorem 2.4?

Back to Exercise 2.34

Answer. It ensures that we exhaust the $\vec{β}$ ’s. That is, it justifies the first sentence of the last paragraph.
Exercise 2.35 Worked answer

Prove that if $U$ and $W$ are both three-dimensional subspaces of $ℝ^{5}$ then $U \cap W$ is non-trivial. Generalize.

Back to Exercise 2.35

Answer. Let $B_{U}$ be a basis for $U$ and let $B_{W}$ be a basis for $W$ . Consider the concatenation of the two basis sequences. If there is a repeated element then the intersection $U \cap W$ is nontrivial. Otherwise, the set $B_{U} \cup B_{W}$ is linearly dependent as it is a six member subset of the five-dimensional space $ℝ^{5}$ . In either case some member of $B_{W}$ is in the span of $B_{U}$ , and thus $U \cap W$ is more than just the trivial space ${\vec{0}}$ .

Generalization: if $U, W$ are subspaces of a vector space of dimension $n$ and if $\dim (U) + \dim (W) > n$ then they have a nontrivial intersection.
Exercise 2.36 Worked answer

A basis for a space consists of elements of that space. So we are naturally led to how the property ‘is a basis’ interacts with operations $\subseteq$ and $\cap$ and $\cup$ . (Of course, a basis is actually a sequence that it is ordered, but there is a natural extension of these operations.)
1. Consider first how bases might be related by $\subseteq$ . Assume that $U, W$ are subspaces of some vector space and that $U \subseteq W$ . Can there exist bases $B_{U}$ for $U$ and $B_{W}$ for $W$ such that $B_{U} \subseteq B_{W}$ ? Must such bases exist?
  
  For any basis $B_{U}$ for $U$ , must there be a basis $B_{W}$ for $W$ such that $B_{U} \subseteq B_{W}$ ?
  
  For any basis $B_{W}$ for $W$ , must there be a basis $B_{U}$ for $U$ such that $B_{U} \subseteq B_{W}$ ?
  
  For any bases $B_{U}, B_{W}$ for $U$ and $W$ , must $B_{U}$ be a subset of $B_{W}$ ?
2. Is the $\cap$ of bases a basis? For what space?
3. Is the $\cup$ of bases a basis? For what space?
4. What about the complement operation?
(Hint. Test any conjectures against some subspaces of $ℝ^{3}$ .)
Back to Exercise 2.36

Answer. First, note that a set is a basis for some space if and only if it is linearly independent, because in that case it is a basis for its own span.
1. The answer to the question in the second paragraph is “yes” (implying “yes” answers for both questions in the first paragraph). If $B_{U}$ is a basis for $U$ then $B_{U}$ is a linearly independent subset of $W$ . Apply Corollary 2.12 to expand it to a basis for $W$ . That is the desired $B_{W}$ .
  
  The answer to the question in the third paragraph is “no”, which implies a “no” answer to the question of the fourth paragraph. Here is an example of a basis for a superspace with no sub-basis forming a basis for a subspace: in $W = ℝ^{2}$ , consider the standard basis $ℰ_{2}$ . No sub-basis of $ℰ_{2}$ forms a basis for the subspace $U$ of $ℝ^{2}$ that is the line $y = x$ .
2. It is a basis (for its span) because the intersection of linearly independent sets is linearly independent (the intersection is a subset of each of the linearly independent sets).
  
  It is not, however, a basis for the intersection of the spaces. For instance, these are bases for $ℝ^{2}$ :
  
  $B_{1} = ⟨ (\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \end{matrix}) ⟩ and B_{2} = ⟨ [⟩ r] (\begin{matrix} 2 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 2 \end{matrix})$
  
  and $ℝ^{2} \cap ℝ^{2} = ℝ^{2}$ , but $B_{1} \cap B_{2}$ is empty. All we can say is that the $\cap$ of the bases is a basis for a subset of the intersection of the spaces.
3. The $\cup$ of bases need not be a basis: in $ℝ^{2}$
  
  $B_{1} = ⟨ (\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \end{matrix}) ⟩ and B_{2} = ⟨ (\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 2 \end{matrix}) ⟩$
  
  $B_{1} \cup B_{2}$ is not linearly independent. A necessary and sufficient condition for a $\cup$ of two bases to be a basis
  
  $B_{1} \cup B_{2} is linearly independent ⟺ [B_{1} \cap B_{2}] = [B_{1}] \cap [B_{2}]$
  
  it is easy enough to prove (but perhaps hard to apply).
4. The complement of a basis cannot be a basis because it contains the zero vector.
Exercise 2.37 Worked answer

Recommended. Consider how ‘dimension’ interacts with ‘subset’. Assume $U$ and $W$ are both subspaces of some vector space, and that $U \subseteq W$ .
1. Prove that $\dim (U) \leq \dim (W)$ .
2. Prove that equality of dimension holds if and only if $U = W$ .
3. Show that the prior item does not hold if they are infinite-dimensional.
Back to Exercise 2.37

Answer.
1. A basis for $U$ is a linearly independent set in $W$ and so can be expanded via Corollary 2.12 to a basis for $W$ . The second basis has at least as many members as the first.
2. One direction is clear: if $V = W$ then they have the same dimension. For the converse, let $B_{U}$ be a basis for $U$ . It is a linearly independent subset of $W$ and so can be expanded to a basis for $W$ . If $\dim (U) = \dim (W)$ then this basis for $W$ has no more members than does $B_{U}$ and so equals $B_{U}$ . Since $U$ and $W$ have the same bases, they are equal.
3. Let $W$ be the space of finite-degree polynomials and let $U$ be the subspace of polynomials that have only even-powered terms.
  
  $U = {a_{0} + a_{1} x^{2} + a_{2} x^{4} + \dots + a_{n} x^{2 n} ∣ a_{0}, \dots, a_{n} \in ℝ}$
  
  Both spaces have infinite dimension but $U$ is a proper subspace.
Exercise 2.38 Worked answer

Here is an alternative proof of this section’s main result, Theorem 2.4. First is an example, then a lemma, then the theorem.
1. Express this vector from $ℝ^{3}$ a as a linear combination of members of the basis.
  
  $B = ⟨ (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix}) ⟩ \vec{v} = (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix})$
2. In that combination pick a basis vector with a non-zero coefficient. Alter $B$ by exchanging $\vec{v}$ for that basis vector, to get a new sequence $\hat{B}$ . Check that $\hat{B}$ is also a basis for $ℝ^{3}$ .
3. (Exchange Lemma) Assume that $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ is a basis for a vector space, and that for the vector $\vec{v}$ the relationship $\vec{v} = c_{1} {\vec{β}}_{1} + c_{2} {\vec{β}}_{2} + \dots + c_{n} {\vec{β}}_{n}$ has $c_{i} \neq 0$ . Prove that exchanging $\vec{v}$ for ${\vec{β}}_{i}$ yields another basis for the space.
4. Use that, with induction, to prove Theorem 2.4.
Back to Exercise 2.38

Answer.
1. $(\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}) = (- 1) \cdot (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + 2 (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}) + 0 \cdot (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix})$
2. Two of the basis vectors are associated with non-zero coefficients. We can for instance pick the first.
  
  $\hat{B} = ⟨ (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 2 \end{matrix}) ⟩$
  
  Checking that it is another basis for $ℝ^{3}$ is routine.
3. Call the outcome of the exchange $\hat{B} = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{i - 1}, \vec{v}, {\vec{β}}_{i + 1}, \dots, {\vec{β}}_{n} ⟩$ . We first show that $\hat{B}$ is linearly independent. Any relationship $d_{1} {\vec{β}}_{1} + \dots + d_{i} \vec{v} + \dots + d_{n} {\vec{β}}_{n} = \vec{0}$ among the members of $\hat{B}$ , after substitution for $\vec{v}$ ,
  
  $\begin{matrix} d_{1} {\vec{β}}_{1} + \dots + d_{i} \cdot (c_{1} {\vec{β}}_{1} + \dots + c_{i} {\vec{β}}_{i} + \dots + c_{n} {\vec{β}}_{n}) + \dots + d_{n} {\vec{β}}_{n} = \vec{0} & (*) \end{matrix}$
  
  gives a linear relationship among the members of $B$ . The basis $B$ is linearly independent so the coefficient $d_{i} c_{i}$ of ${\vec{β}}_{i}$ is zero. Because we assumed that $c_{i}$ is nonzero, $d_{i} = 0$ . Using this in equation $(*)$ gives that all of the other $d$ ’s are also zero. Therefore $\hat{B}$ is linearly independent.
  
  We finish by showing that $\hat{B}$ has the same span as $B$ . Half of this argument, that $[\hat{B}] \subseteq [B]$ , is easy; we can write any member $d_{1} {\vec{β}}_{1} + \dots + d_{i} \vec{v} + \dots + d_{n} {\vec{β}}_{n}$ of $[\hat{B}]$ as $d_{1} {\vec{β}}_{1} + \dots + d_{i} \cdot (c_{1} {\vec{β}}_{1} + \dots + c_{n} {\vec{β}}_{n}) + \dots + d_{n} {\vec{β}}_{n}$ , which is a linear combination of linear combinations of members of $B$ , and hence is in $[B]$ . For the $[B] \subseteq [\hat{B}]$ half of the argument, recall that if $\vec{v} = c_{1} {\vec{β}}_{1} + \dots + c_{n} {\vec{β}}_{n}$ with $c_{i} \neq 0$ then we can rearrange the equation to ${\vec{β}}_{i} = (- c_{1} / c_{i}) {\vec{β}}_{1} + \dots + (1 / c_{i}) \vec{v} + \dots + (- c_{n} / c_{i}) {\vec{β}}_{n}$ . Now, consider any member $d_{1} {\vec{β}}_{1} + \dots + d_{i} {\vec{β}}_{i} + \dots + d_{n} {\vec{β}}_{n}$ of $[B]$ , substitute for ${\vec{β}}_{i}$ its expression as a linear combination of the members of $\hat{B}$ , and recognize, as in the first half of this argument, that the result is a linear combination of linear combinations of members of $\hat{B}$ , and hence is in $[\hat{B}]$ .
4. Fix a vector space with at least one finite basis. Choose, from among all of this space’s bases, one $B = ⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ of minimal size. We will show that any other basis $D = ⟨ {\vec{δ}}_{1}, {\vec{δ}}_{2}, \dots ⟩$ also has the same number of members, $n$ . Because $B$ has minimal size, $D$ has no fewer than $n$ vectors. We will argue that it cannot have more than $n$ vectors.
  
  The basis $B$ spans the space and ${\vec{δ}}_{1}$ is in the space, so ${\vec{δ}}_{1}$ is a nontrivial linear combination of elements of $B$ . By the Exchange Lemma, we can swap ${\vec{δ}}_{1}$ for a vector from $B$ , resulting in a basis $B_{1}$ , where one element is ${\vec{δ}}_{1}$ and all of the $n - 1$ other elements are $\vec{β}$ ’s.
  
  The prior paragraph forms the basis step for an induction argument. The inductive step starts with a basis $B_{k}$ (for $1 \leq k < n$ ) containing $k$ members of $D$ and $n - k$ members of $B$ . We know that $D$ has at least $n$ members so there is a ${\vec{δ}}_{k + 1}$ . Represent it as a linear combination of elements of $B_{k}$ . The key point: in that representation, at least one of the nonzero scalars must be associated with a ${\vec{β}}_{i}$ or else that representation would be a nontrivial linear relationship among elements of the linearly independent set $D$ . Exchange ${\vec{δ}}_{k + 1}$ for ${\vec{β}}_{i}$ to get a new basis $B_{k + 1}$ with one $\vec{δ}$ more and one $\vec{β}$ fewer than the previous basis $B_{k}$ .
  
  Repeat that until no $\vec{β}$ ’s remain, so that $B_{n}$ contains ${\vec{δ}}_{1}, \dots, {\vec{δ}}_{n}$ . Now, $D$ cannot have more than these $n$ vectors because any ${\vec{δ}}_{n + 1}$ that remains would be in the span of $B_{n}$ (since it is a basis) and hence would be a linear combination of the other $\vec{δ}$ ’s, contradicting that $D$ is linearly independent.
Exercise 2.39 Worked answer

Puzzle. [Sheffer] A library has $n$ books and $n + 1$ subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Back to Exercise 2.39

Answer. (This answer is from a site comment by Yuzhou Gu.) For each person assign a vector ${\vec{v}}_{i} \in ℝ^{n}$ , where an entry is $1$ if the person reads the book, and $0$ otherwise. Because the vectors are linear dependent, we will have a equation of the form $\sum a_{i} v_{i} = 0$ . Then the set of $i$ such that $a_{i} > 0$ and the set of $i$ such that $a_{i} < 0$ are two disjoint sets with same union of read books.
Exercise 2.40 Worked answer

Puzzle. [Wohascum no. 47] For any vector $\vec{v}$ in $ℝ^{n}$ and any permutation $σ$ of the numbers $1$ , $2$ , …, $n$ (that is, $σ$ is a rearrangement of those numbers into a new order), define $σ (\vec{v})$ to be the vector whose components are $v_{σ (1)}$ , $v_{σ (2)}$ , …, and $v_{σ (n)}$ (where $σ (1)$ is the first number in the rearrangement, etc.). Now fix $\vec{v}$ and let $V$ be the span of ${σ (\vec{v}) ∣ σ permutes 1, \dots, n}$ . What are the possibilities for the dimension of $V$ ?

Back to Exercise 2.40

Answer. The possibilities for the dimension of $V$ are $0$ , $1$ , $n - 1$ , and $n$ .

To see this, first consider the case when all the coordinates of $\vec{v}$ are equal.

$\vec{v} = (\begin{matrix} z \\ z \\ ⋮ \\ z \end{matrix})$

Then $σ (\vec{v}) = \vec{v}$ for every permutation $σ$ , so $V$ is just the span of $\vec{v}$ , which has dimension $0$ or $1$ according to whether $\vec{v}$ is $\vec{0}$ or not.

Now suppose not all the coordinates of $\vec{v}$ are equal; let $x$ and $y$ with $x \neq y$ be among the coordinates of $\vec{v}$ . Then we can find permutations $σ_{1}$ and $σ_{2}$ such that

$σ_{1} (\vec{v}) = (\begin{matrix} x \\ y \\ a_{3} \\ ⋮ \\ a_{n} \end{matrix}) and σ_{2} (\vec{v}) = (\begin{matrix} y \\ x \\ a_{3} \\ ⋮ \\ a_{n} \end{matrix})$

for some $a_{3}, \dots, a_{n} \in ℝ$ . Therefore,

$\frac{1}{y - x} (σ_{1} (\vec{v}) - σ_{2} (\vec{v})) = (\begin{matrix} - 1 \\ 1 \\ 0 \\ ⋮ \\ 0 \end{matrix})$

is in $V$ . That is, ${\vec{e}}_{2} - {\vec{e}}_{1} \in V$ , where ${\vec{e}}_{1}$ , ${\vec{e}}_{2}$ , …, ${\vec{e}}_{n}$ is the standard basis for $ℝ^{n}$ . Similarly, ${\vec{e}}_{3} - {\vec{e}}_{2}$ , …, ${\vec{e}}_{n} - {\vec{e}}_{1}$ are all in $V$ . It is easy to see that the vectors ${\vec{e}}_{2} - {\vec{e}}_{1}$ , ${\vec{e}}_{3} - {\vec{e}}_{2}$ , …, ${\vec{e}}_{n} - {\vec{e}}_{1}$ are linearly independent (that is, form a linearly independent set), so $\dim V \geq n - 1$ .

Finally, we can write

$\begin{aligned} \vec{v} & = x_{1} {\vec{e}}_{1} + x_{2} {\vec{e}}_{2} + \dots + x_{n} {\vec{e}}_{n} \\ = (x_{1} + x_{2} + \dots + x_{n}) {\vec{e}}_{1} + x_{2} ({\vec{e}}_{2} - {\vec{e}}_{1}) + \dots + x_{n} ({\vec{e}}_{n} - {\vec{e}}_{1}) \end{aligned}$

This shows that if $x_{1} + x_{2} + \dots + x_{n} = 0$ then $\vec{v}$ is in the span of ${\vec{e}}_{2} - {\vec{e}}_{1}$ , …, $\vec{e_{n}} - {\vec{e}}_{1}$ (that is, is in the span of the set of those vectors); similarly, each $σ (\vec{v})$ will be in this span, so $V$ will equal this span and $\dim V = n - 1$ . On the other hand, if $x_{1} + x_{2} + \dots + x_{n} \neq 0$ then the above equation shows that ${\vec{e}}_{1} \in V$ and thus ${\vec{e}}_{1}, \dots, {\vec{e}}_{n} \in V$ , so $V = ℝ^{n}$ and $\dim V = n$ .

Vector Spaces and Linear Systems

We will now reconsider linear systems and Gauss’s Method, aided by the tools and terms of this chapter. We will make three points.

For the first, recall the insight from the Chapter One that Gauss’s Method works by taking linear combinations of rows— if two matrices are related by row operations $A ⟶ \dots ⟶ B$ then each row of $B$ is a linear combination of the rows of $A$ . Therefore, the right setting in which to study row operations in general, and Gauss’s Method in particular, is the following vector space.

Definition 3.1 The row space of a matrix is the span of the set of its rows. The row rank is the dimension of this space, the number of linearly independent rows.

Example 3.2 If

$A = (\begin{matrix} 2 & 3 \\ 4 & 6 \end{matrix})$

then $Rowspace (A)$ is this subspace of the space of two-component row vectors.

${c_{1} \cdot (\begin{matrix} 2 & 3 \end{matrix}) + c_{2} \cdot (\begin{matrix} 4 & 6 \end{matrix}) ∣ c_{1}, c_{2} \in ℝ}$

The second row vector is linearly dependent on the first and so we can simplify the above description to ${c \cdot (\begin{matrix} 2 & 3 \end{matrix}) ∣ c \in ℝ}$ .

Lemma 3.3 If two matrices $A$ and $B$ are related by a row operation

$A ⟶_{\begin{array}{l} \end{array}}^{ρ_{i} \leftrightarrow ρ_{j}} B or A ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i}} B or A ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i} + ρ_{j}} B$

(for $i \neq j$ and $k \neq 0$ ) then their row spaces are equal. Hence, row-equivalent matrices have the same row space and therefore the same row rank.

Proof Corollary One.III.2.4 shows that when $A ⟶ B$ then each row of $B$ is a linear combination of the rows of $A$ . That is, in the above terminology, each row of $B$ is an element of the row space of $A$ . Then $Rowspace (B) \subseteq Rowspace (A)$ follows because a member of the set $Rowspace (B)$ is a linear combination of the rows of $B$ , so it is a combination of combinations of the rows of $A$ , and by the Linear Combination Lemma is also a member of $Rowspace (A)$ .

For the other set containment, recall Lemma One.III.1.5, that row operations are reversible so $A ⟶ B$ if and only if $B ⟶ A$ . Then $Rowspace (A) \subseteq Rowspace (B)$ follows as in the previous paragraph.

QED

Of course, Gauss’s Method performs the row operations systematically, with the goal of echelon form.

Lemma 3.4 The nonzero rows of an echelon form matrix make up a linearly independent set.

Proof Lemma One.III.2.5 says that no nonzero row of an echelon form matrix is a linear combination of the other rows. This result restates that using this chapter’s terminology.

QED

Thus, in the language of this chapter, Gaussian reduction works by eliminating linear dependences among rows, leaving the span unchanged, until no nontrivial linear relationships remain among the nonzero rows. In short, Gauss’s Method produces a basis for the row space.

Example 3.5 From any matrix, we can produce a basis for the row space by performing Gauss’s Method and taking the nonzero rows of the resulting echelon form matrix. For instance,

$(\begin{matrix} 1 & 3 & 1 \\ 1 & 4 & 1 \\ 2 & 0 & 5 \end{matrix}) ⟶_{\begin{array}{l} - 2 ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{6 ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 3 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{matrix})$

produces the basis $⟨ (\begin{matrix} 1 & 3 & 1 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 0 & 3 \end{matrix}) ⟩$ for the row space. This is a basis for the row space of both the starting and ending matrices, since the two row spaces are equal.

Using this technique, we can also find bases for spans not directly involving row vectors.

Definition 3.6 The column space of a matrix is the span of the set of its columns. The column rank is the dimension of the column space, the number of linearly independent columns.

Our interest in column spaces stems from our study of linear systems. An example is that this system

$\begin{array}{rcrcrcr} c_{1} & + & 3 c_{2} & + & 7 c_{3} & = & d_{1} \\ 2 c_{1} & + & 3 c_{2} & + & 8 c_{3} & = & d_{2} \\ c_{2} & + & 2 c_{3} & = & d_{3} \\ 4 c_{1} & + & 4 c_{3} & = & d_{4} \end{array}$

has a solution if and only if the vector of $d$ ’s is a linear combination of the other column vectors,

$c_{1} (\begin{matrix} 1 \\ 2 \\ 0 \\ 4 \end{matrix}) + c_{2} (\begin{matrix} 3 \\ 3 \\ 1 \\ 0 \end{matrix}) + c_{3} (\begin{matrix} 7 \\ 8 \\ 2 \\ 4 \end{matrix}) = (\begin{matrix} d_{1} \\ d_{2} \\ d_{3} \\ d_{4} \end{matrix})$

meaning that the vector of $d$ ’s is in the column space of the matrix of coefficients.

Example 3.7 Given this matrix,

$(\begin{matrix} 1 & 3 & 7 \\ 2 & 3 & 8 \\ 0 & 1 & 2 \\ 4 & 0 & 4 \end{matrix})$

to get a basis for the column space, temporarily turn the columns into rows and reduce.

$(\begin{matrix} 1 & 2 & 0 & 4 \\ 3 & 3 & 1 & 0 \\ 7 & 8 & 2 & 4 \end{matrix}) ⟶_{\begin{array}{l} - 7 ρ_{1} + ρ_{3} \end{array}}^{- 3 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 2 & 0 & 4 \\ 0 & - 3 & 1 & - 12 \\ 0 & 0 & 0 & 0 \end{matrix})$

Now turn the rows back to columns.

$⟨ (\begin{matrix} 1 \\ 2 \\ 0 \\ 4 \end{matrix}), (\begin{matrix} 0 \\ - 3 \\ 1 \\ - 12 \end{matrix}) ⟩$

The result is a basis for the column space of the given matrix.

Definition 3.8 The transpose of a matrix is the result of interchanging its rows and columns, so that column $j$ of the matrix $A$ is row $j$ of $A^{𝖳}$ and vice versa.

So we can summarize the prior example as “transpose, reduce, and transpose back.”

We can even, at the price of tolerating the as-yet-vague idea of vector spaces being “the same,” use Gauss’s Method to find bases for spans in other types of vector spaces.

Example 3.9 To get a basis for the span of ${x^{2} + x^{4}, 2 x^{2} + 3 x^{4}, - x^{2} - 3 x^{4}}$ in the space $𝒫_{4}$ , think of these three polynomials as “the same” as the row vectors $(\begin{matrix} 0 & 0 & 1 & 0 & 1 \end{matrix})$ , $(\begin{matrix} 0 & 0 & 2 & 0 & 3 \end{matrix})$ , and $(\begin{matrix} 0 & 0 & - 1 & 0 & - 3 \end{matrix})$ , apply Gauss’s Method

$(\begin{matrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 0 & 3 \\ 0 & 0 & - 1 & 0 & - 3 \end{matrix}) ⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{2 ρ_{2} + ρ_{3}} (\begin{matrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})$

and translate back to get the basis $⟨ x^{2} + x^{4}, x^{4} ⟩$ . (As mentioned earlier, we will make the phrase “the same” precise at the start of the next chapter.)

Thus, the first point for this subsection is that the tools of this chapter give us a more conceptual understanding of Gaussian reduction.

For the second point observe that row operations on a matrix can change its column space.

$(\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})$

The column space of the left-hand matrix contains vectors with a second component that is nonzero but the column space of the right-hand matrix contains only vectors whose second component is zero, so the two spaces are different. This observation makes next result surprising.

Lemma 3.10 Row operations do not change the column rank.

Proof Restated, if $A$ reduces to $B$ then the column rank of $B$ equals the column rank of $A$ .

This proof will be finished if we show that row operations do not affect linear relationships among columns, because the column rank is the size of the largest set of unrelated columns. That is, we will show that a relationship exists among columns (such as that the fifth column is twice the second plus the fourth) if and only if that relationship exists after the row operation. But this is exactly the first theorem of this book, Theorem One.I.1.5: in a relationship among columns,

$c_{1} \cdot (\begin{matrix} a_{1, 1} \\ a_{2, 1} \\ ⋮ \\ a_{m, 1} \end{matrix}) + \dots + c_{n} \cdot (\begin{matrix} a_{1, n} \\ a_{2, n} \\ ⋮ \\ a_{m, n} \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix})$

row operations leave unchanged the set of solutions $(c_{1}, \dots, c_{n})$ .

QED

Another way to make the point that Gauss’s Method has something to say about the column space as well as about the row space is with Gauss-Jordan reduction. It ends with the reduced echelon form of a matrix, as here.

$(\begin{matrix} 1 & 3 & 1 & 6 \\ 2 & 6 & 3 & 16 \\ 1 & 3 & 1 & 6 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{} \dots ⟶_{\begin{array}{l} \end{array}}^{} (\begin{matrix} 1 & 3 & 0 & 2 \\ 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{matrix})$

Consider the row space and the column space of this result.

The first point made earlier in this subsection says that to get a basis for the row space we can just collect the rows with leading entries. However, because this is in reduced echelon form, a basis for the column space is just as easy: collect the columns containing the leading entries, $⟨ {\vec{e}}_{1}, {\vec{e}}_{2} ⟩$ . Thus, for a reduced echelon form matrix we can find bases for the row and column spaces in essentially the same way, by taking the parts of the matrix, the rows or columns, containing the leading entries.

Theorem 3.11 For any matrix, the row rank and column rank are equal.

Proof Bring the matrix to reduced echelon form. Then the row rank equals the number of leading entries since that equals the number of nonzero rows. Then also, the number of leading entries equals the column rank because the set of columns containing leading entries consists of some of the ${\vec{e}}_{i}$ ’s from a standard basis, and that set is linearly independent and spans the set of columns. Hence, in the reduced echelon form matrix, the row rank equals the column rank, because each equals the number of leading entries.

But Lemma 3.3 and Lemma 3.10 show that the row rank and column rank are not changed by using row operations to get to reduced echelon form. Thus the row rank and the column rank of the original matrix are also equal.

QED

Definition 3.12 The rank of a matrix is its row rank or column rank.

So the second point that we have made in this subsection is that the column space and row space of a matrix have the same dimension.

Our final point is that the concepts that we’ve seen arising naturally in the study of vector spaces are exactly the ones that we have studied with linear systems.

Theorem 3.13 For linear systems with $n$ unknowns and with matrix of coefficients $A$ , the statements

the rank of $A$ is $r$
the vector space of solutions of the associated homogeneous system has dimension $n - r$

are equivalent.

So if the system has at least one particular solution then for the set of solutions, the number of parameters equals $n - r$ , the number of variables minus the rank of the matrix of coefficients.

Proof The rank of $A$ is $r$ if and only if Gaussian reduction on $A$ ends with $r$ nonzero rows. That’s true if and only if echelon form matrices row equivalent to $A$ have $r$ -many leading variables. That in turn holds if and only if there are $n - r$ free variables.

QED

Corollary 3.14 Where the matrix $A$ is $n \times n$ , these statements

the rank of $A$ is $n$
$A$ is nonsingular
the rows of $A$ form a linearly independent set
the columns of $A$ form a linearly independent set
any linear system whose matrix of coefficients is $A$ has one and only one solution

are equivalent.

Proof Clearly $(1) ⟺ (2) ⟺ (3) ⟺ (4)$ . The last, $(4) ⟺ (5)$ , holds because a set of $n$ column vectors is linearly independent if and only if it is a basis for $ℝ^{n}$ , but the system

$c_{1} (\begin{matrix} a_{1, 1} \\ a_{2, 1} \\ ⋮ \\ a_{m, 1} \end{matrix}) + \dots + c_{n} (\begin{matrix} a_{1, n} \\ a_{2, n} \\ ⋮ \\ a_{m, n} \end{matrix}) = (\begin{matrix} d_{1} \\ d_{2} \\ ⋮ \\ d_{m} \end{matrix})$

has a unique solution for all choices of $d_{1}, \dots, d_{n} \in ℝ$ if and only if the vectors of $a$ ’s on the left form a basis.

QED

Remark 3.15 [Munkres] Sometimes the results of this subsection are mistakenly remembered to say that the general solution of an $m$ equations, $n$ unknowns system uses $n - m$ parameters. The number of equations is not the relevant number; rather, what matters is the number of independent equations, the number of equations in a maximal independent set. Where there are $r$ independent equations, the general solution involves $n - r$ parameters.

Exercises

Exercise 3.16 Worked answer

Transpose each.
1. $(\begin{matrix} 2 & 1 \\ 3 & 1 \end{matrix})$
2. $(\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix})$
3. $(\begin{matrix} 1 & 4 & 3 \\ 6 & 7 & 8 \end{matrix})$
4. $(\begin{matrix} 0 \\ 0 \\ 0 \end{matrix})$
5. $(\begin{matrix} - 1 & - 2 \end{matrix})$
Back to Exercise 3.16

Answer.
1. $(\begin{matrix} 2 & 3 \\ 1 & 1 \end{matrix})$
2. $(\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix})$
3. $(\begin{matrix} 1 & 6 \\ 4 & 7 \\ 3 & 8 \end{matrix})$
4. $(\begin{matrix} 0 & 0 & 0 \end{matrix})$
5. $(\begin{matrix} - 1 \\ - 2 \end{matrix})$
Exercise 3.17 Worked answer

Recommended. Decide if the vector is in the row space of the matrix.
1. $(\begin{matrix} 2 & 1 \\ 3 & 1 \end{matrix})$ , $(\begin{matrix} 1 & 0 \end{matrix})$
2. $(\begin{matrix} 0 & 1 & 3 \\ - 1 & 0 & 1 \\ - 1 & 2 & 7 \end{matrix})$ , $(\begin{matrix} 1 & 1 & 1 \end{matrix})$
Back to Exercise 3.17

Answer.
1. Yes. To see if there are $c_{1}$ and $c_{2}$ such that $c_{1} \cdot (\begin{matrix} 2 & 1 \end{matrix}) + c_{2} \cdot (\begin{matrix} 3 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 \end{matrix})$ , we solve
  
  $\begin{array}{rcrcr} 2 c_{1} & + & 3 c_{2} & = & 1 \\ c_{1} & + & c_{2} & = & 0 \end{array}$
  
  and get $c_{1} = - 1$ and $c_{2} = 1$ . Thus the vector is in the row space.
2. No. The equation $c_{1} (\begin{matrix} 0 & 1 & 3 \end{matrix}) + c_{2} (\begin{matrix} - 1 & 0 & 1 \end{matrix}) + c_{3} (\begin{matrix} - 1 & 2 & 7 \end{matrix}) = (\begin{matrix} 1 & 1 & 1 \end{matrix})$ has no solution.
  
  $(\begin{array}{cccr} 0 & - 1 & - 1 & 1 \\ 1 & 0 & 2 & 1 \\ 3 & 1 & 7 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{1} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{3}} (\begin{array}{cccr} 1 & 0 & 2 & 1 \\ 0 & - 1 & - 1 & 1 \\ 0 & 0 & 0 & - 1 \end{array})$
  
  Thus, the vector is not in the row space.
Exercise 3.18 Worked answer

Recommended. Decide if the vector is in the column space.
1. $(\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ , $(\begin{matrix} 1 \\ 3 \end{matrix})$
2. $(\begin{matrix} 1 & 3 & 1 \\ 2 & 0 & 4 \\ 1 & - 3 & - 3 \end{matrix})$ , $(\begin{matrix} 1 \\ 0 \\ 0 \end{matrix})$
Back to Exercise 3.18

Answer.
1. No. To see if there are $c_{1}, c_{2} \in ℝ$ such that
  
  $c_{1} (\begin{matrix} 1 \\ 1 \end{matrix}) + c_{2} (\begin{matrix} 1 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ - 3 \end{matrix})$
  
  we can use Gauss’s Method on the resulting linear system.
  
  $\begin{array}{rcrcr} c_{1} & + & c_{2} & = & 1 \\ c_{1} & + & c_{2} & = & 3 \end{array} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} \begin{array}{rcrcr} c_{1} & + & c_{2} & = & 1 \\ 0 & = & 2 \end{array}$
  
  There is no solution and so the vector is not in the column space.
2. Yes. From this relationship
  
  $c_{1} (\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}) + c_{2} (\begin{matrix} 3 \\ 0 \\ - 3 \end{matrix}) + c_{3} (\begin{matrix} 1 \\ 4 \\ - 3 \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix})$
  
  we get a linear system that, when we apply Gauss’s Method,
  
  $(\begin{array}{cccr} 1 & 3 & 1 & 1 \\ 2 & 0 & 4 & 0 \\ 1 & - 3 & - 3 & 0 \end{array}) ⟶_{\begin{array}{l} - ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{array}{cccr} 1 & 3 & 1 & 1 \\ 0 & - 6 & 2 & - 2 \\ 0 & 0 & - 6 & 1 \end{array})$
  
  yields a solution. Thus, the vector is in the column space.
Exercise 3.19 Worked answer

Recommended. Decide if the vector is in the column space of the matrix.
1. $(\begin{matrix} 2 & 1 \\ 2 & 5 \end{matrix})$ , $(\begin{matrix} 1 \\ - 3 \end{matrix})$
2. $(\begin{matrix} 4 & - 8 \\ 2 & - 4 \end{matrix})$ , $(\begin{matrix} 0 \\ 1 \end{matrix})$
3. $(\begin{matrix} 1 & - 1 & 1 \\ 1 & 1 & - 1 \\ - 1 & - 1 & 1 \end{matrix})$ , $(\begin{matrix} 2 \\ 0 \\ 0 \end{matrix})$
Back to Exercise 3.19

Answer.
1. Yes; we are asking if there are scalars $c_{1}$ and $c_{2}$ such that
  
  $c_{1} (\begin{matrix} 2 \\ 2 \end{matrix}) + c_{2} (\begin{matrix} 1 \\ 5 \end{matrix}) = (\begin{matrix} 1 \\ - 3 \end{matrix})$
  
  which gives rise to a linear system
  
  $\begin{array}{rcrcr} 2 c_{1} & + & c_{2} & = & 1 \\ 2 c_{1} & + & 5 c_{2} & = & - 3 \end{array} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} \begin{array}{rcrcr} 2 c_{1} & + & c_{2} & = & 1 \\ 4 c_{2} & = & - 4 \end{array}$
  
  and Gauss’s Method produces $c_{2} = - 1$ and $c_{1} = 1$ . That is, there is indeed such a pair of scalars and so the vector is indeed in the column space of the matrix.
2. No; we are asking if there are scalars $c_{1}$ and $c_{2}$ such that
  
  $c_{1} (\begin{matrix} 4 \\ 2 \end{matrix}) + c_{2} (\begin{matrix} - 8 \\ - 4 \end{matrix}) = (\begin{matrix} 0 \\ 1 \end{matrix})$
  
  and one way to proceed is to consider the resulting linear system
  
  $\begin{array}{rcrcr} 4 c_{1} & - & 8 c_{2} & = & 0 \\ 2 c_{1} & - & 4 c_{2} & = & 1 \end{array}$
  
  that is easily seen to have no solution. Another way to proceed is to note that any linear combination of the columns on the left has a second component half as big as its first component, but the vector on the right does not meet that criterion.
3. Yes; we can simply observe that the vector is the first column minus the second. Or, failing that, setting up the relationship among the columns
  
  $c_{1} (\begin{matrix} 1 \\ 1 \\ - 1 \end{matrix}) + c_{2} (\begin{matrix} - 1 \\ 1 \\ - 1 \end{matrix}) + c_{3} (\begin{matrix} 1 \\ - 1 \\ 1 \end{matrix}) = (\begin{matrix} 2 \\ 0 \\ 0 \end{matrix})$
  
  and considering the resulting linear system
  
  $\begin{array}{rcrcrcr} c_{1} & - & c_{2} & + & c_{3} & = & 2 \\ c_{1} & + & c_{2} & - & c_{3} & = & 0 \\ - c_{1} & - & c_{2} & + & c_{3} & = & 0 \end{array} ⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} \begin{array}{rcrcrcr} c_{1} & - & c_{2} & + & c_{3} & = & 2 \\ 2 c_{2} & - & 2 c_{3} & = & - 2 \\ - 2 c_{2} & + & 2 c_{3} & = & 2 \end{array} ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{3}} \begin{array}{rcrcrcr} c_{1} & - & c_{2} & + & c_{3} & = & 2 \\ 2 c_{2} & - & 2 c_{3} & = & - 2 \\ 0 & = & 0 \end{array}$
  
  gives the additional information (beyond that there is at least one solution) that there are infinitely many solutions. Parametrizing gives $c_{2} = - 1 + c_{3}$ and $c_{1} = 1$ , and so taking $c_{3}$ to be zero gives a particular solution of $c_{1} = 1$ , $c_{2} = - 1$ , and $c_{3} = 0$ (which is, of course, the observation made at the start).
Exercise 3.20 Worked answer

Recommended. Find a basis for the row space of this matrix.

$(\begin{matrix} 2 & 0 & 3 & 4 \\ 0 & 1 & 1 & - 1 \\ 3 & 1 & 0 & 2 \\ 1 & 0 & - 4 & - 1 \end{matrix})$

Back to Exercise 3.20

Answer. A routine Gaussian reduction

$(\begin{matrix} 2 & 0 & 3 & 4 \\ 0 & 1 & 1 & - 1 \\ 3 & 1 & 0 & 2 \\ 1 & 0 & - 4 & - 1 \end{matrix}) ⟶_{\begin{array}{l} - (1 / 2) ρ_{1} + ρ_{4} \end{array}}^{- (3 / 2) ρ_{1} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{3} + ρ_{4}} (\begin{matrix} 2 & 0 & 3 & 4 \\ 0 & 1 & 1 & - 1 \\ 0 & 0 & - 11 / 2 & - 3 \\ 0 & 0 & 0 & 0 \end{matrix})$

suggests this basis $⟨ (\begin{matrix} 2 & 0 & 3 & 4 \end{matrix}), (\begin{matrix} 0 & 1 & 1 & - 1 \end{matrix}), (\begin{matrix} 0 & 0 & - 11 / 2 & - 3 \end{matrix}) ⟩$ .

Another procedure, perhaps more convenient, is to swap rows first,

$⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{4}} ⟶_{\begin{array}{l} - 2 ρ_{1} + ρ_{4} \end{array}}^{- 3 ρ_{1} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{3} + ρ_{4}} (\begin{matrix} 1 & 0 & - 4 & - 1 \\ 0 & 1 & 1 & - 1 \\ 0 & 0 & 11 & 6 \\ 0 & 0 & 0 & 0 \end{matrix})$

leading to the basis $⟨ (\begin{matrix} 1 & 0 & - 4 & - 1 \end{matrix}), (\begin{matrix} 0 & 1 & 1 & - 1 \end{matrix}), (\begin{matrix} 0 & 0 & 11 & 6 \end{matrix}) ⟩$ .
Exercise 3.21 Worked answer

Recommended. Find the rank of each matrix.
1. $(\begin{matrix} 2 & 1 & 3 \\ 1 & - 1 & 2 \\ 1 & 0 & 3 \end{matrix})$
2. $(\begin{matrix} 1 & - 1 & 2 \\ 3 & - 3 & 6 \\ - 2 & 2 & - 4 \end{matrix})$
3. $(\begin{matrix} 1 & 3 & 2 \\ 5 & 1 & 1 \\ 6 & 4 & 3 \end{matrix})$
4. $(\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$
Back to Exercise 3.21

Answer.
1. This reduction
  
  $⟶_{\begin{array}{l} - (1 / 2) ρ_{1} + ρ_{3} \end{array}}^{- (1 / 2) ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- (1 / 3) ρ_{2} + ρ_{3}} (\begin{matrix} 2 & 1 & 3 \\ 0 & - 3 / 2 & 1 / 2 \\ 0 & 0 & 4 / 3 \end{matrix})$
  
  shows that the row rank, and hence the rank, is three.
2. Inspection of the columns shows that the others are multiples of the first (inspection of the rows shows the same thing). Thus the rank is one.
  
  Alternatively, the reduction
  
  $(\begin{matrix} 1 & - 1 & 2 \\ 3 & - 3 & 6 \\ - 2 & 2 & - 4 \end{matrix}) ⟶_{\begin{array}{l} 2 ρ_{1} + ρ_{3} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & - 1 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$
  
  shows the same thing.
3. This calculation
  
  $(\begin{matrix} 1 & 3 & 2 \\ 5 & 1 & 1 \\ 6 & 4 & 3 \end{matrix}) ⟶_{\begin{array}{l} - 6 ρ_{1} + ρ_{3} \end{array}}^{- 5 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 3 & 2 \\ 0 & - 14 & - 9 \\ 0 & 0 & 0 \end{matrix})$
  
  shows that the rank is two.
4. The rank is zero.
Exercise 3.22 Worked answer

Give a basis for the column space of this matrix. Give the matrix’s rank.

$(\begin{matrix} 1 & 3 & - 1 & 2 \\ 2 & 1 & 1 & 0 \\ 0 & 1 & 1 & 4 \end{matrix})$

Back to Exercise 3.22

Answer. We want a basis for this span.

$[(\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}), (\begin{matrix} 3 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} - 1 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 2 \\ 0 \\ 4 \end{matrix})] \subseteq ℝ^{3}$

The most straightforward approach is to transpose those columns to rows, use Gauss’s Method to find a basis for the span of the rows, and then transpose them back to columns.

$(\begin{matrix} 1 & 2 & 0 \\ 3 & 1 & 1 \\ - 1 & 1 & 1 \\ 2 & 0 & 4 \end{matrix}) ⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \\ - 2 ρ_{1} + ρ_{4} \end{array}}^{- 3 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} - (4 / 5) ρ_{2} + ρ_{4} \end{array}}^{(3 / 5) ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{3} + ρ_{4}} (\begin{matrix} 1 & 2 & 0 \\ 0 & - 5 & 1 \\ 0 & 0 & 8 / 5 \\ 0 & 0 & 0 \end{matrix})$

Discard the zero vector as showing that there was a redundancy among the starting vectors, to get this basis for the column space.

$⟨ (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ - 5 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 8 / 5 \end{matrix}) ⟩$

The matrix’s rank is the dimension of its column space, so it is three. (It is also equal to the dimension of its row space.)
Exercise 3.23 Worked answer

Recommended. Find a basis for the span of each set.
1. ${(\begin{matrix} 1 & 3 \end{matrix}), (\begin{matrix} - 1 & 3 \end{matrix}), (\begin{matrix} 1 & 4 \end{matrix}), (\begin{matrix} 2 & 1 \end{matrix})} \subseteq ℳ_{1 \times 2}$
2. ${(\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}), (\begin{matrix} 3 \\ 1 \\ - 1 \end{matrix}), (\begin{matrix} 1 \\ - 3 \\ - 3 \end{matrix})} \subseteq ℝ^{3}$
3. ${1 + x, 1 - x^{2}, 3 + 2 x - x^{2}} \subseteq 𝒫_{3}$
4. ${(\begin{matrix} 1 & 0 & 1 \\ 3 & 1 & - 1 \end{matrix}), (\begin{matrix} 1 & 0 & 3 \\ 2 & 1 & 4 \end{matrix}), (\begin{matrix} - 1 & 0 & - 5 \\ - 1 & - 1 & - 9 \end{matrix})} \subseteq ℳ_{2 \times 3}$
Back to Exercise 3.23

Answer.
1. This reduction
  
  $(\begin{matrix} 1 & 3 \\ - 1 & 3 \\ 1 & 4 \\ 2 & 1 \end{matrix}) ⟶_{\begin{array}{l} - ρ_{1} + ρ_{3} \\ - 2 ρ_{1} + ρ_{4} \end{array}}^{ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} (5 / 6) ρ_{2} + ρ_{4} \end{array}}^{- (1 / 6) ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 3 \\ 0 & 6 \\ 0 & 0 \\ 0 & 0 \end{matrix})$
  
  gives $⟨ (\begin{matrix} 1 & 3 \end{matrix}), (\begin{matrix} 0 & 6 \end{matrix}) ⟩$ .
2. Transposing and reducing
  
  $(\begin{matrix} 1 & 2 & 1 \\ 3 & 1 & - 1 \\ 1 & - 3 & - 3 \end{matrix}) ⟶_{\begin{array}{l} - ρ_{1} + ρ_{3} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 2 & 1 \\ 0 & - 5 & - 4 \\ 0 & - 5 & - 4 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 2 & 1 \\ 0 & - 5 & - 4 \\ 0 & 0 & 0 \end{matrix})$
  
  and then transposing back gives this basis.
  
  $⟨ (\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ - 5 \\ - 4 \end{matrix}) ⟩$
3. Notice first that the surrounding space is as $𝒫_{3}$ , not $𝒫_{2}$ . Then, taking the first polynomial $1 + 1 \cdot x + 0 \cdot x^{2} + 0 \cdot x^{3}$ to be “the same” as the row vector $(\begin{matrix} 1 & 1 & 0 & 0 \end{matrix})$ , etc., leads to
  
  $(\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 0 & - 1 & 0 \\ 3 & 2 & - 1 & 0 \end{matrix}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & - 1 & - 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})$
  
  which yields the basis $⟨ 1 + x, - x - x^{2} ⟩$ .
4. Here “the same” gives
  
  $(\begin{matrix} 1 & 0 & 1 & 3 & 1 & - 1 \\ 1 & 0 & 3 & 2 & 1 & 4 \\ - 1 & 0 & - 5 & - 1 & - 1 & - 9 \end{matrix}) ⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{2 ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 0 & 1 & 3 & 1 & - 1 \\ 0 & 0 & 2 & - 1 & 0 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix})$
  
  leading to this basis.
  
  $⟨ (\begin{matrix} 1 & 0 & 1 \\ 3 & 1 & - 1 \end{matrix}), (\begin{matrix} 0 & 0 & 2 \\ - 1 & 0 & 5 \end{matrix}) ⟩$
Exercise 3.24 Worked answer

Give a basis for the span of each set, in the natural vector space.
1. ${(\begin{matrix} 1 \\ 1 \\ 3 \end{matrix}), (\begin{matrix} - 1 \\ 2 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 12 \\ 6 \end{matrix})}$
2. ${x + x^{2}, 2 - 2 x, 7, 4 + 3 x + 2 x^{2}}$
Back to Exercise 3.24

Answer.
1. Transpose the columns to rows, bring to echelon form (and then lose any zero rows), and transpose back to columns.
  
  $(\begin{matrix} 1 & 1 & 3 \\ - 1 & 2 & 0 \\ 0 & 12 & 6 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 4 ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 1 & 3 \\ 0 & 3 & 3 \\ 0 & 0 & - 6 \end{matrix})$
  
  One basis for the span is this.
  
  $⟨ (\begin{matrix} 1 \\ 1 \\ 3 \end{matrix}), (\begin{matrix} 0 \\ 3 \\ 3 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ - 6 \end{matrix}) ⟩$
2. As in the prior part we think of those as rows, to take advantage of the work we’ve done with Gauss’s Method.
  
  $\begin{matrix} (\begin{matrix} 0 & 1 & 1 \\ 2 & - 2 & 0 \\ 7 & 0 & 0 \\ 4 & 3 & 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} ⟶_{\begin{array}{l} 2 ρ_{1} + ρ_{4} \end{array}}^{- (7 / 2) ρ_{1} + ρ_{3}} ⟶_{\begin{array}{l} - 7 ρ_{2} + ρ_{4} \end{array}}^{- 7 ρ_{2} + ρ_{3}} \\ ⟶_{\begin{array}{l} \end{array}}^{- (5 / 7) ρ_{3} + ρ_{4}} (\begin{matrix} 2 & - 2 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & - 7 \\ 0 & 0 & 0 \end{matrix}) \end{matrix}$
  
  One basis for the span of that set is $⟨ 2 - 2 x, x + x^{2}, - 5 x^{2} ⟩$ .
Exercise 3.25 Worked answer

Which matrices have rank zero? Rank one?

Back to Exercise 3.25

Answer. Only the zero matrices have rank of zero. The only matrices of rank one have the form

$(\begin{matrix} k_{1} \cdot ρ \\ ⋮ \\ k_{m} \cdot ρ \end{matrix})$

where $ρ$ is some nonzero row vector, and not all of the $k_{i}$ ’s are zero. (Remark. We can’t simply say that all of the rows are multiples of the first because the first row might be the zero row. Another Remark. The above also applies with ‘column’ replacing ‘row’.)
Exercise 3.26 Worked answer

Recommended. Given $a, b, c \in ℝ$ , what choice of $d$ will cause this matrix to have the rank of one?

$(\begin{matrix} a & b \\ c & d \end{matrix})$

Back to Exercise 3.26

Answer. If $a \neq 0$ then a choice of $d = (c / a) b$ will make the second row be a multiple of the first, specifically, $c / a$ times the first. If $a = 0$ and $b = 0$ then any non- $0$ choice for $d$ will ensure that the second row is nonzero. If $a = 0$ and $b \neq 0$ and $c = 0$ then any choice for $d$ will do, since the matrix will automatically have rank one (even with the choice of $d = 0$ ). Finally, if $a = 0$ and $b \neq 0$ and $c \neq 0$ then no choice for $d$ will suffice because the matrix is sure to have rank two.
Exercise 3.27 Worked answer

Find the column rank of this matrix.

$(\begin{matrix} 1 & 3 & - 1 & 5 & 0 & 4 \\ 2 & 0 & 1 & 0 & 4 & 1 \end{matrix})$

Back to Exercise 3.27

Answer. The column rank is two. One way to see this is by inspection—the column space consists of two-tall columns and so can have a dimension of at least two, and we can easily find two columns that together form a linearly independent set (the fourth and fifth columns, for instance). Another way to see this is to recall that the column rank equals the row rank, and to perform Gauss’s Method, which leaves two nonzero rows.
Exercise 3.28 Worked answer

Show that a linear system with at least one solution has at most one solution if and only if the matrix of coefficients has rank equal to the number of its columns.

Back to Exercise 3.28

Answer. We apply Theorem 3.13. The number of columns of a matrix of coefficients $A$ of a linear system equals the number $n$ of unknowns. A linear system with at least one solution has at most one solution if and only if the space of solutions of the associated homogeneous system has dimension zero (recall: in the ‘ $General = Particular + Homogeneous$ ’ equation $\vec{v} = \vec{p} + \vec{h}$ , provided that such a $\vec{p}$ exists, the solution $\vec{v}$ is unique if and only if the vector $\vec{h}$ is unique, namely $\vec{h} = \vec{0}$ ). But that means, by the theorem, that $n = r$ .
Exercise 3.29 Worked answer

Recommended. If a matrix is $5 \times 9$ , which set must be dependent, its set of rows or its set of columns?

Back to Exercise 3.29

Answer. The set of columns must be dependent because the rank of the matrix is at most five while there are nine columns.
Exercise 3.30 Worked answer

Give an example to show that, despite that they have the same dimension, the row space and column space of a matrix need not be equal. Are they ever equal?

Back to Exercise 3.30

Answer. There is little danger of their being equal since the row space is a set of row vectors while the column space is a set of columns (unless the matrix is $1 \times 1$ , in which case the two spaces must be equal).

Remark. Consider

$A = (\begin{matrix} 1 & 3 \\ 2 & 6 \end{matrix})$

and note that the row space is the set of all multiples of $(\begin{matrix} 1 & 3 \end{matrix})$ while the column space consists of multiples of

$(\begin{matrix} 1 \\ 2 \end{matrix})$

so we also cannot argue that the two spaces must be simply transposes of each other.
Exercise 3.31 Worked answer

Show that the set ${(1, - 1, 2, - 3), (1, 1, 2, 0), (3, - 1, 6, - 6)}$ does not have the same span as ${(1, 0, 1, 0), (0, 2, 0, 3)}$ . What, by the way, is the vector space?

Back to Exercise 3.31

Answer. First, the vector space is the set of four-tuples of real numbers, under the natural operations. Although this is not the set of four-wide row vectors, the difference is slight—it is “the same” as that set. So we will treat the four-tuples like four-wide vectors.

With that, one way to see that $(1, 0, 1, 0)$ is not in the span of the first set is to note that this reduction

$(\begin{matrix} 1 & - 1 & 2 & - 3 \\ 1 & 1 & 2 & 0 \\ 3 & - 1 & 6 & - 6 \end{matrix}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & - 1 & 2 & - 3 \\ 0 & 2 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{matrix})$

and this one

$(\begin{matrix} 1 & - 1 & 2 & - 3 \\ 1 & 1 & 2 & 0 \\ 3 & - 1 & 6 & - 6 \\ 1 & 0 & 1 & 0 \end{matrix}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \\ - ρ_{1} + ρ_{4} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} - (1 / 2) ρ_{2} + ρ_{4} \end{array}}^{- ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{3} \leftrightarrow ρ_{4}} (\begin{matrix} 1 & - 1 & 2 & - 3 \\ 0 & 2 & 0 & 3 \\ 0 & 0 & - 1 & 3 / 2 \\ 0 & 0 & 0 & 0 \end{matrix})$

yield matrices differing in rank. This means that addition of $(1, 0, 1, 0)$ to the set of the first three four-tuples increases the rank, and hence the span, of that set. Therefore $(1, 0, 1, 0)$ is not already in the span.
Exercise 3.32 Worked answer

Recommended. Show that this set of column vectors

${(\begin{matrix} d_{1} \\ d_{2} \\ d_{3} \end{matrix}) ∣ there are x, y, and z such that: \begin{array}{rcrcrcr} 3 x & + & 2 y & + & 4 z & = & d_{1} \\ x & - & z & = & d_{2} \\ 2 x & + & 2 y & + & 5 z & = & d_{3} \end{array}}$

is a subspace of $ℝ^{3}$ . Find a basis.

Back to Exercise 3.32

Answer. It is a subspace because it is the column space of the matrix

$(\begin{matrix} 3 & 2 & 4 \\ 1 & 0 & - 1 \\ 2 & 2 & 5 \end{matrix})$

of coefficients. To find a basis for the column space,

${c_{1} (\begin{matrix} 3 \\ 1 \\ 2 \end{matrix}) + c_{2} (\begin{matrix} 2 \\ 0 \\ 2 \end{matrix}) + c_{3} (\begin{matrix} 4 \\ - 1 \\ 5 \end{matrix}) ∣ c_{1}, c_{2}, c_{3} \in ℝ}$

we eliminate linear relationships among the three column vectors from the spanning set by transposing, reducing,

$(\begin{matrix} 3 & 1 & 2 \\ 2 & 0 & 2 \\ 4 & - 1 & 5 \end{matrix}) ⟶_{\begin{array}{l} - (4 / 3) ρ_{1} + ρ_{3} \end{array}}^{- (2 / 3) ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- (7 / 2) ρ_{2} + ρ_{3}} (\begin{matrix} 3 & 1 & 2 \\ 0 & - 2 / 3 & 2 / 3 \\ 0 & 0 & 0 \end{matrix})$

omitting the zero row, and transposing back.

$⟨ (\begin{matrix} 3 \\ 1 \\ 2 \end{matrix}), (\begin{matrix} 0 \\ - 2 / 3 \\ 2 / 3 \end{matrix}) ⟩$
Exercise 3.33 Worked answer

Show that the transpose operation is linear:

${(r A + s B)}^{𝖳} = r A^{𝖳} + s B^{𝖳}$

for $r, s \in ℝ$ and $A, B \in ℳ_{m \times n}$ .

Back to Exercise 3.33

Answer. We can do this as a straightforward calculation.

$\begin{aligned} {(r A + s B)}^{𝖳} & = {(\begin{array}{c} r a_{1, 1} + s b_{1, 1} & \dots & r a_{1, n} + s b_{1, n} \\ ⋮ \\ r a_{m, 1} + s b_{m, 1} & \dots & r a_{m, n} + s b_{m, n} \end{array})}^{𝖳} \\ = (\begin{array}{c} r a_{1, 1} + s b_{1, 1} & \dots & r a_{m, 1} + s b_{m, 1} \\ ⋮ \\ r a_{1, n} + s b_{1, n} & \dots & r a_{m, n} + s b_{m, n} \end{array}) \\ = (\begin{array}{c} r a_{1, 1} & \dots & r a_{m, 1} \\ ⋮ \\ r a_{1, n} & \dots & r a_{m, n} \end{array}) + (\begin{array}{c} s b_{1, 1} & \dots & s b_{m, 1} \\ ⋮ \\ s b_{1, n} & \dots & s b_{m, n} \end{array}) \\ = r A^{𝖳} + s B^{𝖳} \end{aligned}$
Exercise 3.34 Worked answer

Recommended. In this subsection we have shown that Gaussian reduction finds a basis for the row space.
1. Show that this basis is not unique—different reductions may yield different bases.
2. Produce matrices with equal row spaces but unequal numbers of rows.
3. Prove that two matrices have equal row spaces if and only if after Gauss-Jordan reduction they have the same nonzero rows.
Back to Exercise 3.34

Answer.
1. These reductions give different bases.
  
  $(\begin{matrix} 1 & 2 & 0 \\ 1 & 2 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 2 & 0 \\ 1 & 2 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{2 ρ_{2}} (\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 2 \end{matrix})$
2. An easy example is this.
  
  $(\begin{matrix} 1 & 2 & 1 \\ 3 & 1 & 4 \end{matrix}) (\begin{matrix} 1 & 2 & 1 \\ 3 & 1 & 4 \\ 0 & 0 & 0 \end{matrix})$
  
  This is a less simplistic example.
  
  $(\begin{matrix} 1 & 2 & 1 \\ 3 & 1 & 4 \end{matrix}) (\begin{matrix} 1 & 2 & 1 \\ 3 & 1 & 4 \\ 2 & 4 & 2 \\ 4 & 3 & 5 \end{matrix})$
3. Because the row spaces of $A$ and $B$ are equal, the two are row equivalent. Because each row equivalence class contains a unique reduced echelon form (Theorem One.III.2.6), the reduced echelon form of $A$ must equal the reduced echelon form of $B$ .
Exercise 3.35 Worked answer

Why is there not a problem with Remark 3.15 in the case that $r$ is bigger than $n$ ?

Back to Exercise 3.35

Answer. It cannot be bigger.
Exercise 3.36 Worked answer

Show that the row rank of an $m \times n$ matrix is at most $m$ . Is there a better bound?

Back to Exercise 3.36

Answer. The number of rows in a maximal linearly independent set cannot exceed the number of rows. A better bound (the bound that is, in general, the best possible) is the minimum of $m$ and $n$ , because the row rank equals the column rank.
Exercise 3.37 Worked answer

Show that the rank of a matrix equals the rank of its transpose.

Back to Exercise 3.37

Answer. Because the rows of a matrix $A$ are the columns of $A^{𝖳}$ the dimension of the row space of $A$ equals the dimension of the column space of $A^{𝖳}$ . But the dimension of the row space of $A$ is the rank of $A$ and the dimension of the column space of $A^{𝖳}$ is the rank of $A^{𝖳}$ . Thus the two ranks are equal.
Exercise 3.38 Worked answer

True or false: the column space of a matrix equals the row space of its transpose.

Back to Exercise 3.38

Answer. False. The first is a set of columns while the second is a set of rows.

This example, however,

$A = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}), A^{𝖳} = (\begin{matrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{matrix})$

indicates that as soon as we have a formal meaning for “the same”, we can apply it here:

$Columnspace (A) = [{(\begin{matrix} 1 \\ 4 \end{matrix}), (\begin{matrix} 2 \\ 5 \end{matrix}), (\begin{matrix} 3 \\ 6 \end{matrix})}]$

while

$Rowspace (A^{𝖳}) = [{(\begin{matrix} 1 & 4 \end{matrix}), (\begin{matrix} 2 & 5 \end{matrix}), (\begin{matrix} 3 & 6 \end{matrix})}]$

are “the same” as each other.
Exercise 3.39 Worked answer

Recommended. We have seen that a row operation may change the column space. Must it?

Back to Exercise 3.39

Answer. No. Here, Gauss’s Method does not change the column space.

$(\begin{matrix} 1 & 0 \\ 3 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
Exercise 3.40 Worked answer

Prove that a linear system has a solution if and only if that system’s matrix of coefficients has the same rank as its augmented matrix.

Back to Exercise 3.40

Answer. A linear system

$c_{1} {\vec{a}}_{1} + \dots + c_{n} {\vec{a}}_{n} = \vec{d}$

has a solution if and only if $\vec{d}$ is in the span of the set ${{\vec{a}}_{1}, \dots, {\vec{a}}_{n}}$ . That’s true if and only if the column rank of the augmented matrix equals the column rank of the matrix of coefficients. Since rank equals the column rank, the system has a solution if and only if the rank of its augmented matrix equals the rank of its matrix of coefficients.
Exercise 3.41 Worked answer

An $m \times n$ matrix has full row rank if its row rank is $m$ , and it has full column rank if its column rank is $n$ .
1. Show that a matrix can have both full row rank and full column rank only if it is square.
2. Prove that the linear system with matrix of coefficients $A$ has a solution for any $d_{1}$ , …, $d_{n}$ ’s on the right side if and only if $A$ has full row rank.
3. Prove that a homogeneous system has a unique solution if and only if its matrix of coefficients $A$ has full column rank.
4. Prove that the statement “if a system with matrix of coefficients $A$ has any solution then it has a unique solution” holds if and only if $A$ has full column rank.
Back to Exercise 3.41

Answer.
1. Row rank equals column rank so each is at most the minimum of the number of rows and columns. Hence both can be full only if the number of rows equals the number of columns. (Of course, the converse does not hold: a square matrix need not have full row rank or full column rank.)
2. If $A$ has full row rank then, no matter what the right-hand side, Gauss’s Method on the augmented matrix ends with a leading one in each row and none of those leading ones in the furthest right column (the “augmenting” column). Back substitution then gives a solution.
  
  On the other hand, if the linear system lacks a solution for some right-hand side it can only be because Gauss’s Method leaves some row so that it has all zeroes on the left of the “augmenting” bar and has a nonzero entry on the right. Thus, if $A$ does not have a solution for some right-hand sides, then $A$ does not have full row rank because some of its rows have been eliminated.
3. The matrix $A$ has full column rank if and only if its columns form a linearly independent set. That’s equivalent to the existence of only the trivial linear relationship among the columns, so the only solution of the system is where each variable is $0$ .
4. The matrix $A$ has full column rank if and only if the set of its columns is linearly independent, and so forms a basis for its span. That’s equivalent to the existence of a unique linear representation of all vectors in that span. That proves it, since any linear representation of a vector in the span is a solution of the linear system.
Exercise 3.42 Worked answer

How would the conclusion of Lemma 3.3 change if Gauss’s Method were changed to allow multiplying a row by zero?

Back to Exercise 3.42

Answer. Instead of the row spaces being the same, the row space of $B$ would be a subspace (possibly equal to) the row space of $A$ .
Exercise 3.43 Worked answer

What is the relationship between $rank (A)$ and $rank (- A)$ ? Between $rank (A)$ and $rank (k A)$ ? What, if any, is the relationship between $rank (A)$ , $rank (B)$ , and $rank (A + B)$ ?

Back to Exercise 3.43

Answer. Clearly $rank (A) = rank (- A)$ as Gauss’s Method allows us to multiply all rows of a matrix by $- 1$ . In the same way, when $k \neq 0$ we have $rank (A) = rank (k A)$ .

Addition is more interesting. The rank of a sum can be smaller than the rank of the summands.

$(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) + (\begin{matrix} - 1 & - 2 \\ - 3 & - 4 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$

The rank of a sum can be bigger than the rank of the summands.

$(\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix}) + (\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}) = (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$

But there is an upper bound (other than the size of the matrices). In general, $rank (A + B) \leq rank (A) + rank (B)$ .

To prove this, note that we can perform Gaussian elimination on $A + B$ in either of two ways: we can first add $A$ to $B$ and then apply the appropriate sequence of reduction steps

$(A + B) ⟶_{\begin{array}{l} \end{array}}^{{step}_{1}} \dots ⟶_{\begin{array}{l} \end{array}}^{{step}_{k}} echelon form$

or we can get the same results by performing ${step}_{1}$ through ${step}_{k}$ separately on $A$ and $B$ , and then adding. The largest rank that we can end with in the second case is clearly the sum of the ranks. (The matrices above give examples of both possibilities, $rank (A + B) < rank (A) + rank (B)$ and $rank (A + B) = rank (A) + rank (B)$ , happening.)

Combining Subspaces

This subsection is optional. It is required only for the last sections of Chapter Three and Chapter Five and for occasional exercises. You can pass it over without loss of continuity.

One way to understand something is to see how to build it from component parts. For instance, we sometimes think of $ℝ^{3}$ put together from the $x$ -axis, the $y$ -axis, and $z$ -axis. In this subsection we will describe how to decompose a vector space into a combination of some of its subspaces. In developing this idea of subspace combination, we will keep the $ℝ^{3}$ example in mind as a prototype.

Subspaces are subsets and sets combine via union. But taking the combination operation for subspaces to be the simple set union operation isn’t what we want. For instance, the union of the $x$ -axis, the $y$ -axis, and $z$ -axis is not all of $ℝ^{3}$ . In fact this union is not a subspace because it is not closed under addition: this vector

$(\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix})$

is in none of the three axes and hence is not in the union. Therefore to combine subspaces, in addition to the members of those subspaces, we must at least also include all of their linear combinations.

Definition 4.1 Where $W_{1}, \dots, W_{k}$ are subspaces of a vector space, their sum is the span of their union $W_{1} + W_{2} + \dots + W_{k} = [W_{1} \cup W_{2} \cup \dots W_{k}]$ .

Writing ‘ $+$ ’ fits with the conventional practice of using this symbol for a natural accumulation operation.

Example 4.2 Our $ℝ^{3}$ prototype works with this. Any vector $\vec{w} \in ℝ^{3}$ is a linear combination $c_{1} {\vec{v}}_{1} + c_{2} {\vec{v}}_{2} + c_{3} {\vec{v}}_{3}$ where ${\vec{v}}_{1}$ is a member of the $x$ -axis, etc., in this way

$(\begin{matrix} w_{1} \\ w_{2} \\ w_{3} \end{matrix}) = 1 \cdot (\begin{matrix} w_{1} \\ 0 \\ 0 \end{matrix}) + 1 \cdot (\begin{matrix} 0 \\ w_{2} \\ 0 \end{matrix}) + 1 \cdot (\begin{matrix} 0 \\ 0 \\ w_{3} \end{matrix})$

and so $x -axis + y -axis + z -axis = ℝ^{3}$ .

Example 4.3 A sum of subspaces can be less than the entire space. Inside of $𝒫_{4}$ , let $L$ be the subspace of linear polynomials ${a + b x ∣ a, b \in ℝ}$ and let $C$ be the subspace of purely-cubic polynomials ${c x^{3} ∣ c \in ℝ}$ . Then $L + C$ is not all of $𝒫_{4}$ . Instead, $L + C = {a + b x + c x^{3} ∣ a, b, c \in ℝ}$ .

Example 4.4 A space can be described as a combination of subspaces in more than one way. Besides the decomposition $ℝ^{3} = x -axis + y -axis + z -axis$ , we can also write $ℝ^{3} = x y -plane + y z -plane$ . To check this, note that any $\vec{w} \in ℝ^{3}$ can be written as a linear combination of a member of the $x y$ -plane and a member of the $y z$ -plane; here are two such combinations.

$(\begin{matrix} w_{1} \\ w_{2} \\ w_{3} \end{matrix}) = 1 \cdot (\begin{matrix} w_{1} \\ w_{2} \\ 0 \end{matrix}) + 1 \cdot (\begin{matrix} 0 \\ 0 \\ w_{3} \end{matrix}) (\begin{matrix} w_{1} \\ w_{2} \\ w_{3} \end{matrix}) = 1 \cdot (\begin{matrix} w_{1} \\ w_{2} / 2 \\ 0 \end{matrix}) + 1 \cdot (\begin{matrix} 0 \\ w_{2} / 2 \\ w_{3} \end{matrix})$

The above definition gives one way in which we can think of a space as a combination of some of its parts. However, the prior example shows that there is at least one interesting property of our benchmark model that is not captured by the definition of the sum of subspaces. In the familiar decomposition of $ℝ^{3}$ , we often speak of a vector’s ‘ $x$ part’ or ‘ $y$ part’ or ‘ $z$ part’. That is, in our prototype each vector has a unique decomposition into pieces from the parts making up the whole space. But in the decomposition used in Example 4.4, we cannot refer to the “ $x y$ part” of a vector—these three sums

$(\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) = (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 0 \\ 3 \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 2 \\ 3 \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 1 \\ 3 \end{matrix})$

all describe the vector as comprised of something from the first plane plus something from the second plane, but the “ $x y$ part” is different in each.

That is, when we consider how $ℝ^{3}$ is put together from the three axes we might mean “in such a way that every vector has at least one decomposition,” which gives the definition above. But if we take it to mean “in such a way that every vector has one and only one decomposition” then we need another condition on combinations. To see what this condition is, recall that vectors are uniquely represented in terms of a basis. We can use this to break a space into a sum of subspaces such that any vector in the space breaks uniquely into a sum of members of those subspaces.

Example 4.5 Consider $ℝ^{3}$ with its standard basis $ℰ_{3} = ⟨ {\vec{e}}_{1}, {\vec{e}}_{2}, {\vec{e}}_{3} ⟩$ . The subspace with the basis $B_{1} = ⟨ {\vec{e}}_{1} ⟩$ is the $x$ -axis, the subspace with the basis $B_{2} = ⟨ {\vec{e}}_{2} ⟩$ is the $y$ -axis, and the subspace with the basis $B_{3} = ⟨ {\vec{e}}_{3} ⟩$ is the $z$ -axis. The fact that any member of $ℝ^{3}$ is expressible as a sum of vectors from these subspaces

$(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} x \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ y \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 0 \\ z \end{matrix})$

reflects the fact that $ℰ_{3}$ spans the space—this equation

$(\begin{matrix} x \\ y \\ z \end{matrix}) = c_{1} (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + c_{2} (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}) + c_{3} (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix})$

has a solution for any $x, y, z \in ℝ$ . And the fact that each such expression is unique reflects that fact that $ℰ_{3}$ is linearly independent, so any equation like the one above has a unique solution.

Example 4.6 We don’t have to take the basis vectors one at a time, we can conglomerate them into larger sequences. Consider again the space $ℝ^{3}$ and the vectors from the standard basis $ℰ_{3}$ . The subspace with the basis $B_{1} = ⟨ {\vec{e}}_{1}, {\vec{e}}_{3} ⟩$ is the $x z$ -plane. The subspace with the basis $B_{2} = ⟨ {\vec{e}}_{2} ⟩$ is the $y$ -axis. As in the prior example, the fact that any member of the space is a sum of members of the two subspaces in one and only one way

$(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} x \\ 0 \\ z \end{matrix}) + (\begin{matrix} 0 \\ y \\ 0 \end{matrix})$

is a reflection of the fact that these vectors form a basis—this equation

$(\begin{matrix} x \\ y \\ z \end{matrix}) = (c_{1} (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) + c_{3} (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix})) + c_{2} (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix})$

has one and only one solution for any $x, y, z \in ℝ$ .

Definition 4.7 The concatenation of the sequences $B_{1} = ⟨ {\vec{β}}_{1, 1}, \dots, {\vec{β}}_{1, n_{1}} ⟩$ , …, $B_{k} = ⟨ {\vec{β}}_{k, 1}, \dots, {\vec{β}}_{k, n_{k}} ⟩$ adjoins them into a single sequence.

$B_{1}^{⌢} B_{2}^{⌢} \dots^{⌢} B_{k} = ⟨ {\vec{β}}_{1, 1}, \dots, {\vec{β}}_{1, n_{1}}, {\vec{β}}_{2, 1}, \dots, {\vec{β}}_{k, n_{k}} ⟩$

Lemma 4.8 Let $V$ be a vector space that is the sum of some of its subspaces $V = W_{1} + \dots + W_{k}$ . Let $B_{1}$ , …, $B_{k}$ be bases for these subspaces. The following are equivalent.

The expression of any $\vec{v} \in V$ as a combination $\vec{v} = {\vec{w}}_{1} + \dots + {\vec{w}}_{k}$ with ${\vec{w}}_{i} \in W_{i}$ is unique.
The concatenation $B_{1}^{⌢} \dots^{⌢} B_{k}$ is a basis for $V$ .
Among nonzero vectors from different $W_{i}$ ’s every linear relationship is trivial.

Proof We will show that $(1) ⟹ (2)$ , that $(2) ⟹ (3)$ , and finally that $(3) ⟹ (1)$ . For these arguments, observe that we can pass from a combination of $\vec{w}$ ’s to a combination of $\vec{β}$ ’s

$\begin{aligned} d_{1} {\vec{w}}_{1} + \dots + d_{k} {\vec{w}}_{k} & = d_{1} (c_{1, 1} {\vec{β}}_{1, 1} + \dots + c_{1, n_{1}} {\vec{β}}_{1, n_{1}}) \\ + \dots + d_{k} (c_{k, 1} {\vec{β}}_{k, 1} + \dots + c_{k, n_{k}} {\vec{β}}_{k, n_{k}}) \\ = d_{1} c_{1, 1} \cdot {\vec{β}}_{1, 1} + \dots + d_{k} c_{k, n_{k}} \cdot {\vec{β}}_{k, n_{k}} & (*) \end{aligned}$

and vice versa (we can move from the bottom to the top by taking each $d_{i}$ to be $1$ ).

For $(1) ⟹ (2)$ , assume that all decompositions are unique. We will show that $B_{1}^{⌢} \dots^{⌢} B_{k}$ spans the space and is linearly independent. It spans the space because the assumption that $V = W_{1} + \dots + W_{k}$ means that every $\vec{v}$ can be expressed as $\vec{v} = {\vec{w}}_{1} + \dots + {\vec{w}}_{k}$ , which translates by equation ( $*$ ) to an expression of $\vec{v}$ as a linear combination of the $\vec{β}$ ’s from the concatenation. For linear independence, consider this linear relationship.

$\vec{0} = c_{1, 1} {\vec{β}}_{1, 1} + \dots + c_{k, n_{k}} {\vec{β}}_{k, n_{k}}$

Regroup as in ( $*$ ) (that is, move from bottom to top) to get the decomposition $\vec{0} = {\vec{w}}_{1} + \dots + {\vec{w}}_{k}$ . Because the zero vector obviously has the decomposition $\vec{0} = \vec{0} + \dots + \vec{0}$ , the assumption that decompositions are unique shows that each ${\vec{w}}_{i}$ is the zero vector. This means that $c_{i, 1} {\vec{β}}_{i, 1} + \dots + c_{i, n_{i}} {\vec{β}}_{i, n_{i}} = \vec{0}$ , and since each $B_{i}$ is a basis we have the desired conclusion that all of the $c$ ’s are zero.

For $(2) ⟹ (3)$ assume that the concatenation of the bases is a basis for the entire space. Consider a linear relationship among nonzero vectors from different $W_{i}$ ’s. This might or might not involve a vector from $W_{1}$ , or one from $W_{2}$ , etc., so we write it $\vec{0} = \dots + d_{i} {\vec{w}}_{i} + \dots$ . As in equation ( $*$ ) expand the vector.

$\begin{aligned} \vec{0} & = \dots + d_{i} (c_{i, 1} {\vec{β}}_{i, 1} + \dots + c_{i, n_{i}} {\vec{β}}_{i, n_{i}}) + \dots \\ = \dots + d_{i} c_{i, 1} \cdot {\vec{β}}_{i, 1} + \dots + d_{i} c_{i, n_{i}} \cdot {\vec{β}}_{i, n_{i}} + \dots \end{aligned}$

The linear independence of $B_{1}^{⌢} \dots^{⌢} B_{k}$ gives that each coefficient $d_{i} c_{i, j}$ is zero. Since ${\vec{w}}_{i}$ is nonzero vector, at least one of the $c_{i, j}$ ’s is not zero, and thus $d_{i}$ is zero. This holds for each $d_{i}$ , and therefore the linear relationship is trivial.

Finally, for $(3) ⟹ (1)$ , assume that among nonzero vectors from different $W_{i}$ ’s any linear relationship is trivial. Consider two decompositions of a vector $\vec{v} = \dots + {\vec{w}}_{i} + \dots$ and $\vec{v} = \dots + {\vec{u}}_{j} + \dots$ where ${\vec{w}}_{i} \in W_{i}$ and ${\vec{u}}_{j} \in W_{j}$ . Subtract one from the other to get a linear relationship, something like this (if there is no ${\vec{u}}_{i}$ or ${\vec{w}}_{j}$ then leave those out).

$\vec{0} = \dots + ({\vec{w}}_{i} - {\vec{u}}_{i}) + \dots + ({\vec{w}}_{j} - {\vec{u}}_{j}) + \dots$

The case assumption that statement (3) holds implies that the terms each equal the zero vector ${\vec{w}}_{i} - {\vec{u}}_{i} = \vec{0}$ . Hence decompositions are unique.

QED

Definition 4.9 A collection of subspaces ${W_{1}, \dots, W_{k}}$ is independent if no nonzero vector from any $W_{i}$ is a linear combination of vectors from the other subspaces $W_{1}, \dots, W_{i - 1}, W_{i + 1}, \dots, W_{k}$ .

Definition 4.10 A vector space $V$ is the direct sum (or internal direct sum) of its subspaces $W_{1}, \dots, W_{k}$ if $V = W_{1} + W_{2} + \dots + W_{k}$ and the collection ${W_{1}, \dots, W_{k}}$ is independent. We write $V = W_{1} \oplus W_{2} \oplus \dots \oplus W_{k}$ .

Example 4.11 Our prototype works: $ℝ^{3} = x -axis \oplus y -axis \oplus z -axis$ .

Example 4.12 The space of $2 \times 2$ matrices is this direct sum.

${(\begin{matrix} a & 0 \\ 0 & d \end{matrix}) ∣ a, d \in ℝ} \oplus {(\begin{matrix} 0 & b \\ 0 & 0 \end{matrix}) ∣ b \in ℝ} \oplus {(\begin{matrix} 0 & 0 \\ c & 0 \end{matrix}) ∣ c \in ℝ}$

It is the direct sum of subspaces in many other ways as well; direct sum decompositions are not unique.

Corollary 4.13 The dimension of a direct sum is the sum of the dimensions of its summands.

Proof In Lemma 4.8, the number of basis vectors in the concatenation equals the sum of the number of vectors in the sub-bases.

QED

The special case of two subspaces is worth its own mention.

Definition 4.14 When a vector space is the direct sum of two of its subspaces then they are complements.

Lemma 4.15 A vector space $V$ is the direct sum of two of its subspaces $W_{1}$ and $W_{2}$ if and only if it is the sum of the two $V = W_{1} + W_{2}$ and their intersection is trivial $W_{1} \cap W_{2} = {\vec{0}}$ .

Proof Suppose first that $V = W_{1} \oplus W_{2}$ . By definition, $V$ is the sum of the two $V = W_{1} + W_{2}$ . To show that their intersection is trivial let $\vec{v}$ be a vector from $W_{1} \cap W_{2}$ and consider the equation $\vec{v} = \vec{v}$ . On that equation’s left side is a member of $W_{1}$ and on the right is a member of $W_{2}$ , which we can think of as a linear combination of members of $W_{2}$ . But the two spaces are independent so the only way that a member of $W_{1}$ can be a linear combination of vectors from $W_{2}$ is if that member is the zero vector $\vec{v} = \vec{0}$ .

For the other direction, suppose that $V$ is the sum of two spaces with a trivial intersection. To show that $V$ is a direct sum of the two we need only show that the spaces are independent—that no nonzero member of the first is expressible as a linear combination of members of the second, and vice versa. This holds because any relationship ${\vec{w}}_{1} = c_{1} {\vec{w}}_{2, 1} + \dots + c_{k} {\vec{w}}_{2, k}$ (with ${\vec{w}}_{1} \in W_{1}$ and ${\vec{w}}_{2, j} \in W_{2}$ for all $j$ ) shows that the vector on the left is also in $W_{2}$ , since the right side is a combination of members of $W_{2}$ . The intersection of these two spaces is trivial, so ${\vec{w}}_{1} = \vec{0}$ . The same argument works for any ${\vec{w}}_{2}$ .

QED

Example 4.16 In $ℝ^{2}$ the $x$ -axis and the $y$ -axis are complements, that is, $ℝ^{2} = x -axis \oplus y -axis$ . This points out that subspace complement is slightly different than set complement; the $x$ and $y$ axes are not set complements because their intersection is not the empty set.

A space can have more than one pair of complementary subspaces; another pair for $ℝ^{2}$ are the subspaces consisting of the lines $y = x$ and $y = 2 x$ .

Example 4.17 In the space $F = {a \cos θ + b \sin θ ∣ a, b \in ℝ}$ , the subspaces $W_{1} = {a \cos θ ∣ a \in ℝ}$ and $W_{2} = {b \sin θ ∣ b \in ℝ}$ are complements. The prior example noted that a space can be decomposed into more than one pair of complements. In addition note that $F$ can has more than one pair of complementary subspaces where the first in the pair is $W_{1}$ —another complement of $W_{1}$ is $W_{3} = {b \sin θ + b \cos θ ∣ b \in ℝ}$ .

Example 4.18 In $ℝ^{3}$ , the $x y$ -plane and the $y z$ -planes are not complements, which is the point of the discussion following Example 4.4. One complement of the $x y$ -plane is the $z$ -axis.

Here is a natural question that arises from Lemma 4.15: for $k > 2$ is the simple sum $V = W_{1} + \dots + W_{k}$ also a direct sum if and only if the intersection of the subspaces is trivial?

Example 4.19 If there are more than two subspaces then having a trivial intersection is not enough to guarantee unique decomposition (i.e., is not enough to ensure that the spaces are independent). In $ℝ^{3}$ , let $W_{1}$ be the $x$ -axis, let $W_{2}$ be the $y$ -axis, and let $W_{3}$ be this.

$W_{3} = {(\begin{matrix} q \\ q \\ r \end{matrix}) ∣ q, r \in ℝ}$

The check that $ℝ^{3} = W_{1} + W_{2} + W_{3}$ is easy. The intersection $W_{1} \cap W_{2} \cap W_{3}$ is trivial, but decompositions aren’t unique.

$(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ y - x \\ 0 \end{matrix}) + (\begin{matrix} x \\ x \\ z \end{matrix}) = (\begin{matrix} x - y \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} y \\ y \\ z \end{matrix})$

(This example also shows that this requirement is also not enough: that all pairwise intersections of the subspaces be trivial. See Exercise 4.30.)

In this subsection we have seen two ways to regard a space as built up from component parts. Both are useful; in particular we will use the direct sum definition at the end of the Chapter Five.

Exercises

Exercise 4.20 Worked answer

Recommended. Decide if $ℝ^{2}$ is the direct sum of each $W_{1}$ and $W_{2}$ .
1. $W_{1} = {(\begin{matrix} x \\ 0 \end{matrix}) ∣ x \in ℝ}$ , $W_{2} = {(\begin{matrix} x \\ x \end{matrix}) ∣ x \in ℝ}$
2. $W_{1} = {(\begin{matrix} s \\ s \end{matrix}) ∣ s \in ℝ}$ , $W_{2} = {(\begin{matrix} s \\ 1.1 s \end{matrix}) ∣ s \in ℝ}$
3. $W_{1} = ℝ^{2}$ , $W_{2} = {\vec{0}}$
4. $W_{1} = W_{2} = {(\begin{matrix} t \\ t \end{matrix}) ∣ t \in ℝ}$
5. $W_{1} = {(\begin{matrix} 1 \\ 0 \end{matrix}) + (\begin{matrix} x \\ 0 \end{matrix}) ∣ x \in ℝ}$ , $W_{2} = {(\begin{matrix} - 1 \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ y \end{matrix}) ∣ y \in ℝ}$
Back to Exercise 4.20

Answer. With each of these we can apply Lemma 4.15.
1. Yes. The plane is the sum of this $W_{1}$ and $W_{2}$ because for any scalars $a$ and $b$
  
  $(\begin{matrix} a \\ b \end{matrix}) = (\begin{matrix} a - b \\ 0 \end{matrix}) + (\begin{matrix} b \\ b \end{matrix})$
  
  shows that the general vector is a sum of vectors from the two parts. And, these two subspaces are (different) lines through the origin, and so have a trivial intersection.
2. Yes. To see that any vector in the plane is a combination of vectors from these parts, consider this relationship.
  
  $(\begin{matrix} a \\ b \end{matrix}) = c_{1} (\begin{matrix} 1 \\ 1 \end{matrix}) + c_{2} (\begin{matrix} 1 \\ 1.1 \end{matrix})$
  
  We could now simply note that the set
  
  ${(\begin{matrix} 1 \\ 1 \end{matrix}), (\begin{matrix} 1 \\ 1.1 \end{matrix})}$
  
  is a basis for the space (because it is clearly linearly independent, and has size two in $ℝ^{2}$ ), and thus there is one and only one solution to the above equation, implying that all decompositions are unique. Alternatively, we can solve
  
  $\begin{array}{rcrcr} c_{1} & + & c_{2} & = & a \\ c_{1} & + & 1.1 c_{2} & = & b \end{array} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} \begin{array}{rcrcr} c_{1} & + & c_{2} & = & a \\ 0.1 c_{2} & = & - a + b \end{array}$
  
  to get that $c_{2} = 10 (- a + b)$ and $c_{1} = 11 a - 10 b$ , and so we have
  
  $(\begin{matrix} a \\ b \end{matrix}) = (\begin{matrix} 11 a - 10 b \\ 11 a - 10 b \end{matrix}) + (\begin{matrix} - 10 a + 10 b \\ 1.1 \cdot (- 10 a + 10 b) \end{matrix})$
  
  as required. As with the prior answer, each of the two subspaces is a line through the origin, and their intersection is trivial.
3. Yes. Each vector in the plane is a sum in this way
  
  $(\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} x \\ y \end{matrix}) + (\begin{matrix} 0 \\ 0 \end{matrix})$
  
  and the intersection of the two subspaces is trivial.
4. No. The intersection is not trivial.
5. No. These are not subspaces.
Exercise 4.21 Worked answer

Recommended. Show that $ℝ^{3}$ is the direct sum of the $x y$ -plane with each of these.
1. the $z$ -axis
2. the line
  
  ${(\begin{matrix} z \\ z \\ z \end{matrix}) ∣ z \in ℝ}$
Back to Exercise 4.21

Answer. With each of these we can use Lemma 4.15.
1. Any vector in $ℝ^{3}$ can be decomposed as this sum.
  
  $(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} x \\ y \\ 0 \end{matrix}) + (\begin{matrix} 0 \\ 0 \\ z \end{matrix})$
  
  And, the intersection of the $x y$ -plane and the $z$ -axis is the trivial subspace.
2. Any vector in $ℝ^{3}$ can be decomposed as
  
  $(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} x - z \\ y - z \\ 0 \end{matrix}) + (\begin{matrix} z \\ z \\ z \end{matrix})$
  
  and the intersection of the two spaces is trivial.
Exercise 4.22 Worked answer

Is $𝒫_{2}$ the direct sum of ${a + b x^{2} ∣ a, b \in ℝ}$ and ${c x ∣ c \in ℝ}$ ?

Back to Exercise 4.22

Answer. It is. Showing that these two are subspaces is routine. To see that the space is the direct sum of these two, just note that each member of $𝒫_{2}$ has the unique decomposition $m + n x + p x^{2} = (m + p x^{2}) + (n x)$ .
Exercise 4.23 Worked answer

Recommended. In $𝒫_{n}$ , the even polynomials are the members of this set

$ℰ = {p \in 𝒫_{n} ∣ p (- x) = p (x) for all x}$

and the odd polynomials are the members of this set.

$𝒪 = {p \in 𝒫_{n} ∣ p (- x) = - p (x) for all x}$

Show that these are complementary subspaces.

Back to Exercise 4.23

Answer. To show that they are subspaces is routine. We will argue they are complements with Lemma 4.15. The intersection $ℰ \cap 𝒪$ is trivial because the only polynomial satisfying both conditions $p (- x) = p (x)$ and $p (- x) = - p (x)$ is the zero polynomial. To see that the entire space is the sum of the subspaces $ℰ + 𝒪 = 𝒫_{n}$ , note that the polynomials $p_{0} (x) = 1$ , $p_{2} (x) = x^{2}$ , $p_{4} (x) = x^{4}$ , etc., are in $ℰ$ and also note that the polynomials $p_{1} (x) = x$ , $p_{3} (x) = x^{3}$ , etc., are in $𝒪$ . Hence any member of $𝒫_{n}$ is a combination of members of $ℰ$ and $𝒪$ .

Exercise 4.24 Worked answer

Which of these subspaces of $ℝ^{3}$

W_{1}

: the

x

-axis,

W_{2}

: the

y

-axis,

W_{3}

: the

z

-axis,

W_{4}

: the plane

x + y + z = 0

W_{5}

: the

y z

-plane

can be combined to

sum to $ℝ^{3}$ ?
direct sum to $ℝ^{3}$ ?

Back to Exercise 4.24

Answer. Each of these is $ℝ^{3}$ .

These are broken into some separate lines for readability.

W_{1} + W_{2} + W_{3}

W_{1} + W_{2} + W_{3} + W_{4}

W_{1} + W_{2} + W_{3} + W_{5}

W_{1} + W_{2} + W_{3} + W_{4} + W_{5}

W_{1} + W_{2} + W_{4}

W_{1} + W_{2} + W_{4} + W_{5}

W_{1} + W_{2} + W_{5}

W_{1} + W_{3} + W_{4}

W_{1} + W_{3} + W_{5}

W_{1} + W_{3} + W_{4} + W_{5}

$W_{1} + W_{4}$ , $W_{1} + W_{4} + W_{5}$ , $W_{1} + W_{5}$ ,

W_{2} + W_{3} + W_{4}

W_{2} + W_{3} + W_{4} + W_{5}

W_{2} + W_{4}

W_{2} + W_{4} + W_{5}

W_{3} + W_{4}

W_{3} + W_{4} + W_{5}

W_{4} + W_{5}

$W_{1} \oplus W_{2} \oplus W_{3}$ , $W_{1} \oplus W_{4}$ , $W_{1} \oplus W_{5}$ , $W_{2} \oplus W_{4}$ , $W_{3} \oplus W_{4}$

Exercise 4.25 Worked answer

Recommended. Show that $𝒫_{n} = {a_{0} ∣ a_{0} \in ℝ} \oplus \dots \oplus {a_{n} x^{n} ∣ a_{n} \in ℝ}$ .

Back to Exercise 4.25

Answer. Clearly each is a subspace. The bases $B_{i} = ⟨ x^{i} ⟩$ for the subspaces, when concatenated, form a basis for the whole space.
Exercise 4.26 Worked answer

What is $W_{1} + W_{2}$ if $W_{1} \subseteq W_{2}$ ?

Back to Exercise 4.26

Answer. It is $W_{2}$ .
Exercise 4.27 Worked answer

Does Example 4.5 generalize? That is, is this true or false: if a vector space $V$ has a basis $⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{n} ⟩$ then it is the direct sum of the spans of the one-dimensional subspaces $V = [{{\vec{β}}_{1}}] \oplus \dots \oplus [{{\vec{β}}_{n}}]$ ?

Back to Exercise 4.27

Answer. True by Lemma 4.8.
Exercise 4.28 Worked answer

Can $ℝ^{4}$ be decomposed as a direct sum in two different ways? Can $ℝ^{1}$ ?

Back to Exercise 4.28

Answer. Two distinct direct sum decompositions of $ℝ^{4}$ are easy to find. Two such are $W_{1} = [{{\vec{e}}_{1}, {\vec{e}}_{2}}]$ and $W_{2} = [{{\vec{e}}_{3}, {\vec{e}}_{4}}]$ , and also $U_{1} = [{{\vec{e}}_{1}}]$ and $U_{2} = [{{\vec{e}}_{2}, {\vec{e}}_{3}, {\vec{e}}_{4}}]$ . (Many more are possible, for example $ℝ^{4}$ and its trivial subspace.)

In contrast, any partition of $ℝ^{1}$ ’s single-vector basis will give one basis with no elements and another with a single element. Thus any decomposition involves $ℝ^{1}$ and its trivial subspace.
Exercise 4.29 Worked answer

This exercise makes the notation of writing ‘ $+$ ’ between sets more natural. Prove that, where $W_{1}, \dots, W_{k}$ are subspaces of a vector space,

$W_{1} + \dots + W_{k} = {{\vec{w}}_{1} + {\vec{w}}_{2} + \dots + {\vec{w}}_{k} ∣ {\vec{w}}_{1} \in W_{1}, \dots, {\vec{w}}_{k} \in W_{k}},$

and so the sum of subspaces is the subspace of all sums.

Back to Exercise 4.29

Answer. Set inclusion one way is easy: ${{\vec{w}}_{1} + \dots + {\vec{w}}_{k} ∣ {\vec{w}}_{i} \in W_{i}}$ is a subset of $[W_{1} \cup \dots \cup W_{k}]$ because each ${\vec{w}}_{1} + \dots + {\vec{w}}_{k}$ is a sum of vectors from the union.

For the other inclusion, to any linear combination of vectors from the union apply commutativity of vector addition to put vectors from $W_{1}$ first, followed by vectors from $W_{2}$ , etc. Add the vectors from $W_{1}$ to get a ${\vec{w}}_{1} \in W_{1}$ , add the vectors from $W_{2}$ to get a ${\vec{w}}_{2} \in W_{2}$ , etc. The result has the desired form.
Exercise 4.30 Worked answer

(Refer to Example 4.19. This exercise shows that the requirement that pairwise intersections be trivial is genuinely stronger than the requirement only that the intersection of all of the subspaces be trivial.) Give a vector space and three subspaces $W_{1}$ , $W_{2}$ , and $W_{3}$ such that the space is the sum of the subspaces, the intersection of all three subspaces $W_{1} \cap W_{2} \cap W_{3}$ is trivial, but the pairwise intersections $W_{1} \cap W_{2}$ , $W_{1} \cap W_{3}$ , and $W_{2} \cap W_{3}$ are nontrivial.

Back to Exercise 4.30

Answer. One example is to take the space to be $ℝ^{3}$ , and to take the subspaces to be the $x y$ -plane, the $x z$ -plane, and the $y z$ -plane.
Exercise 4.31 Worked answer

Prove that if $V = W_{1} \oplus \dots \oplus W_{k}$ then $W_{i} \cap W_{j}$ is trivial whenever $i \neq j$ . This shows that the first half of the proof of Lemma 4.15 extends to the case of more than two subspaces. (Example 4.19 shows that this implication does not reverse; the other half does not extend.)

Back to Exercise 4.31

Answer. Of course, the zero vector is in all of the subspaces, so the intersection contains at least that one vector.. By the definition of direct sum the set ${W_{1}, \dots, W_{k}}$ is independent and so no nonzero vector of $W_{i}$ is a multiple of a member of $W_{j}$ , when $i \neq j$ . In particular, no nonzero vector from $W_{i}$ equals a member of $W_{j}$ .
Exercise 4.32 Worked answer

Recall that no linearly independent set contains the zero vector. Can an independent set of subspaces contain the trivial subspace?

Back to Exercise 4.32

Answer. It can contain a trivial subspace; this set of subspaces of $ℝ^{3}$ is independent: ${{\vec{0}}, x -axis}$ . No nonzero vector from the trivial space ${\vec{0}}$ is a multiple of a vector from the $x$ -axis, simply because the trivial space has no nonzero vectors to be candidates for such a multiple (and also no nonzero vector from the $x$ -axis is a multiple of the zero vector from the trivial subspace).
Exercise 4.33 Worked answer

Recommended. Does every subspace have a complement?

Back to Exercise 4.33

Answer. Yes. For any subspace of a vector space we can take any basis $⟨ {\vec{ω}}_{1}, \dots, {\vec{ω}}_{k} ⟩$ for that subspace and extend it to a basis $⟨ {\vec{ω}}_{1}, \dots, {\vec{ω}}_{k}, {\vec{β}}_{k + 1}, \dots, {\vec{β}}_{n} ⟩$ for the whole space. Then the complement of the original subspace has this basis $⟨ {\vec{β}}_{k + 1}, \dots, {\vec{β}}_{n} ⟩$ .
Exercise 4.34 Worked answer

Recommended. Let $W_{1}, W_{2}$ be subspaces of a vector space.
1. Assume that the set $S_{1}$ spans $W_{1}$ , and that the set $S_{2}$ spans $W_{2}$ . Can $S_{1} \cup S_{2}$ span $W_{1} + W_{2}$ ? Must it?
2. Assume that $S_{1}$ is a linearly independent subset of $W_{1}$ and that $S_{2}$ is a linearly independent subset of $W_{2}$ . Can $S_{1} \cup S_{2}$ be a linearly independent subset of $W_{1} + W_{2}$ ? Must it?
Back to Exercise 4.34

Answer.
1. It must. We can write any member of $W_{1} + W_{2}$ as ${\vec{w}}_{1} + {\vec{w}}_{2}$ where ${\vec{w}}_{1} \in W_{1}$ and ${\vec{w}}_{2} \in W_{2}$ . As $S_{1}$ spans $W_{1}$ , the vector ${\vec{w}}_{1}$ is a combination of members of $S_{1}$ . Similarly ${\vec{w}}_{2}$ is a combination of members of $S_{2}$ .
2. An easy way to see that it can be linearly independent is to take each to be the empty set. On the other hand, in the space $ℝ^{1}$ , if $W_{1} = ℝ^{1}$ and $W_{2} = ℝ^{1}$ and $S_{1} = {1}$ and $S_{2} = {2}$ , then their union $S_{1} \cup S_{2}$ is not independent.
Exercise 4.35 Worked answer

When we decompose a vector space as a direct sum, the dimensions of the subspaces add to the dimension of the space. The situation with a space that is given as the sum of its subspaces is not as simple. This exercise considers the two-subspace special case.
1. For these subspaces of $ℳ_{2 \times 2}$ find $W_{1} \cap W_{2}$ , $\dim (W_{1} \cap W_{2})$ , $W_{1} + W_{2}$ , and $\dim (W_{1} + W_{2})$ .
  
  $W_{1} = {(\begin{matrix} 0 & 0 \\ c & d \end{matrix}) ∣ c, d \in ℝ} W_{2} = {(\begin{matrix} 0 & b \\ c & 0 \end{matrix}) ∣ b, c \in ℝ}$
2. Suppose that $U$ and $W$ are subspaces of a vector space. Suppose that the sequence $⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{k} ⟩$ is a basis for $U \cap W$ . Finally, suppose that the prior sequence has been expanded to give a sequence $⟨ {\vec{μ}}_{1}, \dots, {\vec{μ}}_{j}, {\vec{β}}_{1}, \dots, {\vec{β}}_{k} ⟩$ that is a basis for $U$ , and a sequence $⟨ {\vec{β}}_{1}, \dots, {\vec{β}}_{k}, {\vec{ω}}_{1}, \dots, {\vec{ω}}_{p} ⟩$ that is a basis for $W$ . Prove that this sequence
  
  $⟨ {\vec{μ}}_{1}, \dots, {\vec{μ}}_{j}, {\vec{β}}_{1}, \dots, {\vec{β}}_{k}, {\vec{ω}}_{1}, \dots, {\vec{ω}}_{p} ⟩$
  
  is a basis for the sum $U + W$ .
3. Conclude that $\dim (U + W) = \dim (U) + \dim (W) - \dim (U \cap W)$ .
4. Let $W_{1}$ and $W_{2}$ be eight-dimensional subspaces of a ten-dimensional space. List all values possible for $\dim (W_{1} \cap W_{2})$ .
Back to Exercise 4.35

Answer.
1. The intersection and sum are
  
  ${(\begin{matrix} 0 & 0 \\ c & 0 \end{matrix}) ∣ c \in ℝ} {(\begin{matrix} 0 & b \\ c & d \end{matrix}) ∣ b, c, d \in ℝ}$
  
  which have dimensions one and three.
2. We write $B_{U \cap W}$ for the basis for $U \cap W$ , we write $B_{U}$ for the basis for $U$ , we write $B_{W}$ for the basis for $W$ , and we write $B_{U + W}$ for the basis under consideration.
  
  To see that $B_{U + W}$ spans $U + W$ , observe that we can write any vector $c \vec{u} + d \vec{w}$ from $U + W$ as a linear combination of the vectors in $B_{U + W}$ , simply by expressing $\vec{u}$ in terms of $B_{U}$ and expressing $\vec{w}$ in terms of $B_{W}$ .
  
  We finish by showing that $B_{U + W}$ is linearly independent. Consider
  
  $c_{1} {\vec{μ}}_{1} + \dots + c_{j + 1} {\vec{β}}_{1} + \dots + c_{j + k + p} {\vec{ω}}_{p} = \vec{0}$
  
  which can be rewritten in this way.
  
  $c_{1} {\vec{μ}}_{1} + \dots + c_{j} {\vec{μ}}_{j} = - c_{j + 1} {\vec{β}}_{1} - \dots - c_{j + k + p} {\vec{ω}}_{p}$
  
  Note that the left side sums to a vector in $U$ while right side sums to a vector in $W$ , and thus both sides sum to a member of $U \cap W$ . Since the left side is a member of $U \cap W$ , it is expressible in terms of the members of $B_{U \cap W}$ , which gives the combination of $\vec{μ}$ ’s from the left side above as equal to a combination of $\vec{β}$ ’s. But, the fact that the basis $B_{U}$ is linearly independent shows that any such combination is trivial, and in particular, the coefficients $c_{1}$ , …, $c_{j}$ from the left side above are all zero. Similarly, the coefficients of the $\vec{ω}$ ’s are all zero. This leaves the above equation as a linear relationship among the $\vec{β}$ ’s, but $B_{U \cap W}$ is linearly independent, and therefore all of the coefficients of the $\vec{β}$ ’s are also zero.
3. Just count the basis vectors in the prior item: $\dim (U + W) = j + k + p$ , and $\dim (U) = j + k$ , and $\dim (W) = k + p$ , and $\dim (U \cap W) = k$ .
4. We know that $\dim (W_{1} + W_{2}) = \dim (W_{1}) + \dim (W_{2}) - \dim (W_{1} \cap W_{2})$ . Because $W_{1} \subseteq W_{1} + W_{2}$ , we know that $W_{1} + W_{2}$ must have dimension greater than that of $W_{1}$ , that is, must have dimension eight, nine, or ten. Substituting gives us three possibilities $8 = 8 + 8 - \dim (W_{1} \cap W_{2})$ or $9 = 8 + 8 - \dim (W_{1} \cap W_{2})$ or $10 = 8 + 8 - \dim (W_{1} \cap W_{2})$ . Thus $\dim (W_{1} \cap W_{2})$ must be either eight, seven, or six. (Giving examples to show that each of these three cases is possible is easy, for instance in $ℝ^{10}$ .)
Exercise 4.36 Worked answer

Let $V = W_{1} \oplus \dots \oplus W_{k}$ and for each index $i$ suppose that $S_{i}$ is a linearly independent subset of $W_{i}$ . Prove that the union of the $S_{i}$ ’s is linearly independent.

Back to Exercise 4.36

Answer. Expand each $S_{i}$ to a basis $B_{i}$ for $W_{i}$ . The concatenation of those bases $B_{1}^{⌢} \dots^{⌢} B_{k}$ is a basis for $V$ and thus its members form a linearly independent set. But the union $S_{1} \cup \dots \cup S_{k}$ is a subset of that linearly independent set, and thus is itself linearly independent.
Exercise 4.37 Worked answer

A matrix is symmetric if for each pair of indices $i$ and $j$ , the $i, j$ entry equals the $j, i$ entry. A matrix is antisymmetric if each $i, j$ entry is the negative of the $j, i$ entry.
1. Give a symmetric $2 \times 2$ matrix and an antisymmetric $2 \times 2$ matrix. (Remark. For the second one, be careful about the entries on the diagonal.)
2. What is the relationship between a square symmetric matrix and its transpose? Between a square antisymmetric matrix and its transpose?
3. Show that $ℳ_{n \times n}$ is the direct sum of the space of symmetric matrices and the space of antisymmetric matrices.
Back to Exercise 4.37

Answer.
1. Two such are these.
  
  $(\begin{matrix} 1 & 2 \\ 2 & 3 \end{matrix}) (\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$
  
  For the antisymmetric one, entries on the diagonal must be zero.
2. A square symmetric matrix equals its transpose. A square antisymmetric matrix equals the negative of its transpose.
3. Showing that the two sets are subspaces is easy. Suppose that $A \in ℳ_{n \times n}$ . To express $A$ as a sum of a symmetric and an antisymmetric matrix, we observe that
  
  $A = (1 / 2) (A + A^{𝖳}) + (1 / 2) (A - A^{𝖳})$
  
  and note the first summand is symmetric while the second is antisymmetric. Thus $ℳ_{n \times n}$ is the sum of the two subspaces. To show that the sum is direct, assume a matrix $A$ is both symmetric $A = A^{𝖳}$ and antisymmetric $A = - A^{𝖳}$ . Then $A = - A$ and so all of $A$ ’s entries are zeroes.
Exercise 4.38 Worked answer

Let $W_{1}, W_{2}, W_{3}$ be subspaces of a vector space. Prove that $(W_{1} \cap W_{2}) + (W_{1} \cap W_{3}) \subseteq W_{1} \cap (W_{2} + W_{3})$ . Does the inclusion reverse?

Back to Exercise 4.38

Answer. Assume that $\vec{v} \in (W_{1} \cap W_{2}) + (W_{1} \cap W_{3})$ . Then $\vec{v} = {\vec{w}}_{2} + {\vec{w}}_{3}$ where ${\vec{w}}_{2} \in W_{1} \cap W_{2}$ and ${\vec{w}}_{3} \in W_{1} \cap W_{3}$ . Note that ${\vec{w}}_{2}, {\vec{w}}_{3} \in W_{1}$ and, as a subspace is closed under addition, ${\vec{w}}_{2} + {\vec{w}}_{3} \in W_{1}$ . Thus $\vec{v} = {\vec{w}}_{2} + {\vec{w}}_{3} \in W_{1} \cap (W_{2} + W_{3})$ .

This example proves that the inclusion may be strict: in $ℝ^{2}$ take $W_{1}$ to be the $x$ -axis, take $W_{2}$ to be the $y$ -axis, and take $W_{3}$ to be the line $y = x$ . Then $W_{1} \cap W_{2}$ and $W_{1} \cap W_{3}$ are trivial and so their sum is trivial. But $W_{2} + W_{3}$ is all of $ℝ^{2}$ so $W_{1} \cap (W_{2} + W_{3})$ is the $x$ -axis.
Exercise 4.39 Worked answer

The example of the $x$ -axis and the $y$ -axis in $ℝ^{2}$ shows that $W_{1} \oplus W_{2} = V$ does not imply that $W_{1} \cup W_{2} = V$ . Can $W_{1} \oplus W_{2} = V$ and $W_{1} \cup W_{2} = V$ happen?

Back to Exercise 4.39

Answer. It happens when at least one of $W_{1}, W_{2}$ is trivial. But that is the only way it can happen.

To prove this, assume that both are non-trivial, select nonzero vectors ${\vec{w}}_{1}, {\vec{w}}_{2}$ from each, and consider ${\vec{w}}_{1} + {\vec{w}}_{2}$ . This sum is not in $W_{1}$ because ${\vec{w}}_{1} + {\vec{w}}_{2} = \vec{v} \in W_{1}$ would imply that ${\vec{w}}_{2} = \vec{v} - {\vec{w}}_{1}$ is in $W_{1}$ , which violates the assumption of the independence of the subspaces. Similarly, ${\vec{w}}_{1} + {\vec{w}}_{2}$ is not in $W_{2}$ . Thus there is an element of $V$ that is not in $W_{1} \cup W_{2}$ .
Exercise 4.40 Worked answer

Consider Corollary 4.13. Does it work both ways—that is, supposing that $V = W_{1} + \dots + W_{k}$ , is $V = W_{1} \oplus \dots \oplus W_{k}$ if and only if $\dim (V) = \dim (W_{1}) + \dots + \dim (W_{k})$ ?

Back to Exercise 4.40

Answer. Yes. The left-to-right implication is Corollary 4.13. For the other direction, assume that $\dim (V) = \dim (W_{1}) + \dots + \dim (W_{k})$ . Let $B_{1}, \dots, B_{k}$ be bases for $W_{1}, \dots, W_{k}$ . As $V$ is the sum of the subspaces, we can write any $\vec{v} \in V$ as $\vec{v} = {\vec{w}}_{1} + \dots + {\vec{w}}_{k}$ and expressing each ${\vec{w}}_{i}$ as a combination of vectors from the associated basis $B_{i}$ shows that the concatenation $B_{1}^{⌢} \dots^{⌢} B_{k}$ spans $V$ . Now, that concatenation has $\dim (W_{1}) + \dots + \dim (W_{k})$ members, and so it is a spanning set of size $\dim (V)$ . The concatenation is therefore a basis for $V$ . Thus $V$ is the direct sum.
Exercise 4.41 Worked answer

We know that if $V = W_{1} \oplus W_{2}$ then there is a basis for $V$ that splits into a basis for $W_{1}$ and a basis for $W_{2}$ . Can we make the stronger statement that every basis for $V$ splits into a basis for $W_{1}$ and a basis for $W_{2}$ ?

Back to Exercise 4.41

Answer. No. The standard basis for $ℝ^{2}$ does not split into bases for the complementary subspaces the line $x = y$ and the line $x = - y$ .
Exercise 4.42 Worked answer

We can ask about the algebra of the ‘ $+$ ’ operation.
1. Is it commutative; is $W_{1} + W_{2} = W_{2} + W_{1}$ ?
2. Is it associative; is $(W_{1} + W_{2}) + W_{3} = W_{1} + (W_{2} + W_{3})$ ?
3. Let $W$ be a subspace of some vector space. Show that $W + W = W$ .
4. Must there be an identity element, a subspace $I$ such that $I + W = W + I = W$ for all subspaces $W$ ?
5. Does left-cancellation hold: if $W_{1} + W_{2} = W_{1} + W_{3}$ then $W_{2} = W_{3}$ ? Right cancellation?
Back to Exercise 4.42

Answer.
1. Yes, $W_{1} + W_{2} = W_{2} + W_{1}$ for all subspaces $W_{1}, W_{2}$ because each side is the span of $W_{1} \cup W_{2} = W_{2} \cup W_{1}$ .
2. This one is similar to the prior one—each side of that equation is the span of $(W_{1} \cup W_{2}) \cup W_{3} = W_{1} \cup (W_{2} \cup W_{3})$ .
3. Because this is an equality between sets, we can show that it holds by mutual inclusion. Clearly $W \subseteq W + W$ . For $W + W \subseteq W$ just recall that every subset is closed under addition so any sum of the form ${\vec{w}}_{1} + {\vec{w}}_{2}$ is in $W$ .
4. In each vector space, the identity element with respect to subspace addition is the trivial subspace.
5. Neither of left or right cancellation needs to hold. For an example, in $ℝ^{3}$ take $W_{1}$ to be the $x y$ -plane, take $W_{2}$ to be the $x$ -axis, and take $W_{3}$ to be the $y$ -axis.

References cited in this section

Sheffer

Adam Sheffer (attributed to Bob Krueger), A Linear Algebra Riddle, blog post, https://adamsheffer.wordpress.com/2018/07/21/linear-algebra-riddle/ July 21, 2018.

Wohascum no. 47

The Wohascum County Problem Book problem number 47.

Munkres

James R. Munkres, Elementary Linear Algebra, Addison-Wesley, 1964.

More information on sequences is in the appendix.↩︎