2B. Basis

Definition:

The basis of a vector space $V$ is a linearly independent list that also spans $V$.

Examples:

1. For $F^n$ the basis is $(1,0,0,0,\mathrm{0..}{0}_{)},(0,1,0,0,...,0_{)},....,(0,0,0,......,1)$. It is linearly independent and also spans $F^n$
2. Similarly, the standard basis for ${\mathcal{P}}_n(F)$ is $1,z,z^2,...,z^n$ as it is linearly independent and spans ${\mathcal{P}}_n(F)$
3. There can be more than one basis, such as $(1,2),(3,5)$ is the basis for $F^2$

Basis definition:

A list $v_1,v_2,..,v_n$ is a basis of $V$ $⟺$ every element in the list can be written uniquely in the form: $v=a_1{v}_1+a_2{v}_2+....+a_n{v}_n$ for $a_i\in F$

Proof:

1. $\Rightarrow$
   1. Assume $v_1,v_2,..,v_n$ is a basis of $V$
   2. Then, $v_1,v_2,..,v_n$ is independent and a spanning list.
   3. By definition of spanning list, we know every element can be written as $v=a_1{v}_1+a_2{v}_2+....+a_n{v}_n$
   4. Now lets prove uniqueness. We know $v_1,v_2,..,v_n$ is linearly independent.
   5. Assume for the sake of contradiction the representation was not unique and $v=a_1{v}_1+a_2{v}_2+....+a_n{v}_n=b_1{v}_1+b_2{v}_2+....+b_n{v}_n$
   6. Then, $a_1{v}_1+a_2{v}_2+....+a_n{v}_n-b_1{v}_1+b_2{v}_2+....+b_n{v}_n=0$
   7. and $(a_1-b_1)v_1+(a_2-b_2)v_2+....+(a_n-b_n)v_n=0$
   8. By independence we know $0$ can be only represented if each $a_i-b_i=0$
   9. This implies each $a_i=b_i$ and the representation was not unique.
2. $\Leftarrow$
   1. Assume very element in the list can be written uniquely in the form: $v=a_1{v}_1+a_2{v}_2+....+a_n{v}_n$.
   2. Then, we know $v_1,v_2,..,v_n$ is a spanning list, as every element can be written as a linear combination
   3. We also know $v_1,v_2,..,v_n$ is independent as $0$ can be written by setting all coefficients to zero, and by definition of uniqueness this can be the only way to write zero
   4. Thus, $v_1,v_2,..,v_n$ is a spanning list of $V$

Spanning list → Basis

Every spanning list in a vector space can be reduced to a basis. Proof:

1. Assume $s_1,s_2,...,s_n$ is a spanning list of $V$
2. If $s_1,s_2,...,s_n$ is also linearly independent, then it is a basis and we are done. If not, by the linear dependence lemma there exists such $s_k\in \text{span}(s_1,s_2,...,s_{k-1})$. Remove this $s_k$, and again this is still a spanning list without the $k$ as by the linear dependence lemma the span remains unchanged. Remove $s_1$ if $s_1=0$
3. Repeat this process, and as every spanning list is larger than a linearly independent list (including the basis), there will no longer be such a $s_k$ left. By definition, as the span did not change, this is a linearly independent spanning list and thus a basis,

Finite dimensional vector space

Every finite dimensional vector space has a basis.

Proof:

1. By definition, every finite dimensional vector space has a spanning list. By the proof above, this can also be reduced to a basis. Hence, Every finite dimensional vector space has a basis.

Linearly independent list → Basis

Every linearly independent list of vectors in a finite-dimensional vector space can be extended to a basis

Proof:

1. Assume $i_1,i_2,...,i_n$ is an independent list in $V$. By definition, $V$ also has a spanning list $s_1,s_2,....,s_m$ where $m\ge n$. We can append these lists to get $i_1,i_2,...,i_n,s_1,s_2,....,s_m$. This list is still a spanning list, but linearly dependent as $s_1,s_2,....,s_m$ spans all vectors in $V$ including $i_1,i_2,...,i_n$. Thus, we can repeat the process that every spanning list can be reduced to a basis.

Example

Utilize the process described in the proof above to transfer the linearly independent list $(2,3,4),(9,6,8)$ in ${\mathbb{R}}^3$ into a basis Proof:

1. Lets appended the basis onto this list: $(2,3,4),(9,6,8),(1,0,0),(0,1,0),(0,0,1)$
2. Now note that $-2(2,3,4)+(9,6,8)=5(1,0,0)⟹-\frac{2}{5}(2,3,4)+\frac{1}{5}(9,6,8)=(1,0,0)$. This works because they are not homogeneous, one equation is the multiple of another.
3. So we can remove $(1,0,0)$
4. Similarly we can remove $(0,0,1)$ leaving us with the basis $(2,3,4),(9,6,8),(0,1,0)$

Direct sum of subspaces

Suppose $V$ is finite-dimensional vector space and $U$ is a subspace of $V$. Then there exists a subspace $W$ of $V$ such that $V=U\oplus W$. Proof:

1. Assume $V$ is some finite dimensional vector space and $U$ is some subspace of $V$.
2. Then, we know that $U$ is also finite dimensional by a previous proof (You can keep adding linearly independent elements to a list until the remaining elements in $U$ are spanned by such list. This has an end because its also linearly independent in $V$ so it cant be greater than basis or spanning list).
3. Then, the basis of $U$ denoted $u_1,u_2,...,u_n$ is also a linearly independent list in $V$. Thus it can be extended to the basis of $V$. Lets call this list $u_1,u_2,...,u_n,w_1,w_2,....,w_m$.
4. We can let the list spanned by the basis $w_1,w_2,....,w_m$ be the subspace $W$.
5. Lets prove $V=U+W$ and $U\oplus W$
   1. For any element $v\in V$ we have $v=a_1{u}_1,a_2{u}_2,...,a_n{u}_n+a_{n+1}{w}_1,a_{n+2}{w}_2,....,a_{n+m}{w}_m$
   2. From this, we can clearly see that $a_1{u}_1,a_2{u}_2,...,a_n{u}_n\in U$ and $a_{n+1}{w}_1,a_{n+2}{w}_2,....,a_{n+m}{w}_m\in W$ showing that any element $v\in V$ is also within the direct sum. Proving $V=U+W$. Do not need to prove other direction as U and W are subspaces so obviously the sum of two elements will be in V
   3. Now lets prove $U\cap W=0$ to show they are direct sums.
      1. Let some $p\in U\cap W$. Then, we know $p\in U$ and $p\in W$ thus $p=a_1{u}_1+a_2{u}_2+...+a_n{u}_n=a_{n+1}{w}_1+a_{n+2}{w}_2+....+a_{n+m}{w}_m$
      2. This means, $a_1{u}_1+a_2{u}_2+...+a_n{u}_n-a_{n+1}{w}_1+a_{n+2}{w}_2+....+a_{n+m}{w}_m=0$
      3. However, the only way to set each variable to 0 is by setting all the coefficients to 0 as both lists were linearly independent and the sum is a basis for $V$. Thus $p=0u_1+0u_2+...+0u_n=0w_1+0w_2+....+0w_m=0$