The Dimension of a Vector Space

Section 33 The Dimension of a Vector Space

Focus Questions

By the end of this section, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the section.

What is a finite dimensional vector space?
What is the dimension of a finite dimensional vector space? What important result about bases of finite dimensional vector spaces makes dimension well-defined?
What must be true about any linearly independent subset of $n$ vectors in a vector space with dimension $n ?$ Why?
What must be true about any subset of $n$ vectors in a vector space with dimension $n$ that spans the vector space? Why?

🔗

Subsection Application: Principal Component Analysis

🔗

The discipline of statistics is based on the idea of analyzing data. In large data sets it is usually the case that one wants to understand the relationships between the different data in the set. This can be difficult to do when the data set is large and it is impossible to visually examine the data for patterns. Principal Component Analysis (PCA) is a tool for identifying and representing underlying patterns in large data sets, and PCA has been called one of the most important and valuable linear algebra tools for statistical analysis. PCA is used to transform a collection of variables into a (usually smaller) number of uncorrelated variables called principal components. The principal components form the most meaningful basis from which to view data by removing extraneous information and revealing underlying relationships in the data. This presents a framework for how to reduce a complex data set to a lower dimension while retaining the important attributes of the data set. The output helps the experimenter determine which dynamics in the data are important and which can be ignored.

🔗

Subsection Introduction

🔗

In Section 15 we learned that any two bases for a subspace of

R^{n}

contain the same number of vectors. This allowed us to define the dimension of a subspace of

R^{n} .

In this section we extend the arguments we made in Section 15 to arbitrary vector spaces and define the dimension of a vector space.

🔗

Preview Activity 33.1.

The main tool we used to prove that any two bases for a subspace of $R^{n}$ must contain the same number of elements was Theorem 15.1. In this preview activity we will show that the same argument can be used for vector spaces. More specifically, we will prove a special case of the following theorem generalizing Theorem 15.1.

🔗

Theorem 33.1.

If $V$ is a vector space with a basis $B = {v_{1}, v_{2}, \dots, v_{k}}$ of $k$ vectors, then any subset of $V$ containing more than $k$ vectors is linearly dependent.

Suppose $V$ is a vector space with basis $B = {v_{1}, v_{2}} .$ Consider the set $U = {u_{1}, u_{2}, u_{3}}$ of vectors in $V .$ We will show that $U$ is linearly dependent using a similar approach to the Preview Activity 15.1.

🔗

(a)

What vector equation involving $u_{1}, u_{2}, u_{3}$ do we need to solve to determine linear independence/dependence of these vectors? Use $x_{1}, x_{2}, x_{3}$ for coefficients.

🔗

(b)

Since $B$ is a basis of $V,$ it spans $V .$ Using this information, rewrite the vectors $u_{i}$ in terms of $v_{j}$ and substitute into the above equation to obtain another equation in terms of $v_{j} .$

🔗

(c)

Since $B$ is a basis of $V,$ the vectors $v_{1}, v_{2}$ are linearly independent. Using the equation in the previous part, determine what this means about the coefficients $x_{1}, x_{2}, x_{3} .$

🔗

(d)

Express the conditions on $x_{1}, x_{2}, x_{3}$ in the form of a matrix-vector equation. Explain why there are infinitely many solutions for $x_{i}$ 's and why this means the vectors $u_{1}, u_{2}, u_{3}$ are linearly dependent.

🔗

Subsection Finite Dimensional Vector Spaces

🔗

Theorem 33.1 shows that if sets

B_{1}

and

B_{2}

are finite bases for a vector space

V,

which are linearly independent by definition, then each cannot contain more elements than the other, so the number of elements in each basis must be equal.

🔗

Theorem 33.2.

If a non-trivial vector space $V$ has a basis of $n$ vectors, then every basis of $V$ contains exactly $n$ vectors.

🔗

Theorem 33.2 states that if a vector space

V

has a basis with a finite number of vectors, then the number of vectors in a basis for that vector space is a well-defined number. In other words, the number of vectors in a basis is an invariant of the vector space. This important number is given a name.

🔗

Definition 33.3.

A finite-dimensional vector space is a vector space that can be spanned by a finite number of vectors. The dimension of a non-trivial finite-dimensional vector space is the number of vectors in a basis for $V .$ The dimension of the trivial vector space is defined to be 0.

🔗

We denote the dimension of a finite dimensional vector space

V

\dim (V) .

🔗

Not every vector space is finite dimensional. We have seen, for example, that the vector space

P

of all polynomials, regardless of degree, is not a finite-dimensional vector space. In fact, the polynomials

1, t, t^{2}, \dots, t^{n}, \dots

🔗

are linearly independent, so

P

has an infinite linearly independent set and therefore has no finite basis. A vector space that has an infinite basis is called an infinite dimensional vector space.

🔗

Activity 33.2.

Since columns of the $n \times n$ identity matrix span $R^{n}$ and are linearly independent, the columns of $I_{n}$ form a basis for $R^{n}$ (the standard basis). Consequently, we have that $\dim (R^{n}) = n .$ In this activity we determine the dimensions of other familiar vector spaces. Find the dimensions of each of the indicated vector spaces. Verify your answers.

🔗

(a)

$P_{1}$

🔗

(b)

$P_{2}$

🔗

(c)

$P_{n}$

🔗

(d)

$M_{2 \times 3}$

🔗

(e)

$M_{3 \times 4}$

🔗

(f)

$M_{k \times n}$

🔗

Finding the dimension of a finite-dimensional vector space amounts to finding a basis for the space.

