04. Bases

4.1 Spans and Spanning Sets

Linear Combination

Let $u_1,u_2,\cdots ,u_m\in V$ for some vector space over $\mathbf{F}$
A linear combination of $u_1,u_2,\cdots ,u_m$ is

$${\alpha }_1{u}_1+{\alpha }_2{u}_2+\cdots +{\alpha }_m{u}_m\text{ for some }{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_m\in \mathbf{F}$$

Link to original

Span

Let $u_1,u_2,\cdots ,u_m\in V$ for some vector space over $\mathbf{F}$
The span of $u_1,u_2,\cdots ,u_m$ is defined as

$$⟨u_1,\cdots ,u_m⟩:=\{{\alpha }_1{u}_1+\cdots +{\alpha }_m{u}_m:{\alpha }_1,\cdots ,{\alpha }_m\in \mathbf{F}\}$$

Also the smallest subspace of $V$ that contains $u_1,\cdots u_m$

AKA all the possible linear combinations of $u_1,u_2,\cdots ,u_m$

Link to original

Spans are a subspace of the Vector Space lemma

Let $u_1,u_2,\cdots ,u_m\in V$ for some vector space over $\mathbf{F}$ then

$$⟨u_1,u_2,\cdots ,u_m⟩\le V$$

Proof of Subspace Property

1. $0_V\in ⟨u_1,u_2,\cdots ,u_m⟩$
   Setting ${\alpha }_1={\alpha }_2=\cdots ={\alpha }_m=0$ we get

$$0_V=0u_1+0u_2+\cdots +0u_m$$

So $0_V\in ⟨u_1,u_2,,\cdots ,u_m⟩$
2) $\lambda v_1+v_2\in U$
Take $v_1,v_2\in U$ so suppose

$$v_1={\alpha }_1{u}_1+{\alpha }_2{u}_2+\cdots +{\alpha }_m{u}_m$$ $$v_2={\beta }_1{u}_1+{\beta }_2{u}_2+\cdots +{\beta }_m{u}_m$$

Then for $\lambda \in \mathbf{F}$

$$\lambda v_1+v_2=(\lambda {\alpha }_1+{\beta }_1)u_1+\cdots +(\lambda {\alpha }_m+{\beta }_m)u_m\in U$$

So by the subspace test $U\le V$

Link to original

Spanning Set

Let $V$ be a vector space over $\mathbf{F}$
If $S\subseteq V$ and $V=⟨S⟩$ then

$$S\text{ spans }V$$

in other words

$$S\text{ is a spanning set for }V$$

Also means every vector $v\in V$ can be written as a linear combination of the elements in $S$

Link to original

Row Space ( $m\times n$ Matrix)

$\mathrm{Row}(A)$: Span of the rows of a matrix
With $\mathrm{Row}(A)\le R^n$

Link to original

Column Space

$\mathrm{col}(A)$: Span of the columns of the matrix
With $\mathrm{col}(A)\le {\mathbb{R}}_{\mathrm{col}}^m$

Link to original

---

4.2 Linear Independence

Linearly Independent

Let $V$ be a vector space over $\mathbf{F}$
$v_1,v_2,\cdots ,v_m\in V$ are linearly independent if the only solution to

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m=0_V\text{ where }{\alpha }_1,\cdots ,{\alpha }_m\in \mathbf{F}$$

is

$${\alpha }_1={\alpha }_2=\cdots ={\alpha }_m=0$$

Otherwise the vectors are linearly dependent

Link to original

Subsets of Vector Spaces being Linearly Independent

Let $S\subseteq V$ then
$S$ is linearly independent of every finite subset of $S$ is linearly independent

Link to original

Comparing Coefficients (of Linearly Independent Vectors)

Let $S=\{v_1,\cdots ,v_m\}$ where $S\subseteq V$, where $V$ is a vector space
Suppose

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

for some ${\alpha }_1,{\beta }_1,\cdots ,{\alpha }_m,{\beta }_m\in \mathbf{F}$

Then ${\alpha }_i={\beta }_i$ for $1\le i\le m$

Proof

Rearrange the equation to

$$({\alpha }_1-{\beta }_1)v_1+({\alpha }_2-{\beta }_2)v_2+\cdots +({\alpha }_m-{\beta }_m)v_m=0_V$$

As the vectors $v_1,\cdots ,v_m$ are linearly independent then

$$\begin{array}{rl}{\alpha }_1-{\beta }_1& =0\\ {\alpha }_2-{\beta }_2& =0\\ ⋮& \\ {\alpha }_m-{\beta }_m& =0\end{array}$$

Hence

$${\alpha }_1={\beta }_1,{\alpha }_2={\beta }_2,\cdots ,{\alpha }_m={\beta }_m$$

Link to original

Useful Examples of Linearly Independent Sets

1. $S=\{1,i\}$ with $V=\mathbb{C}$, the set of complex numbers
2. $S=\{1,x,x^2,\cdots \}$ with $V=\mathbb{R}[x]$, the vector space of polynomials with real coefficients

