Linear independence

Let \(v_1, \dots, v_m \in V\) be \(m\) vectors in some vector space. Then we have

\[ 0 \cdot v_1 + \dots + 0 \cdot v_m = 0 \cdot (v_1 + \dots + v_m) = 0. \]

(3.48)

This follows from the distributive law and the scalar multiplication of any vector with 0, cf. 4. and 8. in Definition 3.10. So, there is always a “trivial” way to obtain the zero vector from \(v_1, \dots, v_m\). We can ask if there are other ways of achieving the zero vector.

Definition 3.49 (Related exercises: Exercise 3.22, Exercise 3.7, Exercise 4.6, Exercise 3.24, Exercise 3.21, Exercise 3.18, Exercise 2.9, Exercise 3.8)

We say \(v_1, \dots, v_m\) are linearly dependent if there is a non-zero linear combination of these that gives the zero vector. I.e., if there are \(a_1, \dots, a_m \in {\bf R}\) of which at least one is non-zero, such that

\[ a_1 v_1 + \dots + a_m v_m = 0. \]

(3.50)

If this is not the case, then we say the vectors are linearly independent.

Thus, they are linearly independent if the zero linear combination in Equation (3.48) is the only way to obtain the zero vector as a linear combination of \(v_1, \dots, v_m\).

Example 3.51

The vectors \(e_1 = (1, 0, 0)\), \(e_2 = (0,1,0)\) and \(e_3=(0,0,1) \in {\bf R}^3\) are linearly independent. To see this, suppose some linear combination equals the zero vector: if

\[ a_1 e_1 + a_2 e_2 + a_3 e_3 = (0,0,0) \]

then we compute the left hand side as

\[ (a_1, 0,0 ) + (0, a_2, 0) + (0,0,a_3) = (a_1, a_2, a_3), \]

so the above equation forces \(a_1 = a_2 = a_3 = 0\). This shows that the vectors are linearly independent.

More generally, the same argument shows that

\[ e_1 = (1, 0, \dots, 0), e_2 = (0, 1, 0, \dots 0), \dots, e_n = (0, \dots, 0, 1) \in {\bf R}^n \]

are linearly independent.

Example 3.52

We revisit the vectors \(v_1 := e_1 = (1, 0, 0)\), \(v_2 = (0, 1, 1)\) and \(v_3 = (2, 1, 1) \in {\bf R}^3\) of Example 3.45. These vectors are not linearly independent. Indeed, we observe that \(v_3 = 2 v_1 + v_2\), so that

\[ 2 v_1 + v_2 - v_3 = 0. \]

Example 3.53

The polynomials \(1 + x\), \(3x+x^2\), \(2+x-x^2\) are linearly independent vectors in \({\bf R}[x]^{\le 2}\). To see this, suppose that a linear combination of them equals the zero vector (i.e., the constant polynomial 0):

\[ \begin{align*} 0 & = a_1 (1+x) + a_2 (3x+x^2) + a_3 (2+x-x^2) \\ & = a_1 + 2 a_3 + (a_1 + 3a_2 + a_3) x + (a_2 - a_3) x^2. \end{align*} \]

Since this must hold for all \(x \in {\bf R}\), this forces the following homogeneous linear system:

\[ \begin{align*} 0 & = a_1 + 2 a_3 \\ 0 & = a_1 + 3a_2 + a_3 \\ 0 & = a_2 - a_3. \end{align*} \]

Solving this system (do it ) one sees that this only has the trivial solution \(a_1 = a_2 = a_3 = 0\). Thus, the polynomials are linearly independent.

The following statement says in some sense that a family of vectors is linearly independent if there is no redundancy among them.

Lemma 3.54 (Related exercises: Exercise 3.27)

Let \(v_1, \dots, v_m \in V\) be some vectors. They are linearly dependent exactly if (at least) one of these vectors can be expressed as a linear combination of the others, i.e., some

\[ v_i = a_1 v_1 + \dots + a_{i-1} v_{i-1} + a_{i+1} v_{i+1} + \dots + a_m v_m \]

(3.55)

for an appropriate \(i\) and appropriate coefficients \(a_1\) etc.