🔗

Activity 33.3.

Let $W = {(a + b) + (a - b) t + (2 a + 3 b) t^{2} ∣ a, b are scalars} .$

🔗

(a)

Find a finite set of polynomials in $W$ that span $W .$

🔗

(b)

Determine if the spanning set from part (a) is linearly independent or dependent. Clearly explain your process.

🔗

(c)

What is $\dim (W) ?$ Explain.

🔗

Subsection The Dimension of a Subspace

🔗

Every subspace of a finite-dimensional vector space is a vector space, and since a subspace is contained in a vector space it is natural to think that the dimension of a subspace should be less than or equal to the dimension of the larger vector space. We verify that fact in this section.

🔗

Activity 33.4.

Let $V$ be a finite dimensional vector space of dimension $n$ and let $W$ be a subspace of $V .$ Explain why $W$ cannot have dimension larger than $\dim (V),$ and if $W \neq V$ then $\dim (W) < \dim (V) .$

Hint.

Use Theorem 33.1.

🔗

Subsection Conditions for a Basis of a Vector Space

🔗

There are two items we need to confirm before we can state that a subset

B

of a subspace

W

of a vector space is a basis for

W :

the set

B

must be linearly independent and span

W .

We can reduce the amount of work it takes to show that a set is a basis if we know the dimension of the vector space in advance.

🔗

Activity 33.5.

Let $W$ be a subspace of a vector space $V$ with $\dim (W) = k .$ We know that every basis of $W$ contains exactly $k$ vectors.

🔗

(a)

Suppose that $S$ is a subset of $W$ that contains $k$ vectors and is linearly independent. In this part of the activity we will show that $S$ must span $W .$

🔗

(i)

Suppose that $S$ does not span $W .$ Explain why this implies that $W$ contains a set of $k + 1$ linearly independent vectors.

🔗

(ii)

Explain why the result of i tells us that $S$ is a basis for $W .$

🔗

(b)

Now suppose that $S$ is a subset of $W$ with $k$ vectors that spans $W .$ In this part of the activity we will show that $S$ must be linearly independent.

🔗

(i)

Suppose that $S$ is not linearly independent. Explain why we can then find a proper subset of $S$ that is linearly independent but has the same span as $S .$

🔗

(ii)

Explain why the result of i tells us that $S$ is a basis for $W .$

🔗

The result of Activity 33.5 is summarized in the following theorem (compare to Theorem 15.4).

🔗

Theorem 33.4.

Let $W$ be a subspace of dimension $k$ of a vector space $V$ and let $S$ be a subset of $W$ containing exactly $k$ vectors.

If $S$ is linearly independent, then $S$ is a basis for $W .$
If $S$ spans $W,$ then $S$ is a basis for $W .$

🔗

Subsection Examples

🔗

What follows are worked examples that use the concepts from this section.

🔗

Example 33.5.

Find a basis and dimension for each of the indicated subspaces of the given vector spaces.

🔗

(a)

${a + b (t + t^{2}) : a, b \in R}$ in $P_{2}$

Solution.

Let $W = {a + b (t + t^{2}) : a, b \in R} .$ Every element in $W$ has the form

a + b (t + t^{2}) = a (1) + b (t + t^{2}) .

So $W = Span {1, t + t^{2}} .$ Since neither $1$ nor $t + t^{2}$ is a scalar multiple of the other, the set ${1, t + t^{2}}$ is linearly independent. Thus, ${1, t + t^{2}}$ is a basis for $W$ and $\dim (W) = 2 .$

🔗

(b)

$Span {1, \frac{1}{1 + x^{2}}, \frac{2 + x^{2}}{1 + x^{2}}, \arctan (x)}$ in $F$

Solution.

Let $W = Span {1, \frac{1}{1 + x^{2}}, \frac{2 + x^{2}}{1 + x^{2}}, \arctan (x)} .$ To find a basis for $W,$ we find a linearly independent subset of ${1, \frac{1}{1 + x^{2}}, \frac{2 + x^{2}}{1 + x^{2}}, \arctan (x)} .$ Consider the equation

c_{1} (1) + c_{2} (\frac{1}{1 + x^{2}}) + c_{3} (\frac{2 + x^{2}}{1 + x^{2}}) + c_{4} \arctan (x) = 0 .

To find the weights $c_{i}$ for which this equality of functions holds, we use the fact that the we must have equality for every $x .$ So we pick four different values for $x$ to obtain a linear system that we can solve for the weights. Evaluating both sides of the equation at $x = 0,$ $x = 1,$ $x = - 1,$ and $x = 2$ yields the equations

\begin{aligned} c_{1} & + & c_{2} & + & 2 c_{3} & = & 0 \\ c_{1} & + & \frac{1}{2} c_{2} & + & \frac{3}{2} c_{3} & + & \frac{π}{4} c_{4} & = & 0 \\ c_{1} & + & \frac{1}{2} c_{2} & + & \frac{3}{2} c_{3} & - & \frac{π}{4} c_{4} & = & 0 \\ c_{1} & + & \frac{1}{5} c_{2} & + & \frac{6}{5} c_{3} & + & \arctan (2) c_{4} & = & 0 & . \end{aligned}

The reduced row echelon form of the coefficient matrix

[\begin{array}{cccr} 1 & 1 & 2 & 0 \\ 1 & \frac{1}{2} & \frac{3}{2} & \frac{π}{4} \\ 1 & \frac{1}{2} & \frac{3}{2} & - \frac{π}{4} \\ 1 & \frac{1}{5} & \frac{6}{5} & \arctan (2) \end{array}]

