03 Linear Dependence and Independence

Lecture from 25.09.2024 | Video: Videos ETHZ

Related to: Linear Combinations

Vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ in ${\mathbb{R}}^m$ are said to be linearly dependent if at least one of them is a linear combination of the others. This means there exists some index $k\in [n]$ and scalars ${\lambda }_j$ such that:

$${\mathbf{v}}_k=\sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n{\lambda }_j{\mathbf{v}}_j$$

If no such scalars exist, the vectors ${\mathbf{v}}_{1,}{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ are linearly dependent.

Examples

Case	In/dependent	Explanation
Two vectors ${\mathbf{v}}_1=(2,3)$ and ${\mathbf{v}}_2=(3,-1)$	Independent	These two vectors are not scalar multiples of each other, so they are linearly independent.
Two vectors ${\mathbf{v}}_1=(2,3)$ and ${\mathbf{v}}_2=(4,6)$	Dependent	${\mathbf{v}}_2$ is a scalar multiple of ${\mathbf{v}}_1$ (${\mathbf{v}}_2=2{\mathbf{v}}_1$), so they are linearly dependent.
Vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ in ${\mathbb{R}}^{n-1}$. Example: Vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ in ${\mathbb{R}}^2$	Dependent	Any set of $n$ vectors in ${\mathbb{R}}^{n-1}$ is always linearly dependent, as either: 1) $n-1$ are independent and span ${\mathbb{R}}^{n-1}$ and the the n-th vector is a combination of them or 2) $n-1$ are not independent and therefore $n$ won’t be either.
A sequence of a single non-zero vector $(v\ne 0)$	Independent	A single non-zero vector is always linearly independent because there is no other vector to form a linear combination.
A sequence of a single zero vector $(v=0)$	Dependent	A single zero vector is always linearly dependent, since the only possible scalar is $0$, and the zero vector can be written as $0\times \mathbf{v}=0$.
Sequence of vectors including the zero vector $(v_1,v_2,\dots ,0,\dots ,v_n)$	Dependent	Any sequence containing the zero vector is linearly dependent because the zero vector can be expressed as a linear combination of the other vectors (with all ${\lambda }_j=0$).
Sequence of vectors where one vector appears twice or more $(v_1,v_2,\dots ,v_{\text{duplicate}},\dots ,v_n)$	Dependent	If a vector appears twice, they are linearly dependent because one vector is a scalar multiple (identity) of the other.
The empty sequence $()$	Independent	The empty sequence is trivially linearly independent since there are no vectors to form a linear dependence relation.

Alternate Definitions of Linear Dependence

Let ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ be vectors in ${\mathbb{R}}^m$. The following statements are equivalent (either all true or all false):

