Applied Linear Algebra - Packet 05

Packet 05

Vectors I: Generators

Basics of nD vectors

Vectors in ${ℝ}^n$ have $n$ real number components:

$$𝐯=(v_1,v_2,\dots ,v_n).$$

Such vectors are added componentwise, and scalars multiply every component simultaneously. All the abstract operations and properties of vectors apply to vectors in ${ℝ}^n$:

• Operations: addition and scalar multiplication,
• Properties: commutativity, associativity, distributivity, zero vector.

There are $n$ standard basis vectors:

$${𝐞}_i=(0,\dots ,0,1^{\underbrace{i^{th}}},0,\dots ,0).$$

Decomposition works as in $3$D:

$$𝐯=v_1{𝐞}_1+v_2{𝐞}_2+\cdots +v_n{𝐞}_n,𝐯=\sum _{i=1}^n{v}_i{𝐞}_i.$$

Pairs of vectors in $n$D also have dot products defined by summing component products:

$$\begin{array}{cc}𝐮\cdot 𝐯& =(u_1,\dots ,u_n)\cdot (v_1,\dots ,v_n)\\ & =u_1{v}_1+\cdots +u_n{v}_n\\ & =\sum _{i=1}^n{u}_i{v}_i.\end{array}$$

The norm of an $n$D vector is still $|𝐮|=\sqrt{𝐮\cdot 𝐮}$.

Dot product still has the meaning of “relative alignment between vectors,” and can still be used to determine the angle between vectors using the cosine formula, $𝐮\cdot 𝐯=|𝐮||𝐯|\cos \theta$. However, this angle is considerably less important in $n$D.

Projection in $n$D is very important. It is computed with the same formula:

$${𝐮}_{||}={\mathrm{proj}}_{𝐯}(𝐮)=(𝐮\cdot {𝐞}_{𝐯}){𝐞}_{𝐯}=\left(\frac{𝐮\cdot 𝐯}{𝐯\cdot 𝐯}\right)𝐯.$$

We also have ${𝐮}_{⟂}=𝐮-{𝐮}_{\parallel }$. Notice that ${𝐮}_{⟂}$ now lives in the hyperplane perpendicular to $𝐯$. Given various $𝐮$ and a fixed $𝐯$, the various ${𝐮}_{\parallel }$ are all parallel to $𝐯$, but the various ${𝐮}_{⟂}$ are not all parallel to each other.

The Cauchy-Schwartz and Triangle inequalities become more important in $n$D:

$$|𝐮\cdot 𝐯|\le |𝐮||𝐯|,|𝐮+𝐯|\le |𝐮|+|𝐯|.$$

The vector formula for a line through ${𝐫}_0$ in the direction of $𝐯$, namely $𝐫(t)={𝐫}_0+t𝐯$, still works in $n$D. However, the formula for a plane:

$$(𝐫-{𝐫}_0)\cdot 𝐧=0$$

determines a hyperplane in $n$D, meaning an $(n-1)$D space inside of ${ℝ}^n$. We could write this space in scalar form as

$$k_1(x_1-a_1)+k_2(x_2-a_2)+\cdots +k_n(x_n-a_n)=0,$$

where:

$$𝐧=(k_1,\dots ,k_n),{𝐫}_{\mathrm{𝟎}}=(a_1,\dots ,a_n),𝐫=(x_1,\dots ,x_n).$$

Spans

Linear combinations of vectors in $n$D work just as in $3$D:

$$𝐯=a_1{𝐮}_1+a_2{𝐮}_2+\cdots +a_n{𝐮}_n,a_i\in ℝ.$$

A span is a collection of all vectors which could be obtained as linear combinations of certain given vectors. For example, the collection of all possible $𝐯$ that can be written as above, for any $a_i$, in terms of the ${𝐮}_i$ given at the outset, is called either of:

$$\mathrm{span}\{{𝐮}_1,\dots ,{𝐮}_n\},⟨{𝐮}_1,\dots ,{𝐮}_n⟩.$$

