Linear Independence of Vectors and Its Importance

This tutorial in dedicated to the concept of linear independence of vectors and its associations with the solution of linear equation systems.

What is the concept of vectors’ linear independence, and why should I care about it? One simple example: Let’s say you want to find the answer to the $\mathbf{A} \mathbf{x}=\mathbf{b}$ . One may say we can simply find the answer by taking an inverse of $\mathbf{A}$ as $\mathbf{x}= \mathbf{A}^{-1}\mathbf{b}$ . NOT SO FAST! There is more in that? What if $\mathbf{A}$ does not have an inverse or is not square? You just let it go? I guess not.

That was just one example. In Machine Learning, it frequently happens that you want to explore the correlation between vectors to analyze them better. For example, you are dealing with a matrix which in essence, is formed by vectors. What would you know if you are not familiar with the concept of linear independence?

In this tutorial, you will learn the following:

The concept of linear independence/dependence!
Examples of the linear dependence of vectors
How to do it in Python using Numpy?
Matrix ranks
The solutions to a system of linear equations

Before You Move On

You may find the following resources helpful to better understand the concept of this article:

Python Tutorials – A FREE Video Course: You will become familiar with Python and its syntax.
Numpy – An Introduction to a Great Package for Linear Algebra: Numpy is one of the best scientific computing packages for Linear Algebra! You always need it for Machine Learning as you always need Linear Algebra for Machine Learning!
The Remarkable Importance of Linear Algebra in Machine Learning: This article talks about why you should care about Linear Algebra if you want to master Machine Learning.
Basic Linear Algebra Definitions that You Hear Every Day: Covers the primary and most frequently used Linear Algebra definitions in Machine Learning.

The Concept of Linear Independence

Assuming we have the set of $\{\mathbf{v}^{1},\mathbf{v}^{2},\hdots,\mathbf{v}^{p}\} \in \mathbb{R}^{q}$ which are $p$ column vectors of size $q$ . Then, we call this set linear independent, if no vector exists that we can represent it as the linear combination of any other two vectors. Although, perhaps it is easier to define linear dependent: A vector $\mathbf{v}^{i}$ is linear dependent if we can express it as the linear combination of another two vectors in the set, as below:

$\mathbf{v}^{i} = \sum_{j \neq i} \alpha_{j} \mathbf{v}^{j}$

In the above case, we say the set of $\{\mathbf{v}^{1},\mathbf{v}^{2},\hdots,\mathbf{v}^{p}\}$ vectors are linearly dependent!

Vector d is a linear combination of vectors a, b, and c. Actually, d = a + b + c.

Example

Consider the three vectors below:

$\mathbf{v}= \begin{bmatrix} 1\\ -1\\ 2 \end{bmatrix} , \mathbf{u}= \begin{bmatrix} 0\\ 3\\ 1 \end{bmatrix} , \mathbf{w}= \begin{bmatrix} 2\\ 1\\ 5 \end{bmatrix}$

The above set is linearly dependent. Why? It is simple. Because $\mathbf{w} = 2\mathbf{v} + \mathbf{u}$ . Let’s do the above with Python and Numpy:

# Import Numpy library
import numpy as np
# Define three column vectors
v = np.array([1, -1, 2]).reshape(-1,1)
u = np.array([0, 3, 1]).reshape(-1,1)
w = np.array([2, 1, 5]).reshape(-1,1)
# Check the linear dependency with writing the equality
print('Does the equality w = 2v+u holds? Answer:', np.all(w == 2*v+u))

Run the above code and see if Numpy confirms that or not!

The Relationship With Matrix Rank

I talked about the linear dependence of vectors so far. Assume we have the matrix $\mathbf{M} \in \mathbb{R}^{m \times n}$ . The matrix has m rows and n columns. Let’s focus on the columns. The n columns form n vectors. I denote the $j^{th}$ column with $\mathbf{M}_{:,j}$ . So we have the set of n vectors $\{\mathbf{M}_{:,1},\mathbf{M}_{:,2},\hdots,\mathbf{M}_{:,n}\}$ as columns. The size of the largest subset of $\{\mathbf{M}_{:,1},\mathbf{M}_{:,2},\hdots,\mathbf{M}_{:,n}\}$ that its vectors are linearly independent, is called the column rank of the matrix $\mathbf{M}$ . Considering the rows of $\mathbf{M}$ , the size of the largest subset of rows that form a linearly independent set is called the row rank of the matrix $\mathbf{M}$ .

We have the following properties for matrix ranks:

