Basis

Given a vector space

V

the set

ℬ \subseteq V

is said to be a basis if

B

is linearly independent and

B

spans

V

The plural of basis is bases.

The Size of a Basis is Unique

Suppose that

ℬ, 𝒞

are bases for

V

then

| ℬ | = | 𝒞 |

TODO: Add the proof here.

Every Vector Space has a Basis

For any vector space

V

there is a basis for it

TODO

Dimension of a Vector Space

Suppose that

V

is a vector space then since it has a basis

ℬ

then we define:

\dim (V) = | ℬ |

Note that the above defintion makes sense as the size of all bases are the same

Finite Dimensional Vector Space

A vector space

V

is said to be finite dimensional if

\dim (V)

is finite

Standard Basis of Rn

The standard basis of

ℝ^{n}

{e_{1}, \dots, e_{n}}

where

e_{i}

is the vector whose

i

-th coordinate is

1

and whose other coordinates are

0

Standard Basis of Rn is a Basis

The standard basis

{e_{1}, \dots, e_{n}}

is a basis of

ℝ^{n}

First, the standard basis spans

ℝ^{n}

. If

x = (x_{1}, \dots, x_{n}) \in ℝ^{n}

, then

x = x_{1} e_{1} + \dots + x_{n} e_{n}

x \in span ({e_{1}, \dots, e_{n}})

by the definition of span.

Second, the standard basis is linearly independent. If

a_{1} e_{1} + \dots + a_{n} e_{n} = 0

then comparing the

i

-th coordinate gives

a_{i} = 0

. Since this holds for every

i

, all coefficients are zero, so

{e_{1}, \dots, e_{n}}

is linearly independent. Therefore it is a basis by the definition of basis.

Dimension of Rn

\dim (ℝ^{n}) = n

By the standard basis of

ℝ^{n}

is a basis proposition,

ℝ^{n}

has a basis with

n

elements. Therefore, by the definition of dimension,

\dim (ℝ^{n}) = n

Linearly Independent Set with Dimension Size is a Basis

Suppose

V

is a finite dimensional vector space with

\dim (V) = n

. If

S \subseteq V

is linearly independent and

| S | = n

, then

S

is a basis of

V

By the linear independent set expansion to basis proposition,

S

can be extended to a basis

ℬ

V

. Since

\dim (V) = n

, every basis of

V

has

n

elements by the definition of dimension. But

S

already has

n

elements, so the extension cannot add any new vectors. Therefore

S = ℬ

, so

S

is a basis of

V

Coordinate Vector in a Basis

Let

V

be an

n

-dimensional vector space over

ℝ

, and let

ℬ = (b_{1}, \dots, b_{n})

be an ordered basis of

V

. The coordinate map in the basis $ℬ$ is the function

{[\cdot]}_{ℬ} : V \to ℝ^{n}

defined as follows. For

v \in V

, write the unique basis expansion

v = \sum_{i = 1}^{n} a_{i} b_{i},

whose existence and uniqueness follow from basis implies unique representation. Then the coordinate vector of

v

in the basis

ℬ

{[v]}_{ℬ} = [\begin{matrix} a_{1} \\ ⋮ \\ a_{n} \end{matrix}] \in ℝ^{n} .

The older notation $wam (v, ℬ)$ means the same thing. The inverse operation takes a coordinate column and reconstructs the vector in $V$ .

A small subtlety appears when $V = ℝ^{n}$ . Since $ℝ^{n}$ is an $n$ -dimensional vector space, any ordered basis $𝒳 = (x_{1}, \dots, x_{n})$ of $ℝ^{n}$ gives a coordinate map ${[\cdot]}_{𝒳} : ℝ^{n} \to ℝ^{n} .$ If $v = (v_{1}, \dots, v_{n}) \in ℝ^{n}$ , then ${[v]}_{𝒳}$ is the vector of coefficients ${[v]}_{𝒳} = [\begin{matrix} c_{1} \\ ⋮ \\ c_{n} \end{matrix}] = (c_{1}, \dots, c_{n}) \in ℝ^{n}$ such that $c_{1} x_{1} + \dots + c_{n} x_{n} = (v_{1}, \dots, v_{n}) .$ Thus, in this special case, the coordinate map takes an element of $ℝ^{n}$ and returns an element of $ℝ^{n}$ , but that is a coincidence of the example. The vector ${[v]}_{𝒳}$ is an encoding: its entries are the coefficients placed on the basis vectors $x_{1}, \dots, x_{n}$ so that the resulting linear combination equals $v$ . It also happens to be an element of $ℝ^{n}$ , just as $v$ is. So even though $v$ and ${[v]}_{𝒳}$ both live in $ℝ^{n}$ , they are being read differently: $v$ is the vector being represented, while ${[v]}_{𝒳}$ is the coefficient list that represents it in the basis $𝒳$ . This is why it is often easier to first learn coordinate vectors in a vector space $V$ that is not literally $ℝ^{n}$ ; then the difference between a vector and its coordinate representation is harder to blur.

