An m×n matrix A=[aij] is an array of mn numbers arranged in m rows and n columns: A=a11⋮am1⋯⋱⋯a1n⋮amn
Basic operations
Equality:A=B⟺aij=bij for all i,j
Sum:A±B=[aij±bij] (same size only)
Scalar multiple:λA=[λaij], λ∈R
Zero matrix0, opposite−A=[−aij]
The set of m×n matrices is a vector space:
Addition
Scalars
Products
A+B=B+A
λ(A+B)=λA+λB
A(BC)=(AB)C
(A+B)+C=A+(B+C)
(λ+μ)A=λA+μA
A(B+D)=AB+AD
A+0=A
λ(μA)=(λμ)A
λ(AB)=(λA)B=A(λB)
A+(−A)=0
1A=A
AB=BA in general
Definition – Matrix–vector and matrix–matrix product
A is m×n, b is n×1: (Ab)i=j=1∑naijbj
A is m×n, B is n×k: (AB)ij=l=1∑nailblj (result is m×k)
Special matrices
Name
Condition
Square
n×n
Diagonal
aij=0 if i=j
Identity I
I=[δij], δij=1 if i=j, else 0
Upper triangular
aij=0 if i>j
Lower triangular
aij=0 if i<j
Definition – Inverse
An n×n matrix A is nonsingular (invertible) if there is A−1 with A−1A=AA−1=I. Otherwise it is singular.
A−1 is unique; (A−1)−1=A
(AB)−1=B−1A−1 (order reverses)
Definition – Transpose
AT=[aji] (size n×m).
(AT)T=A, (A+B)T=AT+BT, (AB)T=BTAT
If A is nonsingular, (A−1)T=(AT)−1
Definition – Determinant
1×1: det[a]=a
n×n: the minorMij is the determinant of the (n−1)×(n−1) submatrix obtained by deleting row i and column j; expanding along row i: detA=∑j=1n(−1)i+jaijMij
Properties
A zero row/column, two equal rows, or one row a multiple of another ⇒detA=0
Swapping two rows changes the sign; multiplying a row by λ multiplies det by λ
det(AB)=detA⋅detB, det(AT)=detA
A singular ⟺detA=0; if nonsingular, det(A−1)=1/detA
Theorem – Linear system Ax=b
The system of n equations in n unknowns Ei:ai1x1+ai2x2+⋯+ainxn=bi,i=1,…,n
is written Ax=b. The following are equivalent:
The system has a unique solution
detA=0
A is invertible
2. Strategy: Two Steps
To solve (S):Ax=b:
Gauss elimination (reduction): transform to an equivalent upper triangular system Ux=c
Reverse-path method (back substitution): solve Ux=c from the bottom up
flowchart LR
A["Ax = b"] -->|"Gauss reduction<br/>(row operations on [A | b])"| B["Ux = c<br/>(upper triangular)"]
B -->|"Back substitution<br/>x_n first, then up"| C["x = (x₁, …, xₙ)"]
3. Reverse-Path Method (Back Substitution)
Method
For U upper triangular with all uii=0, each equation contains one new unknown:
Last equation: xn=unncn
Move the known column to the right-hand side and repeat upward. In general: xi=uiici−j=i+1∑nuijxj,i=n−1,…,1
ending with x1=u11c1−u1nxn−⋯−u12x2.
⚠️ If any diagonal entry uii=0, back substitution breaks down (the matrix is singular).
4. Gauss Reduction Method
Method
Form the augmented matrix[A∣b]. At reduction k=1,…,n−1, equation k is the pivot equation and akk is the pivot. For each i=k+1,…,n: mik=akkaik,equation i←equation i−mik×equation k
The multiplier mik is stored in the spot that became zero (this is what gives L later).
Example (slides) – reduce and solve
\qquad [A\mid b] = \left(\begin{array}{cccc|c} 6 & -2 & 2 & 4 & 16 \\ 12 & -8 & 6 & 10 & 26 \\ 3 & -13 & 9 & 3 & -19 \\ -6 & 4 & 1 & -18 & -34 \end{array}\right)$$
**Reduction 1** – pivot $a_{11} = 6$, multipliers $\{2, \tfrac12, -1\}$:
$E_2 \leftarrow E_2 - 2E_1$, $\;E_3 \leftarrow E_3 - \tfrac12 E_1$, $\;E_4 \leftarrow E_4 + E_1$
$$\left(\begin{array}{cccc|c} 6 & -2 & 2 & 4 & 16 \\ \boxed{2} & -4 & 2 & 2 & -6 \\ \boxed{1/2} & -12 & 8 & 1 & -27 \\ \boxed{-1} & 2 & 3 & -14 & -18 \end{array}\right)$$
**Reduction 2** – pivot $a_{22} = -4$, multipliers $\{3, -\tfrac12\}$:
$E_3 \leftarrow E_3 - 3E_2$, $\;E_4 \leftarrow E_4 + \tfrac12 E_2$
$$\left(\begin{array}{cccc|c} 6 & -2 & 2 & 4 & 16 \\ \boxed{2} & -4 & 2 & 2 & -6 \\ \boxed{1/2} & \boxed{3} & 2 & -5 & -9 \\ \boxed{-1} & \boxed{-1/2} & 4 & -13 & -21 \end{array}\right)$$
**Reduction 3** – pivot $a_{33} = 2$, multiplier $\{2\}$: $E_4 \leftarrow E_4 - 2E_3$
$$(U \mid c) = \left(\begin{array}{cccc|c} 6 & -2 & 2 & 4 & 16 \\ 0 & -4 & 2 & 2 & -6 \\ 0 & 0 & 2 & -5 & -9 \\ 0 & 0 & 0 & -3 & -3 \end{array}\right)$$
**Back substitution:**
| Step | Computation | Result |
|---|---|---|
| $x_4$ | $-3/(-3)$ | $1$ |
| $x_3$ | $(-9 + 5\cdot 1)/2$ | $-2$ |
| $x_2$ | $(-6 - 2(-2) - 2(1))/(-4)$ | $1$ |
| $x_1$ | $(16 + 2(1) - 2(-2) - 4(1))/6$ | $3$ |
$$\boxed{x = (3,\; 1,\; -2,\; 1)}$$
> ⚠️ Always use the **updated** rows when computing multipliers: in reduction 2 the pivot is the new $a_{22} = -4$, not the original $-8$.
---
## 5. Gauss Elimination with Pivoting
### Why pivoting? (small-pivot problem)
Even if every leading submatrix has $\det \neq 0$, a **tiny pivot** produces huge multipliers and large round-off errors.
**Example (slides):**
$$\begin{cases} \varepsilon x_1 + x_2 = 1 \\ x_1 + x_2 = 2 \end{cases}\qquad \text{exact solution } (x_1, x_2) \approx (1, 1) \text{ as } \varepsilon \to 0$$
- **No pivoting** (pivot $\varepsilon$): $\left(1 - \tfrac1\varepsilon\right)x_2 = 2 - \tfrac1\varepsilon \Rightarrow x_2 = \dfrac{2 - 1/\varepsilon}{1 - 1/\varepsilon},\; x_1 = \dfrac{1-x_2}{\varepsilon}$.
On a computer with $1/\varepsilon$ huge, both $2 - 1/\varepsilon$ and $1-1/\varepsilon$ round to $-1/\varepsilon$, so $x_2 = 1$ and $x_1 = 0$. **Wrong:** $(0, 1)$.
- **Swap the equations first** (pivot $1$): $x_1 + x_2 = 2$, $(1-\varepsilon)x_2 = 1 - 2\varepsilon$. **Correct:** $(1,1)$.
> ⚠️ Checked in double precision with $\varepsilon = 10^{-17}$: without the swap you get exactly $(0,\,1)$. The math is exact, but the arithmetic loses everything.
### Index vector $VI$
Rows are **not physically swapped**. A row vector $VI$ records the order in which equations are used as pivots. It starts as $VI = [1, 2, \dots, n]$; each reduction swaps entries of $VI$ only.
### Method – Partial pivoting
At reduction $k$, choose the row with the **largest $|a_{ik}|$** in column $k$ among the rows not yet used ($VI(k),\dots,VI(n)$):
$$|a_{i_k,k}| = \max_{VI(k) \le i \le VI(n)} |a_{ik}|$$
then swap positions $k$ and $i_k$ in $VI$. Row $i_k$ is the pivot equation and $a_{i_k,k}$ the pivot.
**Example (extra, same 4×4 system):**
| Reduction | Candidates $\lvert a_{ik}\rvert$ | Pivot row | $VI$ after |
|---|---|---|---|
| $k=1$ | $6, 12, 3, 6$ | row 2 ($12$) | $[2,1,3,4]$ |
| $k=2$ | rows 1, 3, 4: $2, 11, 0$ | row 3 ($-11$) | $[2,3,1,4]$ |
| $k=3$ | rows 1, 4: $\approx 0.36,\ 4$ | row 4 ($4$) | $[2,3,4,1]$ |
Back substitution in the order $VI$ gives the same $x = (3, 1, -2, 1)$.
### Method – Normalized (scaled) partial pivoting
Use this when entries in the **same row** have very different sizes. Compute once the scale factor of each row:
$$s_i = \max_{1 \le j \le n} |a_{ij}|, \qquad s = [s_1, \dots, s_n]$$
At step $k$, pick the row maximizing the **ratio** $\dfrac{|a_{ik}|}{s_i}$ (take the first index on ties), then swap in $VI$ and continue as before.
**Example (extra, same system):** $s = [6, 12, 13, 18]$
| Reduction | Ratios $\lvert a_{ik}\rvert / s_i$ | Pivot row | $VI$ after |
|---|---|---|---|
| $k=1$ | $1,\ 1,\ 0.231,\ 0.333$ | row 1 (first max) | $[1,2,3,4]$ |
| $k=2$ | rows 2, 3, 4: $0.333,\ 0.923,\ 0.111$ | row 3 | $[1,3,2,4]$ |
| $k=3$ | rows 2, 4: $0.056,\ 0.241$ | row 4 | $[1,3,4,2]$ |
> ⚠️ Plain partial pivoting picks row 2 at $k=1$ (largest $|a_{i1}| = 12$); scaled pivoting keeps row 1 because $12/12 = 6/6$. The two strategies can choose **different** pivots.
>
> ⚠️ The slides call $s_i$ "the maximal element of each column", but the formula $\max_j |a_{ij}|$ is the maximum of **row** $i$. Use the row maximum.
---
## 6. LU Decomposition
### Definition
Factor $A = LU$ with $L$ **lower** triangular (unit diagonal, holding the Gauss multipliers) and $U$ **upper** triangular (the result of Gauss reduction).
### Method
$$Ax = b \iff L(Ux) = b \iff \begin{cases} LD = b & \text{forward substitution} \to D \\ Ux = D & \text{back substitution} \to x \end{cases}$$
```mermaid
flowchart LR
A["A = LU<br/>(factor once)"] --> F["Forward solve<br/>L D = b"]
F --> B["Backward solve<br/>U x = D"]
B --> X["x"]
```
### Example (extra, from the Gauss example above)
The boxed multipliers form $L$:
$$L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ \tfrac12 & 3 & 1 & 0 \\ -1 & -\tfrac12 & 2 & 1 \end{pmatrix}, \qquad U = \begin{pmatrix} 6 & -2 & 2 & 4 \\ 0 & -4 & 2 & 2 \\ 0 & 0 & 2 & -5 \\ 0 & 0 & 0 & -3 \end{pmatrix}$$
(check: $LU = A$ ✓)
**Forward**, $LD = b = (16, 26, -19, -34)^T$:
$D_1 = 16$, $\;D_2 = 26 - 2(16) = -6$, $\;D_3 = -19 - 8 - 3(-6) = -9$, $\;D_4 = -34 + 16 - 3 - 2(-9) = -3$
→ $D = (16, -6, -9, -3)^T$, the same as $c$ from Gauss.
**Backward**, $Ux = D$ → $x = (3, 1, -2, 1)$.
> ⚠️ LU pays off when you solve with the **same $A$** and **many different $b$**: factor once, then each new $b$ costs only two triangular solves.