Linear Dependence and Independence

Given a list of vectors, \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \)

Definition 1 :

\( \mathcal{L} \) is called linearly dependent if one (some) of the vectors can be written as lin. comb. of the rest.
For example, \( u_i = \sum_{j \ne i} c_j u_j \).

\( \mathcal{L} \) is called linearly independent if none of the vectors can be written as lin. comb. of the rest.

Linear Dependence and Independence

Given a list of vectors, \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \)

Definition 2 :

( \( \iff \) Definition 1.)

\( \mathcal{L} \) is called linearly dependent if there are constants (scalars) \( c_1, c_2, \dots, c_k \) not all zero (ie. some non-zero) such that

\[ c_1 u_1 + c_2 u_2 + \dots + c_k u_k = \vec{0} \]

\( \mathcal{L} \) is called linearly independent if \( c_1 = c_2 = \dots = c_k = 0 \) is the only solution of

\[ c_1 u_1 + c_2 u_2 + \dots + c_k u_k = \vec{0} \]

Linear Dependence and Independence

Given a list of vectors, \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \)

\[ c_1 u_1 + c_2 u_2 + \dots + c_k u_k = \vec{0} \]

Dependency Relation / Equation

  1. Can determine if \( u_i \)'s are lin. dep/ind.,
  2. Can find all the relationship between the \( u_i \)'s
  3. Can determine which vectors to be thrown away.

Consequences (Properties) of Lin Dep.

(I) If \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \) is lin. dep., then \( \mathcal{L} \) can be reduced to \( \mathcal{L}' \, (\subseteq \mathcal{L}) \) such that \( \operatorname{Span}(\mathcal{L}) = \operatorname{Span}(\mathcal{L}') \).

For example: \( u_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad u_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \quad u_3 = \begin{pmatrix} -3 \\ 4 \end{pmatrix}. \)

\[ \begin{gathered} 3u_1 + (-4)u_2 + u_3 = \vec{0} \\[0.5em] \text{Let } \vec{v} = 5u_1 + 2u_2 + 3u_3 \end{gathered} \]

Consequences (Properties) of Lin Dep.

(I) If \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \) is lin. dep., then \( \mathcal{L} \) can be reduced to \( \mathcal{L}' \, (\subseteq \mathcal{L}) \) such that \( \operatorname{Span}(\mathcal{L}) = \operatorname{Span}(\mathcal{L}') \).

For example: \( u_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad u_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \quad u_3 = \begin{pmatrix} -3 \\ 4 \end{pmatrix}. \)

\[ \begin{gathered} 3u_1 + (-4)u_2 + u_3 = \vec{0} \\[0.5em] u_3 = -3u_1 + 4u_2 \end{gathered} \] \[ \begin{aligned} \text{Let } \vec{v} &= 5u_1 + 2u_2 + 3(-3u_1 + 4u_2) \\ &= (5-9)u_1 + (2+12)u_2 \\ &= -4u_1 + 14u_2 \in \operatorname{Span}(u_1, u_2) \end{aligned} \]

Consequences (Properties) of Lin Dep.

(II) If \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \) is lin. dep., Then any vector \( \vec{v} \in \operatorname{Span}(\mathcal{L}) \) can be represented in an infinitely many ways as lin. comb. of the \( u_i \)'s.

i.e. the representation is not unique.

For example,

\[ \begin{aligned} \vec{v} &= 2\vec{u}_1 - \vec{u}_2 + 2\vec{u}_3 \\ &= 5\vec{u}_1 - 5\vec{u}_2 + 3\vec{u}_3 \\ &= -\vec{u}_1 + 3\vec{u}_2 + \vec{u}_3 \end{aligned} \]

\( + (3\vec{u}_1 - 4\vec{u}_2 + \vec{u}_3 = \vec{0}) \)

\( -2(3\vec{u}_1 - 4\vec{u}_2 + \vec{u}_3 = \vec{0}) \)

Consequences (Properties) of Lin Dep.

(II)

\[ \begin{aligned} \vec{v} &= 2\vec{u}_1 - \vec{u}_2 + 2\vec{u}_3 \\ &= 5\vec{u}_1 - 5u_2 + 3\vec{u}_3 \\ &= -\vec{u}_1 + 3u_2 + \vec{u}_3 \end{aligned} \]

\( + (3\vec{u}_1 - 4\vec{u}_2 + \vec{u}_3 = \vec{0}) \)

\( -2(3\vec{u}_1 - 4\vec{u}_2 + \vec{u}_3 = \vec{0}) \)

\[ \begin{aligned} \begin{pmatrix} -4 \\ 7 \end{pmatrix} &= 2\begin{pmatrix} 1 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 1 \end{pmatrix} + 2\begin{pmatrix} -3 \\ 4 \end{pmatrix} \\ &= 5\begin{pmatrix} 1 \\ 0 \end{pmatrix} - 5\begin{pmatrix} 0 \\ 1 \end{pmatrix} + 3\begin{pmatrix} -3 \\ 4 \end{pmatrix} \\ &= -\begin{pmatrix} 1 \\ 0 \end{pmatrix} + 3\begin{pmatrix} 0 \\ 1 \end{pmatrix} + \begin{pmatrix} -3 \\ 4 \end{pmatrix} \end{aligned} \]

non-unique representation as lin. comb.

How to Eliminate (All the) Redundant Vectors

Given a list \( \mathcal{L} = \{ u_1, u_2, \dots, u_k \} \).

  1. Consider solving for \( c_1, c_2, \dots, c_k \) :

    \[ c_1 \vec{u}_1 + c_2 \vec{u}_2 + \dots + c_k \vec{u}_k = \vec{0} \]

  2. Throw aways those vectors with the free variable \( c_i \)'s.

  3. The remaining vectors with the pivot variable \( c_i \)'s are linearly independent.