is $[\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}] .$ The general solution to this linear system is $c_{1} = c_{2} = - c_{3}$ and $c_{4} = 0 .$ Notice that

(- 1) (1) + (- 1) (\frac{1}{1 + x^{2}}) + \frac{2 + x^{2}}{1 + x^{2}} = 0

\frac{2 + x^{2}}{1 + x^{2}} = 1 + (\frac{1}{1 + x^{2}}),

so $\frac{2 + x^{2}}{1 + x^{2}}$ is a linear combination of the other vectors. The vectors corresponding to the pivot columns are linearly independent, so it follows that $1,$ $\frac{1}{1 + x^{2}},$ and $\arctan (x)$ are linearly independent. We conclude that ${1, \frac{1}{1 + x^{2}}, \arctan (x)}$ is a basis for $W$ and $\dim (W) = 3 .$

🔗

(c)

${p (t) \in P_{n} : p (- t) = p (t)}$ in $P_{4}$ (The polynomials with the property that $p (- t) = p (t)$ are called even polynomials.)

Solution.

Let $W = {p (t) \in P_{n} : p (- t) = p (t)}$ in $P_{4} .$ Let $p (t) \in W$ and suppose that $p (t) = a_{0} + a_{1} t + a_{2} t^{2} + a_{3} t^{3} + a_{4} t^{4} .$ Since $p (- t) = p (t),$ we must have $p (1) = p (- 1)$ and $p (3) = p (- 3) .$ Since $p (1) = p (- 1),$ it follows that

a_{0} + a_{1} + a_{2} + a_{3} + a_{4} = a_{0} - a_{1} + a_{2} - a_{3} + a_{4}

a_{1} + a_{3} = 0 .

Similarly, the fact that $p (3) = p (- 3)$ yields the equation

a_{0} + 3 a_{1} + 9 a_{2} + 27 a_{3} + 81 a_{4} = a_{0} - 3 a_{1} + 9 a_{2} - 27 a_{3} + 81 a_{4}

a_{1} + 9 a_{3} = 0 .

The reduced row echelon form of the coefficient matrix of system $a_{1} + a_{3} = 0$ and $a_{1} + 9 a_{3} = 0$ is $I_{2},$ so it follows that $a_{1} = a_{3} = 0 .$ Thus, $p (t) = a_{0} + a_{2} t^{2} + a_{4} t^{4}$ and so $W = Span {1, t^{2}, t^{4}} .$ Equating like terms in the equation

c_{1} (1) + c_{2} (t^{2}) + c_{3} (t^{4}) = 0

yields $c_{1} = c_{2} = c_{3} = 0 .$ We conclude that ${1, t^{2}, t^{4}}$ is linearly independent and is therefore a basis for $W .$ Thus, $\dim (W) = 3 .$ As an alternative solution, notice that $p (t) = t$ is not in $W .$ So $W \neq V$ and we know that $\dim (W) < \dim (V) .$ Since $1,$ $t^{2},$ and $t^{4}$ are in $W,$ we can show as above that $1,$ $t^{2},$ and $t^{4}$ are linearly independent. We can conclude that $\dim (W) = 3$ since it cannot be $4 .$

🔗

Example 33.6.

Let $U_{n \times n}$ be the set of all $n \times n$ upper triangular matrices. Recall that a matrix $A = [a_{i j}]$ is upper triangular if $a_{i j} = 0$ whenever $i > j .$ That is, a matrix is upper triangular if all entries below the diagonal are 0.

🔗

(a)

Show that $U_{n \times n}$ is a subspace of $M_{n \times n} .$

Solution.

Since the $n \times n$ zero matrix $0_{n \times n}$ has all entries equal to 0, it follows that $0_{n \times n}$ is in $U_{n \times n} .$ Let $A = [a_{i j}]$ and $B = [b_{i j}]$ be in $U_{n \times n},$ and let $C = [c_{i j}] = A + B .$ Then $c_{i j} = a_{i j} + b_{i j} = 0 + 0$ when $i > j .$ So $C$ is an upper triangular matrix and $U_{n \times n}$ is closed under addition. Let $c$ be a scalar. The $i j$ th entry of $c A$ is $c a_{i j} = c (0) = 0$ whenever $i > j .$ So $c A$ is an upper triangular matrix and $U_{n \times n}$ is closed under multiplication by scalars. We conclude that $U_{n \times n}$ is a subspace of $M_{n \times n} .$

🔗

(b)

Find the dimensions of $U_{2 \times 2}$ and $U_{3 \times 3} .$ Explain. Make a conjecture as to what $\dim (U_{n \times n})$ is in terms of $n .$

Solution.

Let $M_{11} = [\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}],$ $M_{12} = [\begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array}],$ and $M_{22} = [\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}] .$ We will show that $S = {M_{11}, M_{12}, M_{22}}$ is a basis for $U_{2 \times 2} .$ Consider the equation

x_{1} M_{11} + x_{2} M_{12} + x_{3} M_{22} = 0 .

Equating like entries shows that $x_{1} = x_{2} = x_{3} = 0,$ and so $S$ is linearly independent. If $[\begin{array}{cc} a & b \\ 0 & c \end{array}]$ is in $U_{2 \times 2},$ then

[\begin{array}{cc} a & b \\ 0 & c \end{array}] = a M_{11} + b M_{12} + c M_{22}

