# Math for ML – Linear dependence & Linear Equation

M

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.

1. No solution
2. Exactly 1 solution
3. 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$$

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$$

Check that the solution is correct:

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

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

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:

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]