Theory

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).$$

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

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

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.

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.

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.

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