1.6 Linear Independence and Dependence of vectors,Linear combination

Occasionally we have a set of vectors and we need to determine whether the vectors are linearly independent of each other. This may be necessary to determine if the vectors form a basis, or to determine how many independent equations there are.In order to define linear dependence and independence let farther clarify what is a linear combination.

Linear Combination

Consider a vector space $\mathbb{V}$ and a finite number of vectors $x_1,x_2,\ldots,x_k \in \mathbb{V}$. Then every $v \in \mathbb{V}$ of the form.

$ v=\lambda_1x_1+\cdots+\lambda_kx_k= \sum_{i=1}^{k} \lambda_ix_i \in \mathbb{V}$

with $\lambda_1,\ldots,\lambda_k \in \mathbb{R}$ is a linear combination of vectors $x_1,\ldots,x_k$.

For example, if $V=\{[1,2],[2,1]\}$, then $2x_1−x_2=2([1,2])−[2,1]=[0,3]$

is linear combination of the vectors in $V$.

Linear Independence

Let us consider a vector space $\mathbb{V}$ with $k \in \mathbb{N}$ and $x_1,\ldots,x_k \in \mathbb{V}$. If there is a non trivial linear combination such that $0=\sum_{i=1}^{k} \lambda_ix_i$ with at least one $\lambda_i \ne 0$, the vectors $x_1, \ldots,x_k$ are linearly dependent.

If only the trivial solution exist, i.e; $\lambda_1=\ldots=\lambda_k=0$, the vectors $x_1,\ldots,x_k$ are linearly independent.

A set V of k-dimensional vectors is linearly independent if the only linear combination of vectors in V that equals 0 is the trivial linear combination.

The set of vectors
V={[1,0],[0,1]}

is linearly independent. Let prove this claim. We need to find constants $\lambda_1$ and $\lambda_1$ satisfying

$\lambda_1([1,0])+\lambda_2([0,1])=[0,0]$

solving this system of equations gives that $[\lambda_1,\lambda_2]=[0,0] \implies \lambda_1=\lambda_2=0$, in turn this implies that the set of vectors is linearly independent.

Linear independence is one of the most important concepts in linear algebra. Intuitively, a set of linearly independent vectors consists of vectors that have no redundancy, i.e., if we remove any of those vectors from the set, we will lose something.

A set V of k-dimensional vectors is linearly dependent if there is a nontrivial linear combination of the vectors in V that adds up to 0

The set of vectors
V={[1,2],[2,4]}

is linearly dependent set of vectors. Let see how.
$\lambda_1([1,2])+\lambda_2([2,4])=[0,0]$

There is a nontrivial linear combination with $\lambda_1=2$ and $\lambda_2=-1$ that yields 0. This implies that they are linearly dependent set of vectors. It's easy in this case to spot linear dependence by first glance, as the second vector is 2 times the first vector, which indicates linear dependence.

The following properties are useful to find out whether vectors are linearly independent

• k vectors are either linearly dependent or linearly independent.There is no third option.
• if at least one of the vectors $x_1,\ldots,x_k$ is 0 then they are linearly dependent.The same holds if two vectors are identical.
• The vectors $\{x_1,\ldots,x_k:x_i \ne 0,i=1,\ldots,k\}, k \ge 2$ are linearly dependent if and only if(at least) one of them is a linear combination of others.In particular, if one vector is a multiple of another vector i.e, $x_i=\lambda x_j, \lambda \in \mathbb{R}$ then the set $\{x_1,\ldots,x_k:x_i \ne0,i=1,\ldots,k\}$ is  linearly dependent.

A practical way of checking whether vectors $x_1,\ldots,x_k \in V$ are linearly independent is to use Gaussian elimination: Write all vectors as columns of a matrix A and perform Gaussian elimination until the matrix  is in row echelon form.

-The pivot columns indicate the vectors, which are linearly independent of the vectors on the left.  

     Note   that there is an ordering of vectors when the matrix is built.

- The non-pivot columns can be expressed as linear combinations of the pivot columns on their left. For instance, the row-echelon form

tells us that  the first and third columns are pivot columns. The second column is a non-pivot column because it is three times the first column.All column vectors are linearly independent if and only if all columns are pivot columns. If there is at least one non-pivot column, the columns (and, therefore, the corresponding vectors) are linearly dependent.

