Systems of linear equations · Lecture 11

Linear Systems, Cramer's Rule and the Inverse

Writing many equations as $A\mathbf{x} = \mathbf{b}$ , solving them with the two formulas from school, measuring vectors and matrices with norms, and discovering why the formulas break down for real problems.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: currents in a circuit

Kirchhoff's voltage law around each loop of a three-loop circuit gives three equations for the loop currents $I_1, I_2, I_3$ (amperes).

Every loop equation is linear in the currents: resistances times currents add up to the source voltage
Three loops: three equations. A phone charger board: dozens. A chip: millions
School gives two formulas: Cramer's rule and $\mathbf{x} = A^{-1}\mathbf{b}$
Today: use them, count their cost, and see where they fail. A 25-loop circuit by Cramer's rule would take longer than the age of the universe

Loop equations (volts)

\begin{aligned} 7I_1 - 2I_2 \phantom{{}-3I_3} &= 12 \\ -2I_1 + 9I_2 - 3I_3 &= 2 \\ -3I_2 + 6I_3 &= 3 \end{aligned}

The question

Find $I_1, I_2, I_3$ . Then ask: how would the same method cope with 25 loops, or 25 000?

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

2 / 25

Today's goals

Write a system of linear equations as $A\mathbf{x} = \mathbf{b}$ and recognise the three possible outcomes
Solve a system by Cramer's rule and by the inverse (adjugate) method
Count the operations each method needs and explain why both fail for large $n$
Compute vector and matrix norms and the condition number $\kappa(A)$
Predict how many digits of a computed solution can be trusted

Last time

Module 2: Newton for systems needs a linear solve $J\Delta = -F$ at every step.

Today

Linear systems on their own: the school formulas, their cost, and how sensitive the answer is.

Systems of linear equations · you are here

L11 · Linear Systems, Cramer's Rule and the Inverse→L12 · Gaussian and Gauss–Jordan Elimination→L13 · LU, Cholesky and Tridiagonal Systems→L14 · Iterative Methods

Builds on: L5

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

3 / 25

Start here

The idea in one picture

Each linear equation in x and y is a straight line. Solving = finding the crossing.Parallel lines never meet: the equations contradict each other.The same line twice: every point on it is a solution.One number, the determinant, tells the cases apart.

In plain words

Each linear equation is a line (or a plane); solving means finding the common point
Usually there is exactly one, but sometimes none or infinitely many
School formulas work for 2 or 3 unknowns, and become hopeless for many

New words today

system Ax = b: all equations written with one matrix A
determinant: one number that is zero exactly when there is no unique solution
inverse A⁻¹: the matrix that undoes A
norm: a single number for the size of a vector or matrix

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

4 / 25

Many equations, one matrix equation

The circuit in matrix form

\underbrace{\begin{pmatrix} 7 & -2 & 0 \\ -2 & 9 & -3 \\ 0 & -3 & 6 \end{pmatrix}}_{A}\underbrace{\begin{pmatrix} I_1 \\ I_2 \\ I_3 \end{pmatrix}}_{\mathbf{x}} = \underbrace{\begin{pmatrix} 12 \\ 2 \\ 3 \end{pmatrix}}_{\mathbf{b}}

Augmented matrix: all the data in one table

[A \mid \mathbf{b}] = \left(\begin{array}{ccc|c} 7 & -2 & 0 & 12 \\ -2 & 9 & -3 & 2 \\ 0 & -3 & 6 & 3 \end{array}\right)

$a_{ij}$ = coefficient of unknown $j$ in equation $i$
Unique solution exactly when $\det A \ne 0$ (A is nonsingular)
$\det A = 0$ : either no solution (parallel lines) or infinitely many (the same line twice)
Geometry for 2 unknowns: two lines that cross once, never, or everywhere

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

5 / 25

Cramer's rule

2×2: eliminate y, then x (school algebra)

x = \frac{b_1 a_{22} - a_{12} b_2}{a_{11}a_{22} - a_{12}a_{21}} = \frac{\begin{vmatrix} b_1 & a_{12} \\ b_2 & a_{22}\end{vmatrix}}{\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22}\end{vmatrix}}

General rule: Aᵢ is A with column i replaced by b

