# Basis

Let ${\displaystyle V}$ be a vector space over a field ${\displaystyle K}$, and ${\displaystyle {\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}\in V}$

Definition (Linearly dependent vectors)

${\displaystyle {\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}\in V}$ are defined to be linearly dependent if ${\displaystyle \exists \alpha _{1},\alpha _{2},\dots ,\alpha _{n}\in K}$ not all zeros, such that ${\displaystyle \alpha _{1}{\underline {v_{1}}}+\alpha _{2}{\underline {v_{2}}}+\dots +\alpha _{n}{\underline {v_{n}}}=0}$

Definition (Linearly independent vectors)

${\displaystyle {\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}\in V}$ are defined to be linearly independent if ${\displaystyle \alpha _{1}{\underline {v_{1}}}+\alpha _{2}{\underline {v_{2}}}+\dots +\alpha _{n}{\underline {v_{n}}}=0\Leftrightarrow \alpha _{1}=\alpha _{2}=\dots =\alpha _{n}=0}$

Remark

Let ${\displaystyle Y\subseteq V}$.

${\displaystyle Y}$ is a set of linearly independent vectors if ${\displaystyle \forall \left\{{\underline {v_{1}}},\dots ,{\underline {v_{r}}}\right\}\subseteq Y,\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{r}{\underline {v_{r}}}=0\Leftrightarrow \alpha _{1}=\dots =\alpha _{r}=0}$

Definition (Basis)

A set ${\displaystyle B={{\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}}}$ is defined as basis if:

• ${\displaystyle B}$ is a set of linearly independent vectors
• ${\displaystyle span(B)=V}$

Theorem (Existence and uniqueness of the coordinates)

Let ${\displaystyle B}$ be an ordered basis ${\displaystyle B={{\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}}}$ for ${\displaystyle V}$ over ${\displaystyle K}$. Then, ${\displaystyle \exists }$ and uniquely determined some scalars ${\displaystyle \alpha _{1},\dots ,\alpha _{n}\in K}$ such that ${\displaystyle {\underline {v}}=\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{n}{\underline {v_{n}}}}$, ${\displaystyle \forall {\underline {v}}\in V}$. The n-tuple ${\displaystyle {\begin{pmatrix}\alpha _{1}\\\vdots \\\alpha _{n}\end{pmatrix}}}$ is the coordinate vector of ${\displaystyle {\underline {v}}}$ relative to the basis ${\displaystyle B}$.

Proof

${\displaystyle \forall {\underline {v}}\in V}$

• Existence: ${\displaystyle {\underline {v}}\in span(B)\Rightarrow \exists \alpha _{1},\dots ,\alpha _{n}\in K}$ such that ${\displaystyle {\underline {v}}=\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{n}{\underline {v_{n}}}}$
• Uniquely determined: let's suppose (Reductio ad absurdum) that the following expressions are both true, for some ${\displaystyle \alpha _{i},\beta _{i}\in K}$, with ${\displaystyle i\in \left\{1,\dots ,n\right\}}$, such that ${\displaystyle \exists i:\alpha _{i}\neq \beta _{i}}$:

${\displaystyle {\underline {v}}=\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{n}{\underline {v_{n}}}}$

${\displaystyle {\underline {v}}=\beta _{1}{\underline {v_{1}}}+\dots +\beta _{n}{\underline {v_{n}}}}$

Subtracting the second to the first one, the result is:

${\displaystyle {\underline {v}}-{\underline {v}}=0=(\alpha _{1}-\beta _{1}){\underline {v_{1}}}+\dots +(\alpha _{n}-\beta _{n}){\underline {v_{n}}}}$

All the ${\displaystyle {\underline {v_{i}}}}$ are linearly independent (because they are vectors of a basis), therefore it follows that ${\displaystyle \alpha _{i}=\beta _{i}\forall i}$, which contradicts the hypothesis. Thus, the ${\displaystyle \alpha _{i}}$ are uniquely determined. }}

Theorem (Linearly dependent set of vectors)

${\displaystyle S=\{{\underline {v_{1}}},{\underline {v_{2}}},\dots ,{\underline {v_{n}}}\}}$ is linearly dependent ${\displaystyle \Leftrightarrow \exists i\in \{1,\dots ,n\}}$ such that ${\displaystyle {\underline {v_{i}}}}$ is linear combination of the remaining ${\displaystyle {\underline {v_{j}}}}$.

