1. Linear Algebra Quick Review

Definition – Matrix

An matrix is an array of numbers arranged in rows and columns:

Basic operations

  • Equality: for all
  • Sum: (same size only)
  • Scalar multiple: ,
  • Zero matrix , opposite

The set of matrices is a vector space:

AdditionScalarsProducts
in general

Definition – Matrix–vector and matrix–matrix product

  • is , is :
  • is , is : (result is )

Special matrices

NameCondition
Square
Diagonal if
Identity , if , else
Upper triangular if
Lower triangular if

Definition – Inverse

An matrix is nonsingular (invertible) if there is with . Otherwise it is singular.

  • is unique;
  • (order reverses)

Definition – Transpose

(size ).

  • , ,
  • If is nonsingular,

Definition – Determinant

  • :
  • : the minor is the determinant of the submatrix obtained by deleting row and column ; expanding along row :

Properties

  • A zero row/column, two equal rows, or one row a multiple of another
  • Swapping two rows changes the sign; multiplying a row by multiplies by
  • ,
  • singular ; if nonsingular,

Theorem – Linear system

The system of equations in unknowns

is written . The following are equivalent:

  1. The system has a unique solution
  2. is invertible

2. Strategy: Two Steps

To solve :

  1. Gauss elimination (reduction): transform to an equivalent upper triangular system
  2. Reverse-path method (back substitution): solve 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 upper triangular with all , each equation contains one new unknown:

  1. Last equation:
  2. Move the known column to the right-hand side and repeat upward. In general:

    ending with .

⚠️ If any diagonal entry , back substitution breaks down (the matrix is singular).


4. Gauss Reduction Method

Method

Form the augmented matrix . At reduction , equation is the pivot equation and is the pivot. For each :

The multiplier is stored in the spot that became zero (this is what gives 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.