Skip to content

Chapter 01: Linear Equations

Prerequisites: Polynomial Algebra (Ch00)

Chapter Outline: Definition of Linear Systems → Matrix Representation (Augmented Matrices) → Elementary Row Operations → Row Echelon Form (REF) & Reduced Row Echelon Form (RREF) → Gaussian & Gauss-Jordan Elimination → Existence and Uniqueness Theorems (Rank-Presence) → Homogeneous & Non-homogeneous Systems → Geometric Interpretation (Intersections of Hyperplanes) → Introduction to Numerical Stability

Extension: Solving linear systems is the underlying engine of nearly all numerical computing (Finite Elements, Optimization, Machine Learning); the structure of its solution space leads directly to the definition of Vector Spaces (Ch04).

Systems of linear equations are the logical starting point of linear algebra. From ancient algorithmic texts to modern supercomputers, solving \(Ax = b\) remains the most central task in scientific computing. This chapter establishes the standard framework for handling linear systems from two dimensions: algorithmic (elimination methods) and theoretical (the structure of solutions).

01.1 Linear Systems and Matrix Representation

Definition 01.1 (System of Linear Equations)

A system of \(m\) linear equations in \(n\) variables is typically written as: $\(\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}\)$ where \(a_{ij}\) are coefficients, \(b_i\) are constants, and \(x_j\) are variables.

Definition 01.2 (Augmented Matrix)

By combining the coefficients and constants into a single matrix, we obtain the \(m \times (n+1)\) augmented matrix: $\(\tilde{A} = [A | \mathbf{b}] = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & | & b_2 \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & | & b_m \end{pmatrix}\)$

01.2 Elementary Row Operations and Echelon Forms

Definition 01.3 (Elementary Row Operations)

  1. Scaling: Multiply a row by a non-zero constant \(k\).
  2. Swapping: Interchange two rows.
  3. Replacement: Add a multiple of one row to another row. These operations do not change the solution set of the system.

Definition 01.4 (Reduced Row Echelon Form - RREF)

A matrix is in Reduced Row Echelon Form (RREF) if: 1. All non-zero rows are above any rows of all zeros. 2. The leading entry (pivot) of each non-zero row is 1. 3. Each leading 1 is the only non-zero entry in its column. 4. The leading 1 of a row is to the right of the leading 1 of the row above it.

01.3 Gaussian Elimination

Algorithm 01.1 (Gauss-Jordan Elimination Steps)

  1. Forward Phase: Use elementary operations to transform the augmented matrix into Row Echelon Form (REF).
  2. Backward Phase: Scaling pivots to 1 and clearing entries above them to reach RREF.
  3. Read Solution: Write the general solution directly from the RREF.

01.4 Existence and Uniqueness

Theorem 01.1 (Existence and Uniqueness Theorem)

Let \(A\) be an \(m \times n\) matrix, and let \(\operatorname{rank}(A)\) be its rank. 1. No Solution (Inconsistent): \(\operatorname{rank}(A) < \operatorname{rank}([A|\mathbf{b}])\). This happens if a row like \([0 \ 0 \ \cdots \ 0 \ | \ d]\) (\(d \neq 0\)) appears in RREF. 2. Unique Solution: \(\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) = n\) (number of variables). 3. Infinitely Many Solutions: \(\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) < n\). The number of free variables is \(n - \operatorname{rank}(A)\).

01.5 Homogeneous Linear Systems

Definition 01.5 (Homogeneous System)

A system of the form \(Ax = 0\) is called a homogeneous system. It always has the trivial solution \(x = 0\). - A homogeneous system has non-trivial solutions if and only if \(\operatorname{rank}(A) < n\). - If \(m < n\) (fewer equations than variables), \(Ax=0\) always has a non-trivial solution.

Exercises

Solution
Solution
Solution
Solution
Solution
Solution
Solution
Solution
Solution
Solution

Chapter Summary

This chapter bridges intuitive equations and algorithmic matrices:

****: Gaussian elimination is the universal tool for linear problems; its RREF form reveals the intrinsic structure of the system.

****: The existence and uniqueness of solutions are entirely determined by the comparison of the ranks of the coefficient and augmented matrices.

****: The solution set of a homogeneous system forms a subspace, while the solution set of a non-homogeneous system is a translation of that subspace (an affine space).