Link to original

Extending a linearly independent set lemma

Let $v_1,v_2,\cdots ,v_m$ be linearly independent elements of a vector space $V$
Let $v_{m+1}\in V$ then

$$v_1,v_2,\cdots ,v_m,v_{m+1}\text{ are linearly independent }⟺v_{m+1}\notin ⟨v_1,\cdots ,v_m⟩$$

Proof

1. Proving $⟸$
   Suppose $v_{m+1}\notin \{v_1,\cdots ,v_m\}$
   Take ${\alpha }_1,\cdots ,{\alpha }_{m+1}\in \mathbf{F}$ such that

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m+{\alpha }_{m+1}{v}_{m+1}=0_V$$

Then for ${\alpha }_{m+1}\ne 0$

$$v_{m+1}=-\frac{1}{{\alpha }_{m+1}}({\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m)$$

So $v_{m+1}\in V$ however this is a contradiction so ${\alpha }_{m+1}=0$
Then as $v_1,v_2,\cdots ,v_m$ are linearly independent then the solution to

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m=0_V$$

Is ${\alpha }_1={\alpha }_2=\cdots ={\alpha }_m=0$
So $v_1,v_2,\cdots ,v_m,v_{m+1}$ are linearly independent

2. Proving $⟹$
   Suppose $v_1,v_2,\cdots ,v_m,v_{m+1}$ are linearly independent then
   Suppose $v_m\in ⟨v_1,\cdots ,v_m⟩$ then there exists ${\alpha }_1,\cdots ,{\alpha }_m$ such that

$${\alpha }_1{v}_1+{\alpha }_2{v}_2+\cdots +{\alpha }_m{v}_m=v_{m+1}$$

Rearranging this to get

$${\alpha }_1{v}_1+{\alpha }_2{v}_2+\cdots +{\alpha }_m{v}_m-v_{m+1}=0$$

However as $v_1,v_2,\cdots ,v_{m+1}$ are linearly independent then there exists no solution to the above equation
Hence $v_m\notin ⟨v_1,\cdots ,v_m⟩$

Link to original

---

4.3 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

Link to original

Note the basis of a vector space is not unique!

Link to original

Examples of infinite-dimensional vector spaces

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

Link to original

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$

Link to original

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

Link to original

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$

Link to original

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\}$

Link to original

Property of Row Space

Let $A=(a_{ij})$ be a $n\times n$ matrix and $B=(b_{ij})$ be a $k\times m$ matrix
Let $R=(r_{ij})$ be the RRE form of $A$ by EROs

1. The non-zero rows of $R$ are independent
2. Rows of $R$ are linear combinations of the rows of $A$
3. $\mathrm{Row}(BA)$ is contained in $\mathrm{Row}(A)$
4. If $k=m$ and $B$ is invertible then $\mathrm{Row}(BA)=\mathrm{Row}(A)$
5. $\mathrm{Row}(R)=\mathrm{Row}(A)$

Proof

• (1) Denote the non-zero rows of $R$ as ${\mathbf{r}}_1,\cdots ,{\mathbf{r}}_r$ and suppose that

$$c_1{\mathbf{r}}_1+c_2{\mathbf{r}}_2+\cdots +c_r{\mathbf{r}}_r=0$$

Suppose that the leading $1$ or $r_1$ appears in the $j$th column then

$$c_1+c_2{r}_{2j}+c_3{r}_{3j}+\cdots +c_r{r}_{rj}=0$$

However as $R$ is in $\mathrm{RRE}$ form then each of $r_{2j},r_{3j},\cdots ,r_{rj}$ are $0$ as they are entries under a leading $1$ by RRE Form Properties
Hence

$$c_1=0$$

Similarly by focusing on the column which contains the leading $1$ of ${\mathbf{r}}_2$ then likewise

$$c_2=0$$

Repeat this for the rest
Then as $c_i=0$ for each $1\le i\le r$ then the non-zero rows ${\mathbf{r}}_i$ are independent

• (3) Remember that

$$(i,j)\text{th entry of }BA=\sum _{s=1}^m{b}_{is}{a}_{sj}(1\le i\le k,1\le j\le n)$$

Hence the $i$th row of $BA$ is the row vector

$$\left(\sum _{s=1}^m{b}_{is}{a}_{s1},\sum _{s=1}^m{b}_{is}{a}_{s2},\cdots ,\sum _{s=1}^m{b}_{is}{a}_{sn}\right)=\sum _{s=1}^m{b}_{is}\underset{s\text{th row of }A}{\underbrace{(a_{s1},a_{s2},\cdots ,a_{sn})}}$$

Thus it is a linear combination of the rows of $A$ so every row of $BA$ is in $\mathrm{Row}(A)$
As a vector in the row space $\mathrm{Row}(BA)$ is a linear combination of the rows of $BA$ then they are a linear combination of the rows of $A$ hence
$\mathrm{Row}(BA)$ is contained in $\mathrm{Row}(A)$

