Skip to content
Wyatt's Notes — University

Systems of Linear Equations

4.1 Gaussian Elimination

A system of mm linear equations in nn unknowns can be written as Ax=bA\mathbf{x} = \mathbf{b}Where A∈Mm×n(R)A \in \mathcal{M}_{m \times n}(\mathbb{R}), x∈Rn\mathbf{x} \in \mathbb{R}^nAnd b∈Rm\mathbf{b} \in \mathbb{R}^m.

Gaussian elimination transforms the augmented matrix [A∣b][A \mid \mathbf{b}] into row echelon Form (REF) using elementary row operations:

  1. Swap two rows (Ri↔RjR_i \leftrightarrow R_j).
  2. Multiply a row by a non-zero scalar (Ri→αRiR_i \to \alpha R_i).
  3. Add a multiple of one row to another (Ri→Ri+αRjR_i \to R_i + \alpha R_j).

A matrix is in REF if:

  • All zero rows are at the bottom.
  • The leading entry (pivot) of each non-zero row is strictly to the right of the pivot above.
  • All entries below a pivot are zero.

Reduced row echelon form (RREF) additionally requires:

  • Each pivot is 1.
  • Each pivot is the only non-zero entry in its column.

Theorem 4.1. Every matrix has a unique RREF. Two matrices are row-equivalent if and only if they Have the same RREF.

4.2 Existence and Uniqueness

Theorem 4.2 (Rouché—Capelli). The system Ax=bA\mathbf{x} = \mathbf{b} is consistent (has at least one Solution) if and only if

rank(A)=rank([A∣b])\mathrm{rank}(A) = \mathrm{rank}([A \mid \mathbf{b}])

If consistent, the solution set has dim⁡(null(A))\dim(\mathrm{null}(A)) free parameters, where dim⁡(null(A))=n−rank(A)\dim(\mathrm{null}(A)) = n - \mathrm{rank}(A).

Proof. Let the RREF of [A∣b][A \mid \mathbf{b}] have r=rank(A)r = \mathrm{rank}(A) pivots in the coefficient Columns. The system is inconsistent if and only if the last non-zero row is [0⋯0∣1][0 \cdots 0 \mid 1] Which occurs precisely when the augmented column contains a pivot, i.e., when rank([A∣b])>r\mathrm{rank}([A \mid \mathbf{b}]) \gt r.

If consistent, the rr pivot variables are determined by the n−rn - r free variables, yielding n−rank(A)n - \mathrm{rank}(A) degrees of freedom. ■\blacksquare

4.3 LU Decomposition

An LU decomposition of A∈Mn×n(R)A \in \mathcal{M}_{n \times n}(\mathbb{R}) writes A=LUA = LU where LL is Lower triangular with 1s on the diagonal, and UU is upper triangular.

Theorem 4.3. If Gaussian elimination can be performed on AA without row exchanges, then AA Admits an LU decomposition.

Algorithm. Store the multipliers mijm_{ij} (used to eliminate entry aija_{ij}) in the lower Triangular portion. The resulting upper triangular matrix is UUAnd the multipliers form LL.

Worked Example. Find the LU decomposition of

A=(211433879)A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}

Solution

Step 1: Eliminate below a11a_{11}. m21=4/2=2m_{21} = 4/2 = 2, m31=8/2=4m_{31} = 8/2 = 4.

(211011035)\begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 3 & 5 \end{pmatrix}

Step 2: Eliminate below a22a_{22}. m32=3/1=3m_{32} = 3/1 = 3.

U=(211011002)U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}

L=(100210431)L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}

Verify: LU=(211433879)=ALU = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix} = A. ■\blacksquare

To solve Ax=bA\mathbf{x} = \mathbf{b}First solve Ly=bL\mathbf{y} = \mathbf{b} (forward substitution), Then Ux=yU\mathbf{x} = \mathbf{y} (back substitution).

4.4 Gaussian Elimination with Partial Pivoting

When a pivot is zero (or very small), we swap rows to bring the largest available entry in the Current column into the pivot position. This is partial pivoting, and it improves numerical Stability.

Problem. Solve the system using Gaussian elimination with partial pivoting:

x1+2x2+x3=53x1+x2−x3=22x1+3x2+4x3=11\begin{aligned} x_1 + 2x_2 + x_3 &= 5 \\ 3x_1 + x_2 - x_3 &= 2 \\ 2x_1 + 3x_2 + 4x_3 &= 11 \end{aligned}

Solution

Augmented matrix:

[A∣b]=(121531−1223411)[A \mid \mathbf{b}] = \begin{pmatrix} 1 & 2 & 1 & 5 \\ 3 & 1 & -1 & 2 \\ 2 & 3 & 4 & 11 \end{pmatrix}