and so $S$ spans $U_{2 \times 2} .$ Thus, $S$ is a basis for $U_{2 \times 2}$ and so $\dim (U_{2 \times 2}) = 3 .$ Similarly, for the $3 \times 3$ case let $M_{i j}$ for $i \leq j$ be the $3 \times 3$ matrix with a 1 in the $i j$ position and 0 in every other position. Let

S = {M_{11}, M_{12}, M_{13}, M_{22}, M_{23}, M_{33}} .

Equating corresponding entries shows that if

x_{1} M_{11} + x_{2} M_{12} + x_{3} M_{13} + x_{4} M_{22} + x_{5} M_{23} + x_{6} M_{33} = 0,

then $x_{1} = x_{2} = x_{3} = x_{4} = x_{5} = x_{6} = 0 .$ So $S$ is a linearly independent set. If $A = [a_{i j}]$ is in $U_{3 \times 3},$ then $A = \sum_{i \geq j} a_{i j} M_{i j}$ and $S$ spans $U_{3 \times 3} .$ We conclude that $S$ is a basis for $U_{3 \times 3}$ and $\dim (U_{3 \times 3}) = 6 .$ In general, for an $n \times n$ matrix, the set of matrices $M_{i j},$ one for each entry on and above the diagonal, is a basis for $U_{n \times n} .$ There are $n$ such matrices for the entries on the diagonal. The number of entries above the diagonal is equal to half the total number of entries ( $n^{2}$ ) minus half the number of entries on the diagonal ( $n$ ). So there is a total of $\frac{n^{2} - n}{2}$ such matrices for the entries above the diagonal. Therefore,

\dim (U_{n \times n}) = n + \frac{n^{2} - n}{2} = \frac{n^{2} + n}{2} .

🔗

Subsection Summary

A finite dimensional vector space is a vector space that can be spanned by a finite set of vectors.
We showed that any two bases for a finite dimensional vector space must contain the same number of vectors. Therefore, we can define the dimension of a finite dimensional vector space $V$ to be the number of vectors in any basis for $V .$
If $V$ is a vector space with dimension $n$ and $S$ is any linearly independent subset of $V$ with $n$ vectors, then $S$ is a basis for $V .$ Otherwise, we could add vectors to $S$ to make a basis for $V$ and then $V$ would have a basis of more than $n$ vectors.
If $V$ is a vector space with dimension $n$ and $S$ is any subset of $V$ with $n$ vectors that spans $V,$ then $S$ is a basis for $V .$ Otherwise, we could remove vectors from $S$ to obtain a basis for $V$ and then $V$ would have a basis of fewer than $n$ vectors.
For any finite dimensional space $V$ and a subspace $W$ of $V,$ $\dim (W) \leq \dim (V) .$

🔗

Exercises Exercises

🔗

1.

Let $W = Span {1 + t^{2}, 2 + t + 2 t^{2} + t^{3}, 1 + t + t^{3}, t - t^{2} + t^{3}}$ in $P_{3} .$ Find a basis for $W .$ What is the dimension of $W ?$

🔗

2.

Let $A = [\begin{array}{cc} 1 & 2 \\ 1 & 0 \end{array}]$ and $B = [\begin{array}{cr} 1 & 0 \\ 1 & - 1 \end{array}] .$

🔗

(a)

Are $A$ and $B$ linearly independent or dependent? Verify your result.

🔗

(b)

Extend the set $S = {A, B}$ to a basis for $M_{2 \times 2} .$ That is, find a basis for $M_{2 \times 2}$ that contains both $A$ and $B .$

🔗

3.

Let $A = [\begin{array}{ccc} 1 & 2 & 0 \\ 3 & 0 & 2 \end{array}],$ $B = [\begin{array}{rcc} - 1 & 1 & 1 \\ 2 & 4 & 0 \end{array}],$ $C = [\begin{array}{crr} 5 & 1 & - 3 \\ 0 & - 12 & 4 \end{array}],$ $D = [\begin{array}{crr} 5 & 4 & - 2 \\ 5 & - 8 & 6 \end{array}],$ and $E = [\begin{array}{rcc} 2 & 0 & 0 \\ - 2 & 0 & 1 \end{array}]$ in $M_{2 \times 3}$ and let $S = {A, B, C, D, E} .$

🔗

(a)

Is $S$ a basis for $M_{2 \times 3} ?$ Explain.

🔗

(b)

Determine if $S$ is a linearly independent or dependent set. Verify your result.

🔗

(c)

Find a basis $B$ for $Span S$ that is a subset of $S$ and write all of the vectors in $S$ as linear combinations of the vectors in $B .$

🔗

(d)

Extend your basis $B$ from part (c) to a basis $M_{2 \times 3} .$ Explain your method.

🔗

4.

Determine the dimension of each of the following vector spaces.

🔗

(a)

$Span {2, 1 + t, t^{2}}$ in $P_{2}$

🔗

(b)

The space of all polynomials in $P_{3}$ whose constant terms is 0.

🔗

(c)

$Nul [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}]$

🔗

(d)

$Span {[1 2 0 1 - 1]^{T}, [0 1 1 1 0]^{T}, [0 3 2 3 0]^{T}, [- 1 0 1 1 1]^{T}}$ in $R^{5}$

🔗

5.

Let $W$ be the set of matrices in $M_{2 \times 2}$ whose diagonal entries sum to 0. Show that $W$ is a subspace of $M_{2 \times 2},$ find a basis for $W,$ and then find $\dim (W) .$

🔗

6.

Show that if $W$ is a subspace of a finite dimensional vector space $V,$ then any basis of $W$ can be extended to a basis of $V .$

🔗

7.