It is still an important fact that a span passes through the origin $\mathrm{𝟎}=(\mathrm{0,0},\dots ,0)$. This is because linear combinations do not include a constant term, so the point $\mathrm{𝟎}$ can always be achieved by setting $a_i=0$ for all $i$.

Example

Computing a span by hand

Consider the vectors $𝐮=(\mathrm{1,1,0},-\mathrm{1,2})$ and $𝐯=(\mathrm{0,2,3,1},-1)$. Problem: Show that the set of vectors perpendicular to both $𝐮$ and $𝐯$ is a span.

Solution: Let $𝐱=(x_1,\dots ,x_5)$ be an arbitrary vector such that $𝐱\cdot 𝐮=𝐱\cdot 𝐯=0$. By writing these dot products using components, we find a system of two equations:

$$x_1+x_2-x_4+2x_5=0,2x_2+3x_3+x_4-x_5=0.$$

Solve for $x_1$ and $x_3$ in terms of the others:

$$x_1=-x_2+x_4-2x_5,x_3=-\frac{2}{3}{x}_2-\frac{1}{3}{x}_4+\frac{1}{3}{x}_5.$$

Now, we can let $x_2$, $x_4$, and $x_5$ take any value, and using these equations we can specify $x_1$ and $x_3$ to guarantee that the system of equations is valid, implying that $𝐱\cdot 𝐮=𝐱\cdot 𝐯=0$. Conversely, given values of $x_2$, $x_4$, and $x_5$, these equations fully determine the only possible values of $x_1$ and $x_3$. Therefore, the set of possible $𝐱$ is given by varying $x_2$, $x_4$, and $x_5$ in the vector:

$$𝐱=\left(\begin{array}{c}-x_2+x_4-2x_5\\ x_2\\ -\frac{2}{3}{x}_2-\frac{1}{3}{x}_4+\frac{1}{3}{x}_5\\ x_4\\ x_5\end{array}\right).$$

Observe that this vector can be written as the linear combination $x_2{𝐰}_2+x_4{𝐰}_4+x_5{𝐰}_5$, with

$${𝐰}_2=\left(\begin{array}{c}-1\\ 1\\ -2/3\\ 0\\ 0\end{array}\right),{𝐰}_4=\left(\begin{array}{c}1\\ 0\\ -1/3\\ 1\\ 0\end{array}\right),{𝐰}_5=\left(\begin{array}{c}-2\\ 0\\ 1/3\\ 0\\ 1\end{array}\right).$$

So indeed the set of vectors $𝐱$ perpendicular to $𝐮$ and $𝐯$ is the span $⟨{𝐰}_2,{𝐰}_4,{𝐰}_5⟩$.

Convex combinations A convex combination of vectors is a linear combination with a certain constraint on the coefficients:

$$𝐯=c_1{𝐮}_1+c_2{𝐮}_2+\cdots +c_n{𝐮}_n,c_i\in [\mathrm{0,1}],\sum _{i=1}^n{c}_i=1.$$

Subspaces

A subspace is any collection of vectors that satisfies the rules of a vector space, meaning the operations and properties. Since the properties automatically hold for vectors from the original space, the key point is that a subspace is a collection of vectors including the origin, all of whose linear combinations are still in the subspace.

Symbolically: if $W\subset {ℝ}^n$ is any subset of vectors containing $\mathrm{𝟎}$, and if $a{𝐰}_1+b{𝐰}_2\in W$ automatically whenever ${𝐰}_1,{𝐰}_2\in W$, then $W$ is a subspace.

Question 05-01

Subspaces

Suppose a set $W$ satisfies the symbolic hypothesis above:

$${𝐰}_1,{𝐰}_2\in W\text{implies}a{𝐰}_1+b{𝐰}_2\in W,\text{any }a,b.$$

Show that any linear combination of $n$ vectors from $W$ must lie in $W$.

Exercise 05-01

Subspaces given by perpendicularity

