Games · Linear Algebra
Someone shuffled the equations, and now Gauss–Seidel blows up. Swap rows to put a dominant entry on every diagonal, and watch the residual turn from a climb into a dive. Use as few swaps as you can. And watch out: some systems can't be fixed this way at all.
The system A x = b · tap a row, then another, to swap themLevel 1
—
A row is strictly diagonally dominant when its diagonal entry beats every other entry in the row combined:
|aii| > Σj≠i |aij|
If every row passes, Gauss–Seidel is guaranteed to converge from any starting guess. Swapping two equations (with their right-hand sides) doesn't change the solution. It only changes which entry lands on the diagonal.
green = dominant · red = not · dashed = zero pivot (can't even divide)
Gauss–Seidel solves equation i for unknown i: x_i = (b_i − Σ a_ij x_j) / a_ii, using the newest values as soon as it has them. If a_ii is big compared with the rest of its row, each update only nudges x_i by a fraction of the other unknowns' errors, so errors shrink sweep after sweep. If a_ii is small, the division amplifies those errors, and the residual climbs off the top of the chart. If it's zero, the method can't take a single step.
Dominance is a sufficient condition, not a necessary one: some non-dominant systems still converge. It's the one you can check by eye, and it's the one that comes with a guarantee. Finite-difference heat-conduction grids are dominant by construction, which is why relaxation works so reliably in the 2D conduction lab.
Each row has exactly one column where it could be dominant, so there's only one winning arrangement. The scramble breaks into cycles: row A sits where B belongs, B sits where C belongs, and so on back to A. A cycle of length k takes exactly k − 1 swaps to undo, so the minimum is n minus the number of cycles. For three stars, fix each swap so it sends at least one row home for good.
If two rows both need the same column, no reshuffle can make every row dominant. That's not a dead end in real life. You stop relying on the guarantee and reach for a direct solver (Gaussian elimination with partial pivoting), or for a method that doesn't need dominance. You can watch convergence and divergence sweep by sweep in the Gauss–Seidel & Jacobi lab.
EngineeringCandy · Games · swap the rows, earn the stars, learn why the diagonal decides