Linear independence

In the theory of vector spaces, a set of vectors is said to be linearly dependent if at least one of the vectors in the set can be defined as a linear combination of the others; if no vector in the set can be written in this way, then the vectors are said to be linearly independent. These concepts are central to the definition of dimension.[1]

Linearly independent vectors in
Linearly dependent vectors in a plane in

A vector space can be of finite-dimension or infinite-dimension depending on the number of linearly independent basis vectors. The definition of linear dependence and the ability to determine whether a subset of vectors in a vector space is linearly dependent are central to determining a basis for a vector space.

DefinitionEdit

A sequence of vectors   from a vector space V is said to be linearly dependent, if there exist scalars   not all zero, such that

 

where   denotes the zero vector.

Notice that if not all of the scalars are zero, then at least one is non-zero, say  , in which case this equation can be written in the form

 

Thus,   is shown to be a linear combination of the remaining vectors.

A sequence of vectors   is said to be linearly independent if the equation

 

can only be satisfied by   for   This implies that no vector in the sequence can be represented as a linear combination of the remaining vectors in the sequence. In other words, a sequence of vectors is linearly independent if the only representation of   as a linear combination of its vectors is the trivial representation in which all the scalars   are zero.[2] Even more concisely, a sequence of vectors is linearly independent if and only if   can be represented as a linear combination of its vectors in a unique way.

The alternative definition, that a sequence of vectors is linearly dependent if and only if some vector in that sequence can be written as a linear combination of the other vectors, is only useful when the sequence contains two or more vectors. When the sequence contains no vectors or only one vector, the original definition is used.

Infinite dimensionsEdit

In order to allow the number of linearly independent vectors in a vector space to be countably infinite, it is useful to define linear dependence as follows. More generally, let V be a vector space over a field K, and let {vi | iI} be a family of elements of V indexed by the set I. The family is linearly dependent over K if there exists a non-empty finite subset JI and a family {aj | jJ} of elements of K, all non-zero, such that

 

A set X of elements of V is linearly independent if the corresponding family {x}xX is linearly independent. Equivalently, a family is dependent if a member is in the closure of the linear span of the rest of the family, i.e., a member is a linear combination of the rest of the family. The trivial case of the empty family must be regarded as linearly independent for theorems to apply.

A set of vectors which is linearly independent and spans some vector space, forms a basis for that vector space. For example, the vector space of all polynomials in x over the reals has the (infinite) subset {1, x, x2, ...} as a basis.

Geometric meaningEdit

