Chapter 03 - Generators, Independence and Orthogonality

Vectors I: Generators

Basics of nD vectors

Basics of nD vectors

Vectors in ${\mathbb{R}}^n$ have $n$ real number components:

$$\mathbf{v}=(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 ${\mathbb{R}}^n$:

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

There are $n$ standard basis vectors:

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

Decomposition works as in $3$D:

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

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

$$\begin{array}{rl}\mathbf{u}\cdot \mathbf{v}& =(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 $|\mathbf{u}|=\sqrt{\mathbf{u}\cdot \mathbf{u}}$.

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, $\mathbf{u}\cdot \mathbf{v}=|\mathbf{u}||\mathbf{v}|\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:

$${\mathbf{u}}_{||}={\mathrm{proj}}_{\mathbf{v}}(\mathbf{u})=(\mathbf{u}\cdot {\mathbf{e}}_{\mathbf{v}}){\mathbf{e}}_{\mathbf{v}}=\left(\frac{\mathbf{u}\cdot \mathbf{v}}{\mathbf{v}\cdot \mathbf{v}}\right)\mathbf{v}.$$

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

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

$$|\mathbf{u}\cdot \mathbf{v}|\le |\mathbf{u}||\mathbf{v}|,|\mathbf{u}+\mathbf{v}|\le |\mathbf{u}|+|\mathbf{v}|.$$

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

$$(\mathbf{r}-{\mathbf{r}}_0)\cdot \mathbf{n}=0$$

determines a hyperplane in $n$D, meaning an $(n-1)$D space inside of ${\mathbb{R}}^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:

$$\mathbf{n}=(k_1,\dots ,k_n),{\mathbf{r}}_0=(a_1,\dots ,a_n),\mathbf{r}=(x_1,\dots ,x_n).$$ Link to original

Spans

Spans

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

$$\mathbf{v}=a_1{\mathbf{u}}_1+a_2{\mathbf{u}}_2+\cdots +a_n{\mathbf{u}}_n,a_i\in \mathbb{R}.$$

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 $\mathbf{v}$ that can be written as above, for any $a_i$, in terms of the ${\mathbf{u}}_i$ given at the outset, is called either of:

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

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

Link to original

Example

Computing a span by hand

Computing a span by hand

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

Solution: Let $\mathbf{x}=(x_1,\dots ,x_5)$ be an arbitrary vector such that $\mathbf{x}\cdot \mathbf{u}=\mathbf{x}\cdot \mathbf{v}=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 $\mathbf{x}\cdot \mathbf{u}=\mathbf{x}\cdot \mathbf{v}=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 $\mathbf{x}$ is given by varying $x_2$, $x_4$, and $x_5$ in the vector:

$$\mathbf{x}=\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{\mathbf{w}}_2+x_4{\mathbf{w}}_4+x_5{\mathbf{w}}_5$, with

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

So indeed the set of vectors $\mathbf{x}$ perpendicular to $\mathbf{u}$ and $\mathbf{v}$ is the span $⟨{\mathbf{w}}_2,{\mathbf{w}}_4,{\mathbf{w}}_5⟩$.

Link to original

Spans (part 2)

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

$$\mathbf{v}=c_1{\mathbf{u}}_1+c_2{\mathbf{u}}_2+\cdots +c_n{\mathbf{u}}_n,c_i\in [0,1],\sum _{i=1}^n{c}_i=1.$$ Link to original

Subspaces

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 {\mathbb{R}}^n$ is any subset of vectors containing $0$, and if $a{\mathbf{w}}_1+b{\mathbf{w}}_2\in W$ automatically whenever ${\mathbf{w}}_1,{\mathbf{w}}_2\in W$, then $W$ is a subspace.

Link to original

Question

01

Subspaces

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

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

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

Link to original

Exercise

01

Subspaces given by perpendicularity

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

Link to original

Subspaces (part 2)

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.

Link to original

Example

Simple subspaces of n-dimensional space

Simple subspaces of ${\mathbb{R}}^n$

Let $W\subset {\mathbb{R}}^n$ be the collection of all possible vectors $\mathbf{w}=(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 $(0,0,\dots ,0)$, and any linear combination $a{\mathbf{w}}_1+b{\mathbf{w}}_2$ will still have a zero in the final component, so it lies in $W$.

Link to original

Question

02

Iterating from $2$ to $n$

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

Link to original

Spans and subspaces

Spans and subspaces

A span is always a subspace: it contains $0$, 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 ${\mathbb{R}}^k\subset {\mathbb{R}}^n$ by using the first $k$ components, setting the last $n-k$ components to zero. We prove that if we assume every subspace of ${\mathbb{R}}^k$ is a span, then every subspace of ${\mathbb{R}}^{k+1}$ must also be a span. (The result will follow because it is clearly true for ${\mathbb{R}}^1$, and we can use this fact to build up to ${\mathbb{R}}^n$ one dimension at a time.)

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

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

$$\begin{array}{rl}{W}^{\prime }& =W\cap {\mathbb{R}}^k\\ & =\{(w_1,w_2,\dots ,w_{k+1})\in W\mid w_{k+1}=0\}.\end{array}$$

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

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

Now we propose the following key fact:

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

To prove this, let $\mathbf{w}=(w_1,\dots ,w_{k+1})\in W$ be any vector. If $w_{k+1}=0$, then $\mathbf{w}\in W^{\prime }$, so it is in the proposed span above. If $w_{k+1}\ne 0$, then consider the vector $\mathbf{u}=\mathbf{w}-\frac{w_{k+1}}{w_{k+1}^{\star }}{\mathbf{w}}^{\star }$. This vector has zero in the last component. So $\mathbf{u}\in W^{\prime }$, which can be expanded as a linear combination of ${\mathbf{w}}_1,\dots ,{\mathbf{w}}_k$. By vector algebra, $\mathbf{w}=\mathbf{u}+\frac{w_{k+1}}{w_{k+1}^{\star }}{\mathbf{w}}^{\star }$, and we can substitute the expansion of $\mathbf{u}$ to see that $\mathbf{w}$ 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 ${\mathbb{R}}^n$ can be written as the span of $n$ or fewer vectors.

Link to original

Dimension

Dimension

The dimension of a subspace $W\subset {\mathbb{R}}^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 ${\mathbb{R}}^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 ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_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 ${\mathbb{R}}^n$ is $n$-dimensional: Steinitz Exchange Process

Suppose some set $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ with only $k$ vectors could span ${\mathbb{R}}^n$ with $n>k$, so:

$${\mathbb{R}}^n=⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k⟩.$$

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

$${\mathbb{R}}^n=⟨{\mathbf{e}}_1,{\mathbf{v}}_2^{\prime },\dots ,{\mathbf{v}}_k^{\prime }⟩,$$

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

$${\mathbf{e}}_1=a_1{\mathbf{v}}_1+\cdots +a_k{\mathbf{v}}_k$$

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

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

$${\mathbb{R}}^n=⟨{\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{v}}_3^{\prime \prime },\dots ,{\mathbf{v}}_k^{\prime \prime }⟩.$$

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

$${\mathbf{e}}_2=a_1{\mathbf{e}}_1+a_2{\mathbf{v}}_2^{\prime }+\cdots +a_k{\mathbf{v}}_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 ${\mathbf{e}}_2$ using combinations of ${\mathbf{e}}_1$ alone. So we solve for ${\mathbf{v}}_{i^{\star }}^{\prime }$ using the other vectors in the equation. This means we can eliminate ${\mathbf{v}}_{i^{\star }}^{\prime }$ from the spanning set, provided we add in ${\mathbf{e}}_2$.

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

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

Link to original

Vectors II: Independence

Independence

Independence

A collection of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ is called independent when the only solution to the equation

$$x_1{\mathbf{v}}_1+x_2{\mathbf{v}}_2+\cdots +x_k{\mathbf{v}}_k=0$$

is given by setting $x_i=0$ for every $i$.

Link to original

Question

01

Independence vs. dependency equations

Prove the statement:

The collection $\mathcal{V}$ is dependent (i.e. not independent) if and only if at least one of the vectors can be written as a linear combination of the others, i.e. one of them is in the span of the others.

Link to original

Example

Dependent columns implies non-invertible

Dependent columns implies non-invertible

If a square matrix $A$ has column vectors ${\mathbf{a}}_i$ which form a dependent set, then the square matrix is not invertible.

Proof: Let $x_i$ be numbers giving the dependency relation. These numbers can be combined into a vector $\mathbf{x}=(x_1,\dots ,x_n)$. Then:

$$\begin{array}{rl}A\mathbf{x}& =A(x_1{\mathbf{e}}_1+\cdots +x_n{\mathbf{e}}_n)\\ & =A(x_1{\mathbf{e}}_1)+\cdots +A(x_n{\mathbf{e}}_n)\\ & =x_1(A{\mathbf{e}}_1)+\cdots +x_n(A{\mathbf{e}}_n)\\ & =x_1{\mathbf{a}}_1+\cdots +x_n{\mathbf{a}}_n\\ & =0.\end{array}$$

However, since the $x_i$ are not all zero, we know $\mathbf{x}\ne 0$, and therefore $A$ sends something nonzero to zero, which means it cannot be invertible. (Otherwise, what would be the preimage of zero?)

Link to original

Independence (part 2)

Independence and dimension
Recall that the dimension of a subspace is equal to the smallest number of vectors needed to span the subspace.

If a set of vectors has the smallest number that spans whatever they span, then this set is independent. (If there is any dependency relation, then a smaller set will have the same span: just eliminate the dependent vector.)

Conversely, if some vectors are independent, then they are automatically the smallest number that spans their span:

Theorem: Independent vectors span their span minimally

Let $V=⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k⟩\subset {\mathbb{R}}^n$ be the subspace spanned by the set of vectors $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$, and suppose the set $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ is independent. Then any set of vectors spanning $V$ must have at least $k$ elements.

Proof

We use Steinitz Exchange but with ${\mathbf{v}}_i$ in place of ${\mathbf{e}}_i$. Suppose $V=⟨{\mathbf{u}}_1,\dots ,{\mathbf{u}}_r⟩$ for $r$ other vectors ${\mathbf{u}}_j$. Our goal is to show that $r\ge k$.

First, since ${\mathbf{v}}_1\in V$, we know there is a linear combination

$${\mathbf{v}}_1=a_1{\mathbf{u}}_1+\cdots +a_r{\mathbf{u}}_r$$

with at least one coefficient $a_{i^{\star }}\ne 0$. Solve for ${\mathbf{u}}_{i^{\star }}$ in terms of the others in this equation to obtain the fact that $V=⟨{\mathbf{v}}_1,{\mathbf{u}}_2^{\prime },\dots ,{\mathbf{u}}_r^{\prime }⟩$, where we introduce the labels ${\mathbf{u}}_j^{\prime }$ with $j=2,\dots ,r$ for whichever vectors are left from $\left\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_r\right\}$ after removing ${\mathbf{u}}_{i^{\star }}$.

By iterating this process, we obtain

$$⟨{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k,{\mathbf{u}}_{k+1}^{(k-1)},\dots ,{\mathbf{u}}_{r-k}^{(k-1)}⟩,$$

and this is only possible if $r\ge k$.

(Notation: here ${\mathbf{u}}_j^{(p)}$ stands for ${\mathbf{u}}_j^{\prime \prime }{}^{\dots }{}^{\prime }$ with $p$ ticks, just as for higher derivatives.)

We are able to iterate the process because the vectors ${\mathbf{v}}_i$ are independent: at each stage, the next ${\mathbf{v}}_{i+1}$ can be written as a linear combination of the previous ${\mathbf{v}}_j$ ($j<i$) and some other ${\mathbf{u}}_j$. But the coefficient on at least one of the ${\mathbf{u}}_j$ must be nonzero, otherwise we have written ${\mathbf{v}}_i$ in terms of ${\mathbf{v}}_j$ alone, and that is impossible by independence.

Link to original

Exercise

01

Understanding independence

Explain in more detail why we can iterate the process because the ${\mathbf{v}}_j$ are independent. Specifically compare the reason it works here with the reason it worked for the ${\mathbf{e}}_j$ in the Steinitz Exchange at the end of the section on dimension.

Link to original

Question

02

Completing the logic

Explain in more detail the statement: “and this is only possible if $r\ge k$.” Why is this statement true? What would happen if $r<k$?

Link to original

Example

Independence

Independence

Problem: Is the following set of vectors dependent or independent?

$$\left(\begin{array}{c}3\\ -1\\ 2\end{array}\right),\left(\begin{array}{c}0\\ 2\\ -1\end{array}\right),\left(\begin{array}{c}2\\ -4\\ 3\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)$$

Solution: It must be a dependent set. These vectors live in ${\mathbb{R}}^3$, which is spanned by ${\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3$. If these vectors were independent, then we could use Steinitz Exchange to write ${\mathbb{R}}^3=⟨{\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3⟩$ as the span of just three of them. Since the fourth is also in ${\mathbb{R}}^3$, it could then be written as a combination of the other three, contradicting independence.

Link to original

Basis

Basis

A basis for $V\subset {\mathbb{R}}^n$ is a set of independent vectors which span the entire subspace $V$.

For example, the standard basis $\{{\mathbf{e}}_1,\dots ,{\mathbf{e}}_n\}$ is a basis for the whole space ${\mathbb{R}}^n$.

The criterion of independence is a function of the relationships between the vectors in the set. The criterion of spanning also depends upon what other vectors there may be in the subspace.

(Independence is an intrinsic concept, whereas spanning the subspace is an extrinsic concept. These are not precise mathematical terms.)

Any set of vectors spans a certain subspace, namely the span itself. Therefore any independent set of vectors is a basis for its own span.

Because an independent set of vectors is always the minimal number needed to span its span (the theorem above), and a basis for a given space is an independent set of vectors spanning the subspace, every basis for a given subspace has the same number of vectors. (Since every basis has the minimal number needed to span the given subspace.) This number as the dimension of the subspace.

The most important way to think about and use the concept of basis is this: Given a basis $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ for a subspace $V\subset {\mathbb{R}}^n$, every vector $\mathbf{w}$ in $V$ can be obtained uniquely as a linear combination of basis vectors:

$$\mathbf{w}=x_1{\mathbf{v}}_1+\cdots +x_k{\mathbf{v}}_k.$$

(Here ‘unique’ means that the coefficients $x_i$ are uniquely determined by $\mathbf{w}$.)

From this way of thinking about a basis, we see that the dimension $k$ is the number of quantities $x_i$ that are needed to describe everything in the space without redundancy.

Link to original

Example

3 vectors spanning 3D space must be independent

3 vectors spanning 3D space must be independent

In Problem 05-02, we saw 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)⟩$$

is a 3-dimensional subspace of ${\mathbb{R}}^3$. (In fact it is ${\mathbb{R}}^3$, since the Steinitz Exchange will put all three ${\mathbf{e}}_i$ in the same span as this.) Therefore we know the vectors are independent, because there are three vectors spanning a 3D space.

Link to original

Basis (part 2)

Orthonormal systems, orthonormal bases
A collection of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ is called an orthonormal system when they are:

• unit vectors, meaning $|{\mathbf{v}}_i|=1$ for all $i$
• pairwise orthogonal, meaning ${\mathbf{v}}_i\cdot {\mathbf{v}}_j=0$ when $i\ne j$

If the collection is also a basis, then it is called an orthonormal basis.

Vector components in a given basis
The typical application of a basis is to write other vectors as its linear combinations. Since a basis spans the whole space, every other vector in the space can be written using some set of coefficients. Since a basis is linearly independent, there is a unique set of coefficients that will generate a given vector.

For example, if $\mathcal{B}=\{{\mathbf{b}}_1,\dots ,{\mathbf{b}}_k\}$ is a basis of a subspace $V\subset {\mathbb{R}}^n$, which incidentally therefore has dimension $k$, then we can write any $\mathbf{v}\in V$ by:

$$\mathbf{v}=x_1{\mathbf{b}}_1+x_2{\mathbf{b}}_2+\cdots +x_k{\mathbf{b}}_k.$$

Using such linear combinations to express vectors $\mathbf{v}$, we find a unique association between a vector $\mathbf{v}$ and the quantities $x_1,\dots ,x_k$ which express that vector in terms of the ${\mathbf{b}}_i$. We can group those quantities into a list $(x_1,\dots ,x_k)$. The terms are called the components of $\mathbf{v}$ in the basis $\mathcal{B}$.

The ordinary component entries of a vector are actually just the components of the vector in the standard basis. (Think about this!)

Link to original

Vectors III: Orthogonality

Introduction

Subspaces of ${\mathbb{R}}^n$ are extremely important. For example, if $n$ represents the number of pixels in an image, a vector $\mathbf{v}\in {\mathbb{R}}^n$ might represent an image. The number $n$ is very large, and even computers can take a (relatively) long time to perform operations on vectors in ${\mathbb{R}}^n$ such as multiplying $n\times n$ matrices to compose linear transformations.

Frequently a given dataset will belong (or ‘nearly’ belong) to a subspace of ${\mathbb{R}}^n$ of much smaller dimension. It is very useful to be able to describe and work with vectors in such a subspace in an efficient way. This typically means finding a good basis. A good basis should be easy to work with, and it should have a useful interpretation.

Link to original

Orthogonal bases

Orthogonal bases

An orthogonal basis $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ is simply a basis in which the vectors are pairwise perpendicular, meaning ${\mathbf{u}}_i\cdot {\mathbf{u}}_j=0$ for $i\ne j$. It is very easy to tell if a basis is orthogonal: just compute all pairwise dot products. This is a central reason that orthogonal bases are very popular.

If a basis is orthogonal, there is a very fast way to find the components of any given vector in this basis. Suppose $\mathbf{v}\in U\subset {\mathbb{R}}^n$, meaning $\mathbf{v}$ is a vector in the subspace $U$ of ${\mathbb{R}}^n$. Suppose that $U$ is $k$-dimensional with orthogonal basis $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$. The components of $\mathbf{v}$ in this basis are by definition the unique coefficients $c_1,\dots ,c_k$ in the linear combination:

$$\mathbf{v}=c_1{\mathbf{u}}_1+\cdots +c_k{\mathbf{u}}_k.$$

Now, take the dot product of both sides with ${\mathbf{u}}_i$, for any given $i$, using the fact that ${\mathbf{u}}_i\cdot {\mathbf{u}}_j=0$ unless $j=i$:

$$\begin{array}{rl}{\mathbf{u}}_i\cdot \mathbf{v}& =c_1({\mathbf{u}}_i\cdot {\mathbf{u}}_1)+\cdots +c_k({\mathbf{u}}_i\cdot {\mathbf{u}}_k)\\ & =0+\cdots +0+c_i({\mathbf{u}}_i\cdot {\mathbf{u}}_i)+0+\cdots +0,\end{array}$$

so

$$c_i=\frac{{\mathbf{u}}_i\cdot \mathbf{v}}{{\mathbf{u}}_i\cdot {\mathbf{u}}_i}.$$

Summarizing:

Finding components in an orthogonal basis

Given $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ an orthogonal basis, the components of $\mathbf{v}=c_1{\mathbf{u}}_1+\cdots +c_k{\mathbf{u}}_k$ are given by the formulas:

$$c_1=\frac{{\mathbf{u}}_1\cdot \mathbf{v}}{{\mathbf{u}}_1\cdot {\mathbf{u}}_1},c_2=\frac{{\mathbf{u}}_2\cdot \mathbf{v}}{{\mathbf{u}}_2\cdot {\mathbf{u}}_2},\dots c_k=\frac{{\mathbf{u}}_k\cdot \mathbf{v}}{{\mathbf{u}}_k\cdot {\mathbf{u}}_k}.$$

If $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ is not only orthogonal but also orthonormal, then the components are even simpler:

$$c_1={\mathbf{u}}_1\cdot \mathbf{v},c_2={\mathbf{u}}_2\cdot \mathbf{v},\dots c_k={\mathbf{u}}_k\cdot \mathbf{v}.$$

The fact that components are so easy to calculate for orthogonal bases is one of their most important features, and frequently is the main reason they are used.

Link to original

Question

01

Orthogonal vectors, finding components

Show that the set of vectors is orthogonal:

$${\mathbf{u}}_1=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),{\mathbf{u}}_2=\left(\begin{array}{c}-1\\ 1\\ 2\end{array}\right),{\mathbf{u}}_3=\left(\begin{array}{c}2\\ -2\\ 2\end{array}\right),$$

and then compute the components of $\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)$ in the basis $\{{\mathbf{u}}_1,{\mathbf{u}}_2,{\mathbf{u}}_3\}$.

Link to original

Orthogonal bases (part 2)

The above method can be written out succinctly in what is sometimes called the Fourier expansion formula:

$$\mathbf{v}=\sum _{i=1}^k\left(\frac{{\mathbf{u}}_i\cdot \mathbf{v}}{{\mathbf{u}}_i\cdot {\mathbf{u}}_i}\right){\mathbf{u}}_i.$$

A simple observation shows another advantage of orthogonal sets of vectors – that they are automatically independent:

Orthogonal vectors are automatically independent

Suppose that $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ is an orthogonal set.

Assume hypothetically that $x_1{\mathbf{u}}_1+\cdots +x_k{\mathbf{u}}_k=0$.

By dotting both sides with any ${\mathbf{u}}_i$, we see that $x_i({\mathbf{u}}_i\cdot {\mathbf{u}}_i)=0$, so we must have $x_i=0$ (because ${\mathbf{u}}_i\cdot {\mathbf{u}}_i\ne 0$ since we assume ${\mathbf{u}}_i\ne 0$). This can be done for any $i$, so in fact $x_i=0$ for all $i$.

Therefore $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ is an independent set of vectors.

Link to original

Projection

Projection

Projection and orthogonal bases
Recall the projection formula:

$${\mathrm{proj}}_{{\mathbf{u}}_i}(\mathbf{v})=\left(\frac{\mathbf{v}\cdot {\mathbf{u}}_i}{{\mathbf{u}}_i\cdot {\mathbf{u}}_i}\right){\mathbf{u}}_i.$$

So $c_i$ is just the scalar coefficient of the projection of $\mathbf{v}$ onto ${\mathbf{u}}_i$ (sometimes called the ‘scalar projection’).

Using this fact, we could equally write a vector as a decomposition according to an orthogonal basis using a sum of projections to the basis elements:

$$\mathbf{v}={\mathrm{proj}}_{{\mathbf{u}}_1}(\mathbf{v})+\cdots +{\mathrm{proj}}_{{\mathbf{u}}_k}(\mathbf{v}).$$

Projection to a subspace
The projection formula for ${\mathrm{proj}}_{\mathbf{u}}(\mathbf{v})$ provides the closest vector to $\mathbf{v}$ that is on the line spanned by $\mathbf{u}$, and the difference $\mathbf{v}-{\mathrm{proj}}_{\mathbf{u}}(\mathbf{v})$ is perpendicular to $\mathbf{u}$. Furthermore, ${\mathrm{proj}}_{\mathbf{u}}(\mathbf{v})$ does not depend on the length of $\mathbf{u}$ at all, in fact it only depends on the subspace spanned by $\mathbf{u}$, which is a line. Therefore, ${\mathrm{proj}}_{\mathbf{u}}$ could really be called ${\mathrm{proj}}_L$ where $L=⟨\mathbf{u}⟩$ is the subspace spanned by $\mathbf{u}$.

It is extremely useful to be able to compute the projection of a vector $\mathbf{v}$ onto any subspace $U\subset {\mathbb{R}}^n$. This result should be the unique vector $\mathbf{w}$ inside $U$ which is closest to $\mathbf{v}$. It is also the unique vector $\mathbf{w}$ such that the displacement $\mathbf{v}-\mathbf{w}$ is perpendicular to $U$ (meaning: perpendicular to every vector in $U$).

Now suppose that we have an orthogonal basis ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_k$ of $U$. We can define the projection of $\mathbf{v}\in {\mathbb{R}}^n$ onto the subspace $U$ in terms of this basis:

Projection of $\mathbf{v}$ to a subspace $U\subset {\mathbb{R}}^n$

$${\mathrm{proj}}_U(\mathbf{v})={\mathrm{proj}}_{{\mathbf{u}}_1}(\mathbf{v})+\cdots +{\mathrm{proj}}_{{\mathbf{u}}_k}(\mathbf{v}).$$

• Notice that ${\mathrm{proj}}_U(\mathbf{v})$ is a linear combination of basis vectors. (Consider the separate formulas for ${\mathrm{proj}}_{{\mathbf{u}}_i}(\mathbf{v})$.) Therefore it lies inside the subspace $U$. We might have ${\mathrm{proj}}_U(\mathbf{v})\ne \mathbf{v}$ though, because here we do not assume that $\mathbf{v}\in U$.

• In addition, using this formula we can deduce that the displacement vector $\mathbf{x}=\mathbf{v}-{\mathrm{proj}}_U(\mathbf{v})$ is perpendicular to every vector in $U$: Consider the dot product against any basis vector ${\mathbf{u}}_i$:

  $$\begin{array}{rl}{\mathbf{u}}_i\cdot \mathbf{x}& ={\mathbf{u}}_i\cdot \mathbf{v}-{\mathbf{u}}_i\cdot {\mathrm{proj}}_U(\mathbf{v})\\ & ={\mathbf{u}}_i\cdot \mathbf{v}-\left({\mathbf{u}}_i\cdot \left(\frac{\mathbf{v}\cdot {\mathbf{u}}_1}{{\mathbf{u}}_1\cdot {\mathbf{u}}_1}\right){\mathbf{u}}_1+\cdots +{\mathbf{u}}_i\cdot \left(\frac{\mathbf{v}\cdot {\mathbf{u}}_k}{{\mathbf{u}}_k\cdot {\mathbf{u}}_k}\right){\mathbf{u}}_k\right)\\ & ={\mathbf{u}}_i\cdot \mathbf{v}-\left(\left(\frac{\mathbf{v}\cdot {\mathbf{u}}_1}{{\mathbf{u}}_1\cdot {\mathbf{u}}_1}\right)({\mathbf{u}}_i\cdot {\mathbf{u}}_1)+\cdots +\left(\frac{\mathbf{v}\cdot {\mathbf{u}}_k}{{\mathbf{u}}_k\cdot {\mathbf{u}}_k}\right)({\mathbf{u}}_i\cdot {\mathbf{u}}_k)\right)\\ & ={\mathbf{u}}_i\cdot \mathbf{v}-\left(0+\cdots +0+\left(\frac{\mathbf{v}\cdot {\mathbf{u}}_i}{{\mathbf{u}}_i\cdot {\mathbf{u}}_i}\right)({\mathbf{u}}_i\cdot {\mathbf{u}}_i)+0+\cdots +0\right)\\ & ={\mathbf{u}}_i\cdot \mathbf{v}-\frac{\mathbf{v}\cdot {\mathbf{u}}_i}{({\mathbf{u}}_i\cdot {\mathbf{u}}_i)}({\mathbf{u}}_i\cdot {\mathbf{u}}_i)\\ & ={\mathbf{u}}_i\cdot \mathbf{v}-\mathbf{v}\cdot {\mathbf{u}}_i=0.\end{array}$$

  So ${\mathbf{u}}_i\cdot \mathbf{x}=0$ for all $i$. Any element of $U$ can be written as a linear combination of the basis vectors ${\mathbf{u}}_i$, so $\mathbf{x}$ is perpendicular to any vector in $U$.

Link to original

Question

02

Perpendicularity to a subspace

Explain and justify in more detail the last statement: “${\mathbf{u}}_i\cdot \mathbf{x}=0$ for all $i$” implies “$\mathbf{u}\cdot \mathbf{x}=0$ for all $\mathbf{u}\in U$.”

Link to original

Projection (part 2)

To summarize, orthogonal bases allow us to:

• Easily calculate the components of any vector in the orthogonal basis
• Formulate the projection of any vector onto a subspace using an orthogonal basis of the subspace

Link to original

Gram-Schmidt process

Gram-Schmidt process

In this section, we learn a procedure to create an orthogonal basis of a given subspace, starting only with some vectors that are known to generate the subspace as their span. If the original vectors are not independent, we will discover that fact along the way, and possibly wind up with a smaller number of vectors.

Let us illustrate the process with a span of three vectors $V=⟨{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3⟩\subset {\mathbb{R}}^n$. We do not assume they are independent.

• Write ${\mathbf{w}}_1={\mathbf{v}}_1$.
• Exchange ${\mathbf{v}}_2$ for ${\mathbf{w}}_2={\mathbf{v}}_2-{\mathrm{proj}}_{{\mathbf{w}}_1}({\mathbf{v}}_2)$. Since ${\mathbf{w}}_2$ is a linear combination of ${\mathbf{w}}_1$ and ${\mathbf{v}}_2$, and ${\mathbf{v}}_2$ is a linear combination of ${\mathbf{w}}_1$ and ${\mathbf{w}}_2$, we know $⟨{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3⟩=⟨{\mathbf{w}}_1,{\mathbf{w}}_2,{\mathbf{v}}_3⟩$. Furthermore, ${\mathbf{w}}_1$ and ${\mathbf{w}}_2$ are orthogonal.
• Now exchange ${\mathbf{v}}_3$ for ${\mathbf{w}}_3={\mathbf{v}}_3-{\mathrm{proj}}_{V_2}({\mathbf{v}}_3)$, where $V_2=⟨{\mathbf{w}}_1,{\mathbf{w}}_2⟩$. Since ${\mathbf{w}}_3$ is a linear combination of ${\mathbf{v}}_3$ and items in $V_2$, we know $⟨{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3⟩=⟨{\mathbf{w}}_1,{\mathbf{w}}_2,{\mathbf{w}}_3⟩$, and ${\mathbf{w}}_3$ is orthogonal to everything in $V_2$.

We conclude with $V=⟨{\mathbf{w}}_1,{\mathbf{w}}_2,{\mathbf{w}}_3⟩$, where the ${\mathbf{w}}_i\cdot {\mathbf{w}}_j=0$ unless $i=j$. So these vectors are orthogonal.

Link to original

Question

03

Dependence?

What happens in the above Gram-Schmidt process if $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ is a dependent set?

Link to original

Example

Gram-Schmidt illustration for 3 vectors

Gram-Schmidt illustration for 3 vectors

Problem: Use the Gram-Schmidt process to find an orthogonal basis for the following span:

$${\mathbf{v}}_1=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right),{\mathbf{v}}_2=\left(\begin{array}{c}0\\ 1\\ 1\\ 0\end{array}\right),{\mathbf{v}}_3=\left(\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right).$$

Solution: We first define ${\mathbf{w}}_1={\mathbf{v}}_1$. Then compute ${\mathrm{proj}}_{{\mathbf{w}}_1}({\mathbf{v}}_2)$:

$${\mathrm{proj}}_{{\mathbf{w}}_1}({\mathbf{v}}_2)=\frac{{\mathbf{v}}_2\cdot {\mathbf{w}}_1}{{\mathbf{w}}_1\cdot {\mathbf{w}}_1}{\mathbf{w}}_1=\frac{1}{2}{\mathbf{w}}_1,$$

and therefore ${\mathbf{w}}_2={\mathbf{v}}_2-\frac{1}{2}{\mathbf{w}}_1=\left(\begin{array}{c}-1/2\\ 1/2\\ 1\\ 0\end{array}\right)$. At this point we have $⟨{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3⟩=⟨{\mathbf{w}}_1,{\mathbf{w}}_2,{\mathbf{v}}_3⟩$. Since we are just trying to preserve the span, it is convenient to change the definition of ${\mathbf{w}}_2$ to $\left(\begin{array}{c}-1\\ 1\\ 2\\ 0\end{array}\right)$ by multiplying it by $2$. This won’t change the span, and we eliminate the fractions.

Finally compute ${\mathrm{proj}}_{V_2}({\mathbf{v}}_3)$. Since $V_2=⟨{\mathbf{w}}_1,{\mathbf{w}}_2⟩$, and this is actually an orthogonal basis for $V_2$, we can use the formula for $\mathrm{proj}$ that splits it into components according to the orthogonal basis:

$$\begin{array}{rl}{\mathrm{proj}}_{V_2}({\mathbf{v}}_3)& ={\mathrm{proj}}_{{\mathbf{w}}_1}({\mathbf{v}}_3)+{\mathrm{proj}}_{{\mathbf{w}}_2}({\mathbf{v}}_3)\\ & =\frac{{\mathbf{v}}_3\cdot {\mathbf{w}}_1}{{\mathbf{w}}_1\cdot {\mathbf{w}}_1}{\mathbf{w}}_1+\frac{{\mathbf{v}}_3\cdot {\mathbf{w}}_2}{{\mathbf{w}}_2\cdot {\mathbf{w}}_2}{\mathbf{w}}_2\\ & =\frac{1}{2}{\mathbf{w}}_1+\frac{1}{6}{\mathbf{w}}_2=\left(\begin{array}{c}1/3\\ 2/3\\ 1/3\\ 0\end{array}\right).\end{array}$$

Therefore ${\mathbf{w}}_3=\left(\begin{array}{c}2/3\\ -2/3\\ 2/3\\ 1\end{array}\right)$, and we can scale this up as with ${\mathbf{w}}_2$ and use instead $\left(\begin{array}{c}2\\ -2\\ 2\\ 3\end{array}\right)$. So we have an orthogonal basis:

$$⟨\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}-1\\ 1\\ 2\\ 0\end{array}\right),\left(\begin{array}{c}2\\ -2\\ 2\\ 3\end{array}\right)⟩.$$

Link to original

Exercise

01

Gram-Schmidt practice

Perform Gram-Schmidt to find an orthogonal basis of the subspace:

$$⟨\left(\begin{array}{c}2\\ 0\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}2\\ 2\\ 3\\ 2\end{array}\right)⟩.$$

Link to original

Gram-Schmidt process (part 2)

General Gram-Schmidt process

The Gram-Schmidt process can be continued in the same way for more than three vectors. Here is the general rule, in the abstract, for ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$:

• Set ${\mathbf{w}}_1={\mathbf{v}}_1$.
• Write $V_j=⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_j⟩$.
• Set ${\mathbf{w}}_{j+1}={\mathbf{v}}_{j+1}-{\mathrm{proj}}_{V_j}({\mathbf{v}}_{j+1})$.
  • First step: use $j=1,j+1=2$.
  • We know that $⟨{\mathbf{w}}_1,\dots ,{\mathbf{w}}_j⟩=⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_j⟩$ by considering each formula ${\mathbf{v}}_{j+1}-{\mathrm{proj}}_{V_j}({\mathbf{v}}_{j+1})$.
  • We know that ${\mathbf{w}}_i\cdot {\mathbf{w}}_j=0$ when $i\ne j$ (orthogonality of the ${\mathbf{w}}_i$ we are building).
  • Therefore we compute using: ${\mathrm{proj}}_{V_j}({\mathbf{v}}_{j+1})={\mathrm{proj}}_{{\mathbf{w}}_1}({\mathbf{v}}_{j+1})+\cdots +{\mathrm{proj}}_{{\mathbf{w}}_j}({\mathbf{v}}_{j+1})$.
• Repeat with the next step ${\mathbf{w}}_{j+2}$.
• Produce a new list of ${\mathbf{w}}_i$ vectors with $⟨{\mathbf{w}}_1,\dots ,{\mathbf{w}}_k⟩=⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k⟩$.
  • If the original vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$ were independent, then we never have ${\mathbf{w}}_{j+1}=0$ for any $j$.
  • If there is some redundancy in ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$, then at some point ${\mathrm{proj}}_{V_j}({\mathbf{v}}_{j+1})={\mathbf{v}}_{j+1}$ and ${\mathbf{w}}_{j+1}=0$.
  • We can detect this and throw out any ${\mathbf{w}}_j=0$ from the final list to obtain truly independent vectors ${\mathbf{w}}_1^{\prime },\dots ,{\mathbf{w}}_{\ell }^{\prime }$, none of which is zero.
  • The dimension of the space $⟨{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k⟩$ is then $\ell$, then number of nonzero items ${\mathbf{w}}_j$ we obtained.

Link to original

Application: distance from point to subspace

Application - distance from point to subspace

Many applications of linear algebra involve the measure of distance from a given vector to a subspace that does not include the vector. Typically the subspace is known as the span of a list of given vectors.

Suppose $\mathbf{v}\in {\mathbb{R}}^n$ and $U=⟨{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k⟩\subset {\mathbb{R}}^n$ is a subspace, given as the span of the vectors ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_k$.

Here is a standard solution to the problem of finding the distance from $\mathbf{v}$ to $U$:

• First use Gram-Schmidt to produce an orthogonal basis $\{{\mathbf{w}}_1,\dots {\mathbf{w}}_{\ell }\}$ of $U$. It’s possible that $\ell <k$.
• Now compute the projection ${\mathrm{proj}}_U(\mathbf{v})$.
• The orthogonal part ${\mathbf{v}}_{\perp }=\mathbf{v}-{\mathrm{proj}}_U(\mathbf{v})$ is a vector from $U$ straight to $\mathbf{v}$.
• $|{\mathbf{v}}_{\perp }|$ is the distance from $\mathbf{v}$ to $U$.

Link to original

Example

Computing distance of point to subspace

Computing distance of point to subspace

Problem: Find the closest point on the subspace given by the span

$$U=⟨\left(\begin{array}{c}0\\ 2\\ 3\\ -1\end{array}\right),\left(\begin{array}{c}1\\ -2\\ 1\\ -1\end{array}\right),\left(\begin{array}{c}2\\ 0\\ 1\\ 3\end{array}\right)⟩$$

to the vector $\mathbf{x}=(-1,-3,2,1)$.

Solution: Label the vectors in the span ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$, in order. Notice that they are already pairwise orthogonal, so we can skip Gram-Schmidt. Then compute ${\mathrm{proj}}_U(\mathbf{x})$:

$$\begin{array}{rl}{\mathrm{proj}}_U(\mathbf{x})& ={\mathrm{proj}}_{{\mathbf{v}}_1}(\mathbf{x})+{\mathrm{proj}}_{{\mathbf{v}}_2}(\mathbf{x})+{\mathrm{proj}}_{{\mathbf{v}}_3}(\mathbf{x})\\ & =\frac{\mathbf{x}\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1+\frac{\mathbf{x}\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2+\frac{\mathbf{x}\cdot {\mathbf{v}}_3}{{\mathbf{v}}_3\cdot {\mathbf{v}}_3}{\mathbf{v}}_3\\ & =\frac{-1}{14}{\mathbf{v}}_1+\frac{6}{7}{\mathbf{v}}_2+\frac{3}{14}{\mathbf{v}}_3=\left(\begin{array}{c}9/7\\ -13/7\\ 6/7\\ -1/7\end{array}\right).\end{array}$$

Therefore

$$\mathbf{x}-{\mathrm{proj}}_U(\mathbf{x})=\left(\begin{array}{c}-16/7\\ -8/7\\ 8/7\\ 8/7\end{array}\right)$$

and the length of this vector is $\sqrt{\frac{448}{49}}$, which is our answer.

Link to original

Application - distance from point to subspace (part 2)

Basic linear regression as projection

Linear regression: projection of dependent data vector to subspace of “best fit lines”

Basic linear regression is essentially an application of the above idea. Later we will focus on the details for a more general version; here is a preview summary:

• Data is given by vectors $\mathbf{x}$ and $\mathbf{y}$ matching input to output by the order of components. If there are $n$ data pairs $(x,y)$, then $\mathbf{x},\mathbf{y}$ will have $n$ components.
• The line of best fit should have the form $y=mx+b$. We seek $m$ and $b$, as well as the correlation coefficient $r^2$ which expresses how close the data $\mathbf{y}$ is to the best fit line. It is specifically the sum of the square distances from each component, i.e. each data pair.
• The span $⟨\mathbf{x},1⟩$ is all vectors of the form $\{m\mathbf{x}+b1\mid m,b\in \mathbb{R}\}$. These vectors encode outputs of the possible fit lines evaluated at the input data $\mathbf{x}$.
• The best fit line is $y=mx+b$ where $m\mathbf{x}+b1$ is the closest vector to $\mathbf{y}$ in the span $⟨\mathbf{x},1⟩$.
  • Convert $⟨\mathbf{x},1⟩$ to the orthogonal basis $⟨\hat{\mathbf{x}},1⟩$. Here $\hat{\mathbf{x}}=\mathbf{x}-\bar{x}1$ where $\bar{x}$ is the average of the components of $\mathbf{x}$.
  • Compute $\mathbf{z}={\mathrm{proj}}_{⟨\mathbf{x},1⟩}(\mathbf{y})={\mathrm{proj}}_{\hat{\mathbf{x}}}(\mathbf{y})+{\mathrm{proj}}_1(\mathbf{y})$.
  • Define $m,b^{\prime }$ as the coefficients ${\mathrm{proj}}_{\hat{\mathbf{x}}}(\mathbf{y})=m\hat{\mathbf{x}}$ and ${\mathrm{proj}}_1(\mathbf{y})=b^{\prime }1$.
  • Therefore we have $\mathbf{z}=m\hat{\mathbf{x}}+b^{\prime }1$, so then $\mathbf{z}=m\mathbf{x}+(b^{\prime }-m\bar{x})1$, and we have found $m$ and $b=b^{\prime }-m\bar{x}$.
• The distance $|\mathbf{y}-(m\mathbf{x}+b1)|$ determines the correlation $r$. The absolute distance is divided by the relative length of $\hat{\mathbf{y}}=\mathbf{y}-\bar{y}1$ to get a scale-invariant number. The final formula is: $$1-r^2=\frac{|\mathbf{y}-(m\mathbf{x}+b1){|}^2}{|\mathbf{y}-\bar{y}1{|}^2}.$$

Link to original

Exercise

02

Computing a best fit line

Following the steps above, compute the best fine line (i.e. compute $m$ and $b$) for the data used in Problem 05-03:

$$(-3,4),(1,-1),(0,-1),(4,-3),(-2,1).$$

In Problem 05-03, you already found $\bar{x}$ and $\bar{y}$, and implicitly $\hat{\mathbf{x}}$ and $\hat{\mathbf{y}}$.

Link to original

Application - distance from point to subspace (part 3)

[optional] Derivation of correlation coefficient formula

Here we verify that

$$\frac{|\mathbf{y}-(m\mathbf{x}+b1){|}^2}{|\mathbf{y}-\bar{y}1{|}^2}=1-\frac{(\hat{\mathbf{x}}\cdot \hat{\mathbf{y}}{)}^2}{(\hat{\mathbf{x}}\cdot \hat{\mathbf{x}})(\hat{\mathbf{y}}\cdot \hat{\mathbf{y}})}.$$

First, since $|\mathbf{y}-\bar{y}1{|}^2=\hat{\mathbf{y}}\cdot \hat{\mathbf{y}}=|\hat{\mathbf{y}}{|}^2$, it is sufficient (confirm this for yourself!) to show that

$$\begin{array}{rl}|\mathbf{y}-(m\mathbf{x}+b1){|}^2& =|\hat{\mathbf{y}}{|}^2-\frac{(\hat{\mathbf{x}}\cdot \hat{\mathbf{y}}{)}^2}{|\hat{\mathbf{x}}{|}^2}\\ & =|\hat{\mathbf{y}}{|}^2-|{\mathrm{proj}}_{\hat{\mathbf{x}}}(\mathbf{y}){|}^2.\end{array}$$

Since $m$ and $b$ are chosen to give the closest vector to $\mathbf{y}$ via projection, we know:

$$\begin{array}{rl}\mathbf{y}-(m\mathbf{x}+b1)& =\mathbf{y}-{\mathrm{proj}}_{⟨\mathbf{x},1⟩}(\mathbf{y})\\ & =\mathbf{y}-{\mathrm{proj}}_{⟨\hat{\mathbf{x}},1⟩}(\mathbf{y})\\ & =\mathbf{y}-\frac{\mathbf{y}\cdot \hat{\mathbf{x}}}{\hat{\mathbf{x}}\cdot \hat{\mathbf{x}}}\hat{\mathbf{x}}-\frac{\mathbf{y}\cdot 1}{1\cdot 1}1\\ & =\mathbf{y}-\bar{y}1-\frac{\mathbf{y}\cdot \hat{\mathbf{x}}}{\hat{\mathbf{x}}\cdot \hat{\mathbf{x}}}\hat{\mathbf{x}}\\ & =\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\mathbf{y})\\ & =\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}),\end{array}$$

where we have used the fact that $\hat{y}=\frac{\mathbf{y}\cdot 1}{1\cdot 1}$, as well as the fact that $\mathbf{y}=\hat{\mathbf{y}}+1$ and $1$ is perpendicular to $\hat{\mathbf{x}}$ so it can be dropped from the penultimate projection. (Confirm this for yourself!)

Finally, we know that ${\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}})$ and $\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}})$ are perpendicular. (The former lies in the span of $\hat{\mathbf{x}}$ and the latter is perpendicular to this span.) Therefore

$$\begin{array}{rl}|\hat{\mathbf{y}}{|}^2& =|\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}})+{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}){|}^2\\ & =|\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}){|}^2+|{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}){|}^2,\\ |\hat{\mathbf{y}}-{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}){|}^2& =|\hat{\mathbf{y}}{|}^2-|{\mathrm{proj}}_{\hat{\mathbf{x}}}(\hat{\mathbf{y}}){|}^2,\end{array}$$

and by plugging in we see $|\mathbf{y}-(m\mathbf{x}+b1){|}^2=|\hat{\mathbf{y}}{|}^2-|{\mathrm{proj}}_{\hat{\mathbf{x}}}(\mathbf{y}){|}^2$.

Link to original