Linear Independence, Dependence Relations, and Matrix Column Analysis

Foundations of Linear Independence and Dependence

• Linear Independence Definition:

  • An indexed set of vectors $\mathbf{\{v_1, v_2, \dots, v_p\}}$ in $\mathbb{R}^n$ is said to be linearly independent if the vector equation $x_1 v_1 + x_2 v_2 + \dots + x_p v_p = 0$ has only the trivial solution: $x_1 = 0$, $x_2 = 0$, $\dots$, $x_p = 0$.
  • No vector in the set can be expressed as a linear combination of the others when the set is linearly independent.

• Linear Dependence Definition:

  • An indexed set of vectors $\mathbf{\{v_1, v_2, \dots, v_p\}}$ is said to be linearly dependent if there exist weights $x_1, x_2, \dots, x_p$, not all zero, such that $x_1 v_1 + x_2 v_2 + \dots + x_p v_p = 0$.
  • If at least one non-zero weight exists satisfying the equation, a non-trivial solution is confirmed.

• Linear Dependence Relation:

  • An equation $x_1 v_1 + x_2 v_2 + \dots + x_p v_p = 0$ with non-zero weights $x_1, x_2, \dots, x_p$ is called a linear dependence relation among the vectors $v_1, v_2, \dots, v_p$

Algorithmic Verification via Row Reduction and Echelon Forms

• System Representation and Rationale:

  • To test whether a set of vectors $\mathbf{\{v_1, v_2, v_3\}}$ is linearly independent, set up the homogeneous vector equation $x_1 v_1 + x_2 v_2 + x_3 v_3 = 0$ and evaluate if free variables exist in its augmented matrix representation.

• Step-by-Step Echelon Reduction Process:

  • Place vector components into an augmented matrix $[v_1 \quad v_2 \quad v_3 \quad 0]$.
  • Apply Gaussian row reduction operations to transform the augmented matrix into row echelon form (REF) and reduced row echelon form (RREF).
  • Example row elimination yields Intermediate Matrix entries such as $-3, -3, 0, 0, 0, 0$ in intermediate steps.
  • Scale row 2 to obtain a leading pivot entry of $1$.
  • Perform upper elimination to create zeros above all pivot positions.

• Pivot Column Analysis & Basic/Free Variables:

  • Pivot columns correspond directly to basic variables.
  • Columns lacking a pivot entry correspond to free variables.
  • In a system where columns 1 and 2 contain pivots while column 3 lacks a pivot:
  • $x_1$ is a basic variable.
  • $x_2$ is a basic variable.
  • $x_3$ is a free variable.
  • The presence of a free variable confirms the existence of infinitely many non-trivial solutions, establishing that the set of vectors is linearly dependent.

• Deriving a Explicit Linear Dependence Relation:

  • Convert the RREF matrix back into algebraic equations:
  • $x_1 - 2x_3 = 0$
  • $x_2 + x_3 = 0$
  • Solve for the basic variables in terms of the free variable $x_3$:
  • $x_1 = 2x_3$
  • $x_2 = -x_3$
  • $x_3 = x_3$ (free)
  • Choose an arbitrary non-zero value for the free variable to generate a specific relation. Setting $x_3 = 1$ yields:
  • $x_1 = 2$
  • $x_2 = -1$
  • $x_3 = 1$
  • Substituting these weights back into the vector equation yields the explicit linear dependence relation:
  • $2 v_1 - 1 v_2 + 1 v_3 = 0$

Linear Independence of Matrix Columns

• Equivalence of Vector Equations and Matrix Equations:

  • Let $A = [a_1 \quad a_2 \quad \dots \quad a_n]$ be an $m \times n$ matrix with column vectors $a_1, a_2, \dots, a_n$.
  • The matrix equation $A x = 0$ is identical to the vector equation $x_1 a_1 + x_2 a_2 + \dots + x_n a_n = 0$
  • The columns of matrix $A$ are linearly independent if and only if $A x = 0$ has only the trivial solution.

• Criteria via Free Variables:

  • Columns of $A$ are linearly independent $\iff$ Every column of $A$ is a pivot column (no free variables).
  • Columns of $A$ are linearly dependent $\iff$ $A$ contains at least one non-pivot column (at least one free variable).

• Concrete Row Reduction Step Example:

  • Given an augmented matrix setup with top row $1, 2, -1, 0$ and second row $0, 1, 4, 0$:
  • Applying row elimination operations, such as adding $-5$ times Row 1 to Row 2:
  • First entry: $1 \times (-5) + 5 = 0$
  • Second entry: $2 \times (-5) = -10$, and $-10 + 8 = -2$
  • Third entry: $-1 \times (-5) = 5$, and $5 + 0 = 5$
  • Evaluate whether unique solutions exist for basic variables to classify column independence across any arbitrary vector set.

Special Cases: One-Vector and Two-Vector Sets

• Single Vector Sets:

  • A set containing a single vector $\mathbf{\{v_1\}}$ is linearly independent if and only if $v_1 \neq 0$
  • If $v_1 = 0$, the set $\mathbf{\{0\}}$ is linearly dependent because $x_1 (0) = 0$ has non-trivial solutions for any $x_1 \neq 0$