A geographic example may help to clarify the concept of linear independence. A person describing the location of a certain place might say, "It is 3 miles north and 4 miles east of here." This is sufficient information to describe the location, because the geographic coordinate system may be considered as a 2-dimensional vector space (ignoring altitude and the curvature of the Earth's surface). The person might add, "The place is 5 miles northeast of here." Although this last statement is true, it is not necessary.

In this example the "3 miles north" vector and the "4 miles east" vector are linearly independent. That is to say, the north vector cannot be described in terms of the east vector, and vice versa. The third "5 miles northeast" vector is a linear combination of the other two vectors, and it makes the set of vectors linearly dependent, that is, one of the three vectors is unnecessary.

Also note that if altitude is not ignored, it becomes necessary to add a third vector to the linearly independent set. In general, n linearly independent vectors are required to describe all locations in n-dimensional space.

Evaluating linear independenceEdit

The zero vectorEdit

If one or more vectors from a given sequence of vectors   is the zero vector   then the vector   are necessarily linearly dependent (and consequently, they are not linearly independent). To see why, suppose that   is an index (i.e. an element of  ) such that   Then let   (alternatively, letting   be equal any other non-zero scalar will also work) and then let all other scalars be   (explicitly, this means that for any index   other than   (i.e. for  ), let   so that consequently  ). Simplifying   gives:

 

Because not all scalars are zero (in particular,  ), this proves that the vectors   are linearly dependent.

As a consequence, the zero vector can not possibly belong to any collection of vectors that is linearly independent.

Now consider the special case where the sequence of   has length   (i.e. the case where  ). A collection of vectors that consists of exactly one vector is linearly dependent if and only if that vector is zero. Explicitly, if   is any vector then the sequence   (which is a sequence of length  ) is linearly dependent if and only if  ; alternatively, the collection   is linearly independent if and only if  

Linear dependence/independence of two vectorsEdit

This example considers the special case where there are exactly two vector   and   from some real or complex vector space. The vectors   and   are linearly dependent if and only if at least one of the following is true:

  1.   is a scalar multiple of   (explicitly, this means that there exists a scalar   such that  ) or
  2.   is a scalar multiple of   (explicitly, this means that there exists a scalar   such that  ).

If   then by setting   we have   (this equality holds no matter what the value of   is), which shows that (1) is true in this particular case. Similarly, if   then (2) is true because   If   (for instance, if they are both equal to the zero vector  ) then both (1) and (2) are true (by using   for both).

If   then   is only possible if   and  ; in this case, it is possible to multiply both sides by   to conclude   This shows that if   and   then (1) is true if and only if (2) is true; that is, in this particular case either both (1) and (2) are true (and the vectors are linearly dependent) or else both (1) and (2) are false (and the vectors are linearly independent). If   but instead   then at least one of   and   must be zero. Moreover, if exactly one of   and   is   (while the other is non-zero) then exactly one of (1) and (2) is true (with the other being false).

The vectors   and   are linearly independent if and only if   is not a scalar multiple of   and   is not a scalar multiple of  .

Vectors in R2Edit

Three vectors: Consider the set of vectors     and   then the condition for linear dependence seeks a set of non-zero scalars, such that

 

or

 

Row reduce this matrix equation by subtracting the first row from the second to obtain,

 

Continue the row reduction by (i) dividing the second row by 5, and then (ii) multiplying by 3 and adding to the first row, that is

 

Rearrange this equation allows us to obtain

 

which shows that non-zero ai exist such that   can be defined in terms of   and   Thus, the three vectors are linearly dependent.

Two vectors: Now consider the linear dependence of the two vectors   and   and check,

 

or

 

The same row reduction presented above yields,

 

This shows that   which means that the vectors v1 = (1, 1) and v2 = (−3, 2) are linearly independent.

Vectors in R4Edit

In order to determine if the three vectors in  

 

are linearly dependent, form the matrix equation,

 

Row reduce this equation to obtain,

 

Rearrange to solve for v3 and obtain,

 

This equation is easily solved to define non-zero ai,

 

where   can be chosen arbitrarily. Thus, the vectors   and   are linearly dependent.

Alternative method using determinantsEdit

An alternative method relies on the fact that   vectors in   are linearly independent if and only if the determinant of the matrix formed by taking the vectors as its columns is non-zero.

In this case, the matrix formed by the vectors is

 

We may write a linear combination of the columns as

 

We are interested in whether AΛ = 0 for some nonzero vector Λ. This depends on the determinant of  , which is

 

Since the determinant is non-zero, the vectors   and   are linearly independent.

Otherwise, suppose we have   vectors of   coordinates, with   Then A is an n×m matrix and Λ is a column vector with   entries, and we are again interested in AΛ = 0. As we saw previously, this is equivalent to a list of   equations. Consider the first   rows of  , the first   equations; any solution of the full list of equations must also be true of the reduced list. In fact, if i1,...,im is any list of   rows, then the equation must be true for those rows.

 

Furthermore, the reverse is true. That is, we can test whether the   vectors are linearly dependent by testing whether

 

for all possible lists of   rows. (In case  , this requires only one determinant, as above. If  , then it is a theorem that the vectors must be linearly dependent.) This fact is valuable for theory; in practical calculations more efficient methods are available.

More vectors than dimensionsEdit

If there are more vectors than dimensions, the vectors are linearly dependent. This is illustrated in the example above of three vectors in  

Natural basis vectorsEdit

Let   and consider the following elements in  , known as the natural basis vectors:

 

Then   are linearly independent.

Proof

Suppose that   are real numbers such that

 

Since

 

then   for all  

Linear independence of basis functionsEdit

Let   be the vector space of all differentiable functions of a real variable  . Then the functions   and   in   are linearly independent.

ProofEdit

Suppose   and   are two real numbers such that

 

Take the first derivative of the above equation such that

 

for all values of   We need to show that   and   In order to do this, we subtract the first equation from the second, giving  . Since   is not zero for some  ,   It follows that   too. Therefore, according to the definition of linear independence,   and   are linearly independent.

Space of linear dependenciesEdit

A linear dependency or linear relation among vectors v1, ..., vn is a tuple (a1, ..., an) with n scalar components such that

 

If such a linear dependence exists with at least a nonzero component, then the n vectors are linearly dependent. Linear dependencies among v1, ..., vn form a vector space.

If the vectors are expressed by their coordinates, then the linear dependencies are the solutions of a homogeneous system of linear equations, with the coordinates of the vectors as coefficients. A basis of the vector space of linear dependencies can therefore be computed by Gaussian elimination.

Affine independenceEdit

A set of vectors is said to be affinely dependent if at least one of the vectors in the set can be defined as an affine combination of the others. Otherwise, the set is called affinely independent. Any affine combination is a linear combination; therefore every affinely dependent set is linearly dependent. Conversely, every linearly independent set is affinely independent.

Consider a set of   vectors   of size   each, and consider the set of   augmented vectors   of size   each. The original vectors are affinely independent if and only if the augmented vectors are linearly independent.[3]:256

See also: affine space.

See alsoEdit

  • Matroid – Abstract structure that models and generalizes linear independency

ReferencesEdit

  1. ^ G. E. Shilov, Linear Algebra (Trans. R. A. Silverman), Dover Publications, New York, 1977.
  2. ^ Friedberg, Insel, Spence, Stephen, Arnold, Lawrence (2003). Linear Algebra. Pearson, 4th Edition. pp. 48–49. ISBN 0130084514.CS1 maint: multiple names: authors list (link)
  3. ^ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

External linksEdit