6  Bases of Vector Spaces

Bases are fundamental structures in linear algebra that provide a systematic way to represent vectors in a vector space. They act as coordinate systems, allowing us to uniquely express every vector as a combination of a minimal set of basis vectors. A deep understanding of bases is essential for:

• Efficient data representation: Compressing and reconstructing signals in applications like image and audio processing.
• Linear transformations: Understanding how changes in basis can simplify computations, such as diagonalizing matrices for stability analysis in differential equations.
• Solving systems of equations: Expressing solutions in terms of fundamental directions, crucial for optimization and scientific computing.
• Geometric transformations: Rotations, reflections, and changes of perspective in graphics, physics, and computer vision.

6.1 Definition and Properties

Here are three fundamental definitions of the theory of vector spaces.

Definition 6.1 Let \(V\) be a vector space. A set of vectors \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_k\}\) in \(V\) is linearly independent if the only solution to \[c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0}\] is the trivial solution \(c_1 = c_2 = \cdots = c_k = 0\).

Equivalently, no vector in \(S\) can be written as a linear combination of the other vectors in \(S\).

Definition 6.2 Let \(V\) be a vector space. A set of vectors \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_k\}\) in \(V\) spans \(V\) if every vector \(\mathbf{v}\in V\) can be written as a linear combination of vectors in \(S\). That is, for every \(\mathbf{v}\in V\), there exist constants \(c_1,\ldots,c_k\in\mathbb{R}\) such that \[\mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k\]

Definition 6.3 Let \(V\) be a vector space. A set of vectors \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_k\}\) in \(V\) is a basis of \(V\) if it satisfies both:

1. \(S\) is linearly independent
2. \(S\) spans \(V\)

In other words, a basis is a linearly independent spanning set.

Think About This

A basis gives us a minimal spanning set: it contains just enough vectors to span the space, with no redundant vectors. This is why bases are so useful - they provide an efficient way to represent all vectors in the space.

6.1.1 Verifying Linear Independence and Spanning

When working with a set of vectors \(S=\{\mathbf{v}_1,\ldots,\mathbf{v}_k\}\), we often need to verify whether it is linearly independent or whether it spans a space. Here’s how to check each property:

Checking Linear Independence

To verify if the set of vectors is linearly independent, we look at the homogeneous equation \[c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0}\] and we find all solutions. If the only solution is the trivial solution \(c_1=c_2=\cdots=c_k=0\), the set is linearly independent. Otherwise it is linearly dependent.

Example in \(\mathbb{R}^3\)

Let’s check if the following vectors are linearly independent: \[S=\left\{\begin{bmatrix}1\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\1\\3\end{bmatrix}\right\}\]

Set up the equation: \[c_1\begin{bmatrix}1\\0\\1\end{bmatrix} + c_2\begin{bmatrix}0\\1\\1\end{bmatrix} + c_3\begin{bmatrix}1\\1\\3\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix},\] and solve it by converting it to an augmented matrix and then use Gaussian Elimination: \[ \left[\begin{array}{ccc|c}1&0&1&0\\0&1&1&0\\1&1&3&0\end{array}\right] \xrightarrow{\text{RREF}} \left[\begin{array}{ccc|c}1&0&0&0\\0&1&0&0\\0&0&1&0\end{array}\right] \]

From the row reduced echelon matrix we conclude that the only solution is \(c_1=c_2=c_3=0\), which proves that the set is linear independence.

Checking Spanning

To verify if a set of vectors spans the vector space \(V\), we look at the vector equation: \[\mathbf{b} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k,\] where \(\mathbf{b}\in V\) is an arbitrary vector. If this equation has a solution for every \(\mathbf{b}\), the set of vectors spans \(V\), otherwise it doesn’t span \(V\).

Example in \(\mathbb{R}^3\)

Let’s check if the following vectors span \(\mathbb{R}^3\): \[S=\left\{\begin{bmatrix}1\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\1\\3\end{bmatrix}\right\}\]

An arbitrary vector in \(\mathbb{R}^3\) is of the form \(\mathbf{b}=(x_1,x_2,x_3)\).

