Bases for Vector Spaces

Math 303: Section 23

Dr. Janssen

Intro

\[ \def\R{{\mathbb R}} \def\P{{\mathbb P}} \def\b{{\mathbf{b}}} \def\x{{\mathbf{x}}} \def\y{{\mathbf{y}}} \def\u{{\mathbf{u}}} \def\v{{\mathbf{v}}} \def\w{{\mathbf{w}}} \def\z{{\mathbf{z}}} \DeclareMathOperator{\null}{Nul} \DeclareMathOperator{\span}{Span} \newcommand{\set}[1]{\left\{ {#1} \right\}} \newcommand{\setof}[2]{{\left\{#1\,\colon\,#2\right\}}} \]

Linear (In)dependence

Definition 1 A set of vectors \(\set{\v_1, \v_2, \ldots, \v_k}\) in a vector space \(V\) is linearly independent if the vector equation

\[ x_1 \v_1 + x_2 \v_2 + \cdots + x_k \v_k = \mathbf{0} \]

for scalars \(x_1, x_2, \ldots, x_k\) has only the trivial solution

\[ x_1 = x_2 = x_3 = \cdots = x_k = 0. \]

If a set of vectors is not linearly independent, then the set is linearly dependent.

Preview Activity 23.1

(in)dependence of sets of polynomials in \(\P_1\), or the space of \(2\times 2\) matrices.

Consequences

Theorem 1 A set \(\set{\v_1, \ldots, \v_k}\) of vectors in a vector space \(V\) is linearly dependent if and only if at least one of the vectors in the set can be written as a linear combination of the remaining vectors in the set.

Theorem 2 A set \(\set{\v_1, \ldots, \v_k}\) of vectors in a vector space \(V\) is linearly independent if and only if none of the vectors in the set can be written as a linear combination of the remaining vectors in the set.

Upshot is that if a set is linearly independent, we can throw a vector out and the span won’t change.

Spans Preserved

Theorem 3 Let \(\set{\v_1, \v_2, \ldots, \v_k}\) be a set of vectors in a vector space \(V\). If for some \(i\) between \(1\) and \(k\), \(\v_i\in \span\set{\v_1, \v_2, \ldots, \v_{i-1}, \v_{i+1}, \ldots, \v_k}\), then

\[ \span\set{\v_1, \v_2, \ldots, \v_k} = \span\set{\v_1, \v_2, \ldots, \v_{i-1}, \v_{i+1}, \ldots, \v_k}. \]

Bases

Basis = minimal spanning set.

If we have a spanning set \(S\) for a vsp \(V\), then if \(S\) is linearly dependent, we can throw a vector out. This means \(S\) can’t be minimal. But if \(S\) is linearly dependent, we can’t throw a vector out–all vectors in the set are needed to form the span. So we get the following formal definition.

Definition

Definition 2 A basis for a vector space \(V\) is a subset \(S\) of \(V\) if

• \(\span S = V\)
• \(S\) is linearly independent

Key implications

• A basis for a vector space \(V\) is a minimal spanning set for \(V\)
• A basis for \(V\) is a subset \(S\) of \(V\) for which \(\span S = V\) and \(S\) is linearly independent
• No vector in a basis can be written as a linear combination of the other vectors in the basis.
• If a subset \(S\) of a vector space \(V\) has the property that one of the vectors in \(S\) is a linear combination of the other vectors in \(S\), then \(S\) is not a basis for \(V\).

Activity 23.1

• Is \(S = \set{1+t, t, 1-t}\) a basis for \(\P_1\)? Explain.
• Explain why the set \(S = \set{1, t, t^2, \ldots, t^n}\) is a basis for \(\P_n\). This basis is called the standard basis for \(\P_n\).
• Show that the set

\[ \set{ \left[\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}\right], \left[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}\right], \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right], \left[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right]} \]

is a basis for \(\mathcal{M}_{2\times 2}\).

Note that not every vector space has a finite basis! And being able to ‘use’ this ‘fact’ requires a somewhat controversial set theory axiom. But it’s only somewhat controversial, and not with me, so we will use it.

Application: Wavelets and Image Compression

Intro

Need for compression! We’re going to explore wavelets.

The basic idea is that we start with a digital image made of pixels. Each pixel can be assigned a number or a vector depending on the makeup/type of image. We can thus represent an image as a matrix, or set of matrices \(M\), where each entry in \(M\) represents a a pixel of the image.

Simple example: on the left, we see a \(16\times 16\) image of a flower. It’s grayscale (our methods can be extended to color images, but for simplicity we won’t), so each pixel has a numeric representation between 0 and 255, where 0 is black, 255 is white, and numbers in between represent shades of gray.

Now we can apply wavelets to the image and compress it. Essentially, wavelets act by averaging and differencing. The averaging creates smaller versions of the image and the differencing keeps track of how far the smaller version is from a previous copy. The differencing often produces many small (close to 0) entries, and so replacing these entries with 0 doesn’t have much effect on the image (this is called thresholding). By introducing long strings of zeros into our data, we are able to store a (compressed) copy of the image in a smaller amount of space.

The averaging and differencing is done with special vectors (wavelets) that form a basis for a suitable function space.

Compressed flower

A threshold of 10 was used to produce the compressed picture on the right.

Project

We’re going to spend time in class (approximately 2 days) working through Project 23, starting on p. 419 of the text (p. 439 of the PDF).

This will be our first lab.

Let’s get started!