• Two-Vector Sets:

  • A set of two vectors $\mathbf{\{v_1, v_2\}}$ is linearly dependent if and only if at least one of the vectors is a scalar multiple of the other.
  • The set $\mathbf{\{v_1, v_2\}}$ is linearly independent if and only if neither vector is a scalar multiple of the other.
  • Mathematical Proof for Two Vectors:
  • Equation: $x_1 v_1 + x_2 v_2 = 0$
  • If $v_2 = c v_1$, then $c v_1 - 1 v_2 = 0$. Since weight $-1 \neq 0$, non-trivial weights exist, proving linear dependence.
  • If $v_2$ is not a multiple of $v_1$, no non-zero weights $x_1, x_2$ can satisfy $x_1 v_1 + x_2 v_2 = 0$, forcing $x_1 = 0$ and $x_2 = 0$

• Numerical Testing Example:

  • Consider vectors $v_1 = \begin{pmatrix} 6 \\ 5 \end{pmatrix}$ and $v_2 = \begin{pmatrix} 6 \\ 2 \end{pmatrix}$.
  • Check if $v_2$ is a scalar multiple of $v_1$:
  • Setting $c \times 6 = 6$ requires $c = 1$
  • Testing second component: $1 \times 5 = 5 \neq 2$
  • Because $v_2$ is not a scalar multiple of $v_1$, the only solution to $x_1 v_1 + x_2 v_2 = 0$ is $x_1 = 0, x_2 = 0$
  • Conclusion: The set $\mathbf{\{v_1, v_2\}}$ is linearly independent.

Characterization Theorem for Linearly Dependent Sets

• Theorem Statement:

  • An indexed set $S = \{v_1, v_2, \dots, v_p\}$ of two or more vectors (with $v_1 \neq 0$) is linearly dependent if and only if there exists some vector $v_j$ (with $j > 1$) that is a linear combination of the preceding vectors $v_1, v_2, \dots, v_{j-1}$.

• Formal Proof:

  • Direct Direction (Dependence implies linear combination of preceding vectors):
  • Assume $S = \{v_1, v_2, \dots, v_p\}$ is linearly dependent.
  • Then there exist coefficients $c_1, c_2, \dots, c_p$, not all zero, such that $c_1 v_1 + c_2 v_2 + \dots + c_p v_p = 0$
  • Let $c_j$ be the non-zero coefficient with the maximum index $j$ (i.e., $c_j \neq 0$ and $c_{j+1} = c_{j+2} = \dots = c_p = 0$).
  • The dependence equation reduces to $c_1 v_1 + c_2 v_2 + \dots + c_j v_j = 0$
  • The index $j$ must be strictly greater than $1$ ($j > 1$). (If $j = 1$, then $c_1 v_1 = 0$, which requires $v_1 = 0$, contradicting the hypothesis that $v_1 \neq 0$).
  • Isolating $c_j v_j$:       $c_j v_j = -c_1 v_1 - c_2 v_2 - \dots - c_{j-1} v_{j-1}$
  • Dividing by $c_j$ (valid since $c_j \neq 0$):       $v_j = \left(-\frac{c_1}{c_j}\right) v_1 + \left(-\frac{c_2}{c_j}\right) v_2 + \dots + \left(-\frac{c_{j-1}}{c_j}\right) v_{j-1}$
  • Thus, $v_j$ is expressed explicitly as a linear combination of preceding vectors $v_1, \dots, v_{j-1}$.

Geometric Interpretation in Vector Spaces

• Span of Two Non-Collinear Vectors in $\mathbb{R}^3$:

  • Let $u = \begin{pmatrix} 3 \\ 1 \\ 0 \end{pmatrix}$ and $v = \begin{pmatrix} 1 \\ 6 \\ 0 \end{pmatrix}$ in $\mathbb{R}^3$
  • Both vectors lie entirely within the $x_1 x_2$-plane because their third coordinate is zero ($x_3 = 0$).
  • The span $\text{Span}\{u, v\}$ defines a flat 2D plane passing through the origin within $\mathbb{R}^3$, specifically corresponding to the subspace where $x_3 = 0$

• Addition of Coplanar Vectors and Dependent Sets:

  • If a third vector $w$ is selected such that $w \in \text{Span}\{u, v\}$, then $w$ lies inside the plane formed by $u$ and $v$
  • By definition of span, there exist scalars $c_1, c_2$ such that $w = c_1 u + c_2 v$
  • Re-arranging gives $c_1 u + c_2 v - 1 w = 0$, which proves that the set $\mathbf{\{u, v, w\}}$ forms a linearly dependent set.

Questions & Discussion

• Question: How do we verify whether a vector $b = \begin{pmatrix} 1 \\ 3 \end{pmatrix}$ is a scalar multiple of $u = \begin{pmatrix} 3 \\ 1 \end{pmatrix}$?

  • Response: Set up the scalar equation $b = c u$. Component-wise, $1 = 3 c \implies c = \frac{1}{3}$. Checking the second component: $\frac{1}{3} \times 1 = \frac{1}{3} \neq 3$. Thus $b \neq c u$, confirming $b$ is not a scalar multiple of $u$.

• Question: What geometric effect does linear independence have on points in higher dimensions?

  • Response: If vectors are linearly independent, their span expands the overall dimension of the space, allowing reach to any arbitrary point across that higher-dimensional space without collapsing into a lower-dimensional line or plane.