Characterization of Linearly Dependent Sets

A set of two or more vectors is linearly dependent if and only if at least one of the vectors is a linear combination of the others

Proof

Let $\{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\}$ be a set of linearly dependent vectors, and let $c_1, c_2, \ldots, c_n \in \mathbb{R}$.

$\Leftrightarrow \{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\} \text{ is linearly dependent}$

$\Leftrightarrow c_1\vec{u}_1 + c_2\vec{u}_2 + \ldots + c_n\vec{u}_n = \vec{0} \text{ has non-trivial solutions}$

$\Leftrightarrow c_1, c_2, \ldots, c_n \text{ are not all zero, where } c_i \neq 0$

$\Leftrightarrow -c_i\vec{u}_i = c_1\vec{u}_1 + c_2\vec{u}_2 + \ldots + c_{i-1}\vec{u}_{i-1} + c_{i+1}\vec{u}_{i+1} + \ldots + c_n\vec{u}_n$

$\Leftrightarrow \vec{u}_i = -\frac{c_1}{c_i}\vec{u}_1 - \frac{c_2}{c_i}\vec{u}_2 - \ldots - \frac{c_n}{c_i}\vec{u}_n$

$\Leftrightarrow \vec{u}_i \text{ is a linear combination of the other vectors}$

Theorem

A set of two vectors is linearly independent if and only if the vectors are not multiple of one another

Proof (by contrapositive)

Let $\{\vec{u}, \vec{v}\}$ be a set of linearly dependent vectors, and let $c_1$ and $c_2$ be non-zero scalars.

$\Leftrightarrow \{\vec{u}, \vec{v}\} \text{ is linearly dependent}$

$\Leftrightarrow c_1\vec{u} + c_2\vec{v} = \vec{0} \text{ has non-trivial solutions}$

$\Leftrightarrow c_1\vec{u} = -c_2\vec{v}$

$\Leftrightarrow \vec{u} = -\frac{c_2}{c_1}\vec{v} \quad \text{where } c_1, c_2 \neq 0$

$\Leftrightarrow \vec{u} \text{ is a scalar multiple of } \vec{v}$

Theorem

Any set containing the zero vector is linearly dependent.

Proof

Let $\{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\}$ be a set containing the zero vector, say at $\vec{u}_i$. Let $A = [\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n]$. Now, there exists a column of zeros at $\vec{u}_i$. There is no pivot in this column, so a free variable exists. The equation $A\vec{x} = \vec{0}$ has a non-trivial solution. There exist weights $c_1, c_2, \ldots, c_n$, not all zero, specifically $c_i \neq 0$, such that: $$c_1\vec{u}_1 + c_2\vec{u}_2 + \ldots + c_n\vec{u}_n = \vec{0}$$ Thus, the set $\{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\}$ is linearly dependent.

Theorem

A set of only one vector is linearly independent if and only if the vector is not the zero vector

Proof (By contrapositive):

Let ${\vec{v}}$ be a set of only one vector.

$\leftrightarrow$ {$\vec{v_1}$} is linearly dependent.

$\leftrightarrow \ x_1\vec{v}_1 = \vec{0}$ has a non-trivial solution.

$\leftrightarrow \ x_1 \ne 0$

$\leftrightarrow \vec{v_1} = \vec{0}$

Theorem

The columns of a matrix $A$ are linearly independent if and only if the equation $A\vec{x}=\vec{0}$ has only the trivial solution.

Let $A = [\vec{a}_1 \ \vec{a}_2 \ \cdots \ \vec{a}_n]$ and let $\vec{x}=\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$

The columns of $A$ are linearly independent.

$\leftrightarrow x_1\vec{a}_1 + x_2\vec{a}_2 + \cdots + x_n\vec{a}_n = \vec{0}$ has only the trivial solution.

$\leftrightarrow [\vec{a}_1 \ \vec{a}_2 \ \cdots \ \vec{a}_n]\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$ has only the trivial solution.

$A\vec{x}=\vec{0}$ has only the trivial solution.

Theorem

If a set contains more vectors than the dimension of the vecctors, then the set is linearly dependent

Proof

Let $A = [\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n]$, where each $\vec{v}_i$ has $n$ entries. Then $A$ is an $m \times n$ matrix. The equation $A\vec{x} = \vec{0}$ corresponds to a system of $m$ equations and $n$ unknowns. If $m > n$, then we have more unknowns than equations, and we will have a free variable in our system. By a previous theorem, $A\vec{x} = \vec{0}$ has a non-trivial solution, so the set of the columns of $A$ is linearly dependent.