Set up the vector equation: \[c_1\begin{bmatrix}1\\0\\1\end{bmatrix} + c_2\begin{bmatrix}0\\1\\1\end{bmatrix} + c_3\begin{bmatrix}1\\1\\3\end{bmatrix}=\begin{bmatrix}x_1\\x_2\\x_2\end{bmatrix},\] and solve it by converting it to an augmented matrix and then use Gaussian Elimination: \[ \left[\begin{array}{ccc|c}1&0&1&x_1\\0&1&1&x_2\\1&1&3&x_3\end{array}\right] \xrightarrow{\text{RREF}} \left[\begin{array}{ccc|c}1&0&0&2x_1+x_2-x_3\\0&1&0&x_1+2x_2-x_3\\0&0&1&-x_1-x_2+x_3\end{array}\right] \]

From the row reduced echelon matrix we conlude that the vector equation has a solution for every \(\mathbf{b}\in\mathbf{R}^3\), which proves that the set spans \(\mathbb{R}^3\).

Important Points

• Linear Independence: We set the linear combination equal to zero and check for only the trivial solution
• Spanning: We set the linear combination equal to an arbitrary vector and check if solutions always exist
• Linear independence deals with uniqueness, while spanning deals with existence

6.1.2 Examples of Bases

The most fundamental example in any \(\mathbb{R}^n\) is the canonical basis (also called the standard basis) \[\{\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n\}\] where \(\mathbf{e}_i\) has a 1 in position \(i\) and 0’s elsewhere: \[\mathbf{e}_1=\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix}, \mathbf{e}_2=\begin{bmatrix}0\\1\\\vdots\\0\end{bmatrix}, \ldots, \mathbf{e}_n=\begin{bmatrix}0\\0\\\vdots\\1\end{bmatrix}.\]

Here are several examples of bases for \(\mathbb{R}^2\) and \(\mathbb{R}^3\):

Examples of Bases in \(\mathbb{R}^2\):

\[S_1=\left\{\begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}0\\1\end{bmatrix}\right\},\quad S_2=\left\{\begin{bmatrix}1\\1\end{bmatrix}, \begin{bmatrix}-1\\1\end{bmatrix}\right\}, \quad S_3=\left\{\begin{bmatrix}2\\0\end{bmatrix}, \begin{bmatrix}0\\3\end{bmatrix}\right\}.\]

Examples of Bases in \(\mathbb{R}^3\)

\[S_1=\left\{\begin{bmatrix}1\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\1\\0\end{bmatrix}\right\}, \quad S_2 = \left\{\begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}1\\1\\0\end{bmatrix}, \begin{bmatrix}1\\1\\1\end{bmatrix}\right\}\]

6.1.3 Uniqueness of Representations

For any vector \(\mathbf{v} \in V\), if \(S\) is a basis, then \(\mathbf{v}\) can be written uniquely as: \[\mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + ... + c_n\mathbf{v}_n\]

Existence follows from the spanning property. To prove uniqueness, assume we have two representations:

1. \(\mathbf{v} = c_1\mathbf{v}_1 + ... + c_n\mathbf{v}_n\) and
2. \(\mathbf{v} = d_1\mathbf{v}_1 + ... + d_n\mathbf{v}_n\)

Then, subtracting these equations, we get \[\mathbf{0} = (c_1-d_1)\mathbf{v}_1 + ... + (c_n-d_n)\mathbf{v}_n\] Since \(S\) is linearly independent, we must have: \(c_1-d_1 = c_2-d_2 = \cdots = c_n-d_n = 0\) and we conclude that \(c_i = d_i\) for all \(i\)

6.2 Coordinates

Given a basis \(S = \{\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n\}\) of a vector space \(V\) and a vector \(\mathbf{v}\in V\), there exist unique constants \(c_1, c_2, ..., c_n\in\mathbb{R}\) such that

\[\mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n\]

These coefficients \((c_1,c_2,\cdots,c_n)\) are called the coordinates of \(\mathbf{v}\) with respect to the basis \(S\). We write this coordinate vector as \([\mathbf{v}]_S\), which is an element of \(\mathbb{R}^n\).

The relationship between a vector and its coordinates can be expressed as:

\[[\mathbf{v}]_S = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}\quad\Longleftrightarrow\quad \mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n \tag{6.1}\]

This equivalence leads to two fundamental problems in working with coordinates:

1. Coordinate Problem: Given a vector \(\mathbf{v}\), find its coordinates \([\mathbf{v}]_S\)
2. Reconstruction Problem: Given coordinates \([\mathbf{v}]_S\), find the vector \(\mathbf{v}\)

Let’s explore these problems through an example:

Exercise: Let \(S=\left\{\begin{bmatrix}1\\1\end{bmatrix},\begin{bmatrix}0\\1\end{bmatrix}\right\}\) be a basis of \(\mathbb{R}^2\). Find:

