20 - Bases

Basis of vector space $V$

Basis of $V$ is a linearly independent, spanning set

If the basis is finite then $V$ is finite-dimensional

Plural of basis is bases

Note the basis of a vector space is not unique!

Examples of infinite-dimensional vector spaces

1. Vector space of real polynomials
2. Vector space of real sequences

---

Standard Basis (Canonical Basis) of ${\mathbb{R}}^n$

For $1\le i\le n$ define ${\mathbf{e}}_i$ be the row vector with coordinate $1$ in the $i$th entry and $0$ elsewhere

Example - $n=5$ and $i=1,2,4$

$$\begin{array}{rl}{\mathbf{e}}_1& =(1,0,0,0,0)\\ {\mathbf{e}}_2& =(0,1,0,0,0)\\ {\mathbf{e}}_4& =(0,0,0,1,0)\end{array}$$

Proof

1. Linear Independence
   If we consider

$${\alpha }_1{\mathbf{e}}_1+\cdots +{\alpha }_n{\mathbf{e}}_n=0$$

Looking at the $i$th entry we see that ${\alpha }_i=0$ for all $1\le i\le n$
Hence ${\mathbf{e}}_1,\cdots ,{\mathbf{e}}_n$ are linearly independent.

2. Spanning Set
   For any $({\alpha }_1,\cdots ,{\alpha }_n)\in {\mathbb{R}}^n$ then we can write

$$({\alpha }_1,\cdots ,{\alpha }_n)={\alpha }_1{\mathbf{e}}_1+\cdots +{\alpha }_n{\mathbf{e}}_n$$

Hence ${\mathbf{e}}_1,\cdots ,{\mathbf{e}}_n$ spans ${\mathbb{R}}^n$

Standard Basis of Vector Space $V=M_{m\times n}(\mathbf{F})$

Standard basis of $V$ is the set

$$\{E_{ij}:1\le i\le m,1\le j\le n\}$$

Where $E_{ij}$ has a $1$ at the $(i,j)$th entry and $0$ elsewhere

Spanning Property

For matrix $A=(a_{ij})$ then

$$A=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{E}_{ij}$$

This is a unique expression of $A$ and a linear combination of the standard basis

---

Characterising a Basis via Linear Combinations

Let $V$ be a vector space over $\mathbf{F}$ and $S=\{v_1,v_2,\cdots ,v_n\}\subseteq V$

$$S\text{ is a basis of }V⟺\forall v\in V,v\text{ has a unique expression as a linear combination of elements in }S$$

Proof

1. Prove $⟹$
   Let $S$ be a basis of $V$ and take $v\in V$
   Since $S$ spans $V$, there exists ${\alpha }_1,\cdots ,{\alpha }_n\in F$ such that

$$v={\alpha }_1{v}_1+\cdots +{\alpha }_n{v}_n$$

As $S$ is linearly independent then by Unique Coefficients of Linear Combinations then ${\alpha }_1,\cdots ,{\alpha }_n$ are unique

2. Prove $⟸$
   Suppose that every vector $v\in V$ has a unique expression as a linear combination of elements of $S$
   • $S$ spanning set: by definition $S$ spans $V$ as every vector can be written as a linear combination
   • $S$ linearly independent: By uniqueness $0_V=0v_1+0v_2+\cdots +0v_n$ (and is the only solution) so it is linearly independent
     Hence $S$ is a basis for $V$

Coordinates

Given a basis $S=\{v_1,v_2,\cdots v_n\}$ of $V$ then every $v\in V$ can be uniquely written as

$$v={\alpha }_1{v}_1+\cdots +$$

Where $({\alpha }_1,\cdots ,{\alpha }_n)$ is known as the coordinate of $v$ with respect to the basis $\{v_1,v_2,\cdots ,v_n\}$

---

Bases of a finite-dimensional vector space are finite (and same size)

Let $V$ be a finite-dimensional vector space
All bases of $V$ are finite and of the same size

Proof

