Independence

Vector spaces: Spans

Independence

In Reduction with vectors we have seen an example of a subspace spanned by three vectors that can be spanned by two vectors. We now discuss how to find from a given set of vectors an efficient set of vectors that spans the same subspace as the given set. In addition to the theorem Standard operations with spanning sets and the Exchange Theorem, the concepts of dependence and independence play a role here.

(In)dependent set
A sequence of vectors #\vec{u}_1,\ldots ,\vec{u}_n# of a vector space is called (linearly) dependent if at least one of the vectors is dependent on the others, and (linearly) independent if none of the vectors is a linear combination of the others.

If one of the vectors of the above sequence is a linear combination of some of the others, it is said to be (linearly) dependent on these others. If not, it is said to be (linearly) independent of the others.

A non-trivial relation between the vectors #\vec{u}_1,\ldots ,\vec{u}_n# is an equality
\[
\lambda_1 \cdot\vec{u}_1 + \lambda_2\cdot \vec{u}_2 + \cdots + \lambda_n\cdot \vec{u}_n =\vec{0},
\] in which at least one of the numbers #\lambda_1, \lambda_2, \ldots ,\lambda_n# is distinct from #0#.

If there is a non-trivial relation between two vectors #\vec{u}_1# and #\vec{u}_2#, then there are scalars #\lambda_1# and #\lambda_2# such that #\lambda_1 \cdot\vec{u}_1 =- \lambda_2\cdot \vec{u}_2#, where #\lambda_1# or #\lambda_2# is distinct from zero. In the first case, #\vec{u}_1=-\frac{\lambda_2}{\lambda_1}\cdot\vec{u}_2# is a scalar multiple of #\vec{u}_2#, in the second case #\vec{u}_2=-\frac{\lambda_1}{\lambda_2}\cdot\vec{u}_1# is a scalar multiple of #\vec{u}_1#. The existence of a non-trivial relation between two vectors boils down to the fact that (at least) one of the two is a scalar multiple of the other.

Each set of vectors is either dependent or independent.

The properties of dependence and independence of the sequence of vectors #\vec{u}_1,\ldots ,\vec{u}_n# do not depend on the choice of the order of the vectors, so we also speak of the (linear) dependence and independence of a set of vectors.

To determine whether a given set of vectors is linearly independent, we often use the following criterion:

Dependence criterion
A set of vectors #\vec{u}_1,\ldots ,\vec{u}_n# of a vector space is dependent if and only if there is a non-trivial relation between the vectors #\vec{u}_1,\ldots ,\vec{u}_n#.

Proof of the implication #\Leftarrow# : If the equation \[
\lambda_1 \cdot\vec{u}_1 + \lambda_2\cdot \vec{u}_2 + \cdots + \lambda_n\cdot \vec{u}_n =\vec{0}
\] has a solution in which, for example, #\lambda_i \neq 0#, then
\[
\vec{u}_i = \frac{-\lambda_1}{\lambda_i} \vec{u}_1 + \frac{-\lambda_{i-1}}{\lambda_i} \vec{u}_{i-1}+ \frac{-\lambda_{i+1}}{\lambda_i} \vec{u}_{i+1} +
\frac{-\lambda_n}{\lambda_i} \vec{u}_n ,
\]
so #\vec{u}_i# is dependent on the other vectors.

Proof of the implication #\Rightarrow# : Assume that the equation \[
\lambda_1 \cdot\vec{u}_1 + \lambda_2\cdot \vec{u}_2 + \cdots + \lambda_n\cdot \vec{u}_n =\vec{0}
\] has only the zero solution. If, for example #\vec{u}_i# is dependent on the vectors #\vec{u}_1, \ldots , \vec{u}_{i-1}, \vec{u}_{i+1},\ldots , \vec{u}_n#, that is to say, can be written as
\[
\vec{u}_i = \mu_1 \vec{u}_1 + \cdots + \mu_{i-1}\vec{u}_{i-1} + \mu_{i+1}\vec{u}_{i+1}
+ \cdots + \mu_n \vec{u}_n
\]
then it follows from the non-trivial relation that
\[
\mu_1 \vec{u}_1 + \cdots + \mu_{i-1}\vec{u}_{i-1} -1\cdot\vec{u}_i + \mu_{i+1}\vec{u}_{i+1}
+ \cdots + \mu_n \vec{u}_n =\vec{0}
\]
in contradiction to the given hypothesis.

In other words, the set is linearly dependent if and only if one of its vectors is linearly dependent on the others.

Two real numbers #a# and #b# are dependent in #\mathbb{R}#:

if both are zero, then #1\cdot a+ 1\cdot b = 0# is a nontrivial relation;
if at least of #a# and #b# is nonzero, then #b\cdot a- a\cdot b=0# is a nontrivial relation.

With this criterion, we can test (in)dependence of the set of vectors #\vec{u}_1,\ldots ,\vec{u}_n# by solving the system of linear equations \[\lambda_1\cdot\vec{u}_1 + \lambda_2\cdot \vec{u}_2 + \cdots + \lambda_n \cdot\vec{u}_n =\vec{0}\] with unknowns #\lambda_1#, #\lambda_2, \ldots ,\lambda_n#. If the only solution is #\lambda_1 =0, \lambda_2=0, \ldots , \lambda_n=0#, then the set is independent. If there is another solution, then the set is dependent.

Thinning
Each set #\vec{u}_1,\ldots,\vec{u}_m# in a vector space #V# that does not solely consist of zero vectors, can be thinned to an independent set with the same span #U=\linspan{\vec{u}_1,\ldots,\vec{u}_m }#:

If #\vec{u}_1,\ldots \vec{u}_m# is an independent set, then we are ready.
If not, then one of the vectors is dependent on the others. Remove this vector, so we are left with #m-1# vectors that still span #U#, and go back to the previous step.

In this way we find an independent set spanning #U# after at most #m# removals.

The set found that spans #U# will later turn out to be minimal, in the sense that no smaller number of spanning vectors for #U# can be found.

Let #n# be a natural number. Prove that the sequence
\[
\begin{array}{rcl}
\vec{e}_1 & =&\rv{1,0,0,\ldots ,0},\\
\vec{e}_2 & =&\rv{0,1,0,\ldots ,0},\\
& \vdots& \\
\vec{e}_n & =&\rv{0,0,0,\ldots ,1},
\end{array}
\]
of vectors in #\mathbb{R}^n# is independent.

Consider the equation
\[
\lambda_1 \cdot\vec{e}_1 + \cdots + \lambda_n\cdot \vec{e}_n =\rv{0,\ldots ,0}
\] with unknowns #\lambda_1,\ldots, \lambda_n#. After writing out the sum in coordinates, it comes down to #\rv{\lambda_1 ,\ldots , \lambda_n }=\rv{0,\ldots ,0}#. This system has only one solution: #\lambda_1 =\cdots =\lambda_n=0#. According to the Dependence criterion, this proves that the set of vectors #\vec{e}_1 ,\vec{e}_2, \ldots,\vec{e}_n# is independent.

New example