Linear independence

Dependencies:

1. Vector Space

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

$$\mathrm{\forall }(a_1,a_2,\dots ,a_n)\in F^n,(\sum _{i=1}^n{a}_i{v}_i=0\Rightarrow (\mathrm{\forall }i,a_i=0))$$

This can also be stated as

$$\mathrm{\forall }(a_1,a_2,\dots ,a_n)\ne 0\in F^n,\sum _{i=1}^n{a}_i{v}_i\ne 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 \mathrm{\exists }(a_1,a_2,\dots ,a_n)\ne 0\in F^n,\sum _{i=1}^n{a}_i{v}_i=0$.

$(a_1,a_2,\dots ,a_n)\ne 0⟺\mathrm{\exists }k,a_k\ne 0$.

$$\begin{array}{rl}& \sum _{i=1}^n{a}_i{v}_i=0\\ & \Rightarrow \sum _{i=1}^{k-1}{a}_i{v}_i+a_k{v}_k+\sum _{i=k+1}^n{a}_i{v}_i=0\\ & \Rightarrow a_k{v}_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{array}$$

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}_i{v}_i+\sum _{i=k+1}^n{a}_i{v}_i⟹\sum _{i=1}^{k-1}{a}_i{v}_i+(-1)v_k+\sum _{i=k+1}^n{a}_i{v}_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:

• Depth: 4
• Number of transitive dependencies: 4

Transitive dependencies:

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