שנה שפה

English

היכנס אל מתיגון

אוֹ

חשבון חדש     אפס הסיסמה     

Linear Algebra
by Samuel S. Watson
Introduction
Vectors
Span
Linear Independence
Vector Spaces
Linear Transformations
Matrices
Dot Products
Transposes
Orthogonality
Eigenanalysis
Singular Value Decomposition
Determinants

שתף

אפס התקדמות

פעולה זו תמחק את ההתקדמות ואת נתוני הצ'אט עבור כל הפרקים בקורס זה, ולא ניתן לבטל אותה!

מילון מונחים

בחר אחת ממילות המפתח משמאל...

Linear AlgebraVector Spaces

זמן קריאה: ~70 min

Spans of lists of vectors are so important that we give them a special name: a vector space in \mathbf{R}^n is a nonempty set of vectors in \mathbb{R}^n 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 V and W are vector spaces and V \subset W, then V is called a subspace of W.

Example
Lines and planes through the origin are vector subspaces of \mathbb{R}^3. More generally, the span of any list of vectors in \mathbb{R}^n is a vector subspace of \mathbb{R}^n.

Exercise
Show that if V and W are vector spaces in \mathbf{R}^n, then V \cap W is also a vector space.

Hint: start by assuming that \mathbf{x} \in V \cap W and \mathbf{y} \in V \cap W, and reason your way to the conclusion that \mathbf{x} + \mathbf{y} is also in V.

Solution. Our goal is to show that V \cap W is under the vector space operations. In other words, we want to show that if \mathbf{x} \in V \cap W and \mathbf{y} \in V \cap W, then the sum \mathbf{x} + \mathbf{y} V \cap W (and similarly for scalar multiplication).

If \mathbf{x} \in V \cap W and \mathbf{y} \in V \cap W, then \mathbf{x} and \mathbf{y} are in V. Since V is a vector space, this means that \mathbf{x} + \mathbf{y} in V. Similarly, \mathbf{x} + \mathbf{y} is also in W. Therefore, \mathbf{x} + \mathbf{y} \in V \cap W, as desired. Similar reasoning applies to show closure with respect to , concluding the proof.

Spanning lists

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

Example
The list \left\{\begin{bmatrix} 2 \\\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\\ 1 \end{bmatrix}, \begin{bmatrix} 7 \\\ 11 \end{bmatrix} \right\} is a spanning list for \mathbb{R}^2 because any vector \mathbf{v} = \begin{bmatrix} x \\\ y \end{bmatrix} \in \mathbb{R}^2 can be represented as

\begin{align*}\mathbf{v} = (x - y) \begin{bmatrix} 2 \\\ 1 \end{bmatrix} + (2y - x)\begin{bmatrix} 1 \\\ 1 \end{bmatrix} + 0 \begin{bmatrix} 7 \\\ 11 \end{bmatrix}.\end{align*}

Exercise
Select the true statements.

If two vectors span XEQUATIONX3230XEQUATIONX, then they point in the same direction.
Two vectors can span XEQUATIONX3231XEQUATIONX
A spanning list of XEQUATIONX3232XEQUATIONX may contain as few as two vectors.
The list XEQUATIONX3233XEQUATIONX is not the only spanning list of XEQUATIONX3234XEQUATIONX.

Bases

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

Example
The list \left\{\begin{bmatrix} 2 \\\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\\ 1 \end{bmatrix}\right\} is a basis for \mathbb{R}^2 and the list \left\{ \begin{bmatrix} 1 \\\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\\ 1 \end{bmatrix} \right\} is also a basis for \mathbb{R}^2.

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 \mathbb{R}^3 must have at least vectors in order to span a particular plane in \mathbb{R}^2. A linearly independent list of vectors in a plane in \mathbb{R}^3 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 V, there is a number d such that any basis of V must have exactly d vectors. We call d the dimension of V.

Exercise

  1. A line through the origin has dimension
  2. A plane has dimension
  3. \mathbb{R}^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 V of \mathbf{R}^3. Vectors in V can be represented using their three components, but that representation does not capture any information about V. For example, perturbing the three components of a vector in V may yield a vector which in V.

We may instead fix any two vectors \mathbf{u} and \mathbf{v} which span the plane and describe each vector in the plane by identifying how many \mathbf{u}'s and how many \mathbf{v}'s are needed to obtain it. In other words, we associate each vector \mathbf{w} with the pair (a,b) for which \mathbf{w} = a \mathbf{u} + b \mathbf{v}. With this representation, the values a and b may vary freely and represent an element of V.