1. If \(\mathbf{v}=\begin{bmatrix}2\\3\end{bmatrix}\), find \([\mathbf{v}]_S\)
2. If \([\mathbf{v}]_S=\begin{bmatrix}2\\3\end{bmatrix}\), find \(\mathbf{v}\)

Click to see detailed answers

6.3 Problem 1

We have that \(\mathbf{v}=\begin{bmatrix}2\\3\end{bmatrix}\) and we need to find \([\mathbf{v}]_S\)

To find \([\mathbf{v}]_S\), we need to find scalars \(c_1\) and \(c_2\) such that:

\[\mathbf{v} = c_1\begin{bmatrix}1\\1\end{bmatrix} + c_2\begin{bmatrix}0\\1\end{bmatrix}\]

This gives us the system: \(\begin{bmatrix}2\\3\end{bmatrix} = c_1\begin{bmatrix}1\\1\end{bmatrix} + c_2\begin{bmatrix}0\\1\end{bmatrix}\)

Which yields: \[\begin{cases} c_1 = 2 \quad \text{(from first row)}\\ c_1 + c_2 = 3 \quad \text{(from second row)} \end{cases}\]

Solving:

1. From first equation: \(c_1 = 2\)
2. Substitute into second: \(2 + c_2 = 3\)
3. Therefore: \(c_2 = 1\)

Thus, \([\mathbf{v}]_S=\begin{bmatrix}2\\1\end{bmatrix}\)

6.3.1 Verification:

We can verify by checking that: \(2\begin{bmatrix}1\\1\end{bmatrix} + 1\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}2\\3\end{bmatrix}\)

6.4 Problem 2

We have that \([\mathbf{v}]_S=\begin{bmatrix}2\\3\end{bmatrix}\) and we need to find \(\mathbf{v}\)

From Equation 6.1 we have that: \[\mathbf{v} = 2\begin{bmatrix}1\\1\end{bmatrix} + 3\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}2\\2\end{bmatrix} + \begin{bmatrix}0\\3\end{bmatrix} = \begin{bmatrix}2\\5\end{bmatrix} \]

Therefore, \(\mathbf{v}=\begin{bmatrix}2\\5\end{bmatrix}\)

6.4.1 General Method:

• To find \([\mathbf{v}]_S\): Solve the equation \(\mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2\) for the coefficients
• To find \(\mathbf{v}\) from \([\mathbf{v}]_S\): Multiply each basis vector by its corresponding coordinate and sum

Every basis \(S\) gives us a way to represent vectors through their coordinates. This defines a function from the vector space \(V\) to \(\mathbb{R}^n\): \[\begin{align*} \varphi_S: V &\to \mathbb{R}^n\\ \mathbf{v} &\mapsto [\mathbf{v}]_S \end{align*}\]

The following theorem shows that this coordinate map \(\varphi_S\) is linear - it preserves both addition and scalar multiplication.

Theorem 6.1 Suppose that \(S=\{\mathbf{v}_1,\dots,\mathbf{v}_n\}\) is a basis of the vector space \(V\). Then

1. For every \(\mathbf{u},\mathbf{w}\in V\), \([\mathbf{u}+\mathbf{v}]_S=[\mathbf{u}]_S+[\mathbf{w}]_S\).
2. For every \(\mathbf{u}\in V\) and \(c\in\mathbf{R}\), \([c\mathbf{u}]_S=c[\mathbf{u}]_S\).

Exercise: Prove Theorem 6.1.

Click to see the proof

Let’s prove that coordinates respect vector addition and scalar multiplication.

6.4.2 Part 1: Addition Property

Claim: For every \(\mathbf{u},\mathbf{w}\in V\), \([\mathbf{u}+\mathbf{w}]_S=[\mathbf{u}]_S+[\mathbf{w}]_S\)

Proof: Let \([\mathbf{u}]_S=(a_1,\ldots,a_n)\) and \([\mathbf{w}]_S=(b_1,\ldots,b_n)\)

By definition of coordinates, this means: \[\mathbf{u}=a_1\mathbf{v}_1+\cdots+a_n\mathbf{v}_n\] \[\mathbf{w}=b_1\mathbf{v}_1+\cdots+b_n\mathbf{v}_n\]

