Linear dependence and independence

Motivation

A spanning list tells us which vectors can be generated. It may contain redundancy: one member can be a linear combination of the others, so deleting that member leaves the span unchanged. Linear dependence detects exactly this possibility.

Definitions

Definition

Linear independence of a finite list

Let $V$ be a real vector space. A finite list $(u_1,u_2,\ldots,u_n)$ in $V$ is linearly independent if

$$\alpha_1u_1+\alpha_2u_2+\cdots+\alpha_nu_n=0$$

implies $\alpha_1=\alpha_2=\cdots=\alpha_n=0$.

Definition

Linear dependence of a finite list

The same list is linearly dependent if there exists a nontrivial choice of scalars (not all zero) with

$$\alpha_1u_1+\alpha_2u_2+\cdots+\alpha_nu_n=0.$$

The equation with all coefficients zero is the trivial relation. Any other relation is nontrivial. Independence means only the trivial relation exists.

Which vector can be removed?

Theorem

Dependence is equivalent to one vector being generated by the others

For a finite list $(u_1,\ldots,u_n)$ with $n\ge 2$, the following are equivalent:

1. The list is linearly dependent.
2. At least one vector in the list is a linear combination of the remaining vectors.

So a dependent list always contains a removable vector that does not change the span.

Proof

Proof of the redundancy criterion

$(1) \Rightarrow (2)$: start from a nontrivial relation $\sum_{i=1}^n\alpha_i u_i=0$. Choose an index $k$ with $\alpha_k\ne 0$. Rearrange:

$$u_k=-\sum_{i\ne k}\frac{\alpha_i}{\alpha_k}u_i,$$

so $u_k$ is generated by the remaining vectors.

$(2) \Rightarrow (1)$: if $u_k=\sum_{i\ne k}\beta_i u_i$, move all terms to one side. You obtain a nontrivial relation, hence dependence.

The key logic: dependence is exactly the existence of at least one solvable elimination step inside the list.

Proof X-Ray

A relation identifies which vectors can be removed

A nontrivial relation means at least one coefficient is nonzero, not that every coefficient is nonzero. The redundancy proof may divide only by a coefficient known to be nonzero. Thus a particular relation identifies removable vectors at its nonzero positions; it does not license deleting an arbitrary vector.

For example, the list $(e_1,e_2,2e_1)$ in $\mathbb R^2$ satisfies $-2e_1+0e_2+1(2e_1)=0$. Either the first or the third vector can be recovered from the other two. Removing $e_2$, however, leaves only multiples of $e_1$ and loses the vector $e_2$ from the span. The zero coefficient on $e_2$ supplies no formula for recovering it. This is why the proof selects an index with nonzero coefficient before rearranging.

Worked example

A redundant vector can be removed without changing the span

Let

$$u_1 = \begin{bmatrix}1\\2\\1\end{bmatrix},\qquad u_2 = \begin{bmatrix}0\\1\\1\end{bmatrix},\qquad u_3 = \begin{bmatrix}1\\3\\2\end{bmatrix}.$$

Here $u_3 = u_1 + u_2$. So every vector of the form

$$a u_1 + b u_2 + c u_3$$

can be rewritten as

$$(a+c)u_1 + (b+c)u_2.$$

Therefore

$$\operatorname{Span}\{u_1,u_2,u_3\} = \operatorname{Span}\{u_1,u_2\}.$$

The third vector changes the description, but not the span itself.

Theorem

A redundant vector can be removed without changing the span

If one vector in a list is a linear combination of the others, then deleting it does not change the span of the list.

Proof

Why the span stays the same

One inclusion is automatic: the shorter list is a subset of the longer list, so its span is contained in the larger span.

For the other inclusion, replace the redundant vector by the combination of the remaining vectors and collect like terms. Every linear combination of the longer list becomes a linear combination of the shorter one.

Counterexample mode

Spanning does not guarantee independence

False claim. A list that spans the whole ambient space must be linearly independent.

Reconsider $(e_1,e_2,2e_1)$ in $\mathbb R^2$. Every $(a,b)^T$ equals $ae_1+be_2+0(2e_1)$, so the list spans all of $\mathbb R^2$. Nevertheless $-2e_1+0e_2+1(2e_1)=0$ is a nontrivial relation. Thus spanning supplies existence of representations, while independence requires uniqueness; existence alone does not supply uniqueness.

