## Glossary

Select one of the keywords on the left…

# 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 under the vector space operations. In other words, we want to show that if and , then the sum (and similarly for scalar multiplication).

If and , then and are in . Since is a vector space, this means that in . Similarly, is also in . Therefore, , as desired. Similar reasoning applies to show closure with respect to , concluding the proof.

## 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.

If two vectors span XEQUATIONX24XEQUATIONX, then they point in the same direction.
Two vectors can span
A spanning list of XEQUATIONX25XEQUATIONX may contain as few as two vectors.
The list XEQUATIONX26XEQUATIONX is not the only spanning list of XEQUATIONX27XEQUATIONX.

## 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 vectors in order to span a particular plane in . A linearly independent list of vectors in a plane in must have no more than vectors.

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 of .

Exercise

1. A line through the origin has dimension
2. A plane has dimension
3. has dimension
4. 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 in .

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 represent an element of .

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 to ensure that the desired linear combination exists, and we need the assumption to ensure that the representation is unique.

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 as many 's as 's.

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 lemma, there is a vector in the list which is in the of the ones it.

Since the 's are linearly independent, such a vector. Therefore, one of the 's must be removable without changing the span of the list.

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 as many 's as 's at the beginning.

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 as long as . Similarly, is at least as long as . Therefore, their lengths are the same.

## 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 . If not, then there is a vector in which is not in the span of . Appending this vector to our list, we obtain a list which is still by the linear dependence lemma. Continuing in this way, we will eventually get a linearly independent list which spans (the process can't go on forever since by the time the list has linearly independent vectors in it, it spans and therefore also ).

We can trim a list without changing its span by working through the list progressively and removing any vector which is in the of the vectors preceding it. By the linear dependence lemma, applying this procedure to a spanning list results in a linearly independent spanning list.

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 linear dependence lemma, it suffices to check that no vector in the list is in the span of the vectors before it in the list. Since the first vectors form a basis for , they are linearly . Therefore, none of these is in the span of the preceding vectors.

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 linearly independent.

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.

0
1
2
3
4
5
8
9

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 . If , then , so the dimension of could be as large as 4. If is a basis of , and is the span of and is the span of , then would be the span of , so the dimension could also be 3. Likewise, the dimension of could be 2.

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 multiple extension principle, this would give us a total of linearly independent vectors in , which is impossible. Likewise, the dimension of cannot be zero.

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?

All fives
Mostly fives, some numbers fewer than five
Mostly threes, some twos and fours, occasional ones and fives
import numpy as np

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

All fives
Mostly fives, some numbers fewer than five
Mostly threes, some twos and fours, occasional zeros, ones and fives

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 5. Therefore, five random vectors in with entries selected uniformly from are always or nearly always linearly independent. So the first answer is correct.

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.  Bruno