Let $W$ be the set of all polynomials $a + b t + c t^{2}$ in $P_{2}$ such that $a + b + c = 0 .$ Show that $W$ is a subspace of $P_{2},$ find a basis for $W,$ and then find $\dim (W) .$

🔗

8.

Suppose $W_{1}, W_{2}$ are subspaces in a finite-dimensional space $V .$

🔗

(a)

Show that it is not true in general that $\dim (W_{1}) + \dim (W_{2}) \leq \dim (V) .$

🔗

(b)

Are there any conditions on $W_{1}$ and $W_{2}$ that will ensure that $\dim (W_{1}) + \dim (W_{2}) \leq \dim (V) ?$

Hint.

See problem 12 in the previous section.

🔗

9.

Suppose $W_{1} \subseteq W_{2}$ are two subspaces of a finite-dimensional space. Show that if $\dim (W_{1}) = \dim (W_{2}),$ then $W_{1} = W_{2} .$

Hint.

Consider dimensions.

🔗

10.

Suppose $W_{1}, W_{2}$ are both three-dimensional subspaces inside $R^{4} .$ In this exercise we will show that $W_{1} \cap W_{2}$ contains a plane. Let ${u_{1}, u_{2}, u_{3}}$ be a basis for $W_{1}$ and let ${v_{1}, v_{2}, v_{3}}$ be a basis for $W_{2} .$

🔗

(a)

If $v_{1},$ $v_{2},$ and $v_{3}$ are all in $W_{1},$ explain why $W_{1} \cap W_{2}$ must contain a plane.

🔗

(b)

Now we consider the case where not all of $v_{1},$ $v_{2},$ and $v_{3}$ are in $W_{1} .$ Since the arguments will be the same, let us assume that $v_{1}$ is not in $W_{1} .$

🔗

(i)

Explain why the set $S = {u_{1}, u_{2}, u_{3}, v_{1}}$ is a basis for $R^{4} .$

🔗

(ii)

Explain why $v_{2}$ and $v_{3}$ can be written as linear combinations of the vectors in $S .$ Use these linear combinations to find two vectors that are in $W_{1} \cap W_{2} .$ Then show that these vectors span a plane in $W_{1} \cap W_{2} .$

🔗

11.

A magic matrix is an $n \times n$ matrix in which the sum of the entries along any row, column, or diagonal is the same. For example, the $3 \times 3$ matrix

[\begin{array}{rcc} 5 & 4 & 0 \\ - 2 & 3 & 8 \\ 6 & 2 & 1 \end{array}]

is a magic matrix. Note that the entries of a magic matrix can be any real numbers.

🔗

(a)

Show that the set of $n \times n$ magic matrices is a subspace of $M_{n \times n} .$

Hint.

Consider the row, column, and diagonal sums.

🔗

(b)

Let $V$ be the space of $3 \times 3$ magic matrices. Find a basis for $V$ and determine the dimension of $V .$

🔗

12.

Label each of the following statements as True or False. Provide justification for your response.

🔗

(a) True/False.

The dimension of a finite dimensional vector space is the minimum number of vectors needed to span that space.

🔗

(b) True/False.

The dimension of a finite dimensional vector space is the maximum number of linearly independent vectors that can exist in that space.

🔗

(c) True/False.

If $n$ vectors span an $n$ -dimensional vector space $V,$ then these vectors form a basis of $V .$

🔗

(d) True/False.

Any set of $n$ vectors form a basis in an $n$ -dimensional vector space.

🔗

(e) True/False.

Every vector in a vector space $V$ spans a one-dimensional subspace of $V .$

🔗

(f) True/False.

Any set of $n$ linearly independent vectors in a vector space $V$ of dimensional $n$ is a basis for $V .$

🔗

(g) True/False.

If ${v_{1}, v_{2}, \dots, v_{k}}$ is linearly independent in $V,$ then $\dim (V) \geq k .$

🔗

(h) True/False.

If a set of $k$ vectors span $V,$ then any set of more than $k$ vectors in $V$ is linearly dependent.

🔗

(i) True/False.

If an infinite set of vectors span $V,$ then $V$ is infinite-dimensional.

🔗

(j) True/False.

If $W_{1}, W_{2}$ are both two-dimensional subspaces of a three dimensional vector space $V,$ then $W_{1} \cap W_{2} \neq {0} .$

🔗

(k) True/False.

If $\dim (V) = n$ and $W$ is a subspace of $V$ with dimension $n,$ then $W = V .$

🔗

Subsection Project: Understanding Principal Component Analysis

🔗

Suppose we were to film an experiment involving a ball that is bouncing up and down. Naively, we set up several cameras to follow the process of the experiment from different perspectives and collect the data. All of this data tells us something about the bouncing ball, but there may be no perspective that tells us an important piece of information — the axis along which the ball bounces. The question, then, is how we can extract from the data this important piece of information. Principal Component Analysis (PCA) is a tool for just this type of analysis.

🔗

Table 33.7. SAT data

State	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
EBRW	$595$	$540$	$522$	$508$	$565$	$512$	$643$	$574$	$534$	$539$
Math	$571$	$536$	$493$	$493$	$554$	$501$	$655$	$566$	$534$	$539$

🔗

We will use an example to illustrate important concepts we will need. To realistically apply PCA we will have much more data than this, but for now we will restrict ourselves to only two variables so that we can visualize our results. Table 33.7 presents information from ten states on two attributes related to the SAT — Evidence-Based Reading and Writing (EBRW) score and Math score. The SAT is made up of three sections: Reading, Writing and Language (also just called Writing), and Math. The The EBRW score is calculated by combining the Reading and Writing section scores — both the Math and EBRW are scored on a scale of 200-800.

