# Linear AlgebraVector Spaces

Spans of lists of vectors are so important that we give them a special name: a **vector space** in is a nonempty set of vectors in which is closed under the vector space operations. *Closed* in this context means that if two vectors are in the set, then any linear combination of those vectors is also in the set.

If and are vector spaces and , then is called a **subspace** of .

**Example**

Lines and planes through the origin are vector subspaces of . More generally, the span of any list of vectors in is a vector subspace of .

**Exercise**

Show that if and are vector spaces in , then is also a vector space.

Hint: start by assuming that and , and reason your way to the conclusion that is also in .

*Solution.* Our goal is to show that is

If and , then and are

## Spanning lists

A **spanning list** of a vector space is a list of vectors in whose span is equal to .

**Example**

The list is a spanning list for because any vector can be represented as

**Exercise**

Select the true statements.

## Bases

A linearly independent spanning list for a vector space is called a **basis** for .

**Example**

The list is a basis for and the list is also a basis for .

A basis must balance two constraints: it must be long enough to span the space, and it must be short enough to avoid being linearly dependent. Reason geometrically to solve the following exercises.

**Exercise**

A list of vectors in must have at least

As we will show later in this unit, the situation explored in the exercise above holds in general: for each vector space , there is a number such that any basis of must have exactly vectors. We call the **dimension**

**Exercise**

- A line through the origin has dimension
- A plane has dimension
- has dimension
- The set containing only the zero vector has dimension

## Coordinates

Bases provide a concrete and useful way to represent the vectors in a vector space. For example, consider a two-dimensional subspace of . Vectors in can be represented using their three components, but that representation does not capture any information about . For example, perturbing the three components of a vector in may yield a vector which

We may instead fix any two vectors and which span the plane and describe each vector in the plane by identifying how many 's and how many 's are needed to obtain it. In other words, we associate each vector with the pair for which . With this representation, the values and may vary freely and

The values and are called the **coordinates** of with respect to the basis .

**Example**

Consider the line in the plane which passes through and . This vector space is spanned by the vector , and the coordinate of any vector with respect to the basis is

**Example**

For , let be a vector with in the th position and zeros elsewhere. Then is called the **standard basis** for The components of a vector in coincide with its coordinates with respect to this basis.

The idea of vector space coordinates with respect to a basis is fully general: given a vector space and a basis of , we can represent each vector in uniquely as a linear combination of the vectors in the basis. In other words, if a vector space has a basis and , then there exists a unique -tuple of real numbers such that

We call the **coordinates** of with respect to

We need the assumption of

**Exercise**

The vectors , , meet at right angles at the origin (like the standard basis vectors in ). Find the coordinates of the vector with respect to this basis.

Hint: you can solve the linear system

in Python as follows:

```
import numpy as np
A = np.array([[a,b,c],[e,f,g],[i,j,k]])
b = np.array([d,h,l])
np.linalg.solve(A,b)
```

in Julia as follows:

```
A = [a b c; e f g; i j k]
b = [d, h, l]
a \ b
```

However, it's also possible to reason your way through this one without computational assistance (or pen-and-paper calculation).

The three coordinates are

import numpy as np

*Solution.* We can calculate using NumPy as suggested:

import numpy as np A = np.array([[1,1,np.sqrt(2)], [1,1,-np.sqrt(2)], [1,-1,0]]) b = np.array([4,4,0]) np.linalg.solve(A,b)

*Solution.* We can calculate using Julia as suggested:

A = [1 1 sqrt(2); 1 1 -sqrt(2); 1 -1 0] b = [4, 4, 0] A \ b

However, we can obtain the same result by inspection, noticing the relationship between the values at the beginning of the first two basis vectors and the result.

**Exercise**

Consider a basis of a five-dimensional vector space . Suppose that is in the span of . What is the fifth coordinate of with respect to the basis ?

*Solution.* Since can be written as a linear combination of the first four vectors, it can be written as a linear combination of all five basis vectors by appending the term . Since the coordinate representation is unique, this means that is the fifth coordinate of with respect to .

**Exercise**

Consider a three-column spreadsheet of numerical data, with each entry in the third column computed to be the sum of the corresponding entries in the first two columns. Find a basis for the span of the three columns (assuming the first two columns are not multiples of one another), and find the coefficients all three columns with respect to this basis.

*Solution.* The first two columns form a basis for the span. The coordinates of the three columns with respect to this basis are , , and .