Step 1. Column 1: largest entry is 3 in row 2. Swap R1↔R2R_1 \leftrightarrow R_2:

(31−12121523411)\begin{pmatrix} 3 & 1 & -1 & 2 \\ 1 & 2 & 1 & 5 \\ 2 & 3 & 4 & 11 \end{pmatrix}

R2→R2−13R1R_2 \to R_2 - \frac{1}{3}R_1, R3→R3−23R1R_3 \to R_3 - \frac{2}{3}R_1:

(31−1205/34/313/307/314/329/3)\begin{pmatrix} 3 & 1 & -1 & 2 \\ 0 & 5/3 & 4/3 & 13/3 \\ 0 & 7/3 & 14/3 & 29/3 \end{pmatrix}

Step 2. Column 2: largest entry below pivot is 7/37/3 in row 3. Swap R2↔R3R_2 \leftrightarrow R_3:

(31−1207/314/329/305/34/313/3)\begin{pmatrix} 3 & 1 & -1 & 2 \\ 0 & 7/3 & 14/3 & 29/3 \\ 0 & 5/3 & 4/3 & 13/3 \end{pmatrix}

R3→R3−57R2R_3 \to R_3 - \frac{5}{7}R_2:

(31−1207/314/329/300−2/7−6/7)\begin{pmatrix} 3 & 1 & -1 & 2 \\ 0 & 7/3 & 14/3 & 29/3 \\ 0 & 0 & -2/7 & -6/7 \end{pmatrix}

Back substitution. From row 3: −27x3=−67-\frac{2}{7}x_3 = -\frac{6}{7}So x3=3x_3 = 3.

From row 2: 73x2+143(3)=293\frac{7}{3}x_2 + \frac{14}{3}(3) = \frac{29}{3}So 73x2=293−14=−133\frac{7}{3}x_2 = \frac{29}{3} - 14 = -\frac{13}{3} Giving x2=−137x_2 = -\frac{13}{7}.

From row 1: 3x1+(−137)−3=23x_1 + (-\frac{13}{7}) - 3 = 2So 3x1=2+3+137=4873x_1 = 2 + 3 + \frac{13}{7} = \frac{48}{7} Giving x1=167x_1 = \frac{16}{7}.

Solution: x1=167x_1 = \frac{16}{7}, x2=−137x_2 = -\frac{13}{7}, x3=3x_3 = 3. ■\blacksquare

4.5 Least Squares Solutions

When Ax=bA\mathbf{x} = \mathbf{b} is overdetermined (more equations than unknowns) and inconsistent, We seek x\mathbf{x} that minimises ∥Ax−b∥2\lVert A\mathbf{x} - \mathbf{b} \rVert^2.

Theorem 4.4 (Normal Equations). The least squares solution x^\hat{\mathbf{x}} satisfies

ATAx^=ATbA^T A \hat{\mathbf{x}} = A^T \mathbf{b}

If AA has full column rank, then ATAA^T A is invertible and x^=(ATA)−1ATb\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}.

Proof. The error vector e=Ax−b\mathbf{e} = A\mathbf{x} - \mathbf{b} is minimised when e⊥col(A)\mathbf{e} \perp \mathrm{col}(A) I.e., when ATe=0A^T \mathbf{e} = \mathbf{0}. This gives AT(Ax−b)=0A^T(A\mathbf{x} - \mathbf{b}) = \mathbf{0} Or ATAx=ATbA^T A \mathbf{x} = A^T \mathbf{b}. If AA has full column rank, then ker⁡(A)={0}\ker(A) = \{\mathbf{0}\} So ker⁡(ATA)=ker⁡(A)={0}\ker(A^T A) = \ker(A) = \{\mathbf{0}\}Meaning ATAA^T A is invertible. ■\blacksquare

Problem. Find the least squares line y=ax+by = ax + b fitting the data points (1,1)(1, 1), (2,1)(2, 1), (3,3)(3, 3).

Solution

The system is (112131)(ab)=(113)\begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 3 \end{pmatrix} I.e., Ax=bA\mathbf{x} = \mathbf{b} with A=(112131)A = \begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{pmatrix} x=(a,b)T\mathbf{x} = (a, b)^T, b=(1,1,3)T\mathbf{b} = (1, 1, 3)^T.

Compute ATA=(123111)(112131)=(14663)A^T A = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{pmatrix} = \begin{pmatrix} 14 & 6 \\ 6 & 3 \end{pmatrix}.