The values a and b are called the coordinates of \mathbf{w} with respect to the basis \{\mathbf{u}, \mathbf{v}\}.

Example
Consider the line in the plane which passes through (0,0) and (1,1). This vector space is spanned by the vector [1,1], and the coordinate of any vector [a,a] with respect to the basis \{[1,1]\} is .

Example
For 1 \leq i \leq n, let \mathbf{e}_i \in \mathbb{R}^n be a vector with 1 in the i th position and zeros elsewhere. Then \{\mathbf{e}_1, \dots, \mathbf{e}_n\} is called the standard basis for \mathbb{R}^n. The components of a vector in \mathbb{R}^n 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 V and a basis of V, we can represent each vector in V uniquely as a linear combination of the vectors in the basis. In other words, if a vector space V has a basis \mathcal{B} = \{\mathbf{b}_1, \dots \mathbf{b}_n\} and \mathbf{v} \in V, then there exists a unique n-tuple of real numbers (v_1, \dots, v_n) such that

\begin{align*}\mathbf{v} = v_1\mathbf{b}_1 + \cdots + v_n\mathbf{b}_n.\end{align*}

We call (v_1, \dots, v_n) the coordinates of \mathbf{v} with respect to \mathcal{B}.

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 [1,1,\sqrt{2}], [1,1,-\sqrt{2}], [1,-1,0] meet at right angles at the origin (like the standard basis vectors in \mathbf{R}^3). Find the coordinates of the vector [4,4,0] with respect to this basis.

Hint: you can solve the linear system

\begin{align*}ax + by + cz &= d \\\ ex + fy + gz &= h \\\ ix + jy + kz &= l\end{align*}

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 [1,1] values at the beginning of the first two basis vectors and the [4,4] result.
 
Exercise
Consider a basis \mathcal{B} = \{\mathbf{v}_1, \ldots, \mathbf{v}_5\} of a five-dimensional vector space V. Suppose that \mathbf{w} is in the span of \{\mathbf{v}_1, \ldots, \mathbf{v}_4\}. What is the fifth coordinate of \mathbf{w} with respect to the basis \mathcal{B}? 
 
Solution. Since \mathbf{w} 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 0\mathbf{v}_5. Since the coordinate representation is unique, this means that \boxed{0} is the fifth coordinate of \mathbf{w} with respect to \mathcal{B}.
 
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 [1,0], [0,1], and [1,1].
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 V is a vector space, then any spanning list of V is at least as long as any linearly independent list of vectors in V.
 
In other words, the dimension lemma says that if L_1 is a linearly independent list of vectors in V and L_2 is a list of vectors which spans V, then the length of L_1 is less than or equal to the length of L_2.
Proof. The following beautiful idea is presented in Sheldon Axler's book Linear Algebra Done Right.
Consider a linearly independent list \mathbf{l}_1, \ldots, \mathbf{l}_m of vectors in V and a spanning list \mathbf{s}_1, \ldots, \mathbf{s}_n of V. Our goal is to show that there are  as many \mathbf{s}'s as \mathbf{l}'s.
Starting from the spanning list
\begin{align*}\mathbf{s}_1, \ldots, \mathbf{s}_n\end{align*}
we insert \mathbf{l}_1 at the beginning of the list to get
\begin{align*}\mathbf{l}_1, \mathbf{s}_1, \ldots, \mathbf{s}_n\end{align*}
Since \mathbf{l}_1 is in the span of the \mathbf{s}'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 \mathbf{l}'s are linearly independent, \mathbf{l}_1  such a vector. Therefore, one of the \mathbf{s}'s must be removable without changing the span of the list.
We can continue in this way, adding the next \mathbf{l} at the beginning of the list and removing one of the \mathbf{s}'s while preserving the span. Eventually we have placed all of the \mathbf{l}'s into the list, with each displacing exactly one \mathbf{s}. Therefore, there must have been at  as many \mathbf{s}'s as \mathbf{l}'s at the beginning.
 
Exercise
Use the dimension lemma to show that all bases of a vector space V have the same length. In other words, if B_1 is a basis for V, and B_2 is a basis for V, then the lengths of B_1 and B_2 are equal.
 
Solution. Since B_1 is a spanning list and B_2 is linearly independent, we know that B_1 is at  as long as B_2. Similarly, B_2 is at least as long as B_1. 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 V\subset \mathbb{R}^n can be extended to form a basis of V, and show that any spanning list of V can be trimmed to form a basis of V.
 