Coordinate Vector in a Nonstandard Basis

Let

ℰ = (e_{1}, e_{2})

be the standard basis of

ℝ^{2}

, and let

𝒜 = (2 e_{1} + e_{2}, e_{1} + 3 e_{2}) .

v = 7 e_{1} + 11 e_{2},

find

{[v]}_{𝒜}

We need scalars

a_{1}, a_{2} \in ℝ

such that

v = a_{1} (2 e_{1} + e_{2}) + a_{2} (e_{1} + 3 e_{2}) .

Expanding in the standard basis gives

7 e_{1} + 11 e_{2} = (2 a_{1} + a_{2}) e_{1} + (a_{1} + 3 a_{2}) e_{2} .

Since the standard basis representation is unique, the coefficients satisfy

2 a_{1} + a_{2} = 7, a_{1} + 3 a_{2} = 11.

Solving gives

a_{1} = 2

and

a_{2} = 3

. Therefore

{[v]}_{𝒜} = [\begin{matrix} 2 \\ 3 \end{matrix}] .

generating a unit column matrix

Given a vector space

V

with basis

𝒱 = {v 1, \dots, v_{k}}

, then for each element

i \in [k]

wam (v_{i}, 𝒱) = e_{i}

v_{i} = 0 v_{1} + \dots + 1 v_{i} + \dots + 0 v_{k}

therefore by the definition of

w a m

we have

w a m (v_{i}, 𝒱) = e_{i}

uniquely determined

Given a vector space

V

of dimension

k

we say that a vector

x

is uniquely determined, when there exists only one collection of constants

c_{1}, \dots, c_{k}

such that

x = \sum_{i = 1}^{k} c_{i} \cdot v_{i}

where each

v_{i}

is a basis element for the basis of

V

basis implies unique representation

suppose that

V

is a vector space and let

S

be a non-empty subset of

V

. Then

S

is a basis of

V

if and only if every vector

x \in V

can be represented uniquely as a linear combination of the vectors in

S

TODO

something

Let

T : V \to W

be a linear transformation between two vector spaces with

\dim (V) = k

\dim (W) = l

with

k, l \in ℤ^{+}

. Supposing that

{v_{1}, \dots, v_{k}}

and

{w_{1}, \dots, w_{l}}

are the respective bases, then

T : V \to W

is uniquely determined by the

l \cdot k

scalars used to express

T (v_{j})

for each

j \in [k]

in terms of

{w_{1}, \dots, w_{l}}

To show that the linear transformation is uniquely determined by these scalars, we will try to use the fact that elements in each vector space are already uniquely determined by their own constants and go from there.

Let $v_{j}$ be one of the basis vectors for $V$ , then consider $T (v_{j}) \in W$ since it's a vector in $W$ it can be written as a linear combination of the basis vectors in $W$ , so that $T (v_{j}) = \sum_{i = 1}^{l} a_{i} w_{i}$ .

Now given a generic $x \in V$ which is not necessarily a basis vector, we can represent it as follows $T (x) = T (\sum_{j = 1}^{k} c_{j} v_{j}) = \sum_{j = 1}^{k} c_{j} T (v_{j})$ recalling from our previosu paragraph, we can see that $\sum_{j = 1}^{k} (c_{j} \sum_{i = 1}^{l} a_{i} w_{i}) = \sum_{j = 1}^{k} \sum_{i = 1}^{l} c_{j} a_{i} w_{i}$ .

The lets us conclude that $T (x) = \sum_{j = 1}^{k} \sum_{i = 1}^{l} c_{j} a_{i} w_{i}$ and that $T$ is uniquely determined by these $l \cdot k$ constants

matrix representation of a transformation

Let

T : V \to W

be a linear transformation, then there exists a matrix

M_{T}

such that

wav (M_{T} wam (v)) = T v

for any

v \in V

To see what the matrix is, we can try to figure out what it's columns are.

Recall that we can extract the column of a matrix using the column extraction method discussed earlier

To be successful at that we need to generate a unit column matrix. We can do so by plugging in $v_{k} \in 𝒱$ into the above equation which yields: $T v_{k} = wav (M_{T} wam (v_{k}, 𝒱)) = wav (M_{T} e_{k}) = wav ({(M_{T})}_{|}, k})$

Thus $wam (T v_{k}) = {(M_{T})}_{|}, k}$ , so the columns of $M_{T}$ are $T v_{k}$ written as a column matrices. Graphically we have

M_{T} = [\begin{matrix} ↑ & ↑ & ↑ & ↑ \\ wam (T v_{1}) & wam (T v_{2}) & \dots & wam (T v_{k}) \\ ↓ & ↓ & ↓ & ↓ \end{matrix}]

Change of Basis Matrix

Let

V

be an

n

-dimensional vector space over

ℝ

, and let