1. At least one vector is a linear combination of the others (as in the main definition).
2. There exist scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\in \mathbb{R}$, not all zero, such that: $$\sum _{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$$ In other words, the zero vector is a non-trivial linear combination of the vectors.
3. At least one vector is a linear combination of the preceding ones in the sequence ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$.

How do we know these are true? Here are the proofs: The idea is that we prove: $(i)\to (ii)\wedge (ii)\to (iii)\wedge (iii)\to (i)$.

Proof: (i) $⟹$ (ii)

Assume (i) is true: one of the vectors, say ${\mathbf{v}}_k$, is a linear combination of the others. That is, there exist scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_{k-1},{\lambda }_{k+1},\dots ,{\lambda }_n\in \mathbb{R}$ such that:

$${\mathbf{v}}_k=\sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n{\lambda }_j{\mathbf{v}}_j$$

Now, subtract ${\mathbf{v}}_k$ from both sides:

$$0=-{\mathbf{v}}_k+\sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n{\lambda }_j{\mathbf{v}}_j$$

This equation can be rewritten as:

$$0=\sum _{\begin{array}{c}j=1\end{array}}^n{\lambda }_j^{\prime }{\mathbf{v}}_j$$

Where ${\lambda }_k^{\prime }=-1$ and ${\lambda }_j^{\prime }={\lambda }_j$ for all $j\ne k$. Since ${\lambda }_k^{\prime }=-1$, we have a non-trivial solution (not all ${\lambda }_j^{\prime }$ are zero).

Thus, (ii) holds: there exist scalars, not all zero, such that their linear combination of the vectors equals the zero vector.

Proof: (ii) $⟹$ (iii)

Assume (ii) is true: there exist scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\in \mathbb{R}$, not all zero, such that:

$$\sum _{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$$

Let $k$ be the largest index such that ${\lambda }_k\ne 0$ (this must exist, as not all ${\lambda }_j$ are zero by assumption). We can now separate the term involving ${\mathbf{v}}_k$:

$${\lambda }_k{\mathbf{v}}_k+\sum _{j=1}^{k-1}{\lambda }_j{\mathbf{v}}_j=0$$

Now, isolate ${\mathbf{v}}_k$ by moving the sum to the other side:

$${\lambda }_k{\mathbf{v}}_k=-\sum _{j=1}^{k-1}{\lambda }_j{\mathbf{v}}_j$$

Next, divide through by ${\lambda }_k$ (which is non-zero by assumption) to solve for ${\mathbf{v}}_k$:

$${\mathbf{v}}_k=\sum _{j=1}^{k-1}\frac{-{\lambda }_j}{{\lambda }_k}{\mathbf{v}}_j$$

Thus, ${\mathbf{v}}_k$ can be written as a linear combination of the preceding vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{k-1}$. This matches statement (iii): at least one vector (in this case, ${\mathbf{v}}_k$) is a linear combination of the preceding vectors.

Therefore, (ii) implies (iii).

Proof: (iii) $⟹$ (i)

This implication is straightforward.

Assume (iii) is true: at least one vector, say ${\mathbf{v}}_k$, is a linear combination of the preceding vectors in the sequence ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{k-1}$:

$${\mathbf{v}}_k=\sum _{j=1}^{k-1}{\lambda }_j{\mathbf{v}}_j$$

Since ${\mathbf{v}}_k$ is a linear combination of the other vectors in the set, it directly follows that there exists a vector, ${\mathbf{v}}_k$, which is a linear combination of the others. This is exactly what statement (i) asserts.

Thus, (iii) implies (i).

Definitions of Linear Independence

Let ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ be vectors in ${\mathbb{R}}^m$. The following statements are equivalent for the vectors to be linearly independent (either all true or all false):

1. No vector in the set can be written as a linear combination of the others.
2. The only scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\in \mathbb{R}$ that satisfy a linear combination of the vectors resulting in the zero vector are all zero (i.e., the trivial solution).
3. No vector is a linear combination of the preceding ones in the sequence ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$.

Uniqueness of Solutions with Linearly Independent Sets of Vectors

When a set of vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ in ${\mathbb{R}}^m$ is linearly independent, any vector $\mathbf{b}\in {\mathbb{R}}^m$ can have at most one unique solution when expressed as a linear combination of the vectors in that set.

Uniqueness of Solutions with Linearly Independent Sets of Vectors

When a set of vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ in ${\mathbb{R}}^m$ is linearly independent, any vector $\mathbf{b}\in {\mathbb{R}}^m$ can have at most one unique solution when expressed as a linear combination of the vectors in that set.

Proof of Uniqueness

Suppose $\mathbf{b}\in {\mathbb{R}}^m$ can be written as a linear combination of the vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ in two different ways with two sets of coefficients, ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ and ${\mu }_1,{\mu }_2,\dots ,{\mu }_n$, such that:

$$\mathbf{b}={\lambda }_1{\mathbf{v}}_1+{\lambda }_2{\mathbf{v}}_2+\cdots +{\lambda }_n{\mathbf{v}}_n$$

and

$$\mathbf{b}={\mu }_1{\mathbf{v}}_1+{\mu }_2{\mathbf{v}}_2+\cdots +{\mu }_n{\mathbf{v}}_n$$

Now subtract the second equation from the first:

$$({\lambda }_1{\mathbf{v}}_1+{\lambda }_2{\mathbf{v}}_2+\cdots +{\lambda }_n{\mathbf{v}}_n)-({\mu }_1{\mathbf{v}}_1+{\mu }_2{\mathbf{v}}_2+\cdots +{\mu }_n{\mathbf{v}}_n)=0$$

This simplifies to:

$$({\lambda }_1-{\mu }_1){\mathbf{v}}_1+({\lambda }_2-{\mu }_2){\mathbf{v}}_2+\cdots +({\lambda }_n-{\mu }_n){\mathbf{v}}_n=0$$

Since the vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ are linearly independent, the only solution to this equation is for each coefficient to be zero. That is:

$${\lambda }_1-{\mu }_1=0,{\lambda }_2-{\mu }_2=0,\dots ,{\lambda }_n-{\mu }_n=0$$

Therefore, ${\lambda }_k={\mu }_k$ for all $k=1,2,\dots ,n$.

Conclusion

Since ${\lambda }_k={\mu }_k$ for all $k$, the scalars (coefficients) used to express $\mathbf{b}$ as a linear combination of ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ must be the same. This proves that the solution is unique.

Vector Span

Definition

The span of a set of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{\mathbf{n}}\}$ in a vector space is the set of all possible linear combinations of those vectors. Mathematically, the span is defined as:

$$\text{span}(\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{\mathbf{n}}\})=\left\{c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\dots +c_n{\mathbf{v}}_{\mathbf{n}}\mid c_1,c_2,\dots ,c_n\in \mathbb{R}\right\}$$

