One algorithm solves every linear system: row-reduce the augmented matrix to echelon form, find the pivots, and read off a unique solution, a family of solutions with free parameters, or a contradiction $0=c$.
In Section 1.1 we met linear systems, wrote them as augmented matrices and learned the three elementary row operations, which never change the solution set. With two equations in two unknowns we can usually see what to do. With five equations in five unknowns โ or the millions of equations a weather model or a bridge simulation solves every second โ we need a systematic method that always works, never goes round in circles, and tells us at the end exactly what kind of solution set we have.
That method is row reduction. We use row operations to push the augmented matrix into a staircase shape called echelon form; from there the solution can be read off by working upwards (Gaussian elimination with back-substitution), or we keep going to the fully simplified reduced echelon form, where the solution is visible at a glance (GaussโJordan elimination). Along the way the positions of the pivots answer the two big questions about any linear system: does a solution exist? and is it unique?
Row Echelon Form and Reduced Row Echelon Form
In a matrix, a nonzero row is a row with at least one nonzero entry, and its leading entry is the first nonzero entry from the left. The target shapes of row reduction are described in terms of leading entries.
๐ Definition 1.6 โ Row echelon form
A matrix is in row echelon form (REF) if
all zero rows (if any) are at the bottom;
the leading entry of each nonzero row lies in a column strictly to the right of the leading entry of the row above it;
all entries in a column below a leading entry are zero.
Condition 3 follows from 2, but it is worth saying out loud: the nonzero entries form a staircase that steps down and to the right.
๐ Definition 1.7 โ Reduced row echelon form
A matrix in row echelon form is in reduced row echelon form (RREF) if, in addition,
the leading entry of every nonzero row is $1$ (a leading 1);
each leading 1 is the only nonzero entry in its column.
For example, with $*$ standing for any number,
$$\underbrace{\begin{bmatrix}\blacksquare&*&*&*\\0&\blacksquare&*&*\\0&0&0&\blacksquare\end{bmatrix}}_{\text{REF}\ (\blacksquare\ne0)}\qquad\underbrace{\begin{bmatrix}1&0&*&0\\0&1&*&0\\0&0&0&1\end{bmatrix}}_{\text{RREF}}$$
๐ Definition 1.8 โ Pivot positions and pivot columns
A pivot position of a matrix $A$ is a position that holds a leading entry in an echelon form of $A$ (a leading 1 in its RREF). A column of $A$ that contains a pivot position is a pivot column, and the nonzero number used in a pivot position to create zeros is called a pivot.
A matrix can be row-reduced to many different echelon forms โ multiply a row by $2$ and you still have an echelon form. The reduced form, however, is completely determined by the matrix, and so are the pivot positions.
๐ Theorem 1.3 โ Uniqueness of the reduced row echelon form
Every matrix $A$ is row equivalent to one and only one matrix in reduced row echelon form, written $\operatorname{rref}(A)$. Consequently, the pivot positions of $A$ โ and therefore the number of pivots โ are the same in every echelon form of $A$, however the row operations were chosen.
We will not prove Theorem 1.3 here (it follows from the ideas of linear independence in Chapter 5), but we use it constantly: two people who row-reduce the same matrix by different routes must arrive at the same RREF. If they do not, somebody has made an arithmetic slip.
โ๏ธ Example 1 โ Recognising echelon forms
Decide whether each matrix is in REF, in RREF, or neither. For those in echelon form, name the pivot columns.
$$A=\begin{bmatrix}1&4&0&-2\\0&0&1&5\\0&0&0&0\end{bmatrix},\quad B=\begin{bmatrix}3&-1&2\\0&2&7\\0&0&-4\end{bmatrix},\quad C=\begin{bmatrix}1&0&2\\0&0&0\\0&1&3\end{bmatrix},\quad D=\begin{bmatrix}1&2&0\\0&1&0\\0&0&1\end{bmatrix}.$$
๐ก Show solutionโถ
$A$ The zero row is at the bottom; the leading entries (both $1$) step right from column 1 to column 3; each leading 1 is alone in its column. $A$ is in RREF, with pivot columns 1 and 3.
$B$ The leading entries $3,2,-4$ step down and to the right with zeros below them, so $B$ is in REF. It is not reduced: the leading entries are not $1$ and there are nonzero entries above them. Pivot columns 1, 2, 3.
$C$ A zero row sits above a nonzero row, breaking condition 1. $C$ is in neither form (swapping $R_2\leftrightarrow R_3$ would give an RREF).
$D$ $D$ is in REF with leading 1s, but column 2 contains a $2$ above the leading 1 of row 2, so it is REF but not RREF. One more operation, $R_1\to R_1-2R_2$, gives $I_3$.
Gaussian Elimination and Back-Substitution
Row reduction works one column at a time, from left to right, building the staircase as it goes.
๐งญ Problem-solving strategy โ row reduction
Forward phase (reach an echelon form).
Find the leftmost column that is not all zeros (among the rows not yet used). Its top position is the next pivot position.
If the entry there is $0$, interchange the row with a lower row that has a nonzero entry in that column.
Use replacements $R_i\to R_i-cR_{\text{pivot}}$ to create zeros in every position below the pivot.
Cover the pivot row and repeat steps 1โ3 on the rows below it, until no nonzero rows remain.
Backward phase (reach the reduced echelon form).
Starting with the rightmost pivot and working up and to the left, scale its row to make the pivot $1$, then use replacements to create zeros above it.
Gaussian elimination is the forward phase followed by back-substitution: write the echelon form as equations and solve them from the bottom equation upwards. GaussโJordan elimination carries out both phases, so that the RREF can be read off directly.
โ๏ธ Example 2 โ Gaussian elimination with back-substitution
Solve the system $$\begin{aligned}x+2y-z&=3\\2x+5y+z&=14\\-x+y+4z&=9.\end{aligned}$$
๐ก Show solutionโถ
Augment $$\left[\begin{array}{ccc|c}1&2&-1&3\\2&5&1&14\\-1&1&4&9\end{array}\right]$$ The first pivot is the $1$ in row 1, column 1.
Column 2 The next pivot is the $1$ in row 2, column 2: $$\xrightarrow{\ R_3\to R_3-3R_2\ }\left[\begin{array}{ccc|c}1&2&-1&3\\0&1&3&8\\0&0&-6&-12\end{array}\right]$$ This is a row echelon form, with pivots $1,1,-6$ in columns 1, 2, 3.
Back-substitute The echelon form says $$x+2y-z=3,\qquad y+3z=8,\qquad -6z=-12.$$ From the bottom: $z=2$; then $y=8-3(2)=2$; then $x=3-2(2)+2=1$. The unique solution is $(x,y,z)=(1,2,2)$.
โ๏ธ Example 3 โ GaussโJordan elimination with a row interchange
Use GaussโJordan elimination to solve $$\begin{aligned}y+2z&=7\\x+y+z&=6\\2x-y+3z&=12.\end{aligned}$$
๐ก Show solutionโถ
Swap The top-left entry is $0$, so it cannot be a pivot. Interchange rows 1 and 2: $$\left[\begin{array}{ccc|c}0&1&2&7\\1&1&1&6\\2&-1&3&12\end{array}\right]\xrightarrow{\ R_1\leftrightarrow R_2\ }\left[\begin{array}{ccc|c}1&1&1&6\\0&1&2&7\\2&-1&3&12\end{array}\right]$$
Backward Make the last pivot $1$ and clear above it, then clear above the second pivot: $$\xrightarrow{\ R_3\to\frac17R_3\ }\left[\begin{array}{ccc|c}1&1&1&6\\0&1&2&7\\0&0&1&3\end{array}\right]\xrightarrow{\ R_1\to R_1-R_3,\ \ R_2\to R_2-2R_3\ }\left[\begin{array}{ccc|c}1&1&0&3\\0&1&0&1\\0&0&1&3\end{array}\right]\xrightarrow{\ R_1\to R_1-R_2\ }\left[\begin{array}{ccc|c}1&0&0&2\\0&1&0&1\\0&0&1&3\end{array}\right]$$
Read off The RREF says $x=2$, $y=1$, $z=3$. Check: $1+6=7$ โ, $2+1+3=6$ โ, $4-1+9=12$ โ.
Interactive 1 โ Step-Through Row Reducer
Choose a system and press Next (or Play). Each step shows one row operation: the pivot is boxed, the row being changed is shaded blue and the row it borrows from is outlined in green. The forward phase builds the staircase (REF); the backward phase makes leading 1s with zeros above them (RREF). All arithmetic is exact.
stepโ
row operationโ
phaseโ
pivot columns foundโ
โ ๏ธ Common mistakes in row reduction
1. Changing the pivot row by accident. A replacement $R_i\to R_i-cR_j$ changes row $i$ only; row $j$ is copied unchanged. Two replacements may be done in one step only if they both borrow from a row that is not itself being changed (as in Example 2, where $R_2$ and $R_3$ both used $R_1$).
2. Forgetting the right-hand column. Every operation acts on the whole row of the augmented matrix, including the entry after the bar.
3. Working right-to-left in the forward phase. Creating zeros in a later column first and then returning to an earlier column can destroy the zeros you have made. Always finish one column before moving to the next.
4. Over-trusting decimals. Replacing $\tfrac13$ by $0.33$ creates rounding errors that grow. By hand, keep fractions โ or scale rows to clear them.
Leading Variables, Free Variables and Parametric Solutions
Once a system is in reduced echelon form, every variable is one of two kinds.
๐ Definition 1.9 โ Leading (basic) and free variables
For a linear system whose augmented matrix has been row-reduced, a variable whose column in the coefficient part is a pivot column is a leading variable (or basic variable). Every other variable is a free variable. In a consistent system the free variables may be given any values (parameters such as $s,t$), and each leading variable is then determined by them.
โ๏ธ Example 4 โ Infinitely many solutions
Solve $$\begin{aligned}x_1+2x_2\phantom{{}+x_3}-x_4&=4\\2x_1+4x_2+x_3+x_4&=6\\3x_1+6x_2+x_3\phantom{{}+x_4}&=10\end{aligned}$$ and write the solution in parametric vector form.
๐ก Show solutionโถ
Reduce $$\left[\begin{array}{cccc|c}1&2&0&-1&4\\2&4&1&1&6\\3&6&1&0&10\end{array}\right]\xrightarrow{\ R_2\to R_2-2R_1,\ \ R_3\to R_3-3R_1\ }\left[\begin{array}{cccc|c}1&2&0&-1&4\\0&0&1&3&-2\\0&0&1&3&-2\end{array}\right]\xrightarrow{\ R_3\to R_3-R_2\ }\left[\begin{array}{cccc|c}1&2&0&-1&4\\0&0&1&3&-2\\0&0&0&0&0\end{array}\right]$$ Column 2 has no pivot (its entries below row 1 are zero), so the second pivot is in column 3. This matrix is already in RREF.
Classify Pivot columns 1 and 3, so $x_1,x_3$ are leading variables and $x_2,x_4$ are free. The zero row says $0=0$ โ no information, and no contradiction.
Solve Put $x_2=s$, $x_4=t$. The two nonzero rows give $x_1=4-2s+t$ and $x_3=-2-3t$. So the solution set is $$\{(4-2s+t,\ s,\ -2-3t,\ t)\ :\ s,t\in\mathbb{R}\}.$$
Vector form $$\mathbf{x}=\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix}=\begin{bmatrix}4\\0\\-2\\0\end{bmatrix}+s\begin{bmatrix}-2\\1\\0\\0\end{bmatrix}+t\begin{bmatrix}1\\0\\-3\\1\end{bmatrix}.$$ Check with $s=t=0$: $(4,0,-2,0)$ gives $4=4$, $8-2=6$, $12-2=10$ โ.
โ๏ธ Example 5 โ Recognising an inconsistent system
Show that the system $x+y+z=2$, $\ x+2y-z=3$, $\ 2x+3y=7$ has no solution.
Read The last row means $0x+0y+0z=2$, i.e. $0=2$, which is impossible. The system is inconsistent; we can stop here โ there is no point in continuing to the RREF.
Why Adding the first two equations gives $2x+3y=5$, but the third equation demands $2x+3y=7$. Geometrically, the three planes have no common point.
Examples 2โ5 show every possible outcome, and the pivots tell us which one we are in.
๐ Theorem 1.4 โ Existence and uniqueness
Let $\left[\,A\mid\mathbf{b}\,\right]$ be the augmented matrix of a linear system.
Existence. The system is consistent if and only if the rightmost column of $\left[\,A\mid\mathbf{b}\,\right]$ is not a pivot column โ that is, if and only if an echelon form has no row of the form $\left[\,0\ \cdots\ 0\mid c\,\right]$ with $c\ne0$.
Uniqueness. If the system is consistent, then it has exactly one solution when there are no free variables (every column of $A$ is a pivot column), and infinitely many solutions when there is at least one free variable.
In particular โ as we first saw in Section 1.1 โ a linear system has either no solution, exactly one solution, or infinitely many solutions, never exactly two.
Echelon form showsโฆ
Free variables?
Solution set
Example
a row $\left[\,0\ \cdots\ 0\mid c\,\right]$, $c\ne0$
irrelevant
none (inconsistent)
5
no such row; every column of $A$ a pivot column
no
exactly one
2, 3
no such row; some column of $A$ has no pivot
yes
infinitely many
4
Existence and uniqueness at a glance (Theorem 1.4).
Interactive 2 โ A Free Variable Moves Along the Solution Line
Two equations in three unknowns describe two planes in $\mathbb{R}^3$. Their RREF has one free variable, so the solution set is a line. Slide the free parameter $t$: the orange point runs along the line, and both equations stay satisfied for every $t$. The dashed green line is the solution set of the matching homogeneous system โ it passes through the origin and is parallel to the solution line.
free parameter $t$โ
point $(x,y,z)$โ
equation 1: left sideโ
equation 2: left sideโ
Homogeneous Systems
๐ Definition 1.10 โ Homogeneous system
A linear system is homogeneous if every constant term is zero, i.e. it has the form $A\mathbf{x}=\mathbf{0}$. Every homogeneous system is consistent, because $\mathbf{x}=\mathbf{0}$ (all unknowns zero) is a solution, called the trivial solution. Any other solution is a nontrivial solution.
For a homogeneous system the only question is therefore whether there are nontrivial solutions โ and by Theorem 1.4 that happens exactly when there is a free variable. Since the right-hand column of zeros never changes under row operations, we often row-reduce just the coefficient matrix $A$.
๐ Theorem 1.5 โ More unknowns than equations
A homogeneous linear system with more unknowns than equations ($n\gt m$ for $m$ equations in $n$ unknowns) has infinitely many solutions; in particular it has a nontrivial solution.
Reason. Each pivot uses up a different row, so there are at most $m$ pivots. With $n\gt m$ columns, at least $n-m\ge1$ columns of $A$ have no pivot, so there is at least one free variable. The system is consistent (it has the trivial solution), so by Theorem 1.4 it has infinitely many solutions.
โ ๏ธ The hypothesis "homogeneous" matters
A non-homogeneous system with more unknowns than equations can still have no solution: $x+y+z=1$, $x+y+z=2$ has three unknowns, two equations and no solution at all. What Theorem 1.5 really uses is that a homogeneous system is always consistent. For any system, "more unknowns than equations" only guarantees: if there is a solution, there are infinitely many.
โ๏ธ Example 6 โ A homogeneous system
Find all solutions of $$\begin{aligned}x_1+x_2+x_3+4x_4&=0\\2x_1+x_2\phantom{{}+x_3}+3x_4&=0\\x_1\phantom{{}+x_2}+x_3+5x_4&=0.\end{aligned}$$
๐ก Show solutionโถ
Predict Three equations, four unknowns, homogeneous: Theorem 1.5 guarantees infinitely many solutions before we start.
Solve $x_4=t$ is free and $x_1=-2t$, $x_2=t$, $x_3=-3t$: $$\mathbf{x}=t\begin{bmatrix}-2\\1\\-3\\1\end{bmatrix},\quad t\in\mathbb{R}.$$ With $t=1$: $-2+1-3+4=0$ โ, $-4+1+3=0$ โ, $-2-3+5=0$ โ. All solutions lie on one line through the origin of $\mathbb{R}^4$.
Exercises
I
Echelon forms. In parts 1โ5 decide whether the matrix is in REF, RREF or neither, and give the pivot columns of those in echelon form. In parts 6โ8 find the RREF.
8 $R_1\leftrightarrow R_2$; $R_3\to R_3-2R_1$ gives $(0,2,4,2)$, equal to the new $R_2$; $R_3\to R_3-R_2$ gives a zero row; $R_2\to\tfrac12R_2$: $(0,1,2,1)$; $R_1\to R_1-R_2$: $$\begin{bmatrix}1&0&-1&2\\0&1&2&1\\0&0&0&0\end{bmatrix}.$$
II
Solve each system by Gaussian elimination with back-substitution or by GaussโJordan elimination. If there are infinitely many solutions, give them in parametric form; if there are none, say why.
4 $R_2\to R_2-2R_1$: $(0,0,3\mid-3)$, so $x_3=-1$; then $R_1\to R_1+R_2/3$ gives $x_1+2x_2=3$. $x_2=t$ is free: $(x_1,x_2,x_3)=(3-2t,\ t,\ -1)$, $t\in\mathbb{R}$ โ infinitely many.
5 $R_2\to R_2-2R_1$: $(0,1,-3\mid-1)$; $R_3\to R_3-3R_1$: $(0,1,-3\mid0)$; $R_3\to R_3-R_2$: $(0,0,0\mid1)$, i.e. $0=1$. Inconsistent โ no solution. (The first two equations add to $3x+4y+3z=8$, contradicting the third.)
7 RREF is $\left[\,I_4\mid\mathbf{b}'\,\right]$ with $\mathbf{b}'=(2,0,1,2)$. Unique solution $(x_1,x_2,x_3,x_4)=(2,0,1,2)$. Check the last equation: $2+0+1=3$ โ.
8 Equations 2 and 3 are $2\times$ and $-1\times$ equation 1, so the RREF is $\left[\begin{array}{cccc|c}1&2&-1&3&2\end{array}\right]$ followed by two zero rows. One leading variable and three free ones: $x_2=r$, $x_3=s$, $x_4=t$, $x_1=2-2r+s-3t$ โ infinitely many (a 3-dimensional family in $\mathbb{R}^4$).
III
Parameters and homogeneous systems.
1 For which values of $k$ does $x+2y=3$, $\ 2x+ky=6$ have (a) a unique solution, (b) infinitely many solutions, (c) no solution?
2 For which values of $k$ and $h$ does $x+y+z=1$, $\ x+2y+3z=2$, $\ x+3y+kz=h$ have a unique solution, infinitely many solutions, or none?
3 Find the condition on $b_1,b_2$ for $x+2y=b_1$, $\ 3x+6y=b_2$ to be consistent.
4 Solve the homogeneous system $x_1+2x_2-x_3=0$, $\ 2x_1+5x_2+x_3=0$.
5 For which $k$ does $x+y+z=0$, $\ x+2y+kz=0$, $\ 2x+3y+4z=0$ have a nontrivial solution? Find the solutions for that $k$.
6 Without row-reducing, explain why a homogeneous system of $3$ equations in $5$ unknowns has infinitely many solutions. What is the smallest possible number of free variables?
๐ก Show solutionsโถ
1 $R_2\to R_2-2R_1$: $\left[\begin{array}{cc|c}1&2&3\\0&k-4&0\end{array}\right]$. (a) $k\ne4$: two pivots, unique solution (namely $y=0$, $x=3$). (b) $k=4$: the second row is zero, $y$ is free โ infinitely many. (c) Never: the right-hand entry of row 2 is $0$, so a row $\left[\,0\ 0\mid c\ne0\,\right]$ cannot occur.
2 $R_2\to R_2-R_1$, $R_3\to R_3-R_1$, $R_3\to R_3-2R_2$ give $\left[\begin{array}{ccc|c}1&1&1&1\\0&1&2&1\\0&0&k-5&h-3\end{array}\right]$. Unique if $k\ne5$ (any $h$); infinitely many if $k=5$ and $h=3$; none if $k=5$ and $h\ne3$.
3 $R_2\to R_2-3R_1$ gives $\left[\,0\ 0\mid b_2-3b_1\,\right]$, so the system is consistent exactly when $b_2=3b_1$.
5 $R_2\to R_2-R_1$: $(0,1,k-1)$; $R_3\to R_3-2R_1$: $(0,1,2)$; $R_3\to R_3-R_2$: $(0,0,3-k)$. A free variable appears exactly when $k=3$. Then the RREF is $\begin{bmatrix}1&0&-1\\0&1&2\\0&0&0\end{bmatrix}$ and $\mathbf{x}=t\begin{bmatrix}1\\-2\\1\end{bmatrix}$. For $k\ne3$ only the trivial solution exists.
6 There are at most $3$ pivots (one per row) among $5$ columns, so at least $5-3=2$ free variables; a homogeneous system is always consistent, so by Theorem 1.4 there are infinitely many solutions. The smallest possible number of free variables is $2$ (when all three rows have pivots).
IV
Concepts and applications. In parts 1โ4 decide whether the statement is true or false and justify your answer.
1 Every matrix has exactly one row echelon form.
2 A linear system with more unknowns than equations always has infinitely many solutions.
3 If a consistent linear system has a free variable, then it has infinitely many solutions.
4 If the RREF of an augmented matrix contains a zero row, the system has infinitely many solutions.
5 The coefficient matrix $A$ of a system is $3\times5$ and has $3$ pivot positions. Is $A\mathbf{x}=\mathbf{b}$ consistent for every $\mathbf{b}$ in $\mathbb{R}^3$? How many free variables are there?
6Production planning. A bakery makes bread, cakes and biscuits in batches. A batch of bread uses $4$ kg flour, $1$ kg sugar and $1$ kg butter; a batch of cakes uses $2$, $2$ and $2$ kg; a batch of biscuits uses $3$, $2$ and $3$ kg. How many batches of each use up exactly $38$ kg flour, $19$ kg sugar and $23$ kg butter?
7Ticket sales. A theatre sold $500$ tickets at $10$ OMR (adult), $6$ OMR (student) and $4$ OMR (child), taking $3600$ OMR. Find all possible numbers of each ticket type, and the solution in which twice as many student tickets as child tickets were sold.
๐ก Show solutionsโถ
1False Scaling a row of an REF gives another REF, e.g. $\begin{bmatrix}1&2\\0&1\end{bmatrix}$ and $\begin{bmatrix}2&4\\0&1\end{bmatrix}$ are row equivalent and both in REF. Only the reduced form is unique (Theorem 1.3).
2False It may be inconsistent: $x+y+z=1$, $x+y+z=2$ has no solution. (It is true for homogeneous systems, Theorem 1.5.)
3True This is part 2 of Theorem 1.4: each value of the free variable gives a different solution.
4False $\left[\begin{array}{cc|c}1&0&2\\0&1&3\\0&0&0\end{array}\right]$ has a zero row but the unique solution $(2,3)$. What matters is whether there is a free variable, not whether there is a zero row.
5 Yes. Every one of the $3$ rows of $A$ has a pivot, so no echelon form of $\left[\,A\mid\mathbf{b}\,\right]$ can contain a row $\left[\,0\ \cdots\ 0\mid c\,\right]$ with $c\ne0$; the system is consistent for every $\mathbf{b}$. There are $5-3=2$ free variables, so every system $A\mathbf{x}=\mathbf{b}$ has infinitely many solutions.
6 With $b,c,k$ batches of bread, cakes, biscuits: $4b+2c+3k=38$, $b+2c+2k=19$, $b+2c+3k=23$. Subtracting the second equation from the third gives $k=4$; then $b+2c=11$ and $4b+2c=26$, so $3b=15$, $b=5$, $c=3$. Answer: $5$ batches of bread, $3$ of cakes, $4$ of biscuits (check flour: $20+6+12=38$ kg โ).
7 $a+s+c=500$, $10a+6s+4c=3600$. $R_2\to R_2-4R_1$: $6a+2s=1600$, so $s=800-3a$ and $c=500-a-s=2a-300$, with $a$ free. Numbers of tickets must be whole and $\ge0$: $s\ge0$ gives $a\le266$, $c\ge0$ gives $a\ge150$. So $(a,s,c)=(a,\ 800-3a,\ 2a-300)$ for each whole number $150\le a\le266$. If $s=2c$: $800-3a=4a-600$, so $a=200$, giving $200$ adult, $200$ student and $100$ child tickets (check: $2000+1200+400=3600$ OMR โ).
๐ฌ ResearchโTeaching NexusResearch-tutored ยท optional, about 30 minutes
Research question. How does the work needed to solve a linear system grow with its size, and why does that matter for weather forecasting, structural engineering and machine learning?
Why it matters. A national weather service or a finite-element model of a bridge solves systems with millions of unknowns. Whether such a computation takes a second or a year depends on how the number of arithmetic operations in elimination grows with the number $n$ of equations.
What to do.
For an $n\times n$ system with a unique solution, count the operations (each multiplication, division, addition or subtraction counts as one) in the forward phase of Gaussian elimination when no row swaps are needed. Do it by hand for $n=2$ and $n=3$.
Show that clearing below pivot $k$ needs $n-k$ multipliers and $2(n-k)(n-k+1)$ further operations, and add these up for $k=1,\dots,n-1$. Show that back-substitution needs exactly $n^2$ operations.
Use $\sum j^2=\tfrac{m(m+1)(2m+1)}{6}$ to show the forward phase costs about $\tfrac23n^3$ operations for large $n$.
In Python (numpy.linalg.solve), MATLAB or Octave, time the solution of random $n\times n$ systems for $n=500,1000,2000$. Does doubling $n$ multiply the time by about $8$?
Tools: pen and paper; a spreadsheet; Python, MATLAB or Octave
Hand in: A one-page note with your operation counts, a table of timings, and a sentence explaining why engineers try hard to exploit zeros ("sparsity") in very large systems.
Going further. Real software swaps rows to use the largest available pivot ("partial pivoting"). Try solving $0.0001x+y=1$, $x+y=2$ with 3-significant-figure arithmetic, with and without swapping rows first, and explain the difference.
Instructor note: the forward phase costs $\sum_{j=1}^{n-1}j(2j+3)=\tfrac{(n-1)n(2n-1)}{3}+\tfrac{3n(n-1)}{2}$ operations ($5$ for $n=2$, $19$ for $n=3$, $46$ for $n=4$), plus $n^2$ for back-substitution โ about $\tfrac23n^3$ in total for large $n$. Timings will not scale perfectly (memory and parallel hardware intervene), but the factor of roughly $8$ per doubling should be visible.
๐งช Self-check quiz
0/5 correct
Q1. Which matrix is in reduced row echelon form?
Q2. An echelon form of an augmented matrix has last row $\left[\,0\ \ 0\ \ 0\mid 5\,\right]$. The system
Q3. A consistent system has $3$ equations, $5$ unknowns and $3$ pivots. How many free variables does it have?
Q4. A homogeneous system has $4$ equations in $6$ unknowns. Then it
Q5. The solutions of a system are $x_1=4-2s+t$, $x_2=s$, $x_3=-2-3t$, $x_4=t$. The free variables are