• (2) By (3) as $R=BA$ with $B=E_k\cdots E_1$for some Elementary Matrices which are invertible
  Hence $\mathrm{Row}(R)$ is contained in $\mathrm{Row}(A)$
• (4) By (3) as $\mathrm{Row}(A)=\mathrm{Row}(B^{-1}(BA))$ is contained in $\mathrm{Row}(BA)$ and by $(3)$ $\mathrm{Row}(BA)$ is contained in $\mathrm{Row}(A)$ so $\mathrm{Row}(A)=\mathrm{Row}(BA)$

Link to original

Test for Independence corollary

Let $A$ be a $m\times n$ matrix

$$\mathrm{RRE}(A)\text{ has a }0\text{ row }⟺\text{ rows of }A\text{ are dependent}$$

Proof

We know that $\mathrm{RRE}(A)=BA$, where $B$ is a product of EROs so $B^{-1}$ exists
Suppose the $i$th row of $BA$ is $0$
Then

$$0=\sum _{s=1}^m{b}_{is}\cdot (s\text{th, row of A})$$

Where $b_{is}$ are the entries along the $i$th row of $B$ which cannot all be zero (as $B$ is invertible)
Hence rows of $A$ are linearly dependent

Link to original

Test for a Spanning Set corollary

Let $A$ be a $m\times n$ matrix.
Then the rows of $A$ span ${\mathbb{R}}^n$ if and only if

$$\mathrm{RRE}(A)=\left(\begin{array}{c}{I}_n\\ \\ 0_{(k-n)n}\end{array}\right)$$

Proof

1. Let ${\mathbf{r}}_1,{\mathbf{r}}_2,\cdots ,{\mathbf{r}}_m$ be the rows of $A$ in ${\mathbb{R}}^n$ and suppose they span ${\mathbb{R}}^n$
   By Property of Row Space then the row space is invariant under EROs
   If the $i$th column of $\mathrm{RRE}(A)$ does not contain a leading $1$ then ${\mathbf{e}}_i$ would not be in the row space
   Consequently every column contains a leading $1$ and so

$$\mathrm{RRE}(A)=\left(\begin{array}{c}{I}_n\\ \\ 0_{(k-n)n}\end{array}\right)$$

2. Conversely if $\mathrm{RRE}(A)$ has the above form then the rows of $\mathrm{RRE}(A)$ are spanning and hence so the original rows ${\mathbf{r}}_1,{\mathbf{r}}_2,\cdots ,{\mathbf{r}}_m$ are also spanning

Link to original

---

4.4 Addendum

Uniqueness of RRE Form

The reduced row echelon form of a $m\times n$ matrix $A$ is unique

Proof

Link to original

Row Rank (or Rank)

Row Rank or Rank of matrix $A$ is the number of non-zero rows in $\mathrm{RRE}(A)$
$\to \text{Notation: }\mathrm{Rank}(A)$

By Uniqueness of RRE Form then row rank is well-defined

Link to original

Determining whether a system is consistent using row-rank / rank

Let $(A\mid \mathbf{b})$ be the matrix representing the linear system $A\mathbf{x}=\mathbf{b}$

$$\text{System is consistent}⟺\mathrm{Rank}(A\mid B)=\mathrm{Rank}(A)$$

Proof

Note this result was already demonstrated for systems in RRE form during the proof
Suppose that $\mathrm{RRE}(A)=PA$ where $P$ is a product of Elementary Matrices that reduce $A$
If $E$ is an elementary matrix then $\mathrm{RRE}(EA)=\mathrm{RRE}(A)$ by the uniqueness of $\mathrm{RRE}$ form
Hence

$$\mathrm{Rank}(EA)=\mathrm{Rank}(A)$$

Then

$$\begin{array}{rl}\mathrm{Rank}(A\mid \mathbf{b})=\mathrm{Rank}(A)& ⟺\mathrm{Rank}(PA\mid P\mathbf{b})=\mathrm{Rank}(PA)\\ & ⟺\text{the system }PA\mathbf{x}=P\mathbf{b}\text{ is consistent}\\ & ⟺\text{the system }A\mathbf{x}=\mathbf{b}\text{ is consistent}\end{array}$$

as the set of solutions to $A\mathbf{x}=\mathbf{b}$ is unaffected by EROs

Link to original

Classifying the solutions of a Linear System

Let $A$ be a $m\times n$ matrix and $\mathbf{b}$ in ${\mathbb{R}}_{\mathrm{col}}^m$
1)

$$\text{no solutions}⟺(0,0,\cdots ,0\mid 1)\text{ is in }\mathrm{Row}(A\mid \mathbf{b})$$

$$\text{unique solution}⟺\mathrm{Rank}(A)=n$$

Also requires $m\ge n$

$$\text{infinitely many solutions}⟺\mathrm{Rank}(A)<n$$

Set of solutions is a $n\text{-}\mathrm{Rank}(A)$ parameter familyx

Link to original