For $\mathbf{M} \in \mathbb{R}^{m \times n}$ , $rank(M) \leq min(m,n)$ . If $rank(M) = min(m,n)$ , the matrix $\mathbf{M}$ is full rank.
For $\mathbf{M} \in \mathbb{R}^{m \times n}$ , $\mathbf{N} \in \mathbb{R}^{n \times q}$ , and $\mathbf{H=MN} \in \mathbb{R}^{m \times q}$ , $rank(H) \leq min(rank(M),rank(N))$ .
For $\mathbf{M} \in \mathbb{R}^{m \times n}$ , $\mathbf{N} \in \mathbb{R}^{m \times n}$ , and $\mathbf{H= M + N} \in \mathbb{R}^{m \times n}$ , $rank(H) \leq rank(M) + rank(N)$ .

Check first and second property above with the following code:

# Import Numpy library
import numpy as np
from numpy.linalg import matrix_rank
# Define random 3x4 matrix using np.array
# Ref: https://docs.scipy.org/doc/numpy-1.15.1/reference/generated/numpy.random.randint.html
M = np.random.randint(10, size=(3, 4))
N = np.random.randint(10, size=(4, 3))
# np.all() test whether all array elements are True.
# More info: https://docs.scipy.org/doc/numpy/reference/generated/numpy.all.html
checkProperty = np.all(matrix_rank(M) <= min(M.shape[0],M.shape[1]))
if checkProperty: print('Property rank(M) <= min(M.shape[0],M.shape[1]) is confirmed!')
checkProperty = np.all(matrix_rank(np.matmul(M,N)) <= min(matrix_rank(M),matrix_rank(N)))
if checkProperty: print('Property rank(MN) <= min(rank(M),rank(N)) is confirmed!')

Practice: Modify the above code and check property (3).

Linear Equations

I talked about linear dependency and matrix ranks. After that, I would like to discuss their application in finding the solution of linear equations, which is of great importance. Consider the following equality which set a system of linear equations:

$\mathbf{A}^{m \times n}\mathbf{x}^{n \times 1}=\mathbf{b}^{m \times 1}$

Above, we see the matrix $\mathbf{A}$ is multiplied by the vector $\mathbf{x}$ and forms another vector $\mathbf{b}$ . The above equality creates a set of m-line linear equations. Let’s write line $j$ for example:

$\mathbf{A}_{j,1} \mathbf{x}_{1} + \mathbf{A}_{j,2} \mathbf{x}_{2} + \hdots + \mathbf{A}_{j,n} \mathbf{x}_{n} = \mathbf{b}_{j} , j \in \{1,2,\hdots,m\}$

So the question is how many solution exists for the system of equations $\mathbf{A} \mathbf{x}=\mathbf{b}$ . By solution I mean the possible values for the variables $\mathbf{x}=[x_1,x_2,\hdots,x_n]^T$ . The answer is one of the following:

There is NO solution.
The system has one unique solution.
We have infinite numbers of solutions.

As you observed, having more than one BUT less than infinity solutions is off the table!

Theorem: If $\mathbf{u}$ and $\mathbf{v}$ are two solutions of the $\mathbf{A} \mathbf{x}=\mathbf{b}$ equation, then the specific linear combination of them as below, is a solution as well:

$\mathbf{w} = \beta \mathbf{u} + (1-\beta) \mathbf{v}, \forall \beta \in \mathbb{R}$

PROOF: Look at the below equations to see how $\mathbf{w}$ is also a solution:

$\mathbf{A}\mathbf{w} = \mathbf{A}\{ \beta \mathbf{v} + (1-\beta)\mathbf{u}\}= \beta \mathbf{A}\mathbf{v} + \mathbf{A}\mathbf{u} - \beta \mathbf{A}\mathbf{u} = \beta\mathbf{b} + \mathbf{b} - \beta \mathbf{b} = b$

So the above proves shows that if we have more than one solution, then we can say we have infinite number of solutions!

The following two conditions determine the number of solutions if there is at least one solution! Try to prove them based on what you learned so far:

$\mathbf{A}^{m \times n}\mathbf{x}^{n \times 1}=\mathbf{b}^{m \times 1}$ has at least one solution if $m \leq n$ and Rank( $\mathbf{A}$ ) = m.
$\mathbf{A}^{m \times n}\mathbf{x}^{n \times 1}=\mathbf{b}^{m \times 1}$ has exactly one solution if $m = n$ and Rank( $\mathbf{A}$ ) = m.

Conclusion

In this tutorial, I discussed the concept of linear independence of the vectors and their associates with the system of linear equations. This concept is crucial, especially in Machine Learning and optimization theory, in which we are dealing with all sorts of mathematical proofs necessary to justify why a method should work! For the majority of what you may work in Machine Learning, you may not need to use what I talked about here directly. BUT, you need to know it if you would like to stand out! Do you see any ambiguous concept here? Anything missing or wrong? Feel free to ask as it will help me, yourself, and the others to learn better, and I can further improve this article.