Let $W\subset {ℝ}^n$ be defined as the set of vectors which are perpendicular to the given set $\{{𝐯}_1,\dots ,{𝐯}_k\}$. Show that $W$ is a subspace.

To say that $W$ is a subspace is to say that $W$ is a vector space in its own right, even though vectors in $W$ may also live in a bigger space.

Example

Simple subspaces of ${ℝ}^n$

Let $W\subset {ℝ}^n$ be the collection of all possible vectors $𝐰=(w_1,\dots ,w_{n-1},0)$, meaning that the final term is always zero, and the other terms can be anything.

This set is a subspace because it contains $(\mathrm{0,0},\dots ,0)$, and any linear combination $a{𝐰}_1+b{𝐰}_2$ will still have a zero in the final component, so it lies in $W$.

Question 05-02

Iterating from $2$ to $n$

How many distinct subspaces of ${ℝ}^n$ can you describe using the general idea of the previous example?

Spans and subspaces

A span is always a subspace: it contains $\mathrm{𝟎}$, and any linear combination of some vectors in a span can be written as a linear combination of the original vectors defining the span (by expanding each vector in terms of the original vectors, and then collecting like terms).

The converse is also true: any subspace is the span of some vectors. This is not so easy to prove! Here is the proof:

Why every subspace is a span

We consider ${ℝ}^k\subset {ℝ}^n$ by using the first $k$ components, setting the last $n-k$ components to zero. We prove that if we assume every subspace of ${ℝ}^k$ is a span, then every subspace of ${ℝ}^{k+1}$ must also be a span. (The result will follow because it is clearly true for ${ℝ}^1$, and we can use this fact to build up to ${ℝ}^n$ one dimension at a time.)

So we assume that every subspace of ${ℝ}^k$ is a span. Now suppose $W\subset {ℝ}^{k+1}$ is any subspace. Consider the last components of vectors $𝐰\in W$. If all of these last components are zero, then actually $W\subset {ℝ}^k$, and by the assumption, it is a span.

Suppose, on the other hand, that at least one vector ${𝐰}^{\star }\in W$ has a last component $w_{k+1}^{\star }\ne 0$. Now we create the subspace $W^{\prime }\subset {ℝ}^k$ defined as

$$\begin{array}{cc}{W}^{\prime }& =W\cap {ℝ}^k\\ & =\{(w_1,w_2,\dots ,w_{k+1})\in W|w_{k+1}=0\}.\end{array}$$

The collection $W^{\prime }$ is a subspace of ${ℝ}^k$, so it is a span by the assumption, and we can find a generating set of vectors:

$$W^{\prime }=⟨{𝐰}_1,\dots ,{𝐰}_k⟩.$$

Now we propose the following key fact:

$$W=⟨{𝐰}_1,\dots ,{𝐰}_k,{𝐰}^{\star }⟩.$$

To prove this, let $𝐰=(w_1,\dots ,w_{k+1})\in W$ be any vector. If $w_{k+1}=0$, then $𝐰\in W^{\prime }$, so it is in the proposed span above. If $w_{k+1}\ne 0$, then consider the vector $𝐮=𝐰-\frac{w_{k+1}}{w_{k+1}^{\star }}{𝐰}^{\star }$. This vector has zero in the last component. So $𝐮\in W^{\prime }$, which can be expanded as a linear combination of ${𝐰}_1,\dots ,{𝐰}_k$. By vector algebra, $𝐰=𝐮+\frac{w_{k+1}}{w_{k+1}^{\star }}{𝐰}^{\star }$, and we can substitute the expansion of $𝐮$ to see that $𝐰$ is in the proposed span.

The difference between the concept of span and the concept of subspace is a matter of connotation. When working with a ‘span’, we have in mind a collection of vectors that generates the span using linear combinations. When working with a ‘subspace’, we have in mind the abstract rules of vector spaces.

Incidentally, the above proof shows that any subspace of ${ℝ}^n$ can be written as the span of $n$ or fewer vectors.

Dimension

The dimension of a subspace $W\subset {ℝ}^n$, written $\dim W$, is the smallest possible number of vectors needed to span $W$.

