Chapter 4 Exercises — Gaussian Elimination and Row Reduction

How to use these. The ⭐ problems lock in the concepts — what the operations are and why they work — and need no real computation. The ⭐⭐ problems are by-hand row reductions and back-substitutions: get out a pencil and show every row operation, the way the chapter does. The ⭐⭐⭐ problems split into proofs (math track) and coding (build on your toolkit/linear_systems.py). The ⭐⭐⭐⭐ problems apply the algorithm to real systems. Tags: [hand] = pencil only, [code] = needs numpy / your toolkit, [proof] = rigorous argument, [essay] = written explanation. For every hand computation, you can confirm your answer with np.linalg.solve — do it; that is the habit this book is built on.

Tier ⭐ — Conceptual (what is / why)

4.1 [hand] State the three elementary row operations. For each, give the one-sentence reason it does not change the solution set of the system.

4.2 [hand] Why is scaling a row by $0$ forbidden, while scaling by $-3$ or $\tfrac12$ is fine? Frame your answer in terms of reversibility.

4.3 [hand] Define, in your own words, the difference between row echelon form (REF) and reduced row echelon form (RREF). List the two extra conditions RREF demands beyond REF.

4.4 [hand] What is a pivot? What is a free variable? State the relationship between the number of free variables and the shape (dimension) of the solution set.

4.5 [hand] After reducing $[A \mid \mathbf{b}]$ to echelon form, you see a row reading $0\ 0\ 0 \mid 5$. What does this tell you about the system, and why? What if the row had instead read $0\ 0\ 0 \mid 0$?

4.6 [hand] The chapter says "REF is not unique, but RREF is." Explain what this means and why it matters (what does the uniqueness of RREF buy us later?).

4.7 [hand] In one or two sentences each, give the rank condition (in terms of $\operatorname{rank}(A)$, $\operatorname{rank}([A\mid\mathbf{b}])$, and the number of variables $n$) for each of: a unique solution, infinitely many solutions, and no solution.

4.8 [hand] The chapter warns against solving $A\mathbf{x}=\mathbf{b}$ by computing $A^{-1}\mathbf{b}$. Give the two reasons (efficiency and stability) the professional rule "never invert; eliminate" is preferred.

4.9 [hand] Why does forward elimination on an $n\times n$ system cost roughly $\tfrac23 n^3$ operations while back-substitution costs only about $n^2$? (You don't need an exact count — explain the nested-loop intuition.)

Tier ⭐⭐ — Computation by hand (row reduce; back-substitute)

4.10 [hand] Solve by forward elimination and back-substitution, showing every row operation: $$\begin{aligned} 3x + \phantom{1}y &= 9,\\ \phantom{1}x + 2y &= 8. \end{aligned}$$ (Answer to check: $(x,y)=(2,3)$.)

4.11 [hand] Solve the $3\times 3$ system, showing each operation and naming each pivot: $$\begin{aligned} \phantom{1}x + \phantom{1}y + \phantom{1}z &= 6,\\ \phantom{1}x + 2y + 3z &= 14,\\ \phantom{1}x + 4y + 9z &= 36. \end{aligned}$$ (Answer to check: $(1,2,3)$.)

4.12 [hand] The system below has a $0$ in the top-left position. Perform the necessary swap, then eliminate, then back-substitute. Show the swap explicitly. $$\left[\begin{array}{ccc|c} 0 & 2 & 1 & 7 \\ 1 & 1 & 1 & 6 \\ 2 & 1 & 3 & 13 \end{array}\right].$$ (Answer to check: $(1,2,3)$.)

4.13 [hand] Take the system in 4.11 all the way to RREF (Gauss–Jordan): scale each pivot to $1$ and clear above as well as below. Confirm the left block becomes the identity and the answer appears in the last column.

4.14 [hand] Use back-substitution only (the matrix is already upper-triangular) to solve: $$\left[\begin{array}{ccc|c} 2 & -1 & 3 & 13 \\ 0 & 1 & -2 & -3 \\ 0 & 0 & 4 & 8 \end{array}\right].$$ (Answer to check: $(4,1,2)$.)

4.15 [hand] Reduce to echelon form and classify (unique / infinite / none). If infinite, write the solution in parametric form. $$\begin{aligned} \phantom{1}x + 2y &= 3,\\ 2x + 4y &= 7. \end{aligned}$$

4.16 [hand] Same instructions as 4.15, for: $$\begin{aligned} \phantom{1}x + 2y &= 3,\\ 2x + 4y &= 6. \end{aligned}$$ (You should find infinitely many solutions; express them as a point plus $t$ times a direction.)

4.17 [hand] Reduce to RREF and find the complete solution set (it has a free variable): $$\begin{aligned} \phantom{1}x + \phantom{1}y + \phantom{1}z &= 2,\\ \phantom{1}x + 0y + \phantom{1}z &= 1. \end{aligned}$$ (Hint: which variable ends up free? Write the parametric form.)

4.18 [hand] Show that the following system is inconsistent by reducing it until the contradiction row appears. Identify the impossible row. $$\begin{aligned} \phantom{1}x + 2y - \phantom{1}z &= 1,\\ 2x + 3y + \phantom{1}z &= 4,\\ 3x + 5y + 0z &= 7. \end{aligned}$$

4.19 [hand] For the matrix below, find its RREF and read off its rank (number of pivots) and which columns are pivot columns. $$A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 1 & 1 & 1 \end{bmatrix}.$$

Tier ⭐⭐⭐ — Proofs (A track) and coding (C track)

4.20 [proof] Prove that swapping two rows of an augmented matrix does not change the solution set of the corresponding system. (Use the idea that the swap is its own inverse.)

4.21 [proof] Prove that the elementary operation $R_i \leftarrow R_i + cR_j$ (with $i \neq j$) preserves the solution set, by showing every solution of the old system solves the new one and vice versa (the inverse operation recovers the original). This is the "add a multiple" case sketched in the Math-Major Sidebar — fill in the details.

4.22 [proof] Show that the elementary matrix for "$R_2 \leftarrow R_2 + cR_1$" (on a 2-row matrix) is $\begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix}$ and that its determinant is $1$ regardless of $c$. Explain in one sentence why this connects to "row operations of this type preserve area / are reversible." (You may use the $2\times2$ determinant formula $ad-bc$ from Chapter 1.)