In other words, the span of a set of vectors is the collection of all vectors that can be formed by taking scalar multiples of each vector and adding them together.

Proof: Adding a Vector from a Span Does Not Change the Span

Let $v_1,v_2,\dots ,v_n\in {\mathbb{R}}^m$ be vectors, and let $v\in {\mathbb{R}}^m$ be a linear combination of $v_1,\dots ,v_n$. We aim to show that:

$$\text{span}(v_1,\dots ,v_n)=\text{span}(v_1,\dots ,v_n,v)$$

Proof Strategy:

We will prove that the two spans are equal by showing:

1. $\text{span}(v_1,\dots ,v_n)\subseteq \text{span}(v_1,\dots ,v_n,v)$
2. $\text{span}(v_1,\dots ,v_n,v)\subseteq \text{span}(v_1,\dots ,v_n)$

Once both inclusions are established, we can conclude that the two spans are identical.

Part 1: $\text{span}(v_1,\dots ,v_n)\subseteq \text{span}(v_1,\dots ,v_n,v)$

Let $q$ be an arbitrary element of $\text{span}(v_1,\dots ,v_n)$. By definition, $q$ can be written as a linear combination of $v_1,\dots ,v_n$:

$$q=a_1{v}_1+a_2{v}_2+\cdots +a_n{v}_n$$

Since $v\in \text{span}(v_1,\dots ,v_n)$, we can set the coefficient of $v$ to be 0:

$$q=a_1{v}_1+a_2{v}_2+\cdots +a_n{v}_n+0\cdot v$$

Thus, $q$ is also an element of $\text{span}(v_1,\dots ,v_n,v)$. Therefore, every element of $\text{span}(v_1,\dots ,v_n)$ is in $\text{span}(v_1,\dots ,v_n,v)$, proving:

$$\text{span}(v_1,\dots ,v_n)\subseteq \text{span}(v_1,\dots ,v_n,v)$$

Part 2: $\text{span}(v_1,\dots ,v_n,v)\subseteq \text{span}(v_1,\dots ,v_n)$

Let $w$ be an arbitrary element of $\text{span}(v_1,\dots ,v_n,v)$. By definition, $w$ can be written as a linear combination of $v_1,v_2,\dots ,v_n,v$:

$$w=m_1{v}_1+m_2{v}_2+\cdots +m_n{v}_n+m_{v}v$$

Since $v\in \text{span}(v_1,\dots ,v_n)$, we know that $v$ can be expressed as:

$$v=n_1{v}_1+n_2{v}_2+\cdots +n_n{v}_n$$

Substitute this expression for $v$ into the equation for $w$:

$$w=m_1{v}_1+m_2{v}_2+\cdots +m_n{v}_n+m_v(n_1{v}_1+n_2{v}_2+\cdots +n_n{v}_n)$$

Now, simplify the expression:

$$w=(m_1+m_v{n}_1)v_1+(m_2+m_v{n}_2)v_2+\cdots +(m_n+m_v{n}_n)v_n$$

This shows that $w$ is a linear combination of $v_1,\dots ,v_n$. Therefore, $w\in \text{span}(v_1,\dots ,v_n)$, proving:

$$\text{span}(v_1,\dots ,v_n,v)\subseteq \text{span}(v_1,\dots ,v_n)$$

Conclusion:

Since both:

$$\text{span}(v_1,\dots ,v_n)\subseteq \text{span}(v_1,\dots ,v_n,v)\text{and}\text{span}(v_1,\dots ,v_n,v)\subseteq \text{span}(v_1,\dots ,v_n)$$

we conclude that:

$$\text{span}(v_1,\dots ,v_n)=\text{span}(v_1,\dots ,v_n,v)$$

Continue here: 04 Matrices and Linear Combinations