x_i = \frac{D_i}{D}, \qquad D = \det A, \qquad D_i = \det A_i

3×3 determinant by cofactor expansion along row 1

\det A = a_{11}\begin{vmatrix} a_{22} & a_{23} \\ a_{32} & a_{33}\end{vmatrix} - a_{12}\begin{vmatrix} a_{21} & a_{23} \\ a_{31} & a_{33}\end{vmatrix} + a_{13}\begin{vmatrix} a_{21} & a_{22} \\ a_{31} & a_{32}\end{vmatrix}

A closed formula: no iteration, no stopping rule
Needs $D \ne 0$
$n$ unknowns: $n + 1$ determinants of size $n \times n$
Each $n\times n$ determinant by cofactors needs $n$ determinants of size $n - 1$ : the work multiplies by $n$ at every level

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

6 / 25

The method, step by step

Cramer's rule, step by step

Write the system as $[A \mid \mathbf{b}]$
Compute $D = \det A$ . If $D = 0$ , stop: no unique solution
For each $i = 1, \dots, n$ : copy $A$ , replace column $i$ by $\mathbf{b}$ , compute its determinant $D_i$
Set $x_i = D_i / D$
Check: substitute $\mathbf{x}$ into every equation

Pseudocode

input A (n×n), b
D ← det(A)
if D = 0: stop (singular)
for i = 1 … n:
    Aᵢ ← A with column i := b
    x[i] ← det(Aᵢ) / D
return x

det(M):  # cofactor expansion
    if size 1: return m₁₁
    return Σⱼ (−1)^(1+j) m₁ⱼ det(M₁ⱼ)

The recursion in det is where all the work goes: one call of size $n$ makes $n$ calls of size $n - 1$ .

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

7 / 25

Problem 1: the circuit by Cramer's rule

Solve

7I_1 - 2I_2 = 12

,

\;-2I_1 + 9I_2 - 3I_3 = 2

,

\;-3I_2 + 6I_3 = 3

.

1

D = 7(9\cdot 6 - (-3)(-3)) - (-2)((-2)\cdot 6 - 0) + 0 = 7(45) - 24 = 291 \ne 0

2

D_1 = \begin{vmatrix} 12 & -2 & 0 \\ 2 & 9 & -3 \\ 3 & -3 & 6\end{vmatrix} = 12(45) + 2(12 + 9) = 582

3

In the same way (columns 2 and 3 replaced):

D_2 = 7(12 + 9) - 12(-12) = 291

and

D_3 = 291

4

I_1 = 582/291 = 2

,

\;I_2 = 291/291 = 1

,

\;I_3 = 291/291 = 1

. Check eq. 2:

-4 + 9 - 3 = 2

✓

I_1 = 2

A,

I_2 = 1

A,

I_3 = 1

A, using four 3×3 determinants.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

8 / 25

The inverse method: $\mathbf{x} = A^{-1}\mathbf{b}$

If A⁻¹ exists

A\mathbf{x} = \mathbf{b} \;\Longrightarrow\; A^{-1}A\mathbf{x} = A^{-1}\mathbf{b} \;\Longrightarrow\; \mathbf{x} = A^{-1}\mathbf{b}

Adjugate formula

A^{-1} = \frac{1}{\det A}\,\operatorname{adj} A, \qquad \operatorname{adj}A = C^{T}

2×2: swap the diagonal, negate the rest

\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

$M_{ij}$ (minor) = determinant of $A$ without row $i$ and column $j$
$C_{ij}$ (cofactor) = minor with the sign pattern $\begin{smallmatrix} + & - & + \\ - & + & - \\ + & - & + \end{smallmatrix}$
Exists only when $\det A \ne 0$
Once $A^{-1}$ is known, any new $\mathbf{b}$ costs only a matrix–vector product

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

9 / 25

The method, step by step

The inverse method, step by step

Compute $D = \det A$ ; if $D = 0$ , stop
Compute all $n^2$ cofactors $C_{ij} = (-1)^{i+j}M_{ij}$
Transpose: $\operatorname{adj}A = C^{T}$
Divide: $A^{-1} = \operatorname{adj}A / D$ ; check $AA^{-1} = I$
Multiply: $\mathbf{x} = A^{-1}\mathbf{b}$