4.23 [proof] Suppose a system $A\mathbf{x}=\mathbf{b}$ has two distinct solutions $\mathbf{x}_1 \neq \mathbf{x}_2$. Prove it has infinitely many. (Hint: show $\mathbf{x}_1 + t(\mathbf{x}_2 - \mathbf{x}_1)$ is a solution for every scalar $t$; this is why a linear system can never have exactly $2$, or $7$, or any finite number $>1$ of solutions.)

4.24 [code] Implement back_substitute(U, b) from scratch in pure Python (no numpy), as specified in the chapter's Build Your Toolkit callout. Test it against scipy.linalg.solve_triangular on at least three upper-triangular systems, including the one in 4.14.

4.25 [code] Implement gaussian_elimination(A, b) from scratch with partial pivoting. Verify it against np.linalg.solve on (a) the system in 4.11, (b) the swap system in 4.12, and (c) 50 random $4\times 4$ systems using np.allclose. Confirm it raises a clear error on a singular matrix such as $\begin{bmatrix} 1 & 2 \\ 2 & 4\end{bmatrix}$.

4.26 [code] Implement row_reduce(A) to RREF from scratch, returning the reduced matrix and the list of pivot columns. Run it on the augmented matrices of 4.16 (infinite), 4.18 (inconsistent), and 4.11 (unique), and verify the pivot columns and zero/contradiction rows match what you found by hand. Cross-check against sympy.Matrix(...).rref().

4.27 [code] Write a function classify(A, b) that calls your row_reduce on the augmented matrix and returns one of "unique", "infinite", or "inconsistent", using only the pivot structure (compare pivots in the coefficient block vs. the augmented column, and count free variables). Test it on all three case types from the chapter.

4.28 [code] Operation counting. Modify your gaussian_elimination to count the number of multiply/divide operations it performs, and run it on random $n\times n$ systems for $n = 5, 10, 20, 40$. Plot the count against $n$ (or just tabulate it) and confirm it grows roughly like $n^3$ (e.g., doubling $n$ multiplies the count by about $8$).

Tier ⭐⭐⭐⭐ — Application

4.29 [hand/code] Balance a chemical equation. The combustion of ethane is $\;a\,\mathrm{C_2H_6} + b\,\mathrm{O_2} \to c\,\mathrm{CO_2} + d\,\mathrm{H_2O}$. Conservation of carbon, hydrogen, and oxygen gives three equations in the four unknowns $a,b,c,d$. (i) Write the homogeneous linear system. (ii) Row-reduce it; you should find one free variable. (iii) Choose the free variable to make all coefficients the smallest positive integers, and state the balanced equation. (Check with numpy that your $(a,b,c,d)$ lies in the null space.)

4.30 [hand] Traffic flow. At four one-way intersections forming a loop, conservation "flow in = flow out" at each node gives the system $$x_1 - x_2 = -20,\quad x_2 - x_3 = 20,\quad x_3 - x_4 = -20,\quad x_4 - x_1 = 20.$$ Row-reduce and show the system is consistent with one free variable. Write the general solution in terms of the free flow, and explain physically why one degree of freedom remains (think about the loop). If all flows must be nonnegative, what is the smallest the free variable can be?

4.31 [code] Input–output economics. For the consumption matrix $A = \begin{bmatrix} 0.2 & 0.3 \\ 0.4 & 0.1\end{bmatrix}$, solve the Leontief system $(I - A)\mathbf{x} = \mathbf{d}$ for three different demand vectors $\mathbf{d} = (20,10)$, $(0,30)$, and $(50,50)$, using np.linalg.solve. Verify each answer satisfies $\mathbf{x} - A\mathbf{x} = \mathbf{d}$. Then explain, in two sentences, why doing the elimination once (an LU factorization, Chapter 10) and reusing it for all three demands would be more efficient.

4.32 [essay] Why elimination, not guessing? In 150–250 words, explain to a skeptical classmate why Gaussian elimination is guaranteed to find every solution of any linear system, whereas "staring at the equations and trying values" is not. Touch on: reversibility of row operations, the finiteness of the algorithm, and how the echelon form makes the unique/infinite/inconsistent verdict unambiguous.

4.33 [essay] The cubic wall. A weather model must solve a linear system with about $10^6$ unknowns every few minutes. In 150–250 words, explain why the $O(n^3)$ cost of elimination makes this a serious computation, why the modeler would not compute an inverse, and what "factor once, reuse for many right-hand sides" (LU) saves when the same physics is solved at each of thousands of time steps. Connect to the chapter's discussion of efficiency.