1  Linear systems and Gaussian elimination

1.1 Matrices encode equations

A linear system in \(n\) unknowns consists of equations \(a_{i1}x_1+\cdots+a_{in}x_n=b_i\), for \(1\le i\le m\). Write it as \(Ax=b\), with \(A\in\mathbb F^{m\times n}\), \(x\in\mathbb F^n\) and \(b\in\mathbb F^m\). Its augmented matrix is \([A\mid b]\).

A system is consistent if it has at least one solution. The homogeneous system \(Ax=0\) is always consistent, since \(x=0\) solves it. We use exact arithmetic here; floating-point issues belong to Numerical Analysis (planned).

1.2 Row operations and pivots

The elementary row operations are: exchange two rows; multiply a row by a nonzero scalar; add a multiple of one row to another. Each is reversible, so applying it to an augmented matrix preserves precisely the solution set.

In row echelon form, zero rows appear below nonzero rows, and each nonzero row’s leading entry lies strictly to the right of the leading entry above it. Entries below each leading entry are zero. These leading positions are pivots. In reduced row echelon form (RREF), each pivot is \(1\) and is the only nonzero entry in its column. Every matrix over a field has a unique RREF, although different sequences of row operations can reach it.

Gaussian elimination finds echelon form; back substitution solves for pivot variables in terms of free variables. Continuing elimination above pivots gives RREF.

1.2.1 Worked example: a family of solutions

Consider this system over \(\mathbb R\): \[\begin{aligned} x+2y-z&=1,\\ 2x+4y+z&=5,\\ -x-2y+2z&=0. \end{aligned}\] Start from \[\left[\begin{array}{rrr|r}1&2&-1&1\\2&4&1&5\\-1&-2&2&0\end{array}\right].\] Apply \(R_2\leftarrow R_2-2R_1\) and \(R_3\leftarrow R_3+R_1\): \[\left[\begin{array}{rrr|r}1&2&-1&1\\0&0&3&3\\0&0&1&1\end{array}\right].\] Scale \(R_2\) by \(1/3\), subtract it from \(R_3\), and add it to \(R_1\): \[\left[\begin{array}{rrr|r}1&2&0&2\\0&0&1&1\\0&0&0&0\end{array}\right].\] Thus \(z=1\), \(y=t\) is free, and \(x=2-2t\). The solution set is \[\begin{pmatrix}x\\y\\z\end{pmatrix} =\begin{pmatrix}2\\0\\1\end{pmatrix} +t\begin{pmatrix}-2\\1\\0\end{pmatrix},\qquad t\in\mathbb R.\] Substitution into all three original equations verifies every value of \(t\).

1.3 Consistency, uniqueness and rank

Consistency criterion. A system is inconsistent exactly when an echelon form of its augmented matrix contains a row \([0\ \cdots\ 0\mid c]\) with \(c\ne0\). Such a row says \(0=c\). If no such row occurs, assigning free variables and then back substituting constructs a solution.

Define \(\operatorname{rank}(A)\) as the number of pivots in an echelon form of \(A\) (equivalently the dimension of its column space, developed in the following chapters). Then \[Ax=b\text{ is consistent}\iff\operatorname{rank}(A)=\operatorname{rank}([A\mid b]).\] When consistent, the solution is unique exactly when every variable column is a pivot column, that is, \(\operatorname{rank}(A)=n\). Otherwise there are \(n-\operatorname{rank}(A)\) free parameters. Over \(\mathbb R\), at least one free parameter gives infinitely many solutions; over a finite field the family is finite.

If \(x_p\) is one solution, every solution has the form \(x_p+z\) with \(Az=0\). This follows because \(A(x-x_p)=0\), and conversely \(A(x_p+z)=b\). The homogeneous solution set is a vector subspace; a nonhomogeneous solution set need not contain \(0\).

1.3.1 Worked example: a parameter changes consistency

For \(x+y=1\) and \(2x+2y=c\), the row operation \(R_2-2R_1\) gives \(0=c-2\). Thus there are no solutions if \(c\ne2\) and the family \((x,y)=(1-t,t)\) if \(c=2\). There is no value of \(c\) giving a unique solution.

1.4 Exercises

  1. Solve \(x+y=3\), \(2x-y=0\).
  2. Give the solution set of \(x+2y+3z=0\) as a span of two vectors.
  3. An \(m\times n\) real matrix has rank \(r<n\). Can a consistent system \(Ax=b\) have only one solution?
  4. Why is multiplying a row by zero not an elementary row operation?
  1. Add the equations: \(3x=3\), so \((x,y)=(1,2)\).
  2. Put \(y=s\), \(z=t\): \((x,y,z)=s(-2,1,0)+t(-3,0,1)\).
  3. No. There are \(n-r>0\) free parameters; the real solution set is infinite.
  4. It erases information and is not reversible. For example, replacing \(x=1\) by \(0=0\) changes the solution set.

Next: describe these solution sets as vector spaces.