[ALGEBRA] Linear independence

When linear combinations have unique coefficients and how to test for redundancy.

A set is linearly independent when the only combination giving $0$ is the trivial one. This page tests independence by row reduction and shows that it is exactly the condition for coefficients to be unique.

Independence removes redundancy

[DEFINITION]

Span

For a subset $S$ (possibly infinite) in a vector space $V$ over $F$ , the span of $S$ is the set of all finite linear combinations of vectors in $S$ :

\operatorname{span}(S) = \left\{ \lambda_1v_1+\cdots+\lambda_kv_k: k\geq 0,\ v_1,\ldots,v_k\in S,\ \lambda_1,\ldots,\lambda_k\in F \right\}.

For a finite set $S=\{v_1,\ldots,v_n\}$ , this is the same as allowing one coefficient for each listed vector. When $k=0$ , the sum is the empty sum $0$ .

[1]:Linear combination
[2]:Basis
[3]:A basis for a generated subspace
[4]:A basis of $P_1$
[5]:Spanning sets count against independent sets
17 more

[DEFINITION]

Linear independence

Let $S$ be a subset of a vector space over $F$ . The set $S$ is linearly independent if every finite list of distinct vectors $u_1,\ldots,u_n\in S$ has the property that, for scalars $\lambda_1,\ldots,\lambda_n\in F$ ,

\lambda_1u_1+\cdots+\lambda_nu_n=0

implies

\lambda_1=\cdots=\lambda_n=0.

An equation of this form is a relation among the chosen vectors. An independent set is one in which the zero vector has no non-trivial finite representation. An independent set therefore cannot contain the zero vector itself.

[1]:Linear combination
[2]:Span
[3]:Eigenvectors for distinct eigenvalues
[4]:When diagonalisation is possible
[5]:Column independence and nullity
[6]:Basis
15 more

[DEFINITION]

Linear dependence

A set $S$ is linearly dependent if some finite list of distinct vectors $u_1,\ldots,u_n\in S$ has scalars, not all zero, such that

\lambda_1u_1+\cdots+\lambda_nu_n=0.

Dependence is exactly the failure of linear independence.

[EXAMPLE]

A parameter decides independence

Let

u_1=\begin{pmatrix}1\\1\end{pmatrix}, \qquad u_2=\begin{pmatrix}2\\\alpha\end{pmatrix}.

The homogeneous relation

\lambda_1u_1+\lambda_2u_2=0

gives

\lambda_1+2\lambda_2=0, \qquad \lambda_1+\alpha\lambda_2=0.

If $\alpha=2$ , the two equations are the same, so non-zero solutions exist and the set is dependent. If $\alpha\neq2$ , subtraction gives $\lambda_2=0$ , then $\lambda_1=0$ , so the set is independent.

[routine]

[1]:Linear independence
[2]:Linear dependence

Testing independence by row reduction

When the vectors are placed as columns of a matrix, the definition becomes a test on a homogeneous system.

[THEOREM]

The homogeneous-system test

Let $S=\{u_1,\ldots,u_n\}\subseteq\mathbb R^m$ and let

A=[\,u_1\ \cdots\ u_n\,].

Then $S$ is linearly independent if and only if the homogeneous system

Ax=0

has only the zero solution. Equivalently, after row reduction, every column of $A$ contains a pivot. If a column has no pivot, the free variable in that column produces a non-trivial dependence relation among the original columns.

If $m<n$ , there cannot be a pivot in every column, so any $n$ vectors in $\mathbb R^m$ with $m<n$ are dependent.

When $S$ is dependent, the original vectors in the pivot columns form an independent subset with the same span as $S$ . This works because row operations left-multiply by an invertible matrix, so they preserve every linear relation among the columns. Each non-pivot column is therefore a combination of the pivot columns, not necessarily only the earlier ones.

[1]:Linear independence
[2]:Linear dependence
[3]:A linear map, bases and a discrete-time system
[4]:Seen Questions
[5]:A basis of $\mathbb R^3$
[6]:A basis for a generated subspace
11 more

[EXAMPLE]

Two vectors in $\mathbb R^3$

Consider

u_1=\begin{pmatrix}1\\-2\\3\end{pmatrix}, \qquad u_2=\begin{pmatrix}-1\\2\\-4\end{pmatrix}.

The equations in

\lambda_1u_1+\lambda_2u_2=0

include $\lambda_1-\lambda_2=0$ and $3\lambda_1-4\lambda_2=0$ . Hence $\lambda_1=\lambda_2$ and then $\lambda_1=0$ , so $\lambda_2=0$ . The two vectors are linearly independent.

[routine]

[1]:The homogeneous-system test

[EXAMPLE]

Removing a redundant vector

Let

S=\left\{ \begin{pmatrix}1\\2\end{pmatrix}, \begin{pmatrix}1\\3\end{pmatrix}, \begin{pmatrix}1\\4\end{pmatrix} \right\}.

The third vector is twice the second minus the first, so it adds no new direction. The first two vectors are independent because neither is a scalar multiple of the other. Therefore

\left\{ \begin{pmatrix}1\\2\end{pmatrix}, \begin{pmatrix}1\\3\end{pmatrix} \right\}

is independent and has the same span as $S$ .

[routine]