𝒜 = (a_{1}, \dots, a_{n}), ℬ = (b_{1}, \dots, b_{n})

be ordered bases of

V

. The change of basis matrix from $𝒜$ to $ℬ$ , denoted

[ℬ \leftarrow 𝒜],

is the matrix satisfying

[ℬ \leftarrow 𝒜] {[x]}_{𝒜} = {[x]}_{ℬ}

for every

x \in V

Change of Basis Matrix Columns

Let

𝒜 = (a_{1}, \dots, a_{n})

and

ℬ = (b_{1}, \dots, b_{n})

be ordered bases of an

n

-dimensional vector space

V

. Then

[ℬ \leftarrow 𝒜] = [\begin{matrix} ↑ & ↑ & ↑ \\ {[a_{1}]}_{ℬ} & {[a_{2}]}_{ℬ} & \dots & {[a_{n}]}_{ℬ} \\ ↓ & ↓ & ↓ \end{matrix}] .

That is, the

j

-th column of

[ℬ \leftarrow 𝒜]

is the

ℬ

-coordinate vector of the

j

-th basis vector of

𝒜

Let

e_{j}

be the

j

-th vector in the standard basis

ℰ

ℝ^{n}

. Since

a_{j}

is the

j

-th vector of the basis

𝒜

{[a_{j}]}_{𝒜} = e_{j} .

By the definition of the change of basis matrix,

[ℬ \leftarrow 𝒜] {[a_{j}]}_{𝒜} = {[a_{j}]}_{ℬ} .

Substituting

{[a_{j}]}_{𝒜} = e_{j}

gives

[ℬ \leftarrow 𝒜] e_{j} = {[a_{j}]}_{ℬ} .

By matrix times standard basis vector is a column,

[ℬ \leftarrow 𝒜] e_{j}

is the

j

-th column of

[ℬ \leftarrow 𝒜]

. Therefore the

j

-th column is

{[a_{j}]}_{ℬ}

. Since this holds for every

j \in {1, \dots, n}

, the matrix is exactly

[\begin{matrix} ↑ & ↑ & ↑ \\ {[a_{1}]}_{ℬ} & {[a_{2}]}_{ℬ} & \dots & {[a_{n}]}_{ℬ} \\ ↓ & ↓ & ↓ \end{matrix}] .

Suppose that we have an ordered, linearly independent set

S : (s_{1}, \dots s_{k})

for some

k \leq n

of vectors in a finite dimensional vector space

V

, then it can be extended to a basis of

V

By fixing any new basis of

V

(TODO: prove that for any vector space there is always a basis that spans it)

b_{1}, \dots b_{n}

, then by concatenating it with

S

we obtain

(s_{1}, . . ., s_{k}, b_{1}, . . ., b_{n})

. Then for each

i \in [n]

(in order) (TODO: this is an algorithm), remove

v_{i}

from the ordered set iff

v_{i}

is in the span of all the earlier elements in the set. In particular, once we have checked and kept

n - k

of the

v - i

(TODO: say why that's guarenteed), we can discard the remaining

v_{i}

, leaving a basis:

(s_{1}, . . ., s_{k}, v_{i_{1}},, \dots v_{i_{n - k}})

Extending a Basis

Extend the ordered set

([\begin{matrix} - 2 \\ - 2 \\ 3 \\ 0 \end{matrix}], [\begin{matrix} - 4 \\ - 3 \\ 6 \\ 0 \end{matrix}])

to a basis of

ℝ^{4}

First of all note that these two vectors must be linearly independent, if they were dependent, then the by comparing the first component of these two vectors we would see that the second is twice the first, whereas comparing the second component would tell us that the second vector is $\frac{3}{2}$ times the first vector, which is a contradiction, so they must be linearly dependent.

Since the standard basis for $ℝ^{4}$ clearly spans it (by it's very definition), then we would also know that $([\begin{matrix} - 2 \\ - 2 \\ 3 \\ 0 \end{matrix}], [\begin{matrix} - 4 \\ - 3 \\ 6 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix}],)$ spans all of $ℝ^{4}$ , but cannot be a linearly indpenedent set because it would be impossible to have five linearly independent vectors in $ℝ^{4}$ (TODO: prove why),

Now we can use the casting out method to determine which of the column vectors are linearly dependent on the other vectors, we start by putting all the column vectors as the columns of a matrix and then row reduce, which yields

[\begin{matrix} 1 & 0 & 0 & - \frac{1}{2} & 10 & 0 \\ 0 & 1 & 0 & \frac{1}{4} & - \frac{29}{6} & 0 \\ 0 & 0 & 1 & 0 & \frac{2}{3} & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}],

By the casting out method, we know that since the fourth and fifth columns are non-pivot columns and therefore the vectors $[\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}]$ can be cast out, leaving us with the basis:

([\begin{matrix} - 2 \\ - 2 \\ 3 \\ 0 \end{matrix}], [\begin{matrix} - 4 \\ - 3 \\ 6 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix}],)