Linear independence

For linear dependence of random variables, see Covariance.

Linearly independent vectors in $\mathbb {R} ^{3}$

Linearly dependent vectors in a plane in $\mathbb {R} ^{3}$.

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.

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.

Definition

The vectors in a subset $S=\{{\vec {v}}_{1},{\vec {v}}_{2},\dots ,{\vec {v}}_{k}\}$ of a vector space V are said to be linearly dependent, if there exist scalars $a_{1},a_{2},\dots ,a_{k}$ , not all zero, such that

$a_{1}{\vec {v}}_{1}+a_{2}{\vec {v}}_{2}+\cdots +a_{k}{\vec {v}}_{k}={\vec {0}},$

where ${\vec {0}}$ denotes the zero vector.

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

${\vec {v}}_{1}={\frac {-a_{2}}{a_{1}}}{\vec {v}}_{2}+\cdots +{\frac {-a_{k}}{a_{1}}}{\vec {v}}_{k}.$

Thus, ${\vec {v}}_{1}$ is shown to be a linear combination of the remaining vectors.

The vectors in a set $T=\{{\vec {v}}_{1},{\vec {v}}_{2},\dots ,{\vec {v}}_{n}\}$ are said to be linearly independent if the equation

$a_{1}{\vec {v}}_{1}+a_{2}{\vec {v}}_{2}+\cdots +a_{n}{\vec {v}}_{n}={\vec {0}},$

can only be satisfied by $a_{i}=0$ for $i=1,\dots ,n$. This implies that no vector in the set can be represented as a linear combination of the remaining vectors in the set. In other words, a set of vectors is linearly independent if the only representations of ${\vec {0}}$ as a linear combination of its vectors is the trivial representation in which all the scalars $a_{i}$ are zero.

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

Infinite dimensions

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 {v_i | i∈I} be a family of elements of V. The family is linearly dependent over K if there exists a family {a_j | j∈J} of elements of K, not all zero, such that

$\sum _{j\in J}a_{j}v_{j}=0$

where the index set J is a nonempty, finite subset of I.

A set X of elements of V is linearly independent if the corresponding family {x}_x∈X 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, x², ...} as a basis.

Geometric meaning

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 independence

Vectors in R²

Three vectors: Consider the set of vectors v₁ = (1, 1), v₂ = (−3, 2) and v₃ = (2, 4), then the condition for linear dependence seeks a set of non-zero scalars, such that

$a_{1}{\begin{Bmatrix}1\\1\end{Bmatrix}}+a_{2}{\begin{Bmatrix}-3\\2\end{Bmatrix}}+a_{3}{\begin{Bmatrix}2\\4\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}},$

or

${\begin{bmatrix}1&-3&2\\1&2&4\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\\a_{3}\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}}.$

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

${\begin{bmatrix}1&-3&2\\0&5&2\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\\a_{3}\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}}.$

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

${\begin{bmatrix}1&0&16/5\\0&1&2/5\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\\a_{3}\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}}.$

We can now rearrange this equation to obtain

${\begin{bmatrix}1&0\\0&1\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\end{Bmatrix}}={\begin{Bmatrix}a_{1}\\a_{2}\end{Bmatrix}}=-a_{3}{\begin{Bmatrix}16/5\\2/5\end{Bmatrix}}.$

which shows that non-zero a_i exist such that v₃ = (2, 4) can be defined in terms of v₁ = (1, 1), v₂ = (−3, 2). Thus, the three vectors are linearly dependent.

Two vectors: Now consider the linear dependence of the two vectors v₁ = (1, 1), v₂ = (−3, 2), and check,

$a_{1}{\begin{Bmatrix}1\\1\end{Bmatrix}}+a_{2}{\begin{Bmatrix}-3\\2\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}},$

or

${\begin{bmatrix}1&-3\\1&2\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}}.$

The same row reduction presented above yields,

${\begin{bmatrix}1&0\\0&1\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\end{Bmatrix}}={\begin{Bmatrix}0\\0\end{Bmatrix}}.$

This shows that a_i = 0, which means that the vectors v₁ = (1, 1) and v₂ = (−3, 2) are linearly independent.

Vectors in R⁴

In order to determine if the three vectors in R⁴,

$\mathbf {v} _{1}={\begin{Bmatrix}1\\4\\2\\-3\end{Bmatrix}},\mathbf {v} _{2}={\begin{Bmatrix}7\\10\\-4\\-1\end{Bmatrix}},\mathbf {v} _{3}={\begin{Bmatrix}-2\\1\\5\\-4\end{Bmatrix}}.$

are linearly dependent, form the matrix equation,

