Solving Systems by Gaussian Elimination

A system of $m$ equations in $n$ unknowns is written $Ax=b$ with coefficient matrix $A\in\mathbb{R}^{m\times n}$ and right-hand side $b\in\mathbb{R}^{m}$. We record it compactly in the augmented matrix $[A\mid b]\in\mathbb{R}^{m\times(n+1)}$. The whole method rests on one fact: elementary row operations (swap two rows, scale a row by a nonzero scalar, add a multiple of one row to another) do not change the solution set. Each such operation is multiplication on the left by an invertible matrix, and Lemma 5.1 says that multiplying both sides by an invertible $B$ turns $\operatorname{sol}(A,b)$ into $\operatorname{sol}(BA,Bb)=\operatorname{sol}(A,b)$. Applied to the augmented matrix (same operation on $A$ and on $b$ simultaneously), this is Theorem 5.5: $\operatorname{sol}(A',b')=\operatorname{sol}(A,b)$.

The solution set is $\operatorname{sol}(A,b)=\{x\in\mathbb{R}^n\mid Ax=b\}$. The system is consistent if this set is nonempty and inconsistent if it is empty. Theorem 5.4 gives the test: $Ax=b$ is consistent if and only if $b\in\operatorname{im}(A)$, equivalently $\operatorname{rank}(A)=\operatorname{rank}([A\mid b])$. Appending $b$ can only keep the rank the same or raise it by one, so there are exactly two possibilities. If $\operatorname{rank}([A\mid b])>\operatorname{rank}(A)$ the reduced matrix has a row $[\,0\;\cdots\;0\mid c\,]$ with $c\neq 0$, i.e. the impossible equation $0=c$, and the system has no solution (Example 5.8).

When the system is consistent, Theorem 5.4 describes the shape of the answer. First, the homogeneous system $Ax=0$ always has the solution $x=0$ and its full solution set is $\operatorname{sol}(A,0)=\ker A$, a subspace of $\mathbb{R}^n$ of dimension $n-\operatorname{rank}(A)$ (rank-nullity). Second, if $w$ is any one (particular) solution of $Ax=b$, then $\operatorname{sol}(A,b)=w+\ker A=\{w+x\mid x\in\ker A\}$. So the general solution is one particular solution plus all homogeneous solutions. For $b\neq 0$ this is an affine subspace (a point, line, or plane shifted off the origin), not a subspace, because $x=0$ is not a solution.

(1) Bring $[A\mid b]$ to reduced echelon form and compare $\operatorname{rank}(A)$ with $\operatorname{rank}([A\mid b])$; if they differ, stop -- there is no solution. (2) The columns of $A$ without a pivot correspond to free variables; name them $\lambda_1,\dots,\lambda_k$ where $k=n-\operatorname{rank}(A)$. (3) Each nonzero row of the reduced matrix solves one pivot variable in terms of the $\lambda_i$ and the last column. (4) Collect the constant part and the $\lambda_i$-parts to write $\operatorname{sol}(A,b)=w+\lambda_1 u_1+\dots+\lambda_k u_k$, where $w$ is a particular solution and $u_1,\dots,u_k$ form a basis of $\ker A$. Three outcomes: $k=0$ gives a unique solution (Example 5.11); $k\ge 1$ with consistency gives infinitely many (Examples 5.7, 5.9, 5.10); rank mismatch gives none (Example 5.8).