Proof. If holds, then

\[ a_1 v_1 + \dots + a_{i-1} v_{i-1} + (-1) v_i + a_{i+1} v_{i+1} + \dots + a_m v_m =0, \]

so they are linearly dependent.

Conversely, if holds, then pick some \(i\) such that \(a_i \ne 0\) (by assumption this is possible). Then one can subtract \(a_i v_i\) and divide by \(- a_i\) (which is nonzero, crucially!), giving

\[ v_i = \frac{-a_1}{a_i} v_1 + \dots + \frac{-a_{i-1}}{a_i} v_{i-1} + \frac{-a_{i+1}}{a_i} v_{i+1} + \dots + \frac{-a_m}{a_i} v_m. \]

This is an equation of the form . ◻

The following method decides whether a given set of vectors is linearly independent in \({\bf R}^n\). A proof is conveniently done using later results, such as Lemma 4.77.

Method 3.56 (Related exercises: Exercise 3.7, Exercise 4.15, Exercise 3.25, Exercise 3.27, Exercise 3.6, Exercise 3.23)

Let \(v_1, \dots, v_m \in {\bf R}^n\) be some vectors. Form the matrix

\[ A = \left ( \begin{array}{c} v_1 \\ v_2 \\ \vdots \\ v_m \end{array} \right ) \]

(i.e., each the \(i\)-th row of \(A\) is precisely the vector \(v_i\), so that \(A = (v_{ij})\) if \(v_i = (v_{i1}, \dots, v_{in})\).) Bring this matrix into row-echelon form using Gaussian elimination (Method 2.29). Call this resulting matrix \(B\). If \(B\) contains \(m\) leading ones, then \(v_1, \dots, v_m\) are linearly independent. Otherwise, they are linearly dependent.

Corollary 3.57

More than \(n\) vectors can never be linearly independent in \({\bf R}^n\) (i.e., for \(m > n\), any vectors \(v_1, \dots, v_m\) will be linearly dependent, since the matrix \(B\) can contain at most \(n\) leading ones, being in reduced row-echelon form).

Remark 3.58

This method is very similar to Method 3.46, except that there we asked \(B\) to contain \(n\) leading ones: this guarantees that \(v_1, \dots, v_m\) span \({\bf R}^n\). Having as many leading ones as there are vectors, i.e., \(m\) leading ones, instead guarantees that the vectors are linearly independent.

Example 3.59

We revisit the vectors \(v_1 := e_1 = (1, 0, 0)\), \(v_2 = (0, 1, 1)\) and \(v_3 = (2, 1, 1) \in {\bf R}^3\) of Example 3.59. The matrix having these vectors as rows is

\[ \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 1 \end{array} \right ) . \]

We bring it into reduced row echelon form like so:

\[ \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 1 \end{array} \right ) \leadsto \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array} \right ) \leadsto \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{array} \right ). \]

This reduced row-echelon matrix has only 2 leading ones, so the vectors are not linearly independent, i.e., they are linearly dependent.

The importance of linearly independent vectors comes from the following result:

Proposition 3.60

Let \(v_1, \dots, v_m\) be linearly independent vectors in a vector space \(V\). If some vector \(v\) can be expressed as an (ostensibly different) linear combination of those, these presentations must be the same. I.e., if

\[ \begin{align*} v & = a_1 v_1 + \dots + a_m v_m \text{ and }\\ v & = b_1 v_1 + \dots + b_m v_m \end{align*} \]

for appropriate real numbers \(a_1, \dots, a_m, b_1, \dots, b_m\), then necessarily we have

\[ a_1 = b_1, a_2 = b_2, \dots, a_m = b_m. \]

Proof. Subtracting these two equations from one another (and using the commutativity of addition, and the law of distributivity, cf. Definition 3.10), we obtain

\[ \begin{align*} 0 & = v - v \\ & = (a_1 - b_1) v_1 + \dots + (a_m - b_m) v_m. \end{align*} \]

Since the vectors are linearly independent, this implies \(a_1 - b_1 = 0\) etc., so that \(a_1 = b_1\) etc. ◻