Pseudocode

input A (n×n), b
D ← det(A)
if D = 0: stop (singular)
for i, j = 1 … n:
    C[i][j] ← (−1)^(i+j) · det(minor(A, i, j))
Ainv ← transpose(C) / D
for i = 1 … n:
    x[i] ← Σⱼ Ainv[i][j] · b[j]
return x

$n^2$ cofactors, each a determinant of size $n - 1$ : even more work than Cramer for one right-hand side.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

10 / 25

Problem 2: the circuit by the inverse

Find

A^{-1}

for the circuit matrix and use it to find the currents.

1

Cofactors:

C_{11} = 45

,

C_{12} = -\begin{vmatrix} -2 & -3 \\ 0 & 6\end{vmatrix} = 12

,

C_{13} = 6

,

C_{22} = 42

,

C_{23} = 21

,

C_{33} = 59

, and

C_{ji} = C_{ij}

here

2

A^{-1} = \dfrac{1}{291}\begin{pmatrix} 45 & 12 & 6 \\ 12 & 42 & 21 \\ 6 & 21 & 59\end{pmatrix}

(symmetric, because

A

is)

3

\mathbf{x} = A^{-1}\mathbf{b} = \dfrac{1}{291}\begin{pmatrix} 45(12) + 12(2) + 6(3) \\ 12(12) + 42(2) + 21(3) \\ 6(12) + 21(2) + 59(3)\end{pmatrix} = \dfrac{1}{291}\begin{pmatrix} 582 \\ 291 \\ 291\end{pmatrix}

\mathbf{x} = (2, 1, 1)

, as before. Nine 2×2 cofactors plus one 3×3 determinant.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

11 / 25

Limitation 1: the cost explodes

Cofactor determinants: one $n\times n$ determinant costs about $e \cdot n!$ operations
Cramer: $n + 1$ of them. $n = 3$ : 59 operations; $n = 10$ : $1.1\times10^8$ (0.1 s)
$n = 20$ : $1.4 \times 10^{20}$ operations, 4400 years; elimination (Lecture 12): 5910 operations, 6 µs
$n = 25$ : $3.5\times10^{10}$ years, more than the age of the universe

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

12 / 25

Limitations shown failing

Limitations 2 and 3: determinants and inverses in floating point

Underflow

$\det(0.1\,I_{400}) = 10^{-400}$

Below the smallest double ( $4.9\times10^{-324}$ , Lecture 2), so the computer stores 0 and Cramer reports "singular". Yet the system is trivial: $\mathbf{x} = 10\,\mathbf{b}$ .

Overflow

$\det(10\,I_{400}) = 10^{400}$

Overflows to infinity, and every $x_i = D_i/D$ becomes $\infty/\infty$ = NaN. The size of the determinant says nothing useful about the system.

Waste

$A^{-1}$ then $A^{-1}\mathbf{b}$

Even with a good method for the inverse, it costs about $2n^3$ operations, three times elimination, and adds extra rounding errors. Numerical analysts rarely form $A^{-1}$ .

A small determinant does not mean trouble, and a large one does not mean safety. What does measure trouble? The condition number, next.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

13 / 25

Measuring size: vector and matrix norms

Vector norms

\|\mathbf{v}\|_1 = \sum_i |v_i|, \quad \|\mathbf{v}\|_2 = \sqrt{\textstyle\sum_i v_i^2}, \quad \|\mathbf{v}\|_\infty = \max_i |v_i|

Matrix norms: largest column sum, largest row sum

\|A\|_1 = \max_j \sum_i |a_{ij}|, \qquad \|A\|_\infty = \max_i \sum_j |a_{ij}|

Key property

\|A\mathbf{x}\| \le \|A\|\,\|\mathbf{x}\|

$\mathbf{v} = (3, -4, 1)$ : $\|\mathbf{v}\|_1 = 8$ , $\|\mathbf{v}\|_2 = \sqrt{26} = 5.099$ , $\|\mathbf{v}\|_\infty = 4$
Circuit $A$ : row sums 9, 14, 9, so $\|A\|_\infty = 14$ ; column sums give $\|A\|_1 = 14$ too
A norm is a single number for "how big": used for errors, stopping rules and convergence
Same idea as $|x|$ for numbers (Lecture 4), extended to vectors and matrices

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

