Solvability - Executable Engineering: Interactive Numerical Methods in Python

import numpy as np

try:
    import executable_engineering as exe
except ImportError:
    %pip install -q executable_engineering
    import executable_engineering as exe

Solvability of Linear Systems¶

Some systems of equations don’t have a solution, or they do but it’s not unique.

Illustrative example: You are organizing a fundraising event and need to buy chairs and tables.

Chairs cost $20 each
Tables cost $50 each
You have a budget of $700
You need exactly 20 pieces of furniture

How many chairs and tables should you buy?

A System with One Solution¶

Let $c$ and $t$ be the number of chairs and tables respectively.

(1) $20 c + 50 t = 700$ (Budget)
(2) $c+t = 20$ (Pieces)

Solve Graphically¶

Since these are linear equations, we can plot them as lines on a graph.

The point where the lines intersect satisfies both equations and is therefore a solution. Since lines only cross once, it is a unique solution.

A = [[20, 50], [1, 1]]
b = [700, 20]
fig = exe.visual_solve_2d(A, b)
fig.show()

Algebraic Solution (Elimination)¶

We can solve this algebraically by eliminating one variable.

Multiply the second equation (2) by 20:
(3) $20c+20t = 400$

Subtract (3) from (1):
$(20c + 50t) - (20c + 20t) = 700 - 400$
$30t = 300$
$t=10$

Substitute $t=10$ back into (2):
$c = 10$

Matrix Formulation¶

Writing this as a matrix equation ( $\mathbf{A} \mathbf{x} = \mathbf{b}$ ):

\begin{pmatrix} 20 & 50 \\ 1 &1 \end{pmatrix} \begin{pmatrix} c \\ t \end{pmatrix} = \begin{pmatrix} 700 \\ 20 \end{pmatrix}

(1)

Let’s find the inverse $\mathbf{A}^{-1}$ such that $\mathbf{x} = \mathbf{A}^{-1}\mathbf{b}$ . For a 2x2 matrix:

\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \frac{1}{|\mathbf{A}|} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

(2)

where $|\mathbf{A}| = ad-bc$ is the determinant.

For our matrix, $|\mathbf{A}| = 20(1) - 50(1) = -30$ .

\mathbf{A}^{-1} = \frac{1}{-30} \begin{pmatrix} 1 & -50 \\ -1 & 20 \end{pmatrix}

(3)

Thus, $\mathbf{x} = \mathbf{A}^{-1} \mathbf{b} = \begin{pmatrix} 10 \\ 10 \end{pmatrix}$ .

A System with Infinite Solutions¶

Let’s tweak our problem.

There is a discount on tables: they now cost $20 each.
Your budget was cut to $400.

The problem is now:
$20 c + 20 t = 400$
$c+t = 20$

Solve Graphically¶

Solving graphically, we see the lines overlap! What does this mean?

A = [[20, 20], [1, 1]]
b = [400, 20]
fig = exe.visual_solve_2d(A, b)
fig.show()

Solve by Elimination¶

If we multiply the second equation by 20:
$20c+20t = 400$

Subtracting the first, we get:
$0=0$

Any combination of tables and chairs that sums to 20 is a solution. There are an infinite number of solutions.

Examine the matrix (Singular matrix)¶

What happens to our matrix formulation?

\mathbf{A} = \begin{pmatrix} 20 & 20 \\ 1 & 1 \end{pmatrix}

(4)

The determinant is $|\mathbf{A}| = 20(1) - 20(1) = 0$ .

Since the formula for the inverse requires dividing by the determinant ( $\frac{1}{|\mathbf{A}|}$ ), the inverse does not exist.

A matrix with a zero determinant is called singular.

A System with No Solutions¶

Let’s tweak the problem one last time.

Tables and chairs both cost $20.
The budget is raised to $500.

$20 c + 20 t = 500$
$c+t = 20$

Solve Graphically¶

If we examine the solution graphically, we see the lines are parallel and never intersect! There is no combination of 20 pieces of furniture that will cost exactly $500 at $20 each.

A = [[20, 20], [1, 1]]
b = [500, 20]

fig = exe.visual_solve_2d(A, b)
fig.show()

Examine the matrix¶

Just like the infinite solutions case, the determinant of the coefficient matrix is still zero ( $|\mathbf{A}| = 0$ ). The matrix is singular, and the system cannot be solved exactly.

Putting it together¶

Linear equations (in 2 unknowns) are lines in 2D and the solution is the intersection of those lines. 2 lines can intersect either:

In one place, which gives you a unique solution.
Everywhere, which gives you infinite solutions.
Nowhere, where there is no solution!

For 2 and 3, these lines are parallel (you can slide one to lie on top of the other). Such lines are called linearly dependent. Example 1 has linear independent equations which intersect in one place and can be solved.

Scenarios 1 and 2 are called a consistent linear system since an answer can be obtained. Scenario 3 is inconsistent since there is no solution.

The Matrix Interpretation¶

Linear systems generally can be written as:

\mathbf{A}\mathbf{x} = \mathbf{b}

(5)

Solvability, i.e. the ability to find a unique solution, depends solely on $\mathbf{A}$ .

If $|\mathbf{A}| \neq 0$ , the matrix rows are linearly independent, the matrix is invertible (or non-singular), and the system has exactly one solution.
If $|\mathbf{A}| = 0$ , the matrix rows are linearly dependent and the matrix is singular. The lines are parallel, which means either you have infinite solutions or none depending on $\mathbf{b}$ .