Repair. To obtain a basis, require both spanning and independence. Here delete $2e_1$. The remaining $(e_1,e_2)$ still spans, and $ae_1+be_2=0$ forces $a=b=0$ by coordinates. The repair removes redundancy without losing any output.

From a relation to a homogeneous system

The unknowns will be coefficients. A nonzero solution will record a nontrivial relation among the original generators; the pivot test makes this observation computational.

Theorem

Row-reduction test for dependence in $R^m$

Let $u_1,\ldots,u_n\in R^m$ and build

$$A=[u_1\ u_2\ \cdots\ u_n].$$

Then $u_1,\ldots,u_n$ are linearly independent iff the homogeneous system

$$Ax=0$$

has only the zero solution. Equivalently, when reducing $A$ to RREF, every column must be a pivot column.

Equivalently, the null space of this column matrix is $N(A)=\{0\}$.

Proof

Proof of the row-reduction criterion

By definition, dependence asks whether $\alpha_1u_1+\cdots+\alpha_nu_n=0$ has a nonzero coefficient vector. Writing coefficients as $x=(\alpha_1,\ldots,\alpha_n)^T$, this is exactly $Ax=0$ where columns are the vectors. Elementary row operations preserve the solution set of a homogeneous system, so the question is unchanged in RREF. A free variable gives a nonzero solution and therefore dependence; no free variables give only the zero solution and therefore independence.

This gives a complete algorithm.

1. Put the vectors into a column matrix $A=[u_1\ \cdots\ u_n]$.
2. Solve the homogeneous system $A\alpha=0$.
3. If there is a free variable, choose a nonzero value for it and read a nontrivial relation.
4. If every column is a pivot column, only the trivial solution exists and the vectors are independent.

A useful shortcut also falls out immediately: more than $m$ vectors in $R^m$ must be dependent, because an $m \times n$ matrix with $n>m$ cannot have a pivot in every column.

Common mistake

Row reduction is allowed because it preserves the homogeneous solution set

When you row reduce $A$ for independence testing, you are not changing the columns themselves into new vectors you want to study. You are simplifying the equation $A\alpha=0$. Row-equivalent matrices have the same homogeneous solutions, so they have the same dependence relations.

Read the relation, then check an independent list

Worked example

Read a dependence relation from row reduction

Take

$$A= \begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 3\\ 1 & 1 & 2 \end{bmatrix},$$

whose columns are $u_1=(1,2,1)^T$, $u_2=(0,1,1)^T$, and $u_3=(1,3,2)^T$. Row reduction gives

$$\begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 3\\ 1 & 1 & 2 \end{bmatrix} \xrightarrow{R_2-2R_1,\ R_3-R_1} \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 1 \end{bmatrix} \xrightarrow{R_3-R_2} \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0 \end{bmatrix}.$$

The third column is not a pivot column, so $\alpha_3$ is free in $A\alpha=0$. Set $\alpha_3=1$. Then the reduced system gives $\alpha_1=-1$ and $\alpha_2=-1$, so

$$-u_1-u_2+u_3=0,$$

or equivalently $u_3=u_1+u_2$.

Worked example

Independence test by RREF

Let

$$u_1=(1,2,0),\quad u_2=(0,1,1),\quad u_3=(2,5,1).$$

Set $A=[u_1\ u_2\ u_3]$:

$$A=\begin{bmatrix} 1&0&2\\ 2&1&5\\ 0&1&1 \end{bmatrix} \xrightarrow{R_2-2R_1} \begin{bmatrix} 1&0&2\\ 0&1&1\\ 0&1&1 \end{bmatrix} \xrightarrow{R_3-R_2} \begin{bmatrix} 1&0&2\\ 0&1&1\\ 0&0&0 \end{bmatrix}.$$

Column 3 is non-pivot, so $x_3$ is free in $Ax=0$. Therefore the list is dependent.

Worked example

Use row reduction to test independence

Let

$$u_1=\begin{bmatrix}1\\2\\1\end{bmatrix},\quad u_2=\begin{bmatrix}2\\4\\3\end{bmatrix},\quad u_3=\begin{bmatrix}1\\1\\0\end{bmatrix}.$$