Solution. Consider a linearly independent list L of vectors in V. If it spans V, then it is already a . If not, then there is a vector in V which is not in the span of L. 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 V (the process can't go on forever since by the time the list has n linearly independent vectors in it, it spans \mathbb{R}^n and therefore also V).
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 U and V are vector spaces in \mathbb{R}^n. Suppose that \{\mathbf{u}_1, \ldots, \mathbf{u}_j\} is a basis for U \cap V, that \{\mathbf{u}_1, \ldots, \mathbf{u}_k\} is a basis for U, and that \{\mathbf{u}_1, \ldots, \mathbf{u}_j, \mathbf{v}_1, \ldots, \mathbf{v}_\ell\} is a basis for V. Show that
\begin{align*}\{\mathbf{u}_1, \ldots, \mathbf{u}_k, \mathbf{v}_1, \ldots, \mathbf{v}_\ell\}\end{align*}
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 k vectors form a basis for U, they are linearly . Therefore, none of these is in the span of the preceding vectors.
Suppose that one of the \mathbf{v}'s is in the span of the preceding vectors, say
\begin{align*}\mathbf{v}_m = c_{1}\mathbf{u}_1 + c_{2}\mathbf{u}_{2} + \cdots + c_k\mathbf{u}_k+ d_{1}\mathbf{v}_1 + d_{m-1} \mathbf{v}_{m-1}.\end{align*}
Consider the vector \mathbf{v} = \mathbf{v}_m - ( d_{1}\mathbf{v}_1 + d_{m-1} \mathbf{v}_{m-1}) = c_{1}\mathbf{u}_1 + c_{2}\mathbf{u}_{2} + \cdots + c_k\mathbf{u}_k. This vector is in V, since \mathbf{v}_m - ( d_{1}\mathbf{v}_1 + d_{m-1} \mathbf{v}_{m-1}) is a linear combination of vectors in V.
But \mathbf{v} is also in U since c_{1}\mathbf{u}_1 + c_{2}\mathbf{u}_{2} + \cdots + c_k\mathbf{u}_k is a linear combination of vectors in U. Therefore, \mathbf{v} \in U \cap V. But in that case, \mathbf{v} would be in the span of \{\mathbf{u}_1, \ldots \mathbf{u}_j\}, which would mean that \{\mathbf{u}_1, \ldots, \mathbf{u}_j, \mathbf{v}_1, \ldots, \mathbf{v}_\ell\}  linearly independent.
Since \{\mathbf{u}_1, \ldots, \mathbf{u}_j, \mathbf{v}_1, \ldots, \mathbf{v}_\ell\} is a basis for V, we have reached a contradiction. Therefore, we may conclude that
\begin{align*}\{\mathbf{u}_1, \ldots, \mathbf{u}_k, \mathbf{v}_1, \ldots, \mathbf{v}_\ell\}\end{align*}
is linearly .
Exercises
 
Exercise
Suppose that V and W are subspaces of \mathbb{R}^{10} and that V has dimension 4 and W has dimension 8. Which of the following could possibly be equal to the dimension of V \cap W? Select all that apply.
0
1
2
3
4
5
8
9
Hint: consider two two-dimensional spaces in \mathbb{R}^3: what are the possible dimensions for the intersection of two planes through the origin in \mathbb{R}^3?
 
Solution. Since V \cap W\subset V, the dimension of V\cap W is no larger than . If V \subset W, then V \cap W = V, so the dimension of V could be as large as 4. If \{\mathbf{v}_1, \ldots, \mathbf{v}_{10}\} is a basis of \mathbb{R}^{10}, and W is the span of \{\mathbf{v}_1, \ldots, \mathbf{v}_{8}\} and V is the span of \{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_9\}, then V \cap W would be the span of \{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}, so the dimension could also be 3. Likewise, the dimension of V\cap W could be 2.
However, the dimension of V \cap W cannot be 1. To see this, assume that the dimension of V \cap W is 1 and fix a basis \{\mathbf{v}_1\} for V \cap W and extend it to a basis for V, and (separately) also extend it to a basis for W. By the multiple extension principle, this would give us a total of 1 + 7 + 3 = 11 linearly independent vectors in \mathbb{R}^{10}, which is impossible. Likewise, the dimension of V \cap W cannot be zero.
So, the possible values for the dimension of V \cap W are 2, 3, and 4.
 
Exercise A set of 5 column vectors in \mathbb{R}^7 with entries selected uniformly at random from [0,1] 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 \mathbb{R}^7. 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 \frac{1}{2}.
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 \mathbb{R}^7 with entries selected uniformly from [0,1] 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
Bruno Bruno