Proof

${\displaystyle S}$ is linearly dependent ${\displaystyle \Leftrightarrow \exists i\in \{1,\dots ,n\}}$ such that ${\displaystyle \alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{n}{\underline {v_{n}}}}$, where ${\displaystyle \alpha _{i}}$ are not all ${\displaystyle 0}$s. Without loss of generality: ${\displaystyle \alpha _{1}\neq 0}$ ${\displaystyle {\underline {v_{1}}}=-\alpha _{1}^{-1}\alpha _{2}{\underline {v_{2}}}-\dots -\alpha _{1}^{-1}\alpha _{n}{\underline {v_{n}}}}$ Therefore ${\displaystyle S}$ is linearly dependent. }}

Definition (Maximal set of linearly independent vectors)

Let ${\displaystyle S=\{{\underline {v_{1}}},\dots ,{\underline {v_{n}}}\}\subseteq V}$. Then ${\displaystyle {{\underline {v_{1}}},\dots ,{\underline {v_{r}}}}\subseteq S}$ is a maximal subset of linearly independent vectors if:

• ${\displaystyle {\underline {v_{1}}},\dots ,{\underline {v_{n}}}}$ linearly independent
• ${\displaystyle \forall i\in \{r+1,\dots ,n\},}$ ${\displaystyle \{{\underline {v_{1}}},\dots ,{\underline {v_{r}}},{\underline {v_{i}}}\}}$ is linearly dependent

Theorem (Basis as maximal set of l.i. spanning set of vectors)

Let ${\displaystyle S=\{{\underline {v_{1}}},\dots ,{\underline {v_{n}}}\}}$ be a spanning set for ${\displaystyle V}$, and ${\displaystyle S_{1}=\{{\underline {v_{1}}},\dots ,{\underline {v_{r}}}\}}$ be a maximal set of linearly independent vectors (where ${\displaystyle r\leq n}$), then ${\displaystyle S_{1}}$ is a basis.

Proof

I need to prove that ${\displaystyle S_{1}}$ spans ${\displaystyle V}$, which means I have to prove that ${\displaystyle \forall {\underline {v}}\in V,\exists \alpha _{1},\dots ,\alpha _{n}}$ such that ${\displaystyle {\underline {v}}=\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{r}{\underline {v_{r}}}}$.

By hypothesis, ${\displaystyle \exists x_{1},\dots ,x_{n}\in K}$ such that ${\displaystyle {\underline {v}}=x_{1}{\underline {v_{1}}}+\dots +x_{r}{\underline {v_{r}}}+x_{r+1}{\underline {v_{r+1}}}\dots +x_{n}{\underline {v_{n}}}}$. ${\displaystyle \forall i\in \{r+1,\dots ,n\}}$, ${\displaystyle S_{i}=\{{\underline {v_{1}}},\dots ,{\underline {v_{r}}},{\underline {v_{i}}}\}}$ is linearly dependent. Therefore, every ${\displaystyle {\underline {v_{i}}}}$ can be expressed as linear combination of the vectors in ${\displaystyle S_{1}}$.

It follows that every ${\displaystyle {\underline {v}}\in V}$ can be expressed as linear combination of the vectors in ${\displaystyle S_{1}}$, so, ${\displaystyle S_{1}}$ is a basis.

Theorem

Let ${\displaystyle V}$ be a vector space over ${\displaystyle K}$ and let ${\displaystyle \{{\underline {v_{1}}},\dots ,{\underline {v_{m}}}\}}$ be a basis for ${\displaystyle V}$. If ${\displaystyle n>m}$ and ${\displaystyle {\underline {w_{1}}},\dots ,{\underline {w_{n}}}\in V}$, then ${\displaystyle \{{\underline {w_{1}}},\dots ,{\underline {w_{n}}}\}}$ are linearly dependent.

Proof

If ${\displaystyle {\underline {w_{1}}},\dots ,{\underline {w_{n}}}}$ are linearly dependent, the theorem is trivially proved, so let's proceed in the proof assuming they are linearly independent.

Let's prove by induction that ${\displaystyle V=span\{{\underline {w_{1}}},\dots ,{\underline {w_{m}}}\}}$.