Set $A=[u_1\ u_2\ u_3]$. Row reduce:

$$\begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 1\\ 1 & 3 & 0 \end{bmatrix} \xrightarrow{R_2-2R_1,\ R_3-R_1} \begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & -1\\ 0 & 1 & -1 \end{bmatrix} \xrightarrow{R_2\leftrightarrow R_3} \begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & -1\\ 0 & 0 & -1 \end{bmatrix}.$$

There is a pivot in each column, so the three vectors are linearly independent.

Worked example

Why a list containing the zero vector is dependent

Suppose $u_2=0$. Then

$$0\cdot u_1+1\cdot u_2+0\cdot u_3+\cdots+0\cdot u_n=0$$

is already a nontrivial relation (coefficient of $u_2$ is $1$). So any list containing $0$ is dependent.

The geometry behind a dependence relation

The following sequence connects the algebraic test to geometry. A third vector inside the span of the first two can be recovered from them, so adding it changes the list without enlarging its span.

After predicting dependence from the algebra, compare the corresponding geometric configurations below.

Fast low-dimensional tests

Theorem

Two nonzero vectors are independent exactly when neither is a scalar multiple of the other

For an ordered pair $(u,v)$ with both vectors nonzero, the pair is linearly independent if and only if one vector is not a scalar multiple of the other. The list convention retains both positions even when $u=v$.

Proof

Why two vectors reduce to a scalar-multiple test

If $au+bv=0$ is a nontrivial relation, then at least one coefficient is nonzero. If $b\ne 0$, solve for

$$v = -\frac{a}{b}u.$$

If $a\ne 0$, solve for

$$u = -\frac{b}{a}v.$$

Conversely, if $v=\lambda u$, then $\lambda u-v=0$ is a nontrivial relation; the case $u=\lambda v$ is analogous. Thus two vectors are dependent exactly when one is a scalar multiple of the other.

Worked example

Two vectors in $R^2$

Let

$$u = \begin{bmatrix}1\\2\end{bmatrix}, \qquad v = \begin{bmatrix}2\\4\end{bmatrix}.$$

Since $v=2u$, the pair is dependent. Geometrically, both vectors point in the same direction.

Worked example

Three vectors in $R^2$ must be dependent

If $u_1,u_2,u_3 \in R^2$, then the matrix $A=[u_1\ u_2\ u_3]$ has size $2\times 3$. After row reduction it can have at most two pivots, so one column is not a pivot column. Therefore $A\alpha=0$ has a nontrivial solution and the three vectors are linearly dependent.

Worked example

Three vectors in $R^3$ that lie in one plane

If three vectors in $R^3$ all lie in the plane $z=0$, then they all belong to the span of $e_1$ and $e_2$. But that plane is already generated by two independent directions, so a third vector cannot add a new independent direction. The list is dependent.

Theorem

Too many vectors in $R^m$ force dependence

Any list of more than $m$ vectors in $R^m$ is linearly dependent.

Proof

Why more than $m$ vectors cannot be independent in $R^m$

If $A$ is an $m\times n$ matrix with $n>m$, then row reduction can produce at most $m$ pivot columns. So at least one column is not a pivot column. That means $A\alpha=0$ has a free variable, hence a nontrivial solution. So the columns are dependent.

Common mistakes

Common mistake

Confusing dependence with not spanning

Dependent lists can still span a large space. Dependence only says the list is not minimal.

Common mistake

Forgetting that order does not matter for dependence

Permuting vectors changes their positions but not whether a nontrivial relation exists.

Summary

• Linear dependence can be read directly from the definition, as redundancy in a spanning list, or as a nonzero vector in the null space of a column matrix.
• Row reduction is used to simplify the coefficient equation $A\alpha=0$; it is not a replacement of the original vectors by new vectors.
• A free variable gives a nontrivial dependence relation, while a pivot in every column proves independence.
• Low-dimensional shortcuts, such as scalar-multiple tests in $R^2$ and the "more than $m$ vectors in $R^m$" rule, are consequences of the same pivot count logic.

Checkpoints: three ways to detect redundancy

Checkpoint

