How do two airlines split a route so that the seats, the fuel, and the budget all balance? How does a computer rotate a 3D model, or a search engine rank a billion pages? Behind each of these questions sits a system of linear equations and the matrices that organize it. In this chapter you will learn to solve any such system by a reliable, mechanical procedure, to describe every possible solution set, and to use matrix arithmetic, inverses, determinants, and the LU factorization the way working scientists and engineers do.
1. Linear systems and their geometry
A linear equation in the unknowns \(x_1, \dots, x_n\) has the form \(a_1x_1 + a_2x_2 + \cdots + a_nx_n = b\), where the coefficients \(a_i\) and the constant \(b\) are real numbers. A linear system is a list of such equations that must all hold at once. A solution is a list of values that makes every equation true.
With two unknowns, each equation is a line in the plane, and a solution is a point lying on every line. Consider \(x + y = 5\) and \(x - y = 1\). Adding the equations gives \(2x = 6\), so \(x = 3\) and \(y = 2\): the two lines cross at exactly one point.
Two lines can also be parallel, as with \(y = x + 1\) and \(y = x - 1\), and then no point lies on both. Or the two equations can describe the same line, and then every point of the line is a solution.
Every linear system has exactly one solution, no solution (it is inconsistent), or infinitely many solutions. There is never a system with exactly two or exactly five solutions.
2. Matrices and the augmented matrix
A matrix is a rectangular array of numbers. An \(m \times n\) matrix has \(m\) rows and \(n\) columns, and \(a_{ij}\) is the entry in row \(i\), column \(j\). To solve a system, strip away the letters and keep the numbers. The system \(x + 2y = 3,\ 2x + 5y = 7\) becomes the augmented matrix
\[ \left(\begin{array}{cc|c} 1 & 2 & 3 \\ 2 & 5 & 7 \end{array}\right). \]
Three elementary row operations never change the solution set: swap two rows (\(R_i \leftrightarrow R_j\)), scale a row by a nonzero number (\(R_i \leftarrow cR_i\)), and replace a row by itself plus a multiple of another row (\(R_i \leftarrow R_i + cR_j\)).
Scaling a row by \(0\) erases an equation and can change the solution set. Scaling must always use a nonzero number.
3. Gaussian elimination and row echelon form
A matrix is in row echelon form when (1) all rows of zeros are at the bottom, and (2) the first nonzero entry of each row, its pivot, lies strictly to the right of the pivot in the row above. It is in reduced row echelon form (RREF) when, in addition, every pivot equals \(1\) and is the only nonzero entry in its column.
- Find the leftmost column that is not all zeros and put a nonzero entry at the top by swapping rows.
- Use row replacements to create zeros below that pivot.
- Ignore that row and column, and repeat on the remaining rows until the matrix is in REF.
- Back-substitute from the bottom up (or continue to RREF, clearing entries above each pivot).
Solve \(x + y + z = 6,\ 2x - y + z = 3,\ x + 2y - z = 2\).
Start with \(\left(\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & -1 & 1 & 3 \\ 1 & 2 & -1 & 2 \end{array}\right)\). Apply \(R_2 \leftarrow R_2 - 2R_1\) and \(R_3 \leftarrow R_3 - R_1\) to get rows \((0, -3, -1 \mid -9)\) and \((0, 1, -2 \mid -4)\). Swap \(R_2 \leftrightarrow R_3\), then \(R_3 \leftarrow R_3 + 3R_2\) gives \((0, 0, -7 \mid -21)\).
So \(z = 3\). The second row says \(y - 2z = -4\), so \(y = 2\). The first row says \(x + y + z = 6\), so \(x = 1\). The solution is \((x, y, z) = (1, 2, 3)\).
4. Solution sets and free variables
Look at the pivots in the REF of the augmented matrix. A column of the coefficient part that contains a pivot belongs to a basic variable; a column without a pivot belongs to a free variable, which can take any value.
If a row of the form \((0\ 0\ \cdots\ 0 \mid c)\) with \(c \neq 0\) appears, the system is inconsistent. Otherwise, if every variable is basic, the solution is unique. Otherwise the system has infinitely many solutions, described with one parameter for each free variable.
Solve \(x + 2y - z = 4,\ 2x + 4y + z = 11\).
The augmented matrix is \(\left(\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 2 & 4 & 1 & 11 \end{array}\right)\). Then \(R_2 \leftarrow R_2 - 2R_1\) gives \((0, 0, 3 \mid 3)\), so \(z = 1\). The pivots are in columns 1 and 3, so \(y\) is free: set \(y = t\). The first equation gives \(x = 4 - 2t + z = 5 - 2t\). The solution set is \((x, y, z) = (5 - 2t,\ t,\ 1)\) for every real \(t\), a line in space.
On my home planet we count before we solve: if the system has \(n\) unknowns and the REF has \(r\) pivots in the coefficient part, then a consistent system has exactly \(n - r\) free variables. Zero free variables means a unique solution!
5. Matrix operations
Matrices of the same size are added entry by entry, and a scalar multiplies every entry. The product \(AB\) is defined only when the number of columns of \(A\) equals the number of rows of \(B\). If \(A\) is \(m \times p\) and \(B\) is \(p \times n\), then \(AB\) is \(m \times n\) and its entry in row \(i\), column \(j\) is the sum of products of row \(i\) of \(A\) with column \(j\) of \(B\):
\[ (AB)_{ij} = \sum_{k=1}^{p} a_{ik}\,b_{kj}. \]
The transpose \(A^T\) swaps rows and columns. The identity matrix \(I\) has ones on the diagonal and zeros elsewhere, and \(AI = IA = A\).
Let \(A = \begin{pmatrix} 1 & 2 \\ 0 & -1 \\ 3 & 1 \end{pmatrix}\) (a \(3 \times 2\) matrix) and \(B = \begin{pmatrix} 2 & 0 & 1 \\ 1 & 4 & -2 \end{pmatrix}\) (a \(2 \times 3\) matrix).
\(AB\) is \(3 \times 3\). Its first row is \((1\cdot 2 + 2\cdot 1,\ 1\cdot 0 + 2\cdot 4,\ 1\cdot 1 + 2\cdot(-2)) = (4, 8, -3)\). Completing the other rows gives \(AB = \begin{pmatrix} 4 & 8 & -3 \\ -1 & -4 & 2 \\ 7 & 4 & 1 \end{pmatrix}\). But \(BA\) is \(2 \times 2\): \(BA = \begin{pmatrix} 5 & 5 \\ -5 & -4 \end{pmatrix}\). The two products do not even have the same size.
Matrix multiplication is not commutative: usually \(AB \neq BA\). It is associative, \((AB)C = A(BC)\), and \((AB)^T = B^TA^T\) (the order reverses).
6. The inverse of a matrix
A square matrix \(A\) is invertible if there is a matrix \(A^{-1}\) with \(AA^{-1} = A^{-1}A = I\). A matrix with no inverse is singular.
If \(A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\) and \(ad - bc \neq 0\), then \[ A^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}. \]
For larger matrices, row reduce the block matrix \([A \mid I]\). If \(A\) is invertible, the left block turns into \(I\) and the right block becomes \(A^{-1}\). If \(A\) is invertible, the system \(A\mathbf{x} = \mathbf{b}\) has the unique solution \(\mathbf{x} = A^{-1}\mathbf{b}\). Also \((AB)^{-1} = B^{-1}A^{-1}\).
Let \(A = \begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix}\). Then \(ad - bc = 6 - 5 = 1\), so \(A^{-1} = \begin{pmatrix} 3 & -1 \\ -5 & 2 \end{pmatrix}\). To solve \(2x + y = 4,\ 5x + 3y = 11\), compute \(\mathbf{x} = A^{-1}\begin{pmatrix} 4 \\ 11 \end{pmatrix} = \begin{pmatrix} 12 - 11 \\ -20 + 22 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\). So \(x = 1\) and \(y = 2\).
7. Determinants
The determinant of a square matrix is a single number that tells you whether the matrix is invertible. For \(2 \times 2\) matrices, \(\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\). For larger matrices, use cofactor expansion along any row or column: multiply each entry by its signed minor (the determinant left after deleting its row and column, with signs in a checkerboard pattern \(+ - +\) \(\dots\)) and add.
\(A\) is invertible exactly when \(\det A \neq 0\). Also \(\det(AB) = \det A \cdot \det B\), \(\det A^T = \det A\), \(\det A^{-1} = 1/\det A\), swapping two rows flips the sign, adding a multiple of one row to another changes nothing, and for an \(n \times n\) matrix \(\det(cA) = c^n \det A\). The determinant of a triangular matrix is the product of its diagonal entries.
Geometrically, \(|\det A|\) is the area (in 2D) or volume (in 3D) of the shape spanned by the columns of \(A\). The vectors \((3, 1)\) and \((1, 2)\) above span a parallelogram of area \(|3\cdot 2 - 1\cdot 1| = 5\).
Expand \(\det\begin{pmatrix} 2 & 0 & 1 \\ 1 & 3 & 2 \\ 0 & -1 & 4 \end{pmatrix}\) along the first row. The terms are \(2\,(3\cdot 4 - 2\cdot(-1)) = 2\cdot 14 = 28\), then \(0\), then \(+1\,(1\cdot(-1) - 3\cdot 0) = -1\). The determinant is \(28 - 1 = 27\), so the matrix is invertible.
8. LU factorization
Gaussian elimination can be recorded as a product. If a square matrix \(A\) can be reduced to an upper triangular matrix \(U\) using only row replacements (no swaps), then \(A = LU\), where \(L\) is lower triangular with ones on the diagonal. The entry of \(L\) in position \((i, j)\) is the multiplier \(m\) used in the operation \(R_i \leftarrow R_i - m R_j\). To solve \(A\mathbf{x} = \mathbf{b}\), first solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution, then \(U\mathbf{x} = \mathbf{y}\) by back substitution. Once \(L\) and \(U\) are known, each new right-hand side \(\mathbf{b}\) is cheap to handle. When row swaps are needed, a permutation matrix \(P\) is added: \(PA = LU\).
Take \(A = \begin{pmatrix} 1 & 2 & 1 \\ 3 & 8 & 5 \\ 2 & 10 & 9 \end{pmatrix}\). The operations \(R_2 \leftarrow R_2 - 3R_1\), \(R_3 \leftarrow R_3 - 2R_1\), \(R_3 \leftarrow R_3 - 3R_2\) give \(U = \begin{pmatrix} 1 & 2 & 1 \\ 0 & 2 & 2 \\ 0 & 0 & 1 \end{pmatrix}\) and the multipliers fill \(L = \begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 3 & 1 \end{pmatrix}\).
For \(\mathbf{b} = (4, 16, 21)\): forward substitution in \(L\mathbf{y} = \mathbf{b}\) gives \(y_1 = 4\), \(y_2 = 16 - 12 = 4\), \(y_3 = 21 - 8 - 12 = 1\). Back substitution in \(U\mathbf{x} = \mathbf{y}\) gives \(x_3 = 1\), \(x_2 = (4 - 2)/2 = 1\), \(x_1 = 4 - 2 - 1 = 1\). So \(\mathbf{x} = (1, 1, 1)\).
Key takeaways
- A linear system has no solution, exactly one solution, or infinitely many solutions.
- Elementary row operations (swap, scale by a nonzero number, add a multiple of a row) keep the solution set unchanged.
- Gaussian elimination reaches row echelon form; pivots mark basic variables and pivot-free columns give free variables.
- A row \((0\ \cdots\ 0 \mid c)\) with \(c \neq 0\) means the system is inconsistent.
- \(AB\) needs columns of \(A\) = rows of \(B\); in general \(AB \neq BA\), and \((AB)^T = B^TA^T\).
- \(A^{-1}\) exists exactly when \(\det A \neq 0\); \((AB)^{-1} = B^{-1}A^{-1}\); \(\mathbf{x} = A^{-1}\mathbf{b}\).
- \(A = LU\): the multipliers of elimination fill \(L\), and solving takes two easy triangular steps.
Test yourself: quick challenge for College
Speed drill for College: how many in 60 seconds?
🚀 Keep exploring with Zyro
✏️ Math practiceLinear Systems and Matrices: math practice, College
📝 Math testsLinear Systems and Matrices: math test, College
🎯 Math quizzesLinear Systems and Matrices: math quiz, College
✏️ Math practiceVector Spaces and Linear Transformations: math practice, College
✏️ Math practiceEigenvalues and Orthogonality: math practice, College
📝 Math testsVector Spaces and Linear Transformations: math test, College