${\begin{bmatrix}1&7&-2\\4&10&1\\2&-4&5\\-3&-1&-4\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\\a_{3}\end{Bmatrix}}={\begin{Bmatrix}0\\0\\0\\0\end{Bmatrix}}.$

Row reduce this equation to obtain,

${\begin{bmatrix}1&7&-2\\0&-18&9\\0&0&0\\0&0&0\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\\a_{3}\end{Bmatrix}}={\begin{Bmatrix}0\\0\\0\\0\end{Bmatrix}}.$

Rearrange to solve for v₃ and obtain,

${\begin{bmatrix}1&7\\0&-18&\end{bmatrix}}{\begin{Bmatrix}a_{1}\\a_{2}\end{Bmatrix}}=-a_{3}{\begin{Bmatrix}-2\\9\end{Bmatrix}}.$

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

$a_{1}=-3a_{3}/2,a_{2}=a_{3}/2,$

where a₃ can be chosen arbitrarily. Thus, the vectors v₁, v₂ and v₃ are linearly dependent.

Alternative method using determinants

An alternative method relies on the fact that n vectors in $\mathbb {R} ^{n}$ 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

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

We may write a linear combination of the columns as

$A\Lambda ={\begin{bmatrix}1&-3\\1&2\end{bmatrix}}{\begin{bmatrix}\lambda _{1}\\\lambda _{2}\end{bmatrix}}.$

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

$\det A=1\cdot 2-1\cdot (-3)=5\neq 0.$

Since the determinant is non-zero, the vectors (1, 1) and (−3, 2) are linearly independent.

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

$A_{{\langle i_{1},\dots ,i_{m}}\rangle }\Lambda ={\mathbf {0} }.$

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

$\det A_{{\langle i_{1},\dots ,i_{m}}\rangle }=0$

for all possible lists of m rows. (In case m = n, this requires only one determinant, as above. If m > n, 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 dimensions

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

Natural basis vectors

Let V = Rⁿ and consider the following elements in V, known as the natural basis vectors:

${\begin{matrix}\mathbf {e} _{1}&=&(1,0,0,\ldots ,0)\\\mathbf {e} _{2}&=&(0,1,0,\ldots ,0)\\&\vdots \\\mathbf {e} _{n}&=&(0,0,0,\ldots ,1).\end{matrix}}$

Then e₁, e₂, ..., e_n are linearly independent.

Proof

Suppose that a₁, a₂, ..., a_n are elements of R such that

$a_{1}\mathbf {e} _{1}+a_{2}\mathbf {e} _{2}+\cdots +a_{n}\mathbf {e} _{n}=\mathbf {0} .$

Since

$a_{1}\mathbf {e} _{1}+a_{2}\mathbf {e} _{2}+\cdots +a_{n}\mathbf {e} _{n}=(a_{1},a_{2},\ldots ,a_{n}),$

then a_i = 0 for all i in {1, ..., n}.

Linear independence of basis functions

Let $V$ be the vector space of all differentiable functions of a real variable $t$. Then the functions $e^{t}$ and $e^{2t}$ in $V$ are linearly independent.

Proof

Suppose $a$ and $b$ are two real numbers such that

$ae^{t}+be^{2t}=0$

Take the first derivative of the above equation such that

$ae^{t}+2be^{2t}=0$

for all values of t. We need to show that $a=0$ and $b=0$. In order to do this, we subtract the first equation from the second, giving $be^{2t}=0$. Since $e^{2t}$ is strictly greater than zero (thus not equal to zero) for all t, $b=0$ for all t. It follows that $a=0$ too. Therefore, according to the definition of linear independence, $e^{t}$ and $e^{2t}$ are linearly independent.

Projective space of linear dependencies

A linear dependence among vectors v₁, ..., v_n is a tuple (a₁, ..., a_n) with n scalar components, not all zero, such that

$a_{1}\mathbf {v} _{1}+\cdots +a_{n}\mathbf {v} _{n}=\mathbf {0} .$

If such a linear dependence exists, then the n vectors are linearly dependent. It makes sense to identify two linear dependencies if one arises as a non-zero multiple of the other, because in this case the two describe the same linear relationship among the vectors. Under this identification, the set of all linear dependencies among v₁, ...., v_n is a projective space.

See also

• Gramian matrix
• Matroid
• Orthogonality
• Wronskian
• Multicollinearity

External links

• Hazewinkel, Michiel, ed. (2001) [1994], "Linear independence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• Linearly Dependent Functions at WolframMathWorld.
• Tutorial and interactive program on Linear Independence.
• Introduction to Linear Independence at KhanAcademy.