Since $V$ is finite-dimensional and $V$ has a finite basis $B$
By 05 - Size Inequality for Independent vs Spanning Sets then
Any finite linearly independent subset of $V$ has size at most $|B|$

Given another basis $S$ of $V$ (also linearly independent) then every finite subset of $S$ is linearly independent
So $S$ is finite and $|S|\le |B|$

But $B$ is linearly independent and $S$ is spanning so $|B|\le |S|$

Basis of Row Space

The non-zero rows of a matrix in RRE form

---

Spanning Sets contain a basis

Let $V$ be a vector space over $\mathbf{F}$ and $S$ be a finite spanning set then

$$S\text{ contains a basis }$$

Proof

Let $S$ be a finite spanning set for $V$
Take $T\subseteq S$ such that $T$ is linearly independent (and hence $T$ is the largest such set)

Suppose for contradiction that $⟨T⟩\ne V$
Since $⟨S⟩=V$ then there exists $v\in S\setminus ⟨T⟩$

By Expansion of Linearly Independent Sets,

$$T\cap \{v\}\text{ is linearly independent }\text{ and }T\cap \{v\}\subseteq S$$

With

$$|T\cap \{v\}|>|T|$$

Which is a contradiction of the maximality of $T$, so $T$ spans $V$ and hence linearly independent and thus a basis.

Linearly Independent Sets are a subset of a Basis

Let $V$ be a finite-dimensional vector space over $\mathbf{F}$
Let $S$ be a linearly independent set
Then

$$\text{there exists basis }B\text{ such that }S\subseteq B$$

Proof

If $⟨S⟩=V$ then done as $S$ is linearly independent and spanning so a basis with $S\subseteq S$

If $⟨S⟩\ne V$ then extend $S$ to $S_1=S\cup \{u_1\}$ where $u_1\in V\setminus ⟨S⟩$ (a larger linearly independent set)

• If $⟨S_1⟩=V$ then $S_1$ is a basis with $S\subseteq S_1$
• If not then we repeat this until $⟨S_k⟩=V$ (so that $S_k$ is a basis)
• This cannot continue infinitely as the maximum linearly independent subset of $V$ contains at most $\dim V$ elements so $k\le \dim V$

Alternate Definition of a Basis (using Linearly Independency)

Maximal Linearly Independent Subset of a finite-dimensional vector space

Proof

Let $S$ be a maximal linearly independent subset of a finite-dimensional vector space $V$
If $⟨S⟩\ne V$ then by Extending a linearly independent set with

$$S_1=S\cup \{u_1\}\text{ where }{u}_1\in V\setminus ⟨S⟩$$

which is still linearly independent

This contradicts the maximality of $S$ so $⟨S⟩=V$

Alternate Definition of a Basis (using Span)

Minimal Spanning subset of a finite-dimensional vector space

Proof

Let $S$ be a minimal spanning set of a finite-dimensional vector space $V$

If $S$ is not linearly independent then there exists

$$v\in S\text{ that is a linear combination of }S\setminus \{v\}$$

However $S\setminus \{v\}$ is linearly independent
As shown in Extension of a linearly independent set then $S\setminus \{v\}$ is still spanning
This contradicts the minimality of $S$ hence $S$ is a basis

Finding a basis for a finite set of vectors in ${\mathbb{R}}^n$

Suppose the set of vectors $S=\{v_1,v_2,\cdots ,v_m\}$
Define

$$A=\left(\begin{array}{cccc}\uparrow & \uparrow & & \uparrow \\ v_1& v_2& \cdots & v_m\\ \downarrow & \downarrow & & \downarrow \end{array}\right)$$

So $⟨S⟩=\mathrm{Row}(A)$
As applying EROs does not change row space then

$$\mathrm{Row}(A)=\mathrm{Row}(\mathrm{RRE}(A))$$

Hence the basis of $⟨S⟩$ is the

$$\text{non-zero rows of }\mathrm{RRE}(A)$$