The induction hypothesis is: ${\displaystyle \exists r}$ where ${\displaystyle 1\leq r such that (after having possibly rearranged ${\displaystyle {\underline {v_{1}}},\dots ,{\underline {v_{m}}}}$), the vectors ${\displaystyle {\underline {w_{1}}},\dots ,{\underline {w_{r}}},{\underline {v_{r+1}}},\dots ,{\underline {v_{m}}}}$ will span ${\displaystyle V}$.

Base case: ${\displaystyle r=1}$

${\displaystyle \{{\underline {v_{1}}},\dots ,{\underline {v_{m}}}\}}$ is a basis, therefore ${\displaystyle \exists \alpha _{1},\dots ,\alpha _{m}}$ such that:

${\displaystyle {\underline {w_{1}}}=\alpha _{1}{\underline {v_{1}}}+\dots +\alpha _{m}{\underline {v_{m}}}}$

${\displaystyle {\underline {w_{1}}}\neq 0}$ and WLOG ${\displaystyle \alpha _{1}\neq 0}$, so:

${\displaystyle {\underline {v_{1}}}=\alpha _{1}^{-1}{\underline {w_{1}}}-\alpha _{1}^{-1}\alpha _{2}{\underline {v_{2}}}-\dots -\alpha _{1}^{-1}\alpha _{m}{\underline {v_{m}}}}$

${\displaystyle \{{\underline {v_{1}}},\dots ,{\underline {v_{m}}}\}}$ spans ${\displaystyle V}$, and ${\displaystyle {\underline {v_{1}}}\in span\{{\underline {w_{1}}},{\underline {v_{2}}}\dots ,{\underline {v_{m}}}\}}$, therefore the last set spans ${\displaystyle V}$ as well.

Inductive step:

For the induction hypothesis, ${\displaystyle V=span\{{\underline {w_{1}}},\dots ,{\underline {w_{r}}},{\underline {v_{r+1}}},\dots ,{\underline {v_{m}}}\}}$. Therefore, ${\displaystyle \exists \beta _{1},\dots ,\beta _{r},\gamma _{r+1},\dots \gamma _{m}\in K}$ such that

${\displaystyle {\underline {w_{r+1}}}=\beta _{1}{\underline {w_{1}}}+\dots +\beta _{r}{\underline {w_{r}}}+\gamma _{r+1}{\underline {v_{r+1}}}+\dots +\gamma _{m}{\underline {v_{m}}}}$

Not all ${\displaystyle \gamma }$ can be zero because we assumed all ${\displaystyle {\underline {w_{i}}}}$ to be linearly independent so, WLOG, ${\displaystyle \gamma _{r+1}\neq 0}$ and we get to the result:

${\displaystyle {\underline {v_{r+1}}}=\gamma _{r+1}^{-1}{\underline {w_{r+1}}}-\gamma _{r+1}^{-1}\beta _{1}{\underline {w_{1}}}-\dots -\gamma _{r+1}^{-1}\beta _{r}{\underline {w_{r}}}-\gamma _{r+1}^{-1}\gamma _{r+2}{\underline {v_{r+2}}}-\dots -\gamma _{r+1}^{-1}\gamma _{m}{\underline {v_{m}}}}$

${\displaystyle {\underline {v}}_{r+1}\in span\{{\underline {w_{1}}},\dots ,{\underline {w_{r+1}}},{\underline {v_{r+2}}},\dots ,{\underline {v_{m}}}\}}$ ${\displaystyle \Rightarrow span\{{\underline {w_{1}}},\dots ,{\underline {w_{r+1}}},{\underline {v_{r+2}}},\dots ,{\underline {v_{m}}}\}=V}$

It is now proved by induction that ${\displaystyle V=span\{{\underline {w_{1}}},\dots ,{\underline {w_{m}}}\}}$ It follows that ${\displaystyle \exists d_{1},d_{2},\dots ,d_{m}\in K}$ such that ${\displaystyle {\underline {w_{n}}}=d_{1}{\underline {w_{1}}}+\dots +d_{m}{\underline {w_{m}}}}$ That is, ${\displaystyle \{{\underline {w_{1}}},\dots ,{\underline {w_{n}}}\}}$ are linearly dependent.

Remark

From this theorem, it trivially follows that all the possible bases for a particular vector space, have the same cardinality. In fact, suppose that a vector space has two possible bases, the first one has ${\displaystyle n}$ elements, the second one has ${\displaystyle m}$ elements. It can be neither ${\displaystyle n>m}$ nor ${\displaystyle m>n}$, therefore ${\displaystyle n=m}$