[Linear Algebra] Linear Independence

Uniqueness of Solution for $A\textrm{x} = \textrm{b}$

e.g.

$A\textbf{x} = \textbf{b}$

$\begin{bmatrix} 2 & 2 & 1 \\ 3 & 1 & 0 \\ 1 & 3 & 1 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 6 \\ 14 \\ 18 \end{bmatrix}$

$\textbf{a}_1 x_1 + \textbf{a}_2 x_2 + \textbf{a}_3 x_3 = \textbf{b}$

$\begin{bmatrix} 2 \\ 3 \\ 1 \\ \end{bmatrix} x_1 + \begin{bmatrix} 2 \\ 1 \\ 3 \\ \end{bmatrix} x_2 + \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} x_3 = \begin{bmatrix} 6 \\ 14 \\ 18 \end{bmatrix}$

• Solution exists only when $\textbf{b} \in \textrm{Span} \begin{Bmatrix} \textbf{a}_1, \textbf{a}_2, \textbf{a}_3 \end{Bmatrix}$
• If $\textbf{a}_1, \textbf{a}_2,$ and $\textbf{a}_3$ are linearly independent, then unique solution exists
• If $\textbf{a}_1, \textbf{a}_2,$ and $\textbf{a}_3$ are linearly dependent, then infinitely many solutions exist

Linear Independence

Formal Definition

Consider $x_1 \textbf{v}_1 + x_2 \textbf{v}_2 + \cdots + x_p \textbf{v}_p = \textbf{0}$

Obviously, one solution is $\textbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_p \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$, which we call a trivial solution

• If trivial solution is the only solution, $\textbf{v}_1, \cdots, \textbf{v}_p$ are linearly independent
• If other non-trivial solution exists, $\textbf{v}_1, \cdots, \textbf{v}_p$ are linearly dependent

Practical Definition

Given a set of vectors $\textbf{v}_1, \cdots, \textbf{v}_p \in \mathbb{R}^{n}$, check if $\textbf{v}_j$ can be represented as a linear combination of the previous vectors $\begin{Bmatrix} \textbf{v}_1, \textbf{v}_2, \cdots, \textbf{v}_{j-1} \end{Bmatrix}$ for $j = 1, \cdots, p$

$\textbf{v}_j \in \textrm{Span} \begin{Bmatrix} \textbf{v}_1, \textbf{v}_2, \cdots, \textbf{v}_{j-1} \end{Bmatrix}$ for some $j = 1, \cdots, p$

• If at least one such $\textbf{v}_j$ is found, then $\begin{Bmatrix} \textbf{v}_1, \cdots, \textbf{v}_{p} \end{Bmatrix}$ is linearly dependent
• If no such $\textbf{v}_j$ is found, then $\begin{Bmatrix} \textbf{v}_1, \cdots, \textbf{v}_{p} \end{Bmatrix}$ is linearly independent

Two Definitions are Equivalent

If $\textbf{v}_1, \cdots, \textbf{v}_p$ are linearly dependent, consider a non-trivial solution

Let's just denote j as the last index then

$x_j \textbf{v}_j = - x_1 \textbf{v}_1 - \cdots - x_{j-1} \textbf{v}_{j-1}$

If $x_j \ne 0$, then $\textbf{v}_j$ can be represented as a linear combination of the previous vectors

$\textbf{v}_j = - \frac{x_1}{x_j} \textbf{v}_1 - \cdots - \frac{x_{j-1}}{x_j} \textbf{v}_{j-1} \in \textrm{Span} \begin{Bmatrix} \textbf{v}_1, \textbf{v}_2, \cdots, \textbf{v}_{j-1} \end{Bmatrix}$

If $x_j = 0$, then just iterate

$x_1 \textbf{v}_1 + \cdots + x_{j-1} \textbf{v}_{j-1} = \textbf{0}$