Skip to content

Linear Independence

Definition

\(S\subset V\) is linear dependent set if \(\exists v_1, v_2,...,v_n\in V, a_1,a_2,...,a_n\in F\) (not all zero) st. \(a_1v_1+a_2v_2+...+a_nv_n=0\)

Note. \(S=\{0\}\) is linearly dependent set as \(1\cdot 0=0\in S\)

HW

Let \(S_1\subset S_2\subset V\)

If \(S_1\) is linear dependent, then \(S_2\) is linear dependent

If \(S_2\) is linear independent then \(S_1\) is linear independent

Theorem (Basis gives coordinates)

Let \(\beta=\{v_1, ..., v_n\}\subset V\) Then \(\beta\) is a basis \(\iff\) each \(v\in V\) has a unique expression as linear combination of vectors of \(\beta\)

Proof

  • Forward:

    Suppose \(\beta\) is a basis. Take \(v\in V\).

    As \(\text{span}(\beta)=V\), so \(\exists a_1,...,a_n\in F\), \(\sum a_nv_n=v\)

    Suppose \(\exists b_1,...,b_n\in F\)

    \(v=\sum b_nv_n\)

    \(\implies \sum (a_n-b_n)v_n=0\)

    Since \(\beta\) is Linear Independent

    \(a_n-b_n=0\) or \(a_n=b_n\)

    Thus, the linear combination of vectors of \(\beta\) that would yield \(v\) is unique.

  • Reverse:

    Since every \(v\in V\) has a unique linear combination of the vectors of \(\beta\).

    \(\text{span}(\beta)=V\)

    \(\forall v\in V, \exists a_n\in F, \exists b_n\in F, v=\sum a_nv_n, v=\sum b_nv_n\)

    Thus, \(0=v-v=(\sum a_nv_n)-(\sum b_nv_n)=\sum (a_n-b_n)v_n\)

    By uniqueness, \(a_n=b_n\), \(0=\sum 0v_n\), thus Linear independence

Theorem (Spanning sets contains basis)

Let \(S\subset V\) be a finite spanning set. Then, \(\exists\) a basis \(\beta\in S\)

Proof

If \(S=\emptyset\) or \(S=\{0\}\), then \(\beta=\emptyset\in S\)

Otherwise:

\(S\) contains a non-zero vector \(v_1\)

Thus, \(\beta_1=\{v_1\}\) is a linearly independent set

If \(\exists c\neq0\in F\) st. \(cv_1=0\)

\(c^{-1}cv_1=1v_1=0\)

This is a contradiction

Suppose \(\exists\) vector \(v_{k+1}\in S\backslash \beta_k\) st. \(\beta_k\cup \{v_{k+1}\}\) is linear independent.

Then take \(\beta_{k+1}=\beta_k\cup \{v_{k+1}\}\)

Since \(S\) is finite, we got a set \(\beta_n=\{v_1,...,v_n\}\) which is linear independent

\(\forall v\in S\backslash\beta_n, \beta_n\cup\{v\}\) is linear dependent

Suppose \(\exists v\in S, v\not\in \text{span}(\beta_n)\)

By the process above, we only not added to \(\beta_n\) if \(\beta_v:=\beta_n\cup \{v\}\) is linear dependent.

Thus, \(\exists a_n\neq 0\in F, 0=\sum a_n\cdot v_n\)

Thus, \(a_nv_n=-\sum a_{n-1}\cdot v_{n-1}\)

Thus, \(v_n=\frac{-\sum a_{n-1}\cdot v_{n-1}}{a_n}\)

Thus, \(v_n=-\sum \frac{a_{n-1}}{a_n}\cdot v_{n-1}\)

Since \(F\) is a field, \(\frac{a_{n-1}}{a_n}\in F\)

Thus, \(v_n\) has an expression as linear combination of \(\beta_n\)

Thus, \(v\in \text{text}(\beta_b)\)

\(\implies S\subset\text{span}(\beta_n)\)

\(\implies \text{span}(S)\subseteq\text{span}(\beta_n)\)

\(\implies V=\text{span}(\beta_n)\)

Thus, \(\beta_n\) is a basis

Theorem (Linear independent set can be expanded to a basis via a generating set)

Let \(G\subset V\) st \(\text{span}(G)=V\) and \(|G|=n\)

Let \(L\subset V\) st \(L\) is linearly independent and \(|L|=m\)

Thus:

  1. \(m<n\)
  2. \(\exists H\subset G, |H|=n-m, \text{span}(L\cup H)=V\)

Proof

If \(m=0\) take \(H=G\) so \(|H|=n-0\) and \(\text{span}(L\cup H)=\text{span}(G)=V\)

Suppose the theorem is true for \(m=k\)

Let \(L=\{v_1,...,v_{k+1}\}\) be linear independent set

Let \(L'=\{v_1,...,v_{k}\}\) be linear independent set

By induction set

  • \(k\leq n\)
  • \(\exists H'\subset G, |H'|=n-k\) st \(\text{span}(L'\cup H')=V\)

Then \(\exists a_1,...,a_k,b_1,...,b_{n-k}\in F\) st

\(\sum_{i=1}^k(a_iv_i)+\sum_{i=1}^{n-k}(b_iu_i)=v_{k+1}\)

If \(k=n\) then \(H'=\emptyset\) and \(v_{k+1}\in \text{span}(\{v_1,...,v_k\})\)

But \(L=\{v_1,...,v_{k+1}\}\) is linear independent, so we get a contradiction

So, \(k\leq n-1\)

Also some \(\beta_i\) is non zero

Assume \(\beta_1\neq 0\), so \(u_1=b_1^{-1}(-\sum_{i=1}^k(a_iv_i)+v_{k+1}-\sum_{i=1}^{n-k}(b_iu_i))\)

So, \(u_1\in\text{span}(L\cup H)\), \(L'\cup H'\subset \text{span}(L\cup H)\)

\(\implies \text{span}(L'\cup H')\subset \text{span}(L\cup H)\)

\(\text{span}(L\cup H)=V\)

and \(|H|=(n-k)-1=n-(k+1)\)

So theorem is true for \(m=k+1\), by induction, the theorem is true

Corollaries

  1. \(B_1\) and \(B_2\) be basis of \(V\), thus \(|B_1|=|B_2|=\text{dim}(V)\)
  2. \(G\subset V\) be a generating set, then \(|G|\geq\text{dim}(V)\) (\(|G|=\text{dim}(V)\) if \(G\) is a basis)
  3. \(L\subset V\) be a linearly independent set, then \(|L|\leq\text{dim}(V)\) (\(|L|=\text{dim}(V)\) if \(L\) is a basis)