Linear independence

Dependencies:

  1. Vector Space

Let $S = \{v_1, v_2, \ldots, v_n\}$ be a subset of vector space $V$ over field $F$. Then $S$ is linearly independent iff

\[ \forall (a_1, a_2, \ldots, a_n) \in F^n, \left (\sum_{i=1}^n a_iv_i = 0 \Rightarrow (\forall i, a_i = 0 )\right) \]

This can also be stated as

\[ \forall (a_1, a_2, \ldots, a_n) \neq 0 \in F^n, \sum_{i=1}^n a_iv_i \neq 0 \]

This is equivalent to saying that "no vector in $S$ is a linear combination of the rest of the elements of $S$". When a vector $v$ in $S$ is a linear combination of the other elements of $S$, $v$ is said to be linearly dependent in $S$.

An empty set is defined to be linearly independent.

When $S$ is of infinite size, then it is linearly dependent iff it has a subset of finite size which is linearly dependent.

Proof

Let $S$ be linearly dependent. $\Rightarrow \exists (a_1, a_2, \ldots, a_n) \neq 0 \in F^n, \sum_{i=1}^n a_iv_i = 0$.

$(a_1, a_2, \ldots, a_n) \neq 0 \iff \exists k, a_k \neq 0$.

\begin{align} & \sum_{i=1}^n a_iv_i = 0 \\ &\Rightarrow \sum_{i=1}^{k-1} a_iv_i + a_kv_k + \sum_{i=k+1}^n a_iv_i = 0 \\ &\Rightarrow a_kv_k = \sum_{i=1}^{k-1} (-a_i)v_i + \sum_{i=k+1}^n (-a_i)v_i \\ &\Rightarrow v_k = \sum_{i=1}^{k-1} (-a_k^{-1}a_i)v_i + \sum_{i=k+1}^n (-a_k^{-1}a_i)v_i \end{align}

Therefore, $v_k$ is a linear combination of the rest of the vectors in $S$.

Conversely, assume $v_k$ is a linear combination of the rest of the vectors in $S$.

\[ v_k = \sum_{i=1}^{k-1} a_iv_i + \sum_{i=k+1}^n a_iv_i \implies \sum_{i=1}^{k-1} a_iv_i + (-1)v_k + \sum_{i=k+1}^n a_iv_i = 0 \]

Therefore, a linear combination of $S$ is 0 where all coefficients are not 0. Therefore, $S$ is linearly dependent.

Dependency for:

  1. Extreme point iff BFS
  2. Pointing a polyhedron
  3. Basic feasible solutions
  4. Eigenvectors of distinct eigenvalues are linearly independent
  5. A is diagonalizable iff there are n linearly independent eigenvectors
  6. A set of mutually orthogonal vectors is linearly independent
  7. Gram-Schmidt Process
  8. Joining orthogonal linindep sets
  9. Incrementing a linearly independent set
  10. Linearly independent set is not bigger than a span
  11. span(A)=span(B) & |A|=|B| & A is linindep ⟹ B is linindep
  12. Affine independence (incomplete)
  13. Decrementing a span
  14. Basis of a vector space
  15. Vector matroid

Info:

Transitive dependencies:

  1. Group
  2. Ring
  3. Field
  4. Vector Space