Linear Independence, Rank, and Bases

A set of vectors is linearly independent when none of them is a combination of the others. The rank of a matrix is the number of independent columns it has, and a square matrix is invertible exactly when its columns are independent. These facts decide which column sets can serve as a basis, and therefore which points a linear program can call a basic solution.

Definition

Vectors $v_{1}, \dots, v_{k}$ are linearly independent when the only scalars $λ_{1}, \dots, λ_{k}$ satisfying $λ_{1} v_{1} + \dots + λ_{k} v_{k} = 0$ are all zero; otherwise they are dependent, and some vector is a combination of the others. The rank of a matrix is the number of vectors in its largest independent set of columns, which equals the number of pivots in its reduced row echelon form. A square matrix is invertible exactly when its columns are independent, equivalently when its rank is full, equivalently when its determinant is nonzero.

Formal statement

For $A \in R^{m \times n}$ , $rank (A)$ is the dimension of the column space. For square $A \in R^{m \times m}$ the following are equivalent: the columns are linearly independent; $rank (A) = m$ ; $det A \neq 0$ ; $A^{- 1}$ exists; $A x = b$ has exactly one solution for every $b$ .

Assumptions and scope

More than $m$ vectors in $R^{m}$ are always dependent, so a counting argument settles independence before any computation when the set is large enough.
Independence is a property of a set, not of individual vectors. No single vector is independent or dependent on its own, apart from the zero vector, which makes any set containing it dependent.
A determinant of zero shows singularity but not how the columns are related. Reduced row echelon form both detects dependence and exhibits the combination.
Rank is the number of independent columns, and equals the number of independent rows. Column rank and row rank always agree, which is why row operations can be used to find either.

Worked material

Example

An independent pair and a dependent triple

Independent. Take

a_{1} = (\begin{matrix} 1 \\ 2 \end{matrix}), a_{2} = (\begin{matrix} 3 \\ 1 \end{matrix}) .

Suppose $λ_{1} a_{1} + λ_{2} a_{2} = 0$ . Reading the two rows gives $λ_{1} + 3 λ_{2} = 0$ and $2 λ_{1} + λ_{2} = 0$ . From the second, $λ_{2} = - 2 λ_{1}$ ; substituting into the first gives $λ_{1} - 6 λ_{1} = - 5 λ_{1} = 0$ , so $λ_{1} = 0$ and then $λ_{2} = 0$ . Only the trivial combination vanishes, so the pair is independent.

Equivalently, the matrix $(\begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix})$ has determinant $1 - 6 = - 5 \neq 0$ .

Dependent. Now add

a_{3} = (\begin{matrix} 2 \\ - 1 \end{matrix}) .

Three vectors in $R^{2}$ are always dependent, because rank cannot exceed 2. The counting argument settles the question before any computation.

The explicit relation is

a_{3} = - a_{1} + a_{2},

since $- 1 + 3 = 2$ in the first component and $- 2 + 1 = - 1$ in the second. Rearranged, $a_{1} - a_{2} + a_{3} = 0$ is a nontrivial combination giving the zero vector.

What this shows. No two of $a_{1}, a_{2}, a_{3}$ are multiples of one another, yet the set is dependent. Independence is not a pairwise property.

Contrast

Pairwise non-proportionality is not independence

Checking that no two vectors are multiples of each other is a valid test for a set of two. Applied to three or more it gives the wrong answer, and it gives it confidently.

The tempting reasoning. Take

a_{1} = (\begin{matrix} 1 \\ 2 \end{matrix}), a_{2} = (\begin{matrix} 3 \\ 1 \end{matrix}), a_{3} = (\begin{matrix} 2 \\ - 1 \end{matrix}) .

No two are proportional: $a_{2}$ is not a multiple of $a_{1}$ , nor $a_{3}$ of $a_{1}$ , nor $a_{3}$ of $a_{2}$ . Each points a different way. So the set looks independent.

Why it is not. The definition allows all three coefficients to vary at once, and

a_{1} - a_{2} + a_{3} = (\begin{matrix} 1 - 3 + 2 \\ 2 - 1 - 1 \end{matrix}) = (\begin{matrix} 0 \\ 0 \end{matrix})

is a nontrivial combination giving zero. Equivalently $a_{3} = - a_{1} + a_{2}$ : the third vector is reachable from the first two, so it adds no new direction.

The counting argument settles it instantly. Three vectors in $R^{2}$ are always dependent, whatever they look like, because rank cannot exceed the number of components. The pairwise check cannot see this, since it never considers three vectors together.

Where it does real damage. In a linear program, a basis is a set of $m$ columns that must be independent. Selecting columns by eye because they look different produces a singular basis matrix, and then $A_{B}^{- 1}$ does not exist: the basic solution is undefined and the iteration cannot proceed. The failure appears as a division by zero deep in the arithmetic rather than as a clear message about the columns.

The reliable test. Count first; if the count does not settle it, reduce or take a determinant. Reserve the proportionality check for pairs.

Common errors

Common misconception

A set of vectors is linearly independent as long as no two of them are multiples of each other.

Related units

Connected

Extreme Points and Basic Feasible Solutions (used by)
One Iteration of the Simplex Method (used by)
Basic Solutions (suggested next)

Learn this topic

Linear Independence, Rank, and Bases

Used in

Foundations for Operational Research

Sources

Introduction to Linear Algebra (2016)
Introduction to Linear Optimization (1997)

Linear Independence, Rank, and Bases

Assumptions and scope

Worked material

An independent pair and a dependent triple

Pairwise non-proportionality is not independence

Common errors

Related units

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history