Decide whether $(1,0,0),(0,1,0),(1,1,0)$ in $R^3$ is independent.

Use either the redundancy criterion or the RREF test.

Solution · Exercise 1

Dependent, because $(1,1,0)=(1,0,0)+(0,1,0)$.

Checkpoint

Let $S=\{(1,1),(2,2)\}$ in $R^2$. Is $S$ independent?

Try to write one vector as a scalar multiple of the other.

Solution · Exercise 2

Dependent, because $(2,2)=2(1,1)$.

Checkpoint

If $\{u_1,u_2,u_3\}$ is independent, can $\{u_1,u_2,u_3,u_1+u_2\}$ be independent?

Translate the question into a linear relation.

Solution · Exercise 3

No. $u_1+u_2-(u_1+u_2)=0$ is a nontrivial relation in the larger list.

Exercises

Checkpoint

If a set has 5 vectors in $R^3$, can it be linearly independent?

Use pivots and the number of rows.

Solution · Answer

No. A $3\times 5$ matrix can have at most 3 pivots, so at least two columns are free-variable columns. Therefore a nontrivial relation must exist.

Checkpoint

Determine whether $\{(1,0,1),(2,1,3),(0,1,1)\}$ is independent.

Set them as columns, reduce, and read pivot columns.

Solution · Guided solution

Let $u_1,u_2,u_3$ denote the vectors in the stated order. The answer is dependent. Put them in the columns of $A$:

$$A=\begin{bmatrix}1&2&0\\0&1&1\\1&3&1\end{bmatrix} \sim\begin{bmatrix}1&2&0\\0&1&1\\0&0&0\end{bmatrix} \sim\begin{bmatrix}1&0&-2\\0&1&1\\0&0&0\end{bmatrix}.$$

The first stage subtracts row $1$ and row $2$ from row $3$; the second subtracts twice row $2$ from row $1$. Only columns $1$ and $2$ are pivot columns. Setting the free coefficient $\alpha_3=1$ gives $\alpha_1=2$ and $\alpha_2=-1$. Direct verification confirms

$$2(1,0,1)-(2,1,3)+(0,1,1)=(0,0,0).$$

The coefficient vector $(2,-1,1)$ is nonzero, so this is a nontrivial relation. Equivalently, $u_2=2u_1+u_3$.

Checkpoint

Show that $\{(1,2,3),(2,4,6),(1,0,1)\}$ is dependent by writing one vector from others.

Look for a direct scalar-multiple relation first.

Solution · Guided solution

$(2,4,6)=2(1,2,3)$, so $2(1,2,3)-(2,4,6)+0(1,0,1)=0$ is nontrivial. The set is dependent.

Checkpoint

Is any list containing the zero vector automatically dependent?

Test the definition directly.

Solution · Answer

Yes. Put coefficient $1$ on the zero vector and $0$ on every other vector. That already gives a nontrivial relation.

Checkpoint

If a $4\times 4$ matrix has four pivot columns, what does that say about its columns?

Use the matrix test.

Solution · Answer

The columns are linearly independent, because $A\alpha=0$ has only the trivial solution.

Checkpoint

Explain why any subset of a linearly independent set is linearly independent.

Think about what would happen if the subset had its own relation.

Solution · Guided solution

If a subset had a nontrivial relation, that same relation would also be a relation among the larger set after giving coefficient $0$ to the vectors that were not used. That would make the larger set dependent. So a subset of an independent set must also be independent.

Checkpoint

A list satisfies $2u_1-u_2+0u_3=0$. Which vectors can this relation justify deleting without changing the span?

Identify the nonzero coefficients; do not assume every vector is removable.

Solution · Guided solution

The relation gives $u_2=2u_1$ and $u_1=\tfrac12u_2$, so either $u_1$ or $u_2$ can be deleted. It gives no expression for $u_3$. For example, if $u_1=e_1$, $u_2=2e_1$ and $u_3=e_2$, deleting $u_3$ changes the span from the plane to a line.

Read this first

This section builds directly on 6.3 Linear combinations and span and the row-reduction workflow in 2.3 Gaussian elimination and RREF.

Independence removes redundancy; it does not guarantee that every target is reachable. In 6.5 Basis and dimension, we require independence and spanning together, then prove that the size of such a list is a property of the space.