Published by Dimitris Kougioumtzis · Updated
Swap in the largest remaining absolute column pivot, eliminate below it, and distinguish unique, underdetermined and inconsistent systems.
Choose the largest available absolute column pivot, swap its row into place, and subtract suitable row multiples below it. Skip unusable pivot columns, detect contradictory zero rows, and back-substitute only when a unique solution exists.
When to use Gaussian elimination with partial pivoting
Solving a small square linear system while showing row pivoting, elimination and numerical rank classification.
Choosing an alternative
Unpivoted elimination can divide by a zero or poorly scaled pivot. Partial pivoting controls elimination multipliers but does not remove ill-conditioning or turn a numerical rank test into an exact algebraic proof.
Worked example: input and state changes
Example input
0,2,4;1,1,3
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Input preserved; working augmented matrix uses absolute pivot tolerance 1e-10.
State at this checkpoint
{ "values": [ 0, 2, 4, 1, 1, 3 ], "active": [], "kind": "matrix", "columns": 3, "columnLabels": [ "x0", "x1", "rhs" ], "rowLabels": [ "r0", "r1" ], "result": 0, "output": [ 0, 0, 0 ] }Step 2: Eliminate row 1 using multiplier 0.
State at this checkpoint
{ "values": [ 1, 1, 3, 0, 2, 4 ], "active": [ 3, 4, 5 ], "kind": "matrix", "columns": 3, "columnLabels": [ "x0", "x1", "rhs" ], "rowLabels": [ "r0", "r1" ], "result": 0, "output": [ 0, 0, 0 ] }Step 3: Select largest absolute pivot in column 1; swap row 1 into 1.
State at this checkpoint
{ "values": [ 1, 1, 3, 0, 2, 4 ], "active": [ 4 ], "kind": "matrix", "columns": 3, "columnLabels": [ "x0", "x1", "rhs" ], "rowLabels": [ "r0", "r1" ], "result": 0, "output": [ 1, 0, 0 ] }Step 5: Back-substitute x0 = 1.
State at this checkpoint
{ "values": [ 1, 1, 3, 0, 2, 4 ], "active": [ 0 ], "kind": "matrix", "columns": 3, "columnLabels": [ "x0", "x1", "rhs" ], "rowLabels": [ "r0", "r1" ], "result": 1, "output": [ 2, 1, 2 ] }Step 6: Unique solution: 1, 2.
State at this checkpoint
{ "values": [ 1, 1, 3, 0, 2, 4 ], "active": [], "kind": "matrix", "columns": 3, "columnLabels": [ "x0", "x1", "rhs" ], "rowLabels": [ "r0", "r1" ], "result": 1, "output": [ 2, 1, 2 ] }
Expected final state
Unique solution: 1, 2.
Complexity and input bounds
Family: Numerical. Time complexity: O(n^3).
Implementation detail: One through four equations with n+1 finite augmented entries per row, absolute values at most 99. Absolute pivot and right-hand-side threshold 1e-10. Downloads output [numericalRank,x0,...] and return 1 unique, 0 consistent rank deficiency, -2 inconsistent, or -1 invalid n without writes. Singular cases leave solution slots zero. Independent minor ranks and Cramer determinants check ordinary systems; explicit near-threshold fixtures check the documented numerical convention.
Space complexity: O(n^2) working augmented matrix and O(n) solution output, excluding frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Square augmented matrix: 1..4 rows separated by ;, n+1 comma-separated values per row. Finite entries -99..99. Absolute pivot tolerance 1e-10; source preserves input.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Preserve the input matrix when working in scratch space. Update the right-hand side along with coefficients. Distinguish consistent rank deficiency from an inconsistent row, and never report zero solution slots as a unique answer in those cases.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 | // Square Gaussian elimination with partial row pivoting. n 1..4, row-major augmented matrix n*(n+1) finite doubles with absolute entries <=99. Input unchanged. Output capacity n+1 doubles: [numericalRank,x0,...,x(n-1)]. Return 1 unique solution, 0 rank-deficient consistent system (solution slots zero), -2 inconsistent system (solution slots zero), -1 invalid n without output writes. Absolute pivot/RHS threshold 1e-10; near-singular classifications are numerical, not exact algebraic guarantees. First largest-magnitude pivot wins ties. O(n^3) time and O(n^2) working matrix. Compare floating solutions with explicit tolerances. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(augmented, n, output) { if (n < 1 || n > 4) { return -1; } let work = Array(256).fill(0); let rank = 0; let pivot = 0; let swapValue = 0.0; let factor = 0.0; let value = 0.0; for (let i = 0; i < n*(n+1); i++) { work[i] = augmented[i]; } for (let i = 0; i <= n; i++) { output[i] = 0.0; } for (let column = 0; column < n && rank < n; column++) { pivot = rank; for (let row = rank+1; row < n; row++) { if (Math.abs(work[row*(n+1)+column]) > Math.abs(work[pivot*(n+1)+column])) { pivot = row; } } if (Math.abs(work[pivot*(n+1)+column]) <= 1e-10) { continue; } for (let j = 0; j <= n; j++) { swapValue = work[rank*(n+1)+j]; work[rank*(n+1)+j] = work[pivot*(n+1)+j]; work[pivot*(n+1)+j] = swapValue; } for (let row = rank+1; row < n; row++) { factor = work[row*(n+1)+column]/work[rank*(n+1)+column]; work[row*(n+1)+column] = 0.0; for (let j = column+1; j <= n; j++) { work[row*(n+1)+j] -= factor*work[rank*(n+1)+j]; } } rank++; } output[0] = rank; for (let row = rank; row < n; row++) { if (Math.abs(work[row*(n+1)+n]) > 1e-10) { return -2; } } if (rank < n) { return 0; } for (let row = n-1; row >= 0; row--) { value = work[row*(n+1)+n]; for (let column = row+1; column < n; column++) { value -= work[row*(n+1)+column]*output[1+column]; } output[1+row] = value/work[row*(n+1)+row]; } return 1; } |
Source
NIST?s authored reference explains Gaussian elimination and partial pivoting. No original-paper attribution is claimed. The playground adds explicit numerical-rank and inconsistent-system handling under a fixed absolute tolerance.
- DLMF 3.2: Linear Algebra
N. M. Temme; NIST Digital Library of Mathematical Functions (2010?present). Authoritative numerical reference.