Consider \(\mathbf{u}+\mathbf{w}\): \[\begin{align*} \mathbf{u}+\mathbf{w}&=(a_1\mathbf{v}_1+\cdots+a_n\mathbf{v}_n)+(b_1\mathbf{v}_1+\cdots+b_n\mathbf{v}_n)\\ &=(a_1+b_1)\mathbf{v}_1+\cdots+(a_n+b_n)\mathbf{v}_n \end{align*}\]

Therefore, \([\mathbf{u}+\mathbf{w}]_S=(a_1+b_1,\ldots,a_n+b_n)\)

But this is exactly \([\mathbf{u}]_S+[\mathbf{w}]_S=(a_1,\ldots,a_n)+(b_1,\ldots,b_n)\)

Therefore, \([\mathbf{u}+\mathbf{w}]_S=[\mathbf{u}]_S+[\mathbf{w}]_S\)

6.4.3 Part 2: Scalar Multiplication Property

Claim: For every \(\mathbf{u}\in V\) and \(c\in\mathbb{R}\), \([c\mathbf{u}]_S=c[\mathbf{u}]_S\)

Proof: Let \([\mathbf{u}]_S=(a_1,\ldots,a_n)\)

By definition of coordinates: \[\mathbf{u}=a_1\mathbf{v}_1+\cdots+a_n\mathbf{v}_n\]

Consider \(c\mathbf{u}\): \[\begin{align*} c\mathbf{u}&=c(a_1\mathbf{v}_1+\cdots+a_n\mathbf{v}_n)\\ &=(ca_1)\mathbf{v}_1+\cdots+(ca_n)\mathbf{v}_n \end{align*}\]

Therefore, \([c\mathbf{u}]_S=(ca_1,\ldots,ca_n)\)

But this is exactly \(c[\mathbf{u}]_S=c(a_1,\ldots,a_n)\)

Therefore, \([c\mathbf{u}]_S=c[\mathbf{u}]_S\)

6.5 Dimension

A very important linear algebra result is that all bases of the same vector space have the same number of elements. This isn’t obvious at first glance – after all, we can find many different bases for a vector space. Yet this common number, which we call the dimension of the vector space, is a fundamental invariant.

Since the cannonical basis of \(\mathbb{R}^n\) has \(n\) elements, all bases have \(n\)-elements, and \(\mathbb{R}^n\) has dimension equal to \(n\). This result is stated in the next theorem:

Theorem 6.2 Suppose that \(S = \{\mathbf{v}_1,...,\mathbf{v}_k\}\) is a subset of \(\mathbb{R}^n\). Then

1. If \(S\) is linearly independent, \(k\leq n\).
2. If \(S\) spans \(\mathbb{R}^n\), then \(k\geq n\).

Consequently, if \(S\) is a basis (both linearly independent and spanning), then \(k=n\).

Proof. To prove this theorem, we analyze the \(n\times k\) matrix whose columns are the vectors in \(S\): \[\begin{bmatrix} \uparrow & \uparrow & \cdots & \uparrow \\ \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_k \\ \downarrow & \downarrow & \cdots & \downarrow \end{bmatrix}.\]

Let \(R\) be the reduced row echelon form (RREF) of this matrix. We then consider two cases:

1. Case of Linear Independence: If \(S\) is linearly independent, then by Theorem 5.3, \(R\) has a pivot position in every column. Since \(S\) contains \(k\) vectors, \(R\) has \(k\) columns and therefore \(k\) pivots. However, in a matrix with \(n\) rows, we cannot have more than \(n\) pivots (since we can have at most one pivot per row). Therefore, \(k \leq n\).

2. Case of Spanning: If \(S\) spans \(\mathbb{R}^n\), then by Theorem 5.6, \(R\) has a pivot position in every row. Since \(R\) has \(n\) rows, it must have \(n\) pivots. However, we cannot have more pivots than columns (since we can have at most one pivot per column), and \(R\) has \(k\) columns (one for each vector in \(S\)). Therefore, \(k \geq n\). \(\square\)

6.5.1 Special Case: \(n\) Vectors in \(\mathbb{R}^n\)

The previous theorem has a remarkable consequence when the number of vectors equals the dimension. In this case, either property (linear independence or spanning) automatically implies the other.

Corollary 6.1 Let \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) be a set of exactly \(n\) vectors in \(\mathbb{R}^n\). Then:

1. If \(S\) is linearly independent, then \(S\) automatically spans \(\mathbb{R}^n\)
2. If \(S\) spans \(\mathbb{R}^n\), then \(S\) is automatically linearly independent