Eg: Lets consider three vectors $x_1=[2,-1,3] x_2=[1,1,-2] x_3=[3,-3,8]$
Use sympy Matrix to store these vectors as columns of the matrix and find row reduced echelon form.

import sympy as sp

import numpy as np

row1=[2,1,3]

row2=[-1,1,-3]

row3=[3,-2,8]

M = sp.Matrix((row1,row2,row3))

display(M)

print("Row reduced echelon form")

display(M.rref())

o/p

Row reduced echelon form

(Matrix([
 [1, 0,  2],
 [0, 1, -1],
 [0, 0,  0]]),
 (0, 1))

The pivot column represent linearly independent vectors.The output clearly shows that the first two vectors are linearly independent and the third vector is a linear combination of first two( 2x1-x2).

consider a set of linearly independent vectors $b_1,b_2,b_3,b_4 \in \mathbb{R}^n$ and

$x_1=b_1 - 2b_2 + b_3 - b_4$

$x_2=-4b_1 -2b_2 \quad +4b_4$

$x_3=2b_1+ 3b_2+ -b_3 -3b_4$

$x_4=17b_1 -10b_2+11b_3+b_4$

To check whether the vectors $x_1,x_2,x_3$ and $x_4$ are linearly independent, we can form a matrix with coefficients of each vector $b_1\ldots b_4$ as column vectors and check whether they are linearly independent.

The following program will illustrate this

import sympy as sp

import numpy as np

row1=[1,-4,2,17]

row2=[-2,-2,3,-10]

row3=[1,0,-1,11]

row4=[-1,4,-3,1]

M = sp.Matrix((row1,row2,row3,row4))

print("Coefficient Matrix")

display(M)

print("Reduced Echelon Form")

display(M.rref())

O/p

Coefficient Matrix

$\displaystyle \left[\begin{matrix}1 & -4 & 2 & 17\\-2 & -2 & 3 & -10\\1 & 0 & -1 & 11\\-1 & 4 & -3 & 1\end{matrix}\right]$

Reduced Echelon Form

(Matrix([
 [1, 0, 0,  -7],
 [0, 1, 0, -15],
 [0, 0, 1, -18],
 [0, 0, 0,   0]]),
 (0, 1, 2))

It is noted that the last column is not a pivot column and $x_4=-7x_1-15x_2-18x_3$. Therefore $x_1,\ldots,x_4$ are linearly dependent as $x_4$ can be expressed as a linear combination of $x_1,\ldots,x_3$.

Example : (University question)

Are the following vectors linearly independent

$x_1=\begin{bmatrix}
2\\
-1\\
3
\end{bmatrix}$ $x_2=\begin{bmatrix}
1\\
1\\
-2
\end{bmatrix}$ $ x_3=\begin{bmatrix}
3\\
-3\\
8
\end{bmatrix}$

create a matrix with columns as $x_1,x_2$ and $x_3$. Then we can use Gauss Jordan elimination to find pivot columns

$\begin{bmatrix}
2 & 1 & 3\\
-1 &1 & -3\\
3 & -2 & 8
\end{bmatrix}$

$R_1=R_1+R_2$

$\begin{bmatrix}
1 & 2 & 0\\
-1 &1 & -3\\
3 & -2 & 8
\end{bmatrix}$

$R_2=R_2+R_1, R_3=R_3-3R_1$

$\begin{bmatrix}
1 & 2 & 0\\
0 &3 & -3\\
0 & -8 & 8
\end{bmatrix}$

$R_2=R_2/3, R_3=R_3/-8$

$\begin{bmatrix}
1 & 2 & 0\\
0 &1 & -1\\
0 &1 & -1
\end{bmatrix}$

$R_3=R_3-R_2, R_1=R_1-2R_2$

$\begin{bmatrix}
1 & 0 & 2\\
0 &1 & -1\\
0 &0 & 0
\end{bmatrix}$

This how that the first two columns are pivot columns and the third column is not

So the vectors $x_1$ and $x_2$ are linearly independent .How ever the third vector $x_3$ is $2x_1-x_2$, which you can verify.