🔗

Each attribute (Math, EBRW score) creates a vector whose entries are the student responses for that attribute. The data provides the average scores from participating students in each state. In this example we have two attribute vectors:

\begin{aligned} x_{1} & = [595 540 522 508 565 512 643 574 534 539]^{T} and \\ x_{2} & = [571 536 493 493 554 501 655 566 534 539]^{T} . \end{aligned}

🔗

These vectors form the rows of a

2 \times 10

matrix

X_{0} = [\begin{matrix} x_{1}^{T} \\ x_{2}^{T} \end{matrix}] = [\begin{array}{cccccccccc} 595 & 540 & 522 & 508 & 565 & 512 & 643 & 574 & 534 & 539 \\ 571 & 536 & 493 & 493 & 554 & 501 & 655 & 566 & 534 & 539 \end{array}]

🔗

that makes up our data set. A plot of the data is shown at left in Figure 33.8, where the EBRW score is along the horizontal axis and the math score is along the vertical axis.

🔗
Figure 33.8. Two views of the data set (EBRW horizontal, math vertical).

🔗

The question we want to answer is, how do we represent our data set so that the most important features in the data set are revealed?

🔗

Project Activity 33.6.

Before analyzing a data set there is often some initial preparation that needs to be made. Issues that have to be dealt with include the problem that attributes might have different units and scales. For example, in a data set with attributes about people, height could be measured in inches while weight is measured in pounds. It is difficult to compare variables when they are on different scales. Another issue to consider is that some attributes are independent of the others (height, for example does not depend on hair color), while some are interrelated (body mass index depends on height and weight). To simplify our work, we will not address these type of problems. The only preparation we will do with our data is to center it.

🔗

(a)

An important piece of information about a one-dimensional data set $x = [x_{1} x_{2} x_{3} \dots x_{n}]^{T}$ is the sample average or mean

\overset{―}{x} = \sum_{i = 1}^{n} x_{i} .

Calculate the means $\overset{―}{x_{1}}$ and $\overset{―}{x_{2}}$ for our SAT data from the matrix $X_{0} .$

🔗

(b)

We can use these sample means to center our data at the origin by translating the data so that each column of our data matrix has mean $0 .$ We do this by subtracting the mean for that row vector from each component of the vector. Determine the matrix $X$ that contains the centered data for our SAT data set from matrix $X_{0} .$

🔗

A plot of the centered data for our SAT data is shown at right in Figure 33.8. Later we will see why centering the data is useful — it will more easily allow us to project onto subspaces. The goal of PCA is to find a matrix

P

so that

P X = Y,

and

Y

is suitably transformed to identify the important aspects of the data. We will discuss what the important aspects are shortly. Before we do so, we need to discuss a way to compare the one dimensional data vectors

x_{1}

and

x_{2} .

🔗

Project Activity 33.7.

To compare the two one dimensional data vectors, we need to consider variance and covariance.

🔗

(a)

It is often useful to know how spread out a data set is, something the average doesn't tell us. For example, the data sets $[1 2 3]^{T}$ and $[- 2 0 8]^{T}$ both have averages of $2,$ but the data in $[- 2 0 8]^{T}$ is more spread out. Variance provides one measure of how spread out a one-dimensional data set $x = [x_{1} x_{2} x_{3} \dots x_{n}]^{T}$ is. Variance is defined as

var (x) = \frac{1}{n - 1} \sum_{i = 1}^{n} {(x_{i} - \overset{―}{x})}^{2} .

The variance provides a measure of how far from the average the data is spread.⁶⁰ Determine the variances of the two data vectors $x_{1}$ and $x_{2} .$ Which is more spread out?

🔗

(b)

In general, we will have more than one-dimensional data, as in our SAT data set. It will be helpful to have a way to compare one-dimensional data sets to try to capture the idea of variance for different data sets — how much the data in two different data sets varies from the mean with respect to each other. One such measure is covariance — essentially the average of all corresponding products of deviations from the means. We define the covariance of two data vectors $x = [x_{1} x_{2} \dots x_{n}]^{T}$ and $y = [y_{1} y_{2} \dots y_{n}]^{T}$ as

cov (x, y) = \frac{1}{n - 1} \sum_{i = 1}^{n} (x_{i} - \overset{―}{x}) (y_{i} - \overset{―}{y}) .

Determine all covariances

cov (x_{1}, x_{1}), cov (x_{1}, x_{2}), cov (x_{2}, x_{1}), and cov (x_{2}, x_{2}) .

How are $cov (x_{1}, x_{2})$ and $cov (x_{2}, x_{1})$ related? How are $cov (x_{1}, x_{1})$ and $cov (x_{2}, x_{2})$ related to variances?

🔗

(c)

What is most important about covariance is its sign. Suppose $y = [y_{1} y_{2} \dots y_{n}]^{T},$ $z = [z_{1} z_{2} \dots z_{n}]^{T}$ and $cov (y, z) > 0 .$ Then if $y_{i}$ is larger than $y_{j}$ it is likely that $z_{i}$ is also larger than $z_{j} .$ For example, if $y$ is a vector that records a persons height from age $2$ to $10$ and $z$ records that same person's weight in the same years, we might expect that when $y_{i}$ increases so does $z_{i} .$ Similarly, if $cov (y, z) < 0,$ then as one data set increases, the other decreases. As an example, if $y$ records the number of hours a student spends playing video games each semester ad $z$ gives the student's GPA for each semester, then we might expect that $z_{i}$ decreases as $y_{i}$ increases. When $cov (y, z) = 0,$ then $y$ and $z$ are said to be uncorrelated or independent of each other. For our example $x_{1}$ and $x_{2},$ what does $cov (x_{1}, x_{2})$ tell us about the relationship between $x_{1}$ and $x_{2} ?$ Why should we expect this from the context?