[1]:The homogeneous-system test
[2]:Span

Independence is uniqueness

[THEOREM]

Independence and uniqueness

Suppose

v=\lambda_1u_1+\cdots+\lambda_nu_n.

The coefficients $\lambda_1,\ldots,\lambda_n$ are unique if and only if $\{u_1,\ldots,u_n\}$ is linearly independent.

The span gives existence of a representation; independence gives its uniqueness.

[1]:Linear independence
[2]:Span
[3]:Representation in a basis
[4]:Coordinate vector
[5]:Proof
[6]:Dependence gives non-unique coefficients

[PROOF]

If the coefficients in the displayed representation of $v$ are unique, suppose a non-zero relation

c_1u_1+\cdots+c_nu_n=0

exists. Then

v=(\lambda_1+c_1)u_1+\cdots+(\lambda_n+c_n)u_n

is another representation of $v$ . Since some $c_j\neq0$ , the two representations are different, a contradiction. Thus the set is linearly independent. Conversely, suppose

v=\lambda_1u_1+\cdots+\lambda_nu_n =\alpha_1u_1+\cdots+\alpha_nu_n.

Subtracting gives

(\lambda_1-\alpha_1)u_1+\cdots+(\lambda_n-\alpha_n)u_n=0.

Independence forces $\lambda_j-\alpha_j=0$ for every $j$ , so the two representations are the same.

[1]:Independence and uniqueness

[EXAMPLE]

Dependence gives non-unique coefficients

The set

S=\left\{ \begin{pmatrix}1\\2\end{pmatrix}, \begin{pmatrix}1\\3\end{pmatrix}, \begin{pmatrix}1\\4\end{pmatrix} \right\}

is dependent. For example,

\begin{pmatrix}1\\4\end{pmatrix} =-\begin{pmatrix}1\\2\end{pmatrix} +2\begin{pmatrix}1\\3\end{pmatrix} =-2\begin{pmatrix}1\\2\end{pmatrix} +4\begin{pmatrix}1\\3\end{pmatrix} -\begin{pmatrix}1\\4\end{pmatrix}.

The relation $(1,2)^T-2(1,3)^T+(1,4)^T=0$ explains the two representations: adding a multiple of it changes the coefficients without changing the vector.

[routine]

[1]:Independence and uniqueness

Locating the redundant direction

Dependence can also be read as one vector lying in the span of the others. The polynomial example below is over $\mathbb R$ , so $P_1$ denotes $P_1(\mathbb R)$ .

[THEOREM]

Independence and the span of the other vectors

A finite set $S$ is linearly independent if and only if no vector in $S$ belongs to the span of the other vectors.

If $u_j$ is a combination of the other vectors, moving it to one side gives a non-trivial relation equal to zero. Conversely, in a non-trivial relation, choose a vector with a non-zero coefficient and solve for it in terms of the others.

[EXAMPLE]

Dependence in $P_1$

The set

\{x,\ 1+x,\ 1-x\}

is dependent: equating coefficients in

\lambda_1x+\lambda_2(1+x)+\lambda_3(1-x)=0

gives the non-trivial choice $\lambda_1=-2$ , $\lambda_2=1$ , $\lambda_3=-1$ . The subset $\{x,1+x\}$ is independent, since the constant coefficient forces the coefficient of $1+x$ to be zero and then the coefficient of $x$ forces the other coefficient to be zero.

[routine]

[1]:Independence and the span of the other vectors

Extending an independent set

[THEOREM]

Adding a vector to a span

For a finite set $S$ and a vector $v$ ,

\operatorname{span}(S\cup\{v\})=\operatorname{span}(S)

if and only if

v\in\operatorname{span}(S).

Since $S\subseteq S\cup\{v\}$ , we always have $\operatorname{span}(S)\subseteq\operatorname{span}(S\cup\{v\})$ . If $v\in\operatorname{span}(S)$ , every combination using $v$ can be rewritten using only vectors in $S$ , so the reverse inclusion also holds. Conversely, if the spans are equal, then $v$ belongs to $\operatorname{span}(S\cup\{v\})$ and hence to $\operatorname{span}(S)$ .

Two consequences follow. Removing any vector from an independent set leaves an independent set with a smaller span. From a dependent set, some vector can be removed without changing the span.

[COROLLARY]

Adjoining a vector outside the span

If $S$ is linearly independent and $v\notin\operatorname{span}(S)$ , then $S\cup\{v\}$ is linearly independent.

[1]:Adding a vector to a span
[2]:Linear independence
[3]:Extend an independent set to a basis
[4]:Proof

[PROOF]

Write $S=\{u_1,\ldots,u_n\}$ . Suppose

\lambda_1u_1+\cdots+\lambda_nu_n+\mu v=0.

If $\mu\neq0$ , then $v$ is a linear combination of the vectors in $S$ , contradicting $v\notin\operatorname{span}(S)$ . Hence $\mu=0$ and the independence of $S$ forces $\lambda_1=\cdots=\lambda_n=0$ . Therefore $S\cup\{v\}$ is linearly independent.

[1]:Adjoining a vector outside the span

This result is the step used to extend an independent set to a basis.

Basis and dimension combines spanning with independence and counts the vectors required.

Linear independence

Span

On this page