Example University Question

Check whether the polynomials $x(t) = 1 + t + 𝑡^2$; $y(t) = -2 + 3t - 7𝑡^2$; $z(t) = 4 + 8t$ over $R$ are linearly independent or not.

The coefficient matrix is

$\begin{bmatrix}
1 & 1 & 1\\
-2 &3 & -7\\
4 &8 & 0
\end{bmatrix}$

$R_3=R_2*2+R_3$

$\begin{bmatrix}
1 & 1 & 1\\
-2 &3 & -7\\
0 &14 & -14
\end{bmatrix}$

$R_3=R_3/14$

$\begin{bmatrix}
1 & 1 & 1\\
-2 &3 & -7\\
0 &1 & -1
\end{bmatrix}$

$R_2=R_1*2+R_2$

$\begin{bmatrix}
1 & 1 & 1\\
0  &5  & -5\\
0 &1 & -1
\end{bmatrix}$

$R_2=R_2/5$

$\begin{bmatrix}
1 & 1 & 1\\
0  &1  & -1\\
0 &1 & -1
\end{bmatrix}$

$R_3=R_3-R_2$

$\begin{bmatrix}
1 & 1 & 1\\
0  &1  & -1\\
0 &0 &0
\end{bmatrix}$

The last column is a non pivot column which indicates that they are linearly dependent.

Example: ( University question)

Are the following set of vectors linearly independent

$X_1=\begin{bmatrix}
1 \\
2\\
-3
\end{bmatrix} X_2=\begin{bmatrix}
2 \\
5\\
6
\end{bmatrix} X_3= \begin{bmatrix}
5 \\
7\\
9
\end{bmatrix}$

create a matrix with columns as $X_1,X_2$ and $X_3$. Then we can use Gauss Jordan elimination to find pivot columns

$\begin{bmatrix}
1 & 2& 5\\
2 &5 & 7\\
-3 & 6 & 9
\end{bmatrix}$

After row reductions we will end up with an identity matrix, which shows that the vectors are linearly independent.

$\begin{bmatrix}
1 & 0& 0\\
0 &1 & 0\\
0 & 0 & 1
\end{bmatrix}$

Note: All columns are pivot columns

Example:

Represent the vector 

$b=\begin{bmatrix}
2 \\
13\\
6
\end{bmatrix}$ as a linear combination of 

$v_1=\begin{bmatrix}
1 \\
5\\
-1
\end{bmatrix} v_2=\begin{bmatrix}
1 \\
2\\
1
\end{bmatrix} v_3=\begin{bmatrix}
1 \\
4\\
3
\end{bmatrix}$

Here We need to find numbers $x_1,x_2,x_3$ satisfying

$x_1v_1+x_2v_2+x_3v_3=b.$
This vector equation is equivalent to the following matrix equation.$[v_1v_2v_3]x=b$

$\begin{bmatrix}
1 & 1 & 1\\
5 &2 & 4\\
-1 &1 &3
\end{bmatrix}\begin{bmatrix}
x_1 \\
x_2\\
x_3
\end{bmatrix}=\begin{bmatrix}
2 \\
13\\
6
\end{bmatrix}$

Thus the problem is to find the solution of this matrix equation.Let us consider the augmented matrix for this system to apply Gauss-Jordan elimination.

The augmented matrix is

$\begin{bmatrix}
1 & 1 & 1 & | & 2\\
5 &2 & 4& | & 13 \\
-1 &1 &3& | & 6
\end{bmatrix}$

We apply elementary row operations and obtain a matrix in reduced row echelon form as follows.

Therefore the solution for the system is

$x_1=1,x_2=−2,$ and $x_3=3$ and we obtain the linear combination

$b=v_1−2v_2+3v_3$

Note:Any set of vectors which contains the zero vector is linearly dependent.

Let 0 be the zero vector, and $v_1,⋯,v_k$ are the other vectors in the set.

Then we have the non-trivial linear combination

$1⋅0+0.v_1+0.v_2+⋯+0.v_k=0$
This is a non-trivial linear combination because one of the coefficients is non-zero.

Thus by definition, the set  $\{0,v_1,\dots,v_k\}$ is linearly dependent.