This definition is very intuitive: a space has $n$ dimensions if $n$ different numbers are needed to locate every item in the space. These numbers are the coefficients of the spanning vectors in a minimal spanning set for the space.

The definition can also be hard to work with in a rigorous way. How could we prove that a given space could not be spanned by an ever smaller number of vectors?

For example, of course ${ℝ}^n$ should be $n$-dimensional. That is why we have been saying “$n$D.” Of course it is spanned by the $n$ standard basis vectors ${𝐞}_1,\dots ,{𝐞}_n$. But how do we know it cannot be spanned by a smaller number?

In the next section the concept of independence will be developed to handle this question more generally. However, it is worthwhile practice with the general theory of spans to demonstrate this fact by learning about Steinitz Exchange:

Showing ${ℝ}^n$ is $n$-dimensional: Steinitz Exchange Process

Suppose some set $\{{𝐯}_1,\dots ,{𝐯}_k\}$ with only $k$ vectors could span ${ℝ}^n$ with $n>k$, so:

$${ℝ}^n=⟨{𝐯}_1,\dots ,{𝐯}_k⟩.$$

This means that ${𝐞}_1\in ⟨{𝐯}_1,\dots ,{𝐯}_k⟩$. Then it turns out we can “exchange” ${𝐞}_1$ for one of the ${𝐯}_i$:

$${ℝ}^n=⟨{𝐞}_1,{𝐯}_2^{\prime },\dots ,{𝐯}_k^{\prime }⟩,$$

where the notation ${𝐯}_2^{\prime },\dots ,{𝐯}_k^{\prime }$ means some subset of ${𝐯}_1,\dots ,{𝐯}_k$ with only $k-1$ elements, but we don’t care which is which. The reason we can do this is important: since ${𝐞}_1\in ⟨{𝐯}_1,\dots ,{𝐯}_k⟩$, we can write a linear combination

$${𝐞}_1=a_1{𝐯}_1+\cdots +a_k{𝐯}_k$$

with at least one $a_{i^{\star }}\ne 0$. The equation can be solved for ${𝐯}_{i^{\star }}$ using the other vectors in the equation, and therefore every vector in ${ℝ}^n$ can be expressed as a linear combination of those other vectors in the equation. But that is the meaning of “${ℝ}^n=⟨{𝐞}_1,{𝐯}_2^{\prime },\dots ,{𝐯}_k^{\prime }⟩$.”

Now iterate this process: we can exchange ${𝐞}_2$ for another vector out of ${𝐯}_2^{\prime },\dots ,{𝐯}_k^{\prime }$:

$${ℝ}^n=⟨{𝐞}_1,{𝐞}_2,{𝐯}_3^{\prime \prime },\dots ,{𝐯}_k^{\prime \prime }⟩.$$

The reason we can do this is similar, but with a slight twist. As before, write a linear combination:

$${𝐞}_2=a_1{𝐞}_1+a_2{𝐯}_2^{\prime }+\cdots +a_k{𝐯}_k^{\prime }.$$

This time, however, we know that at least one of $a_2,\dots ,a_k$ is nonzero, say $a_{i^{\star }}$, because there is no way to generate ${𝐞}_2$ using combinations of ${𝐞}_1$ alone. So we solve for ${𝐯}_{i^{\star }}^{\prime }$ using the other vectors in the equation. This means we can eliminate ${𝐯}_{i^{\star }}^{\prime }$ from the spanning set, provided we add in ${𝐞}_2$.

Now iterate the process $k$ times, replacing some ${𝐯}_{i^{\star }}$ at each successive stage with a new vector ${𝐞}_j$, observing that the linear combination for ${𝐞}_j$ could not involve nonzeros only on the other ${𝐞}_i$.

After $k$ iterations, we have ${ℝ}^n=⟨{𝐞}_1,\dots ,{𝐞}_k⟩$. This is impossible! Since $k<n$, there is no way to get nonzero entries in components higher than $k$.

