Linear Independence of Vectors

Vectors can be combined using scalar multiplication and addition to form linear combinations, which span a certain space or subspace. A natural question arises: given a set of vectors that span a space, are all of them truly necessary? Could the same span be achieved with fewer vectors because some are 'redundant'? This leads to the concept of linear independence.

What is Linear Independence?

Imagine you have a set of vectors {$v_1, v_2, ..., v_k$}. We want to know if any vector in this set can be represented as a linear combination of the others. If one vector can be formed by combining the others, it doesn't add anything new to the direction or dimension spanned by the set; it's essentially redundant information within the context of the span. If no vector in the set can be expressed as a linear combination of the others, the set is called linearly independent.

Formally, a set of vectors {$v_1, v_2, ..., v_k$} in a vector space is said to be linearly independent if the only solution to the vector equation:

$c_1v_1 + c_2v_2 + ... + c_kv_k = \vec{0}$

is the trivial solution where all the scalar coefficients are zero: $c_1 = 0, c_2 = 0, ..., c_k = 0$.

Conversely, the set of vectors is linearly dependent if there exists at least one non-trivial solution, meaning at least one coefficient $c_i$ is non-zero. If the vectors are linearly dependent, it implies that at least one vector $v_i$ can be isolated and written as a linear combination of the other vectors in the set. For example, if $c_i \neq 0$, we could rearrange the equation to:

$v_i = -\frac{c_1}{c_i}v_1 - ... - \frac{c_{i-1}}{c_i}v_{i-1} - \frac{c_{i+1}}{c_i}v_{i+1} - ... - \frac{c_k}{c_i}v_k$

This confirms that $v_i$ lies within the span of the other vectors.

Geometric Intuition

Let's visualize this in familiar spaces:

• In 2D ($\mathbb{R}^2$):
  • Two vectors are linearly dependent if they lie on the same line passing through the origin. One is just a scaled version of the other (collinear). Adding the second vector doesn't expand the span of the line defined by the first.
  • Two vectors are linearly independent if they point in different directions (not collinear). Together, they can span the entire 2D plane.
• In 3D ($\mathbb{R}^3$):
  • Three vectors are linearly dependent if they all lie within the same plane passing through the origin (coplanar). At least one vector can be expressed as a combination of the other two. They cannot span the full 3D space, only a plane (or a line, if they are all collinear).
  • Three vectors are linearly independent if they are not coplanar. They point in sufficiently different directions to span the entire 3D space.

Consider two sets of vectors in $\mathbb{R}^2$: Set A = { (2, 1), (4, 2) } and Set B = { (2, 1), (1, 3) }.

Set A vectors (black and red) are linearly dependent as v2 is just 2 * v1. They lie on the same line. Set B vectors (black and blue) are linearly independent as v3 cannot be written as a scalar multiple of v1. They point in different directions.

Why Linear Independence Matters in Machine Learning

Linear independence is not just an abstract algebraic property. It has direct consequences in machine learning, particularly when dealing with features:

1. Feature Redundancy: If feature vectors in a dataset are linearly dependent, it indicates that some features don't provide unique information relative to others. For instance, if one feature is simply the sum of two other features (e.g., total_sales = domestic_sales + international_sales), including all three might be redundant. This can increase model complexity unnecessarily and sometimes obscure the importance of the underlying independent factors.

2. Multicollinearity in Models: In models like linear regression, we often solve systems of equations involving the feature matrix $X$. If the columns of $X$ (representing different features) are linearly dependent, the matrix $X^TX$ becomes singular (non-invertible) or close to singular. This situation, known as perfect or high multicollinearity, makes it impossible to find a unique solution for the model coefficients. The estimates become highly sensitive to small changes in the data, standard errors inflate, and interpreting the contribution of individual features becomes unreliable.

3. Dimensionality and Basis: Linearly independent sets of vectors are essential for defining a "basis" for a vector space or subspace, which represents the fundamental directions or components of that space. Understanding linear independence helps in dimensionality reduction techniques where the goal is often to find a smaller set of linearly independent vectors (or components) that capture most of the information in the original data.

Checking for Linear Independence

How do we determine if a set of vectors {$v_1, v_2, ..., v_k$} is linearly independent? We need to check if the only solution to $c_1v_1 + c_2v_2 + ... + c_kv_k = \vec{0}$ is $c_1 = c_2 = ... = c_k = 0$.

This vector equation can be rewritten as a matrix equation. Let $A$ be the matrix whose columns are the vectors $v_1, v_2, ..., v_k$. Let $c$ be the column vector of the unknown coefficients $[c_1, c_2, ..., c_k]^T$. The equation becomes:

$Ac = \vec{0}$

This is a homogeneous system of linear equations.

• The vectors {$v_1, ..., v_k$} are linearly independent if and only if the system $Ac = \vec{0}$ has only the trivial solution $c = \vec{0}$.
• The vectors are linearly dependent if and only if the system $Ac = \vec{0}$ has at least one non-trivial solution (where at least one $c_i \neq 0$).

From our knowledge of linear systems (Chapter 3), we know that $Ac = \vec{0}$ has only the trivial solution if and only if the matrix $A$ has full column rank. That is, the rank of the matrix $A$ must be equal to the number of columns (which is the number of vectors, $k$).

Practical Check using Rank: The most common way to check for linear independence computationally is to form the matrix $A$ with the vectors as columns and then compute its rank.

• If rank(A) == k (number of vectors), the vectors are linearly independent.
• If rank(A) < k, the vectors are linearly dependent.

We can use libraries like NumPy to compute the rank:

import numpy as np

# Example 1: Linearly Dependent Vectors (from plot)
v1 = np.array([2, 1])
v2 = np.array([4, 2])
A = np.array([v1, v2]).T # Vectors as columns
# A is [[2, 4],
#       [1, 2]]
rank_A = np.linalg.matrix_rank(A)
num_vectors_A = A.shape[1]
print(f"Set A: Matrix rank = {rank_A}, Number of vectors = {num_vectors_A}")
# Output: Set A: Matrix rank = 1, Number of vectors = 2
# Since rank < number of vectors, they are linearly dependent.

# Example 2: Linearly Independent Vectors (from plot)
v1 = np.array([2, 1])
v3 = np.array([1, 3])
B = np.array([v1, v3]).T # Vectors as columns
# B is [[2, 1],
#       [1, 3]]
rank_B = np.linalg.matrix_rank(B)
num_vectors_B = B.shape[1]
print(f"Set B: Matrix rank = {rank_B}, Number of vectors = {num_vectors_B}")
# Output: Set B: Matrix rank = 2, Number of vectors = 2
# Since rank == number of vectors, they are linearly independent.

# Example 3: Three vectors in R^2 (must be dependent)
v1 = np.array([2, 1])
v3 = np.array([1, 3])
v4 = np.array([-1, 1])
C = np.array([v1, v3, v4]).T
# C is [[ 2,  1, -1],
#       [ 1,  3,  1]]
rank_C = np.linalg.matrix_rank(C)
num_vectors_C = C.shape[1]
print(f"Set C: Matrix rank = {rank_C}, Number of vectors = {num_vectors_C}")
# Output: Set C: Matrix rank = 2, Number of vectors = 3
# Since rank < number of vectors, they are linearly dependent.
# (As expected, you can't have 3 linearly independent vectors in R^2)

Understanding linear independence is fundamental. It helps us identify redundancy in data, ensures the stability of certain machine learning algorithms, and forms the foundation for concepts like basis and dimension, which we will explore next. These concepts allow us to precisely define the "size" and structure of the vector spaces our data lives in.