14 / 25

The condition number of a matrix

Definition

\kappa(A) = \|A\|\,\|A^{-1}\| \;\ge\; 1

Error bound: relative error in b is amplified by at most κ

\frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \;\le\; \kappa(A)\,\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}

Same idea as $\kappa_f$ in Lecture 5, now for systems
Rule of thumb: about $\log_{10}\kappa$ significant digits are lost
Circuit: $\|A^{-1}\|_\infty = 86/291 = 0.2955$ , so $\kappa_\infty = 14 \times 0.2955 = 4.14$ : well-conditioned
$\kappa(cA) = \kappa(A)$ for any $c \ne 0$ : unlike the determinant, it is not fooled by scaling

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

15 / 25

Problem 3: an ill-conditioned system

Find

\kappa_\infty(A)

for

A = \begin{pmatrix} 1 & 1 \\ 1 & 1.0001\end{pmatrix}

. Solve with

\mathbf{b} = (2, 2.0001)

, then with

b_2 = 2.0002

.

1

\det A = 0.0001

,

\;A^{-1} = \dfrac{1}{0.0001}\begin{pmatrix} 1.0001 & -1 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 10001 & -10000 \\ -10000 & 10000\end{pmatrix}

2

\|A\|_\infty = 2.0001

,

\;\|A^{-1}\|_\infty = 20001

,

\;\kappa_\infty = 40004

: about 4–5 digits can be lost

3

\mathbf{b} = (2, 2.0001)

gives

\mathbf{x} = (1, 1)

;

\;b_2 = 2.0002

gives

\mathbf{x} = (0, 2)

4

Input changed by

5\times10^{-5}

, answer by 100%: amplified 20000 times (bound: 40004)

Nearly parallel lines: a tiny change in the data moves the crossing point a long way.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

16 / 25

Classical vs numerical

Same circuit, two approaches

Formula