In other words, for a set of \(n\) vectors in \(\mathbb{R}^n\), either property alone is sufficient to prove that \(S\) is a basis.

Idea of the Proof

The proof follows from the same matrix analysis as before:

• Linear independence gives us \(n\) pivots in \(n\) columns, forcing every row to have a pivot
• Spanning gives us \(n\) pivots in \(n\) rows, forcing every column to have a pivot

6.6 Orthonormal Bases of \(\mathbb{R}^n\)

A particularly useful type of basis combines orthogonality and normalization:

A basis \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) of \(\mathbb{R}^n\) is orthonormal if:

1. \(\mathbf{v}_i \cdot \mathbf{v}_j = 0\) for all \(i \neq j\) (orthogonal vectors)
2. \(\|\mathbf{v}_i\| = 1\) for all \(i\) (unit vectors)

The standard basis \(\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}\) is the most obvious example of an orthonormal basis, but there are many, like this example in \(\mathbb{R}^3\):

\[\left\{\frac{1}{\sqrt{3}}\begin{bmatrix}1\\1\\1\end{bmatrix}, \frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\end{bmatrix}, \frac{1}{\sqrt{6}}\begin{bmatrix}1\\1\\-2\end{bmatrix}\right\}.\]

6.6.1 Finding Coordinates

Working with orthonormal bases simplifies finding coordinates dramatically. For any basis, finding \([\mathbf{v}]_S\) means solving a system of equations. However, with an orthonormal basis \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\), we can find each coordinate independently: \[[\mathbf{v}]_S = \begin{bmatrix} \mathbf{v}\cdot\mathbf{v}_1 \\ \vdots \\ \mathbf{v}\cdot\mathbf{v}_n \end{bmatrix}\]

To see this, suppose that \([\mathbf{v}]_S=(c_1,c_2,\dots,c_n)\). Then \[\mathbf{v}=c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_n\mathbf{v}_n.\] Fix \(i\leq n\) and take the dot product of \(\mathbf{v}\) with \(\mathbf{v}_i\) to get: \[\mathbf{v}\cdot\mathbf{v}_i =c_1(\mathbf{v}_1\cdot\mathbf{v}_i)+c_2(\mathbf{v}_2\cdot\mathbf{v}_i)+\cdots+c_n(\mathbf{v}_n\cdot\mathbf{v}_i).\] Since \(S = \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) is orthonormal, \(\mathbf{v}_j\cdot\mathbf{v}_i=1\) if \(j=i\) and \(\mathbf{v}_j\cdot\mathbf{v}_i=0\) if \(j\not=i\). Therefore \[\mathbf{v}\cdot\mathbf{v}_i=c_i.\] This shows we can find each coefficient by computing a dot product.

6.6.2 Constructing Orthonormal Bases

Finding orthonormal bases usually requires computation (like the Gram-Schmidt process, which we’ll see in the lab). However, some special orthonormal bases are known. One remarkable example is the Hadamard basis, which exists in dimensions that are powers of 2. For \(n=4\), the Hadamard basis is:

\[\left\{ \frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}, \frac{1}{2}\begin{bmatrix}1\\1\\-1\\-1\end{bmatrix}, \frac{1}{2}\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix}, \frac{1}{2}\begin{bmatrix}1\\-1\\-1\\1\end{bmatrix} \right\}\]

6.6.3 Orthogonal Matrices

Definition 6.4 An \(n\times n\) matrix \(A\) is said to be an orthogonal matrix if \[A^TA=AA^T=I.\]

If follows from Equation 3.6 that the \(n\times n\) matrix \(A\) is orthogonal if and only if the columns of \(A\) are an orthonormal basis of \(\mathbb{R}^n\).

This property makes orthogonal matrices particularly useful because:

1. The inverse is simply the transpose: \(A^{-1} = A^T\)
2. They preserve distances: \(\|A\mathbf{v}\| = \|\mathbf{v}\|\)
3. They preserve angles: if \(\mathbf{u}\cdot\mathbf{v} = 0\), then \((A\mathbf{u})\cdot(A\mathbf{v}) = 0\)

Common examples include:

• Rotation matrices in \(\mathbb{R}^2\): \(\begin{bmatrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{bmatrix}\)
• Reflection matrices across a unit vector \(\mathbf{u}\): \(I - 2\mathbf{u}\mathbf{u}^T\)

Every orthogonal matrix represents either a rotation, a reflection, or a combination of both. These transformations preserve distances and angles, making them crucial in applications from computer graphics to quantum mechanics.