Linear Algebra - Week 2

Dive into the fundamentals of linear algebra for machine learning and data science. This week you’ll learn to solve equations using the elimination and substitution methods.

import numpy as np

Solving a system of equations

We can solve this system by elimination or substitution.

$\{\begin{array}{l}5a+b=17\\ 4a-3b=6\end{array}$

Elimination method

1. $\{\begin{array}{l}a+0.2b=3.4\\ a-0.75b=1.5\end{array}$

2. $\{\begin{array}{l}a+0.2b=3.4\\ a-0.75b=1.5\end{array}$

Eliminate $a$

3. $\{\begin{array}{l}a+0.2b=3.4\\ 0-0.95b=-1.9\end{array}$

4. $\{\begin{array}{l}a+0.2b=3.4\\ b=2.\end{array}$

5. $\{\begin{array}{l}a=3.\\ b=2.\end{array}$

Substitution method

1. $\{\begin{array}{l}a+0.2b=3.4\\ a-0.75b=1.5\end{array}$

2. $\{\begin{array}{l}a=3.4-0.2b\\ a=1.5+0.75b\end{array}$

Substitute $a$

3. $\{\begin{array}{l}a=3.4-0.2b\\ 3.4-0.2b-1.5-0.75b=0\end{array}$

4. $\{\begin{array}{l}a=3.4-0.2b\\ 1.9-0.95b=0\end{array}$

5. $\{\begin{array}{l}a=3.4-0.2b\\ b=2.\end{array}$

6. $\{\begin{array}{l}a=3.\\ b=2.\end{array}$

Let’s check the solution.

a = 3.0
b = 2.0

assert 5.0 * a + b == 17.0
assert 4.0 * a - 3.0 * b == 6.0
assert np.allclose(
    np.linalg.solve(np.array([[5.0, 1.0], [4.0, -3.0]]), np.array([17.0, 6.0])),
    np.array([a, b]),
)

Let’s build an elimination algorithm using this system as an example.

$\{\begin{array}{l}a+b+2c=12\\ 3a-3b-c=2\\ 2a-b+6c=24\end{array}$

a = np.array([[1, 1, 2], [3, -3, -1], [2, -1, 6]], dtype="float32")
b = np.array([12, 2, 24], dtype="float32")


def solve_by_elimination(a: np.array, b: np.array) -> np.array:
    c = np.hstack((a, b.reshape(-1, 1)))
    for i in range(c.shape[0] - 1):
        # normalize row i
        c[i:, :] /= c[i:, i].reshape(-1, 1)
        # remove row i from row i+1, i+2, etc...
        c = np.vstack((c[: i + 1, :], c[i + 1 :,] - c[i, :]))
    for i in range(c.shape[0] - 1, -1, -1):
        # bring solved (if any) to RHS
        c[i, -1] -= np.sum(c[i, (i + 1) : -1])
        c[i, (i + 1) : -1] = 0
        # divide whole row by coefficient of variable
        c[i, :] /= c[i, i]
        # replace solution across the system
        c[:i, i] *= c[i, -1]
    return c[:, -1]


solve_by_elimination(a, b)

array([3.757576 , 2.0606058, 3.0909092], dtype=float32)

Let’s check the solution.

assert np.allclose(solve_by_elimination(a, b), np.linalg.solve(a, b))

Let’s try it with another one.

a = np.array(
    [[2, -1, 1, 1], [1, 2, -1, -1], [-1, 2, 2, 2], [1, -1, 2, 1]], dtype="float32"
)
b = np.array([6, 3, 14, 8], dtype="float32")
assert np.allclose(solve_by_elimination(a, b), np.linalg.solve(a, b))