Linear Equations

Systems of linear equations appear in virtually every area of science and engineering: circuit analysis, structural mechanics, computer graphics, and machine learning all reduce to solving $Ax = b$ at their core. This chapter develops the two main direct methods for solving such systems — Gaussian elimination and LU decomposition — along with the pivoting strategies needed to make them numerically reliable.

Learning Objectives

By the end of this chapter you should be able to:

Write a system of $m$ linear equations in $n$ unknowns in the compact matrix form $Ax = b$ .
State the two conditions a matrix $A$ must satisfy for a unique solution to exist (square and non-singular).
Identify lower and upper triangular matrices and explain why they simplify solving a linear system.
Apply forward substitution to a lower triangular system and back substitution to an upper triangular system.
Derive the total operation count for forward or back substitution and show it equals $n^2$ .
Apply Gaussian elimination row operations to transform an augmented matrix $[A\,|\,b]$ into upper triangular form.
Define a Frobenius matrix, compute it from the elimination multipliers, and use it to represent one round of Gaussian elimination.
Assemble the $L$ and $U$ factors of a matrix from the Frobenius matrices produced during elimination, and use the factorization $A = LU$ to solve $Ax = b$ efficiently.
Explain why a zero pivot causes Gaussian elimination to fail and apply both partial pivoting (row swapping) and complete pivoting (column swapping) to resolve it.

Chapter Sections

#	Section	Key Concepts
1	Systems of Linear Equations	System notation, matrix form $Ax=b$ , solution via $A^{-1}$ , non-singularity
2	Gaussian Elimination	Triangular matrices, forward/back substitution, operation count $n^2$ , augmented matrix example
3	LU Decomposition	Frobenius matrices, assembling $L$ and $U$ , solving $Ly=b$ then $Ux=y$
4	Pivoting	Zero pivot failure, partial pivoting (row swap), complete pivoting (column swap)