🔗

(d)

The covariance gives us information about the relationships between the attributes. So instead of working with the original data, we work with the covariance data. If we have $m$ data vectors $x_{1},$ $x_{2},$ $\dots,$ $x_{m}$ in $R^{n},$ the covariance matrix $C = [c_{i j}]$ satisfies $c_{i j} = cov (x_{i}, x_{j}) .$ Calculate the covariance matrix for our SAT data. Then explain why $C = \frac{1}{n - 1} X X^{T} .$

🔗

Recall that the goal of PCA is to find a matrix

P

such that

P X = Y

where

P

transforms the data set to a coordinate system in which the important aspects of the data are revealed. We are now in a position to discuss what that means.

🔗

An ideal view of our data would be one in which we can see the direction of greatest variance and one that minimizes redundancy. With redundant data the variables are not independent — that is, covariance is nonzero. So we would like the covariances to all be zero (or as close to zero as possible) to remove redundancy in our data. That means that we would like a covariance matrix in which the non-diagonal entries are all zero. This will be possible if the covariance matrix is diagonalizable.

🔗

Project Activity 33.8.

Consider the covariance matrix $C = [\begin{array}{cc} 1760.18 & 1967.62 \\ 1967.62 & 2319.29 \end{array}] .$ Explain why we can find a matrix $P$ with determinant 1 whose columns are unit vectors that diagonalizes $C .$ Then find such a matrix. Use technology as appropriate.

🔗

For our purposes, we want to diagonalize

X X^{T}

with

P X X^{T} P^{- 1},

so the matrix

P

that serve our purposes is the one whose rows are the eigenvectors of

X X^{T} .

To understand why this matrix is the one we want, recall that we want to have

P X = Y,

and we want to diagonalize

X X^{T}

to a diagonal covariance matrix

Y Y^{T} .

In this situation we will have (recalling that

P^{- 1} = P^{T}

)

\frac{1}{n - 1} Y Y^{T} = \frac{1}{n - 1} (P X) (P X)^{T} = \frac{1}{n - 1} P (X X^{T}) P^{T} = P (X X^{T}) P^{- 1} .

🔗

So the matrix

P

that we want is exactly the one that diagonalizes

X X^{T} .

🔗

Project Activity 33.9.

There are two useful ways we can interpret the results of our work so far. An eigenvector of $X X^{T}$ that corresponds to the largest (also called the dominant) eigenvalue $λ_{1}$ is $[0.66 0.76]^{T} .$ A plot of the centered data along with the eigenspace $E_{λ_{1}}$ of $X X^{T}$ spanned by $v_{1} = [0.66 0.76]^{T}$ is shown at left in Figure 33.9. The eigenvector $v_{1}$ is called the first principal component of $X .$ Notice that this line $E_{λ_{1}}$ indicates the direction of greatest variation in the data. That is, the sum of the squares of the differences between the data points and the mean is as large as possible in this direction. In other words, when we project the data points onto $E_{λ_{1}},$ as shown at right in Figure 33.9, the variation of the resulting points is larger than it is for any other line. In other words, the data is most spread out in this direction.

🔗

(a)

There is another way we can interpret this result. If we drop a perpendicular from one of our data points to the space $E_{λ_{1}}$ it creates a right triangle with sides of length $a,$ $b,$ and $c$ as illustrated in the middle of Figure 33.9. Use this idea to explain why maximizing the variation also minimizes the sum of the squares of the distances from the data points to this line. As a result, we have projected our two-dimensional data onto the one-dimensional space that maximizes the variance of the data.

🔗

(b)

Recall that the matrix (to two decimal places) $P = [\begin{array}{rr} - 0.66 & - 0.76 \\ 0.76 & 0.66 \end{array}]$ transforms the data set $X$ to a new data set $Y = P X$ whose covariance matrix is diagonal. Explain how the $x$ -axis is related to the transformed data set $Y .$

🔗

The result of Project Activity 33.9 is that we have reduced the problem from considering the data in a two-dimensional space to a one-dimensional space

E_{λ_{1}}

where the most important aspect of the data is revealed. Of course, we eliminate some of the characteristics of the data, but the most important aspect is still included and highlighted. This is one of the important uses of PCA, data dimension reduction, which allows us to reveal key relationships between the variables that might not be evident when looking at a large dataset.

🔗

The second eigenvector of

X X^{T}

also has meaning. A picture of the eigenspace

E_{λ_{2}}

corresponding to the smaller eigenvector

λ_{2}

X X^{T}

is shown in Figure 33.11. The second eigenvector of

X X^{T}

is orthogonal to the first, and the direction of the second eigenvector tells us the direction of the second most amount of variance as can be seen in Figure 33.11.

🔗
Figure 33.11. The second principal component.

🔗

To summarize, the unit eigenvector for the largest eigenvalue of

X X^{T}

indicates the direction in which the data has the greatest variance. The direction of the unit eigenvector for the smaller eigenvalue shows the direction in which the data has the second largest variance. This direction is also perpendicular to the first (indicating

0

covariance). The directions of the eigenvectors are called the principal components of

X .

