Basis, Dimensions of Vector Spaces.

$\newcommand{\br}{\\}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\P}{\mathbb{P}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\L}{\mathcal{L}}$ $\newcommand{\spa}[1]{\text{span}(#1)}$ $\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\emptyset}{\varnothing}$ $\newcommand{\otherwise}{\text{ otherwise }}$ $\newcommand{\if}{\text{ if }}$ $\newcommand{\union}{\cup}$ $\newcommand{\intercept}{\cap}$ $\newcommand{\abs}[1]{| #1 |}$ $\newcommand{\pare}[1]{\left$$#1\right$$}$ $\newcommand{\t}[1]{\text{ #1 }}$ $\newcommand{\head}{\text H}$ $\newcommand{\tail}{\text T}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\nullity}[1]{\text{nullity}(#1)}$ $\newcommand{\rank}[1]{\text{rank}(#1)}$ $\newcommand{\oto}{\text{ one-to-one }}$ $\newcommand{\ot}{\text{ onto }}$ $\newcommand{\Vcw}[2]{\begin{pmatrix} #1 \br #2 \end{pmatrix}}$ $\newcommand{\Vce}[3]{\begin{pmatrix} #1 \br #2 \br #3 \end{pmatrix}}$ $\newcommand{\Vcr}[4]{\begin{pmatrix} #1 \br #2 \br #3 \br #4 \end{pmatrix}}$ $\newcommand{\Vct}[5]{\begin{pmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{pmatrix}}$ $\newcommand{\Vcy}[6]{\begin{pmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{pmatrix}}$ $\newcommand{\Vcu}[7]{\begin{pmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{pmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Mqr}[4]{\begin{bmatrix} #1 & #2 & #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqt}[5]{\begin{bmatrix} #1 & #2 & #3 & #4 & #5 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mrq}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Mtq}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Mww}[4]{\begin{bmatrix} #1 & #2 \br #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mwe}[6]{\begin{bmatrix} #1 & #2 & #3\br #4 & #5 & #6 \end{bmatrix}}$ $\newcommand{\Mew}[6]{\begin{bmatrix} #1 & #2 \br #3 & #4 \br #5 & #6 \end{bmatrix}}$ $\newcommand{\Mee}[9]{\begin{bmatrix} #1 & #2 & #3 \br #4 & #5 & #6 \br #7 & #8 & #9 \end{bmatrix}}$
Definition: Basis

$V/F$, a subset $\beta\subseteq V$ is called a basis of $V$ if

1. $\beta$ generates $V$, i.e. $\spa{\beta}=V$.
2. $\beta$ is linearly independent.
Example

Prove that $\beta=\set{(1,0), (0,1)}$ is a basis of $\R^2$.

Proof [expand]
1. need to prove $\beta$ generates $V$.
$\forall (a,b) \in \R^2,$
$(a, b)=a(1,0)+b(0,1)$ i.e. $\spa{\beta}=\R^2$.

2. need to prove $\beta$ is linearly independent.
$x(1,0) + y(0,1) = (0,0)$
$(x,y) = (0,0)$
$x = 0, y = 0$

$\therefore$ $\beta$ is a basis of $\R^2$.

Example

$e_1=(1,0,0,…)$, $e_2=(0,1,0, …)$, $e_3=(0,0,1, …)$,
$e_n=(0,0,…,1, 0, …)$.
Is $S= \set{e_1, e_2, e_3, …}$abasis of $\R^\infty$?

Proof [expand]

No. it is not.

Let $e = (1, 1, 1, 1, …), e \in \R^\infty$.

$e \notin \spa{S}$, but $e \in \R^\infty$.

$\spa{\beta} \neq R^\infty$ i.e. $\spa{\beta}$ cannot generate $\R^\infty$.

Hence, $\beta$ is not a basis of $\R$.

Remarks

$R^\infty$ does have a basis, although we don’t know what it is.
Every vector space have a basis.

Example: $\R^n/\R$

$e_1=(1,0,0,…)$, $e_2=(0,1,0, …)$, $e_3=(0,0,1, …)$,
$e_n=(0,0,…,1, …, 0)$.
$S= \set{e_1, e_2, e_3, …, e_n}$ is a basis of $\R^n$.

Proof [expand]
1. need to prove that $S$ generates $\R^n$.
$(a_1, a_2, …, a_{n}) \in \R^n$
$(a_1, a_2, …, a_{n}) = a_1e_1 + a_2e_2 + … + a_{n} e_{n}$
$\spa{S} = R$ i.e. $S$ generates $\R^n$.

2. need to prove $S$ is linearly independent.
$a_1e_1 + a_2e_2 + … + a_{n} e_{n} = 0$
$(a_1, a_2, …, a_{n}) = 0$
$a_i = 0, i = 1, 2, …, n$ $\therefore, S$ linearly independent.

Example: $\P\_n(X)/\R$

$\beta = \set{1, x, x^2, …, x^n}$ is a basis of $P_n(X)$ over $\R$.

Example: $\P(X)/\R$

Prove that $\beta = \set{1, x, x^2, …}$ is a basis of $\P(x) / \R$.

1. need to prove that $\beta$ generates $\P(x)$.
$a_0 + a_1x + a_2x^2 + … + a_{n} x^{n} \in \P(x)$ $\spa{\beta} = \P(x)$

2. need to prove that $\beta$ is linearly independent.
To prove an infinite set is linearly independent, we only need to prove its every finite subset’s only solution is the trivial representation.

Remarks: the basis of $\set{0}/F$

The empty set $\emptyset$ is the basis of $V=\set{0}/F$.

Proof [expand]
1. need to prove that $\emptyset$ generates $\set{0}$.
Trivial. It is defined that $\spa{\emptyset} = \set{0}$.
2. need to prove that $\emptyset$ is linearly independent.
Trivial.
Theorem 1.8: Uniqueness of Linear Combination With Bases

$\beta \subseteq V$,
$\beta$ is a basis of $V \iff$ $\forall v \in V, \exists v_1, v_2, …, v_n \in \beta$ and unique $a_1, a_2, …, a_n \in F$ s.t. $$v = \sum^n_{i=1}a_iv_i$$

Proof [expand]

$\implies$

$\spa{\beta} = V$, since $\beta$ is a basis of $V$.

Assume that for $v\in V, \exists a_1, a_2, …, a_n, b_1, b_2, …, b_n$ s.t.

$$v = \sum_{i=1}^na_iv_i= \sum_{i=1}^nb_iv_i$$

then we have

$$\sum_{i=1}^n(a_i-b_i)v_i= 0$$

$\because \beta$ linearly independent $\therefore a_i-b_i = 0, \forall i = 1 … n$.

$\therefore \forall i, a_i=b_i$, the coefficients are unique.

$\impliedby$

1. need to prove $\spa{\beta} = V$.
Since $\forall v \in V, v \in \spa{\beta}, V\subseteq \spa{\beta}$.
$\beta \subseteq V \implies \spa{\beta} \subseteq V$.
$\therefore V = \spa{\beta}$.

2. need to prove $\beta$ is linearly independent.
Choose $v = 0$, then $\forall v_1, v_2, …, v_k (k \leq n)$, there exist unique $a_1, a_2, …, a_k$ s.t.
$$a_1v_1 + a_2v_2 + … + a_kv_k = 0$$
then $a_i$ must be all zero. Hence $\beta$ is linearly dependent.

$\therefore$ by definition, $\beta$ is a basis of $V$.

Theorem 1.9: Deletion Theorem

$V/F, S$ is a finite generating subset of $V$. Then $\exists T \subseteq S, T$ is a basis of $V$.

Proof [expand]

case 1: If $S=\emptyset$ or $S= \set{0}$, then $\spa{S} = \set{0} = V.$

Then $\emptyset \subseteq S$ is the basis of $V = \set{0}, T = \emptyset.$

case 2: If $S \neq \emptyset$ and $S \neq \set{0}$, then $\exists v_1 \in S$, s.t. $v_1 \neq 0, \set{v_1}$ linearly independent.

Step 1: Is $\spa{{v_1}} = V$?

If yes, then stop and set $T=\set{v_1}$.

Otherwise, we claim that $S \setminus \spa{\set{v_1}} \neq \emptyset$

Indeed $S\setminus \spa{\set{v_1}} \neq \emptyset$.

Assume that $S\setminus \spa{\set{v_1}} = \emptyset$.

then $S \subseteq \spa{v_1}$

then $\spa{S} \subseteq \spa{v_1}$

then $V \subseteq \spa{v_1}$

$v_2\in V \setminus \spa{\set{v_1}}$. Thus $\set{v_1,v_2} = \set{v_1}\cup\set{v_2}$ linearly independent by Theorem 1.7.

Step 2: check if $\spa{\set{v_1, v_2}} = V$? If yes, then stop… otherwise ….

Repeat this way after finitely many steps (since S is a finite) we will get a set $T=\set{v_1, v_2, …, v_k}$ s.t. $T$ is linearly independent $\subset S$ and $\spa{T} = V$.

Theorem 1.10: Replacement Theorem

Let $V/F$ and $\beta = \set{v_1, v_2, …, v_n}$ be a basis of $V$.

Let $v \in V$ be a non-zero vector and $v=c_1v_1 + c_2v_2 + … + c_jv_j + … + a_nv_n$ s.t. $c_j \neq 0$ Then $\set{v_1, v_2, …, v_{j-1}, v, v_{j+1}, …, v_n}$ is a basis of $V$. i.e. the $j$th vector of $\beta$ can be replaced by $v$.

Proof [expand]

Denote $\set{v_1, v_2, …, v_{j-1}, v, v_{j+1}, …, v_n}$ by $\beta’$.

want to prove: $\spa{\beta’} = V, \beta’$ is linearly independent.

let $u \in V, since \beta = \set{v_1, v_2, …, v_j, …, v_n}$ is a basis of $V, \exists a_1, a_2, a_n \in F$ s.t. $u = \set{v_1, v_2, …, v_{j} …, v_n}$

We are given that $v = c_1v_1+ c_2v_2+ …+ c_jv_j, …+ c_nv_n$, and $c_j \neq 0$

Solve for $v_j$: $c_jv_j = c_1v_1 + … + c_{j-1}v_{j-1} -v + c_{j+1}v_{j+1} + … + c_nv_n$

$\because c_j \neq 0, \frac1{c_j}$ exists

$v_j = \sum^n_{i=1}(-\frac{-c_i}{c_j}v_i + \frac{1}{c_j} v) (i\neq j)$

$u = \sum^n_{i=1}a_iv_i + \sum^n_{i=1}(-\frac{-c_i}{c_j})a_jv_i + \frac{1}{c_j} a_jv (i\neq j)$

$u = \sum^n_{i=1}(a_i-\frac{-c_i}{c_j}c_i)v_i + \frac{1}{c_j} v (i\neq j)$

$b_1v_1 +b_2v_2 + … + b_{j-1}v_{j-1} + bv + b{j+1}v_{j+1} + … + b_nv_n = 0$b_1v_1 +b_2v_2 + … + b_{j-1}v_{j-1} + b(c_1v_1 + … + c_nv_n) + b{j+1}v_{j+1} + … + b_nv_n = 0

$(b_1 + bc_1)v_1 +(b_2 + bc_2)v_2 + … + (b_{j-1} + bc_{j-1})v_{j-1} + bc_jv_j + …+ (b_n + bc_n) v_n = 0 (c_j \neq 0)$

since $\beta = \set {v_1, v_2, …, v_j, …, v_n}$ is a basis. It is linearly dependent.

$\therefore b_c_j = 0 \implies b = 0,c ….. lol, cant catch up Example:$\R^3\beta= \set{e_1,e_2,e_3}$, standard basis.$u = (-1, 0, \frac12) = -1e_1 + 0e_2+ \frac12 e_3\beta’ = \set{u, e_2, e_3}$is a basis. Corollary 1: Of Theorem 1.10$V/F, V$is finite-dimensional, Then any two basis of$V$has exactly same number of elements, namely,$\dim V$. Proof [expand] let$\beta = \set{v_1, v_2, …, v_n}$and$\gamma = \set{u_1, u_2, …, u_n}$be two basis of$V$. need to prove$\abs{\beta} \geq \abs{\gamma}$and$\abs{\gamma} \geq \abs{\beta}u_1 \neq 0$write$u_1 = a_1v_1 + a_2v_2 + … + a_mv_m$one of the$a_i$is non-zero without loss of generality we may assume that$a_1 \neq 0$. Then by the replacement theorem,$\set{v_1,v_2, …, v_n}$is a basis of$V$.$\delta_1 = \set{u_1, v_2, v_3, …, v_m}$is a basis of V. write$u_2 \in \delta$is a linear combination from$\delta$, i.e.$u_2 = b_1u_1 + b_2v_2 + b_3v_3 + … = b_mv_mu_2 \neq 0$Claim At least that one of$b_2, b_3, …, b_m$is non-zero If not, then assume they are all zeor i.e. b_2=b_3=…= b_m =0 Then u_2= b_1u_1 =$\set{u_1, u_2}$is linearly dependent. This is a contradiction since \delta is a basis if$b_i \neq 0$Aussume W.L.G. that$b2 \neq = 0$. Then by Reprlacement theorem applied to$\delta_1, \delta_2 = \set{u_1, u_2, v_3, v_n, …, v_m}$is a basis. Continue this way until$\set{u_1, u_2, u_3, …, u_n, v_{n+1}, v_{n+2}, …, v_m}$Similarly,$\abs{m}\leq n$Definition: Dimensions of Vector Spaces$V/F$. If$V$is generated by a finite subset, then$V$is called a finite-dimensional vector space. In this case the number of vectors in a basis of$V$is called the dimension of$V$denoted by$\dim V$. If$V$is NOT a finite-dimensional vector space, or alternatively if there exists an infinite linearly independent subset$S$of$V$, i.e.$\abs{S} = \infty$and$S$is linearly independent, Then$V$is called an infinite-dimensional vector space, and we write$\dim V = \infty$. Example:$P(x) / \R\beta = \set{1, x, x^2, x^3, …}\dim_\R \P(x) = \infty$Example:$\R^\infty/\R\dim_\R \R^\infty = \infty$Example:$\R^n/\Re_1 = (1, 0, …, 0)e_2 = (0, 1, …, 0)e_n = (0, 1, …, n)\beta = \set{e_1, e_2, …, e_n}, \dim_\R R^n = n$. Example:$M\_{m\times n}(\R)\dim_\R M_{m\times n} = mn$Example:$W \subseteq M\_{2\times 2}(\R)W = \set{A \in M_{2\times 2}(\R) | tr(A) = 0}\dim_\R W = 3$Example:$\R/\R\dim_\R \R = 1$In fact,$\dim_F F = 1$Example:$\C/\R\dim_\C \R = 2$Example:$\C^2/\R$1.$V = \C^2, \F = \C, \dim_\C \C^2 = 1\beta_1 = \set{(1, 0), (0, 1)}/\C$2.$V = \C^2, \F = \R, \dim_\R \C^2 = 2\beta_2 = \set{(1, 0), (i, 0), (0, 1), (0, -i)}/\C$3.$V = \C^n, \F = \R, \dim_\R \C^2 = 2n$Remarks:$\R/\Q\dim_\Q \R = \infty$(will be useful in MATH 131A) Corollary 2: Of Theorem 1.9 & 1.10 Let$V$be a$n$dimension vector space over a field$F$. i.e.$\dim V = n$1. (a) Any finite generating set of$V$must contain at least$n$elements.$\forall S \subseteq V, \spa{S} = V \implies \abs{S} \geq n.$(b) Any finite generating set of$V$containing exactly$n$elements is a basis.$\forall S \subseteq V, \spa{S} = V, \abs{S} = n \implies S$is a basis of$V$. 2. Any linearly independent subset of$V$containing exactly$n$elements is a basis.$\forall S \subseteq V, S$is linearly independent,$\abs{S} = n \implies S$is a basis of$V$. 3. Every linearly independent subset of$V$can be extended to a basis of$V$. Proof [expand] Let$S$be a finite set and$\spa{S} = V$. On the contrary, assume that$\abs{S} < n$. Since$S$is finite and$\spa{S} = V$, by possibly remaining same vector from$S$, let$T$be a subset of$S$s.t.$T$is a basis. (theorem 1.9)$\dim V = \abs{T} \leq \abs{S} < n = \dim V$. Contradiction.$\therefore \abs{S} \geq \dim V. $Proof [expand]$\abs{S} = n$and$\spa{S} = V$. We try to prove that$S$is not a basis. On the contrary assume that$S$is not a basis. Then,$S$must be linearly dependent. Let$T \subset S$s.t.$T$is a basis. Then$\dim V = \abs{T} < \abs{S} = n = \dim{V}$. Contradiction.$\therefore S $must be a basis. Proof [expand] Let$S$be a linearly independent,$\abs{S} = n = \dim V$. Let$\beta = \set{v_1, v_2, …, v_n}$be a basis of$V$. Let$S = \set{u_1, u_2, …, u_n}$. Since$S$is linearly independent.$u_i \neq 0, \forall i = 1, 2, …, n$. Then by theorem 1.10, we can replace$v_1, v_2, v_3, …, v_n$with$u_1, u_2, …, u_n$one by one.$\therefore u_1, u_2, …, u_n$is a basis. Proof [expand] Let$S = {v_1, v_2, …, v_k}$be a linearly independent set in$V$. if$\spa{S} = V$, then$S$is already a basis. (definition of basis) If not, there exist a vector$w_{k+1} \in V \setminus S$s.t.$T_{k + 1} = S \cup \set{w_{k+1}}$is linearly independent. Check if$\spa{T_{k+1}} = V$? If yes, then stop. and$T_{k + 1}$is a basis. If not, continue is a basis. Continuing this way, we will stop after a finitely many steps and with$T_n = S \cup \set{w_{k+1}, w_{k+2}, w_{k+3}, … w_{n}}$since$\dim V = n$. Theorem Let$V$be a finite dimension vector space over a field$F$, and$W$a subspace of$V$, then$\dim W \leq \dim V$. Moreover, if$\dim W = \dim V$, then$W = V$. Proof [expand] DOUBLE CHECK let$\dim V = n \geq 0$, If$W = \set{0}, \dim W = 0 \leq n = \dim V$so assume that$W \neq \set{0}$. Then$\exists w_1 \in w$s.t.$w_1 \neq 0$continuing this way, let$\set{w_1, w_2, …, w_k}$be a linearly independent subset of$W$s.t. if$w$is any other vector in$W$s.t.$w \notin \set{w_1, w_2, …, w_k}$, then$\set{w_1, w_2, …, w_k}\cup \set{w}$is linearly dependent. But$w_1, w_2, …, w_k$is also linearly independent in V, since$W \subseteq V \implies$Proof [expand] Assume that$\dim W = \dim V = n$let #\beta = \set{w_1, w_2, …, _n}# be a basis of$W$. Then$\spa{\beta} = W$and$w_1, w_2, …, w_n$is a linearly independent set in$V$, since$W\subseteq V$. This implies that$w_1, w_2, …, w_n$is a bais of$V$, since$\dim V = n$, \therefore,$\spa{w_1, w_2, …, w_n}= V$i.e.$\spa{\beta} = V$We get$W=V\$