ATb=(123111)(113)=(125)A^T \mathbf{b} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 12 \\ 5 \end{pmatrix}.

Solve (14663)(ab)=(125)\begin{pmatrix} 14 & 6 \\ 6 & 3 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} 12 \\ 5 \end{pmatrix}:

det⁡(ATA)=42−36=6\det(A^T A) = 42 - 36 = 6.

(ATA)−1=16(3−6−614)(A^T A)^{-1} = \frac{1}{6}\begin{pmatrix} 3 & -6 \\ -6 & 14 \end{pmatrix}.

x^=16(3−6−614)(125)=16(36−30−72+70)=16(6−2)=(1−1/3)\hat{\mathbf{x}} = \frac{1}{6}\begin{pmatrix} 3 & -6 \\ -6 & 14 \end{pmatrix}\begin{pmatrix} 12 \\ 5 \end{pmatrix} = \frac{1}{6}\begin{pmatrix} 36 - 30 \\ -72 + 70 \end{pmatrix} = \frac{1}{6}\begin{pmatrix} 6 \\ -2 \end{pmatrix} = \begin{pmatrix} 1 \\ -1/3 \end{pmatrix}.

The least squares line is y=x−1/3y = x - 1/3. ■\blacksquare

4.6 Worked Example: System with Infinitely Many Solutions

Problem. Solve the system:

x1+2x2−x3+3x4=12x1+4x2−x3+5x4=2x1+2x2+x3+x4=0\begin{aligned} x_1 + 2x_2 - x_3 + 3x_4 &= 1 \\ 2x_1 + 4x_2 - x_3 + 5x_4 &= 2 \\ x_1 + 2x_2 + x_3 + x_4 &= 0 \end{aligned}

Solution

(12−13124−15212110)→R2−2R1,R3−R1(12−131001−10002−2−1)\begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 2 & 4 & -1 & 5 & 2 \\ 1 & 2 & 1 & 1 & 0 \end{pmatrix} \xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 2 & -2 & -1 \end{pmatrix}

→R3−2R2(12−131001−100000−1)\xrightarrow{R_3 - 2R_2} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1 \end{pmatrix}

The last row reads 0=−10 = -1So the system is inconsistent (no solution).

Revised problem: Change the last equation to x1+2x2+x3+x4=2x_1 + 2x_2 + x_3 + x_4 = 2:

(12−13124−15212112)→R2−2R1,R3−R1(12−131001−10002−21)\begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 2 & 4 & -1 & 5 & 2 \\ 1 & 2 & 1 & 1 & 2 \end{pmatrix} \xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 2 & -2 & 1 \end{pmatrix}

→R3−2R2(12−131001−1000001)\xrightarrow{R_3 - 2R_2} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}

Still inconsistent! The RREF reveals 0=10 = 1 in the last row.

Revised again: Change the last equation to x1+2x2+x3+x4=1x_1 + 2x_2 + x_3 + x_4 = 1:

(12−13124−15212111)→R2−2R1,R3−R1(12−131001−10002−20)\begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 2 & 4 & -1 & 5 & 2 \\ 1 & 2 & 1 & 1 & 1 \end{pmatrix} \xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 2 & -2 & 0 \end{pmatrix}

→R3−2R2(12−131001−1000000)\xrightarrow{R_3 - 2R_2} \begin{pmatrix} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}

Now the system is consistent. Pivots in columns 1 and 3; free variables are x2x_2 and x4x_4. From row 2: x3=x4x_3 = x_4. From row 1: x1=1−2x2+x3−3x4=1−2x2−2x4x_1 = 1 - 2x_2 + x_3 - 3x_4 = 1 - 2x_2 - 2x_4.

Solution set: {(1−2s−2t,s,t,t):s,t∈R}\{(1 - 2s - 2t, s, t, t) : s, t \in \mathbb{R}\}.

In parametric form: (x1x2x3x4)=(1000)+s(−2100)+t(−2011)\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + s\begin{pmatrix} -2 \\ 1 \\ 0 \\ 0 \end{pmatrix} + t\begin{pmatrix} -2 \\ 0 \\ 1 \\ 1 \end{pmatrix}.

The solution space is a 2-dimensional affine subspace (a plane) in R4\mathbb{R}^4. ■\blacksquare

4.7 Common Pitfalls

  • Partial pivoting is not optional for numerical work. Without it, Gaussian elimination can produce catastrophically wrong results due to rounding errors.
  • The normal equations can be ill-conditioned. For better numerical stability, use QR decomposition to solve least squares problems instead of forming ATAA^T A.
  • Not every system has a solution. Always check consistency via the Rouché—Capelli theorem before attempting to solve.