The eigenvector with the highest eigenvalue is the first principal component of the data set and the other eigenvectors are ordered by the eigenvalues, highest to lowest. The principal components provide a new coordinate system from which to view our data — one in which we can see the maximum variance and in which there is zero covariance.

🔗

Project Activity 33.10.

We can use the eigenvalues of $X X^{T}$ to quantify the amount of variance that is accounted for by our projections. Notice that the points along the $x$ -axis at right in Figure 33.10 are exactly the numbers in the first row of $Y .$ These numbers provide the projections of the data in $Y$ onto the $x$ -axis — the axis along which the data has its greatest variance.

🔗

(a)

Calculate the variance of the data given by the first row of $Y .$ This is the variance of the data i the direction of the eigenspace $E_{λ_{1}} .$ How does the result compare to entries of the covariance matrix for $Y .$

🔗

(b)

Repeat part (a) for the data along the second row of $Y .$

🔗

(c)

The total variance of the data set is the sum of the variances. Explain why the amount of variance in the data that is accounted for in the direction of $E_{λ_{1}}$ is

\frac{λ_{1}}{λ_{1} + λ_{2}} .

Then calculate this amount for the SAT data.

🔗

In general, PCA is most useful for larger data sets. The process is the same.

Start with a set of data that forms the rows of an $m \times n$ matrix. We center the data by subtracting the mean of each row from the entries of that row to create a centered data set in a matrix $X .$
The principal components of $X$ are the eigenvectors of $X X^{T},$ ordered so that they correspond to the eigenvalues of $X X^{T}$ in decreasing order.
Let $P$ be the matrix whose rows are the principal components of $X,$ ordered from highest to lowest. Then $Y = P X$ is suitably transformed to identify the important aspects of the data.
If $λ_{1},$ $λ_{2},$ $\dots,$ $λ_{n}$ are the eigenvalues of $X X^{T}$ in decreasing order, then the amount of variance in the data accounted for by the first $r$ principal components is given by

$\frac{λ_{1} + λ_{2} + \dots + λ_{r}}{λ_{1} + λ_{2} + \dots + λ_{n}} .$
The first $r$ rows of $Y = P X$ provide the projection of the data set $X$ onto an $r$ -dimensional space spanned by the first $r$ principal components of $X .$

🔗

Project Activity 33.11.

Let us now consider a problem with more than two variables. We continue to keep the data set small so that we can conveniently operate with it. Table 33.12 presents additional information from ten states on four attributes related to the SAT — Participation rates, Evidence-Based Reading and Writing (EBRW) score, Math score, and average SAT score. Use technology as appropriate for this activity.

Table 33.12. SAT data

State	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
Rate	$6$	$60$	$97$	$100$	$64$	$99$	$4$	$23$	$79$	$70$
EBRW	$595$	$540$	$522$	$508$	$565$	$512$	$643$	$574$	$534$	$539$
Math	$571$	$536$	$493$	$493$	$554$	$501$	$655$	$566$	$534$	$539$
SAT	$1166$	$1076$	$1014$	$1001$	$1120$	$1013$	$1296$	$1140$	$1068$	$1086$

🔗

(a)

Determine the centered data matrix $X$ for this data set.

🔗

(b)

Find the covariance matrix for this data set. Round to four decimal places.

🔗

(c)

Find the principal components of $X .$ Include at least four decimal places accuracy.

🔗

(d)

How much variation is accounted for in the data by the first principal component? In other words, if we reduce this data to one dimension, how much of the variation do we retain? Explain.

🔗

(e)

How much variation is accounted for in the data by the first two principal components? In other words, if we reduce this data to two dimensions, how much of the variation do we retain? Explain.

🔗

We conclude with a comment. A reasonable question to ask is how we interpret the principal components. Let

P

be an orthogonal matrix such that

P C P^{T}

is the diagonal matrix with the eigenvalues of

C

along the diagonal, in decreasing order. We then have the new perspective

Y = P X

from which to view the data. The first principal component

p_{1}

(the first row of

P

) determines the new variable

y_{1} = [y_{i}]

(the first row of

Y

) in the following manner. Let

p_{1} = [p_{i}]^{T}

and let

c_{i}

represent the columns of

X

so that

X = [c_{1} c_{2} c_{3} \dots c_{20}] .

Recognizing that

P X = [\begin{matrix} p_{1}^{T} \\ p_{2}^{T} \\ p_{3}^{T} \\ p_{4}^{T} \\ p_{5}^{T} \\ p_{6}^{T} \end{matrix}] [c_{1} c_{2} c_{3} \dots c_{20}],

🔗

we have that

y_{i} = p_{1}^{T} c_{i} .

🔗

That is,

y_{1} = [p_{1}^{T} c_{1} p_{1}^{T} c_{2} p_{1}^{T} c_{3} \dots p_{1}^{T} c_{20}] .

🔗

So each

y_{i}

is a linear combination of the original variables (contained in the

c_{i}

) with weights from the first principal component. The other new variables are obtained in the same way from the remaining principal components. So even though the principal components may not have an easy interpretation in context, they are connected to the original data in this way. By reducing the data to a few important principal components — that is, visualizing the data in a subspace of small dimension — we can account for almost all of the variation in the data and relate that information back to the original data.

It might seem that we should divide by

n

instead of

n - 1

in the variance, but it is generally accepted to do this for reasons we won't get into. Suffice it to say that if we are using a sample of the entire population, then dividing by

n - 1

provides a variance whose square root is closer to the standard deviation than we would get if we divide by

n .

If we are calculating the variance of an entire population, then we would divide by

n .