Classical (Cramer's rule)

Four 3×3 determinants: 291, 582, 291, 291
59 operations, exact fractions by hand
$\mathbf{x} = (2, 1, 1)$

vs

Algorithm

Numerical (Gaussian elimination, Lecture 12)

Eliminate $I_1$ , then $I_2$ , then back-substitute
28 operations
$\mathbf{x} = (2, 1, 1)$

When the classical approach cannot work

A circuit with 25 loops

Cramer's rule: $1.1\times10^{27}$ operations, $3.5\times10^{10}$ years at $10^9$ operations per second. Elimination: 11 325 operations, about 11 µs. Real circuit simulators (SPICE) solve systems with thousands of unknowns many times per second.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

17 / 25

Cramer, the inverse and κ in Python and C

det3 is cofactor expansion along row 1
Cramer: replace column $i$ by $\mathbf{b}$ , divide by $D$
Inverse from cofactors (note the transpose: inv[j][i])
Then $\kappa_\infty = \|A\|_\infty\|A^{-1}\|_\infty$

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

18 / 25

Practice

Practice problem

Problem 4"Solve by Cramer's rule:

x + y + z = 6

,

\;2x - y + z = 3

,

\;x + 2y - z = 2

. Explain why Cramer's rule is not used for large systems."

How to write a complete answer

Write $[A \mid \mathbf{b}]$ ; compute $D$ and state $D = 7 \ne 0$ before anything else
Show each $D_i$ with the replaced column: $D_1 = 7$ , $D_2 = 14$ , $D_3 = 21$
Answer $x = 1$ , $y = 2$ , $z = 3$ , and substitute back as a check
Cost: $n + 1$ determinants, each about $e\cdot n!$ operations by cofactors; give a number (e.g. $n = 20$ : 4400 years) and name the alternative (Gaussian elimination, $\approx 2n^3/3$ )

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

19 / 25

When to use it

Cramer's rule and the adjugate inverse: method profile

Best case

2×2 and 3×3 systems by hand, with exact fractions
When a formula is needed, e.g. the slope of a regression line
Theory: shows the solution depends continuously on the data when $\det A \ne 0$

Worst case

$n \ge 10$ : cost grows like $n!$
Very large or very small determinants: overflow, underflow
Nearly singular $A$ : huge $A^{-1}$ , digits lost

Best suited for

Hand calculation and small symbolic systems
Closed-form formulas: regression coefficients, 2×2 Newton steps (Lecture 10), small graphics transforms
Teaching what a solution means

Avoid when

Any program with $n > 3$
Several right-hand sides (use LU, Lecture 13)
Ill-conditioned problems: these methods add rounding of their own

Rule of thumb: formulas for 2×2 and 3×3 on paper; elimination for everything a computer solves.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

20 / 25

Comparative analysis: methods for $A\mathbf{x} = \mathbf{b}$

Method	Operations (about)	$n = 3$	$n = 1000$	New $\mathbf{b}$ costs	Best for
Cramer (cofactors)	$e\,(n+1)!$	59	impossible	everything again	2×2, 3×3 by hand
Adjugate inverse	$e\,n^2 (n-1)!$	≈ 65	impossible	$2n^2$	tiny matrices, formulas
Gaussian elimination	$\tfrac23 n^3$	28	0.67 s	$\tfrac23 n^3$	one system (L12)
LU factorisation	$\tfrac23 n^3$ once	28	0.67 s	$2n^2$	many right-hand sides (L13)
Jacobi, Gauss–Seidel	per sweep $\approx 2\cdot$ nonzeros	—	fast if sparse	iterate again	huge sparse systems (L14)

Times assume $10^9$ operations per second. "Impossible" means more than $10^{2500}$ years.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

21 / 25

Roadmap

Limitations, and where we fix them

The formulas are exact but hopelessly slow, and blind to floating point. Each limitation has a fix:

What it does well (keep this)

Matrix form $A\mathbf{x} = \mathbf{b}$ and the augmented matrix
Existence: unique solution iff $\det A \ne 0$
Norms and the condition number $\kappa(A)$
Closed formulas for 2×2 and 3×3

LimitationHow it is overcomeWhere

Cost grows like

n!

→

Elimination:

\tfrac23 n^3

operations, with pivoting for safety

Lecture 12 →

Many right-hand sides, same

A

→

Factor once (

A = LU

), then

2n^2

per

\mathbf{b}

Lecture 13 →

Millions of unknowns, mostly zeros

→

Iterative methods that never store the full matrix

Lecture 14 →

Ill-conditioned

A

(large

\kappa

)

→

Cannot be cured by any solver; reformulate (e.g. least squares)

Lecture 23 →

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

22 / 25

Applications

Where this method runs in the real world

Click a card: each one solves a small linear system, or inverts a matrix, at a specific step.

data $x$	1	2	3	4
data $y$	2	3	5	6

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

23 / 25

Checkpoint

Checkpoint · think, then discuss with your neighbourCramer's rule for

2x + 3y = 8

,

\;4x - y = 2

. What is

D_y

?

A

-28

B

28

C

-14

D

2

A.

D = (2)(-1) - (3)(4) = -14

.

D_y = \begin{vmatrix} 2 & 8 \\ 4 & 2\end{vmatrix} = 4 - 32 = -28

, so

y = 2

;

D_x = -8 - 6 = -14

, so

x = 1

.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

24 / 25

Summary

Key points

$A\mathbf{x} = \mathbf{b}$ has a unique solution exactly when $\det A \ne 0$
Cramer: $x_i = D_i/D$ ; inverse: $A^{-1} = \operatorname{adj}A/\det A$ ; both fine for 2×2 and 3×3
Cofactor determinants cost about $e\cdot n!$ : hopeless beyond $n \approx 12$
Norms measure size; $\kappa(A) = \|A\|\|A^{-1}\|$ measures sensitivity; about $\log_{10}\kappa$ digits are lost

Opening problem: solved

Cramer: $D = 291$ , $D_1 = 582$ , $D_2 = D_3 = 291$ , so $I = (2, 1, 1)$ A. The inverse gives the same. For 25 loops, Cramer would need $3.5\times10^{10}$ years: we need elimination.

Homework

Solve $2x + y + z = 7$ , $\;x - y + 2z = 5$ , $\;3x + 2y - z = 4$ by Cramer's rule.
Find the inverses of $\begin{pmatrix} 2 & 1 \\ 5 & 3\end{pmatrix}$ and $\begin{pmatrix} 1 & 0 & 2 \\ 2 & -1 & 3 \\ 4 & 1 & 8\end{pmatrix}$ .
For $A = \begin{pmatrix} 4 & 1 \\ 2 & 3\end{pmatrix}$ find $\|A\|_1$ , $\|A\|_\infty$ , $A^{-1}$ and $\kappa_\infty(A)$ .
With the cost explorer (or the lab program), find the smallest $n$ for which Cramer's rule takes more than one hour.

Next lecture

Gaussian and Gauss–Jordan elimination. The systematic version of school elimination: $\tfrac23 n^3$ operations, and pivoting to protect against rounding.

Md Mahbub E Noor

Lecture 11: Cramer's Rule and the Inverse

University of Barishal

25 / 25

Linear Systems, Cramer's Rule and the Inverse

The problem: currents in a circuit

Today's goals

The idea in one picture

Many equations, one matrix equation

Cramer's rule

Cramer's rule, step by step

Problem 1: the circuit by Cramer's rule

The inverse method: $\mathbf{x} = A^{-1}\mathbf{b}$

The inverse method, step by step

Problem 2: the circuit by the inverse

Limitation 1: the cost explodes

Limitations 2 and 3: determinants and inverses in floating point

$\det(0.1\,I_{400}) = 10^{-400}$

$\det(10\,I_{400}) = 10^{400}$

$A^{-1}$ then $A^{-1}\mathbf{b}$

Measuring size: vector and matrix norms

The condition number of a matrix

Problem 3: an ill-conditioned system

Same circuit, two approaches

Classical (Cramer's rule)

Numerical (Gaussian elimination, Lecture 12)

A circuit with 25 loops

Cramer, the inverse and κ in Python and C

Practice problem

Cramer's rule and the adjugate inverse: method profile

Comparative analysis: methods for $A\mathbf{x} = \mathbf{b}$

Limitations, and where we fix them

Where this method runs in the real world

⚡ Circuit analysis

📈 Regression slope (machine learning)

🖼️ Computer graphics: undo a transform

🔐 Hill cipher (cryptography)

Checkpoint

Summary

Linear Systems, Cramer's Rule and the Inverse

The problem: currents in a circuit

Today's goals

The idea in one picture

Many equations, one matrix equation

Cramer's rule

Cramer's rule, step by step

Problem 1: the circuit by Cramer's rule

The inverse method: x=A−1b\mathbf{x} = A^{-1}\mathbf{b}x=A−1b

The inverse method, step by step

Problem 2: the circuit by the inverse

Limitation 1: the cost explodes

Limitations 2 and 3: determinants and inverses in floating point

det⁡(0.1 I400)=10−400\det(0.1\,I_{400}) = 10^{-400}det(0.1I400​)=10−400

det⁡(10 I400)=10400\det(10\,I_{400}) = 10^{400}det(10I400​)=10400

A−1A^{-1}A−1 then A−1bA^{-1}\mathbf{b}A−1b

Measuring size: vector and matrix norms

The condition number of a matrix

Problem 3: an ill-conditioned system

Same circuit, two approaches

Classical (Cramer's rule)

Numerical (Gaussian elimination, Lecture 12)

A circuit with 25 loops

Cramer, the inverse and κ in Python and C

Practice problem

Cramer's rule and the adjugate inverse: method profile

Comparative analysis: methods for Ax=bA\mathbf{x} = \mathbf{b}Ax=b

Limitations, and where we fix them

Where this method runs in the real world

⚡ Circuit analysis

📈 Regression slope (machine learning)

🖼️ Computer graphics: undo a transform

🔐 Hill cipher (cryptography)

Checkpoint

Summary

The inverse method: $\mathbf{x} = A^{-1}\mathbf{b}$

$\det(0.1\,I_{400}) = 10^{-400}$

$\det(10\,I_{400}) = 10^{400}$

$A^{-1}$ then $A^{-1}\mathbf{b}$

Comparative analysis: methods for $A\mathbf{x} = \mathbf{b}$