Problems due Tuesday 20 Feb 2024 by 11:59pm

Problem 05-01

Spans of column vectors

Matrices $M_1,M_2$ are $n\times n$ matrices, and $k<n$. Matrix $M_1$ has ones everywhere on and above the main diagonal, down to the $k^{\text{th}}$ row, and zeros elsewhere, including everything after the $k^{\text{th}}$ row. Matrix $M_2$ has ones on the main diagonal only, down to the $k^{\text{th}}$ row, and zeros everywhere else. Show that the span of the column vectors of $M_1$ is the same subspace as the span of the column vectors of $M_2$. What subspace is it?

(Hint: first try to verify the assertion for small values of $k$ and $n$, for example when $n=2$ and $k=1$, and then $n=3$ and $k=1$ or $k=2$. Then see if you can generalize your method to all $k<n$.)

Problem 05-02

Computing dimensions by hand

• Show that the span $⟨\left(\begin{array}{c}1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ -1\end{array}\right)⟩$ has dimension $2$ as a subspace by using the “exchange” technique.
• Show that the span $⟨\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 2\\ 2\end{array}\right)⟩$ has dimension $3$ as a subspace by using the “exchange” technique.
• Show that the span $⟨\left(\begin{array}{c}1\\ -2\\ 3\end{array}\right),\left(\begin{array}{c}4\\ 0\\ 2\end{array}\right),\left(\begin{array}{c}3\\ -2\\ 4\end{array}\right)⟩$ has dimension $2$ as a subspace.

Problem 05-03

Suppose we are given a collection of data points $(x_1,y_1),\dots ,(x_n,y_n)$. Later in the course, we will learn how to compute the linear regression of this data, namely the line of best fit. In this problem, you will learn about the correlation coefficient of the data: a measure of how linear the data is. There is no point in computing a linear regression if the data is not very linear!

First, let $𝐱=(x_1,x_2,\dots ,x_n)$ and $𝐲=(y_1,y_2,\dots ,y_n)$. Then let $\overline{x}$ be the average of the $x_i$, and $\overline{y}$ be the average of the $y_i$. Therefore $𝐱-\overline{x}$ and $𝐲-\overline{y}$ have zero average. (By subtracting a scalar from a vector, we really mean to subtract the scalar from each component.) Then define the correlation coefficient:

$$\rho (𝐱,𝐲)=\frac{(𝐱-\overline{x})\cdot (𝐲-\overline{y})}{|𝐱-\overline{x}||𝐲-\overline{y}|}.$$

Correlation coefficient

Problem: Compute the correlation coefficient of the data:

$$(-\mathrm{3,4}),(1,-1),(0,-1),(4,-3),(-\mathrm{2,1}).$$

The correlation coefficient $\rho (𝐱,𝐲)$ is frequently written ‘$r$’. The formula describes $r$ as a dot product of unit vectors, so $-1\le r\le +1$. When $r=\pm 1$, the data are very linear. When $r=+1$, the data lie on a line with positive slope, meaning that if you increase $x$ then you expect $y$ to increase as well. When $r=-1$, the data lie on a line with negative slope, so if you increase $x$ then you expect $y$ to decrease.

In a future Packet we will see why $r=\rho (𝐱,𝐲)$ measures linearity. For now, consider the following. Suppose the data is linear, so $y_i=m{x}_i+b$ for some $m$ and $b$. Then as vectors, we have $𝐲=m𝐱+b$. If we subtract the average of both sides, we have

$$\begin{array}{cc}𝐲-\overline{y}& =m𝐱+b-\overline{m𝐱+b}\\ & =m(𝐱-\overline{x})+b-\overline{b}\\ & =m(𝐱-\overline{x}).\end{array}$$

Therefore $𝐲-\overline{y}$ is a scalar multiple of $𝐱-\overline{x}$, and the dot product of their unit vectors tells us whether they align or anti-align.

This problem (and its sequel) illustrates the use of $n$D vectors to study data that is presented as $2$D vectors.