Table of contents

Continue with math for machine learning, this article will give a quick note on definition of linear dependence and demonstration with python.

### Linear Dependence

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**.

** 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.$$ \vec v_1 = \{1, 2, 3\} \\ \vec v_2 = \{2, 3, 4\} \\ \vec v_3 = \{3, 5, 8\}$$

The above vectors are not linear independent as \(\vec { v_1} + \vec { v_2} – \vec {v_3} = \vec 0 \)

### System of linear equation

Linear dependence has a strong relation to solution of linear equations. Since it is all about systems of linear equations, let’s start again with the set of equations:

$$A_{1,1}x_1 + A_{1,2}x_2 + \cdots + A_{1,n}x_n = b_1 \\ A_{2,1}x_1 + A_{2,2}x_2 + \cdots + A_{2,n}x_n = b_2 \\ \cdots \\ A_{m,1}x_1 + A_{m,2}x_2 + \cdots + A_{m,n}x_n = b_n $$

We know `A`

and `b`

as constant terms and need to find `x`

.

#### Matrix equation

The system is equivalent to a matrix equation of the form

\(A \times x= b\)

Where `A`

is a `m x n`

matrix of coefficients, `x`

and `b`

is column vectors. The equation corresponds to:

$$A=

\begin{bmatrix}

a_{11} & a_{12} & \cdots & a_{1n} \\

a_{21} & a_{22} & \cdots & a_{2n} \\

\vdots & \vdots & \ddots & \vdots \\

a_{m1} & a_{m2} & \cdots & a_{mn}

\end{bmatrix},\quad

\mathbf{x}=

\begin{bmatrix}

x_1 \\

x_2 \\

\vdots \\

x_n

\end{bmatrix},\quad

\mathbf{b}=

\begin{bmatrix}

b_1 \\

b_2 \\

\vdots \\

b_m

\end{bmatrix}$$

#### Number of solutions

Three cases can represent the number of solutions of the system of equations Ax=b.

- No solution
- Exactly 1 solution
- An infinite number of solutions

It is because we are dealing with linear systems: 2 lines can’t cross more than once as illustrated below

### Solve systems of equations with `numpy`

.

To find x:

$$x = A^{-1} \times b$$

So the solution exists if A is invertible (\(A^{-1}\) exists). To solve the standard linear system, we can use `numpy.linalg.solve(A, b)`

.

**Example 1:** Solve the system of equations (no solution)

$$ -3x_0 – x_1 = 9 \\ -3x_0 -x_1 = 7$$

1 2 3 4 5 | a = np.array([[-3,-1], [-3, -1]]) b = np.array([9,7]) x = np.linalg.solve(a, b) print(x) #LinAlgError: Singular matrix |

**Example 2: ** Solve the system of equations (one solution)

$$3 x_0 + x_1 + x_2 = 9 \\ x_0 + 2 x_1 + 3x_2 = 8 \\ 2x_0 + 0.5 x_1 + 4x_2 = 7 $$

1 2 3 4 5 | a = np.array([[3,1,1], [1,2,3], [2, 0.5,4]]) b = np.array([9,8,7]) x = np.linalg.solve(a, b) print(x) #[2.08333333 2.33333333 0.41666667] |

Check that the solution is correct:

1 2 | np.allclose(np.dot(a, x), b) #True |

** Example 3: ** Solve the system of equations (infinite solutions)

$$ 3x_0 + x_1 = 9 \\ 6x_0 + 2 * x_1 = 18 $$

1 2 3 4 5 6 | import numpy as np a = np.array([[3,1], [6,2]]) b = np.array([9,18]) x = np.linalg.solve(a, b) print(x) #LinAlgError: Singular matrix |

This system has infinite solutions and matrix a is not invertible. Its rows are linear dependent.

### Check linear dependency

**Use Eigenvalue**: If one eigenvalue of the matrix is zero, its corresponding eigenvector is linearly dependent. The eigenvalues are not necessarily ordered. A method would be:

1 2 3 4 5 6 7 8 9 10 11 | matrix = np.array( [ [0, 1 ,0 ,0], [0, 0, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1] ]) w, v = np.linalg.eig(matrix.T) # The linearly dependent row vectors print matrix[w == 0,:] |

w: The eigenvalues, each repeated according to its multiplicity.

v: The normalized (unit “length”) eigenvectors, such that the column `v[:,i]`

is the eigenvector corresponding to the eigenvalue `w[i]`

### References:

[1] Marc P.D, A. Aldo, Cheng S.O, Math for machine learning, url: https://mml-book.github.io/book/mml-book.pdf

[2] Deep learning book series, url https://hadrienj.github.io/posts/Deep-Learning-Book-Series-2.4-Linear-Dependence-and-Span/

[3] Wikipedia, https://en.wikipedia.org/wiki/System_of_linear_equations