## Proof of the dimension theorem

The **dimension theorem** says that every basis of a given vector space has the same length. The key step to establishing the dimension theorem is the dimension lemma:

**Theorem** (dimension lemma)

If is a vector space, then any spanning list of is at least as long as any linearly independent list of vectors in .

In other words, the dimension lemma says that if is a linearly independent list of vectors in and is a list of vectors which spans , then the length of is less than or equal to the length of .

*Proof.* The following beautiful idea is presented in Sheldon Axler's book *Linear Algebra Done Right*.

Consider a linearly independent list of vectors in and a spanning list of . Our goal is to show that there are

Starting from the spanning list

we insert at the beginning of the list to get

Since is in the span of the 's, this list is linearly dependent. Therefore, by the linear

Since the 's are linearly independent,

We can continue in this way, adding the next at the beginning of the list and removing one of the 's while preserving the span. Eventually we have placed all of the 's into the list, with each displacing exactly one . Therefore, there must have been at

**Exercise**

Use the dimension lemma to show that all bases of a vector space have the same length. In other words, if is a basis for , and is a basis for , then the lengths of and are equal.

*Solution.* Since is a spanning list and is linearly independent, we know that is at

## Extending and trimming lists

The following two exercises provide simple yet powerful tools for reasoning about linear independence, span, and dimension.

**Exercise**

Show that any linearly independent list of vectors in a vector space can be extended to form a basis of , and show that any spanning list of can be trimmed to form a basis of .

*Solution.* Consider a linearly independent list of vectors in . If it spans , then it is already a

We can trim a list without changing its span by working through the list progressively and removing any vector which is in the

The following exercise tells us that if we start with a basis for the intersection of two vector spaces, and extend it separately to a basis for each of the vector spaces, then the compiled list of all of those basis vectors is still linearly independent.

**Exercise** (multiple extension principle)

Suppose that and are vector spaces in . Suppose that is a basis for , that is a basis for , and that is a basis for . Show that

is a linearly independent list.

Note: this exercise is on the challenging side. You might want to make your best effort over a reasonable period of time, submit what you've got, and then read the solution.

*Solution.* By the

Suppose that one of the 's is in the span of the preceding vectors, say

Consider the vector . This vector is in , since is a linear combination of vectors in .

But is also in since is a linear combination of vectors in . Therefore, . But in that case, would be in the span of , which would mean that

Since is a basis for , we have reached a contradiction. Therefore, we may conclude that

is linearly

## Exercises

**Exercise**

Suppose that and are subspaces of and that has dimension 4 and has dimension 8. Which of the following could possibly be equal to the dimension of ? Select all that apply.

Hint: consider two two-dimensional spaces in : what are the possible dimensions for the intersection of two planes through the origin in ?

*Solution.* Since , the dimension of is no larger than

However, the dimension of cannot be 1. To see this, assume that the dimension of is 1 and fix a basis for and extend it to a basis for , and (separately) also extend it to a basis for . By the

So, the possible values for the dimension of are 2, 3, and 4.

**Exercise** A set of 5 column vectors in with entries selected uniformly at random from may be generated using `np.random.random_sample((7,5))`

`rand(7, 5)`

. The dimension of the span of the columns of a matrix may then by computed using the function `np.linalg.matrix_rank`

`rank`

.

Calculate the dimension of many such spans of random lists of five vectors in . What can you say about the values you get?

import numpy as np

**Exercise**

Repeat the preceding exercise with random vectors whose entries are 0 or 1 with probability .

Hint: for part (b): `np.random.randint(0,2,(5,7))`

generates the desired random matrix, and importing `Counter`

from `collections`

might be helpful for helping you inspect the contents of the list of ranks.

import numpy as np

*Solution.* If we run

rank = np.linalg.matrix_rank def randmat(): return np.random.random_sample((7,5)) set([rank(randmat()) for _ in range(100_000)])

using LinearAlgebra Set([rank(rand(7,5)) for _ in range(100_000)])

we get a set containing only

If we run

from collections import Counter Counter([rank(np.random.randint(0,2,(7,5))) for i in range(100_000)])

import StatsBase: countmap import LinearAlgebra: rank countmap([rank(rand(0:1, 7, 5)) for i in range(100_000)])

we get mostly fives, quite a few fours, some threes and perhaps a few twos. Therefore, the vectors are not always linearly independent in this case.