A.I, Data and Software Engineering

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.

math for machine learning

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

Linear dependence and number of solution

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]

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

Add comment

A.I, Data and Software Engineering

PetaMinds focuses on developing the coolest topics in data science, A.I, and programming, and make them so digestible for everyone to learn and create amazing applications in a short time.

Pin It on Pinterest

Newsletters

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Petaminds will use the information you provide on this form to be in touch with you and to provide updates.