Apply Gaussian elimination to the supplied nonsymmetric matrix,The first pivot element is , with elimination multiplier . Perform , givingThe second pivot element is , with elimination multiplier . Perform , then use the third pivot element and elimination multiplier to perform . The LU factorization isHere is a unit lower triangular matrix, hence an invertible matrix, and is an upper triangular matrix. No row interchange is needed: all three pivot elements used in elimination are nonzero. The final diagonal entry is zero, with an entirely zero last row; there is no further division by it. The three nonzero rows of are linearly independent, so the matrix rank is and is a singular matrix. Direct matrix multiplication gives .
Pivoted LU decomposition 2026-10-14
We fix the convention : the permutation matrix acts on the rows of , and the same row ordering must be applied to before the Triangular solves for LU decomposition. Equivalently, , since . LAPACK documents its factors as instead, so check the defining equation rather than just the letter .[ref] Partial pivoting selects the largest absolute candidate in the current column, among rows , before forming elimination multipliers.[ref]
Fundamentals of Numerical Computation by Tobin A. Driscoll and others. §2.6.1, Definition 2.6.1; §2.6.2, Definition 2.6.2 and equation (2.6.1): pivot selection and reordered-row factorization
A zero first pivot element does not imply a singular matrix. For example,Unpivoted Gaussian elimination would divide by zero. Indeed, no with a unit lower triangular matrix exists: would force , contradicting . One row interchange resolves the obstruction. For , use ; back substitution then gives . Using the original with these factors would solve a different linear system.
Partial pivoting bounds each elimination multiplier by one in absolute value in exact arithmetic. This helps control roundoff error, but intermediate entries can still grow; it is not an unconditional guarantee of numerical stability for every matrix.[ref]
Fundamentals of Numerical Computation by Tobin A. Driscoll and others. §2.6.4, Example 2.6.6 and the concluding discussion: stability of unpivoted and pivoted factorization
It also does not remove the original problem's condition number. For the diagonal matrix with , the condition number in the Euclidean norm is . Row permutations preserve this condition number, because they preserve Euclidean norms. Even an exact solve changes from to when the right-hand side changes from to . This sensitivity is a property of the linear system, not a zero-pivot element failure.[ref] Pivot element Created 2026-10-14 Updated 2026-10-18
A pivot element is the current diagonal entry used to eliminate entries below it in Gaussian elimination, after any row interchange. At step it is , where is the current reduced matrix. Computing elimination multipliers requires this entry to be nonzero. A zero pivot element can reflect an unsuitable row order even for an invertible matrix, as Pivoted LU decomposition illustrates.
Quadratic-equation satisfiability over F2 Created 2026-09-24 Updated 2026-11-05
Quadratic-equation satisfiability over F2 asks whether finitely many polynomials of polynomial degree at most two over the finite field have a common zero. Each unknown therefore takes one of the two truth values zero and one, with addition and multiplication performed modulo two.
A Boolean circuit can be encoded by introducing a Boolean variable for every logic gate output. An AND gate becomes , while a NOT gate becomes . Forcing the final output to one adds . All these constraints have degree at most two, and an assignment to the logic gate variables solves them exactly when it is a consistent accepting Boolean circuit evaluation.
The construction has polynomial size and reduces the Circuit satisfiability problem to this task. Guessing values and checking the displayed polynomials proves membership in NP, so the problem is NP-complete. This explains why allowing quadratic terms changes the computational picture from a system of linear equations solved by Gaussian elimination.
Work over the rational numbers, allowing unknowns in the real numbers when interpreting the geometry. Consider four equations in three unknowns:The third row of is the sum of its first two rows, and the fourth is their difference, second minus first. The same relations must hold on the right: consistency requires and . The latter condition already holds. Gaussian elimination makes this compatibility test explicit while exposing the remaining freedom.
Apply the elementary row operations in this order, using each row's current value:then and . The resulting augmented matrix is in row echelon form for every :When , the third row has its pivot element in the augmented column. It says , so the linear system has no solution. When , that entire row vanishes and only two pivot elements remain. More equations than unknowns therefore do not force a unique solution: some equations may repeat information.
The final operation reduces the coefficient block toThe product of all six elementary matrices isDirect matrix multiplication verifies both displayed transformations. Its determinant is one, so this transformation is reversible. In particular, the third row of extracts the discrepancy between the third equation and the sum of the first two.
Row echelon form exposes compatibility; a right-hand-side pivot element distinguishes inconsistency from a free variable in a linear system
. Details. For , is the reduced row echelon form of the full augmented matrix. For , only its coefficient block is reduced: scale the third row by and clear the entries above its augmented pivot element. The full reduced row echelon form is thenThe last column is part of the matrix when testing the echelon conditions. Calling fully reduced before clearing that column would miss this distinction.
Simon's algorithm Created 2026-09-28 Updated 2026-10-25
Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over , and samples vectors satisfying over . Repeated samples and Gaussian elimination recover with oracle queries and polynomial computation.
To solve Simon's problem, prepare a uniform quantum superposition, evaluate the function coherently into a second quantum register, and perform Simon Fourier sampling on the first. Each run produces a uniform binary string with over the two-element field. Once the observed rows have matrix rank , Gaussian elimination recovers as the unique nonzero element of their kernel. The random spanning of a binary vector space bounds the required number of runs.
Sparse elimination of a four-leaf star 2026-10-18
Take a star graph with center and four leaves . Let be its Laplacian matrix and the identity matrix. In the order , the original example isFor a nonzero vector , its quadratic form isThus is a symmetric positive-definite matrix and either ordering below admits a Cholesky decomposition. Changing the ordering changes the work, rather than the mathematical solvability.
Center first. Eliminating with pivot element leaves the Schur complementEvery pair of leaves now has coupling : six new edges, hence six undirected fill-in positions. The four remaining vertices form a clique. In the Cholesky decomposition, the first column has and . The rest of the lower triangular matrix is dense. To check that later cancellation does not remove its entries, after leaves have also been eliminated, the active leaf block isIndeed a leaf step sends to . All active off-diagonal entries remain negative. The successive pivot elements in ordinary symmetric Gaussian elimination, equivalently the squared diagonals in the Cholesky decomposition, areThe Cholesky decomposition therefore stores nonzero entries, including its diagonal.
Leaves first. Permute to . Each leaf has only one remaining neighbor, so its elimination changes only the center's diagonal, reducing it by . The successive pivot elements are , and the exact Cholesky decomposition isThere is no fill-in, and only nonzero entries in . This is a concrete instance of leaf elimination of a tree-pattern positive-definite matrix; its general proof explains why the same idea works on every tree pattern. The minimum degree algorithm also chooses a leaf at every nontrivial stage of this particular example, but that success gives no general optimality guarantee.
Eliminating the center of a four-leaf star graph creates a clique; eliminating leaves creates no fill-in
. Details. The same symmetric positive-definite matrix has 15 or nine nonzero Cholesky decomposition factor entries, depending on its ordering
. Details. The input has 13 nonzero matrix elements when both symmetric halves are counted, or nine in its lower triangle. The six added undirected edges correspond to six added positions in one triangular factor, or 12 positions if both symmetric halves of the filled pattern are displayed. Comparing all 13 input entries directly with the 15 entries of would mix counting conventions.
Sparse Gaussian elimination Created 2026-10-14 Updated 2026-10-18
Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.
For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.[ref]
Lecture 27: Sparse Gaussian Elimination. Applications of Parallel Computers, CS267, Spring 1996; CS267, Lecture 27, 23 April 1996, Cholesky versus LU Decomposition: distinction between numerical pivot selection and advance ordering, and phases 1–4; Sparse Matrix Storage Schemes
For a fixed ordering, let be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here is the lower triangular matrix in the Cholesky decomposition of ; . Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because for every nonzero vector . A row permutation alone generally loses the symmetric matrix structure.
The local mechanism is a Schur complement. If the active pivot element is , then for remaining indices ,Even when , two nonzero couplings through make the second term nonzero. Thus the elimination graph removes and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.
This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.[ref]
Algorithmic Aspects of Vertex Elimination on Graphs by Donald J. Rose and others. Abstract: symmetric positive-definite systems, fill calculation for a prescribed ordering, and algorithms for special orderings; publication information, June 1976
Tridiagonal matrix Created 2026-09-25 Updated 2026-11-05
A tridiagonal matrix has zero entries outside its main diagonal and the two adjacent diagonals. With nonzero elimination pivots, the Thomas algorithm solves its linear system in linear time by specialized Gaussian elimination and back substitution.
Nonsingularity alone does not ensure that the unpivoted Thomas algorithm is defined: the invertible matrix has a zero first pivot. Conditions such as strict diagonal dominance guarantee suitable nonzero pivots; otherwise row interchanges or another factorization are needed.
Tridiagonal matrix algorithm 2026-10-14
The Thomas algorithm is Gaussian elimination specialized to a tridiagonal matrix: each row couples an unknown only to its immediate neighbours. Eliminating one unknown changes just the next diagonal entry and right-hand side. Provided all pivot elements are nonzero, a forward sweep followed by back substitution solves an -unknown linear system in time and storage, using Big O notation. Treating the same entries as a full matrix wastes the zeros: classical dense LU factorization and solve costs grow cubically for factorization and quadratically for storage.
A concrete reason to care is the Dirichlet Poisson solution by tridiagonal elimination: a three-point finite difference for the second derivative couples adjacent points on a mesh, producing precisely this tridiagonal matrix. The same structure occurs in one-dimensional Crank-Nicolson method calculations. NPTEL's archived Lecture 13 introduces the Thomas algorithm from that time-stepping problem and labels the procedure “Thomas algorithm (1949)”.[ref]
Thomas algorithm (NPTEL Lecture 13). Lecture 13, Thomas algorithm: opening historical attribution and Crank Nicolson motivation
Unimodular matrix Created 2026-09-24 Updated 2026-10-14
A unimodular matrix is a square integer matrix whose determinant is or . The decisive property is that its inverse matrix also has integer entries: multiplication by gives a bijection of the integer lattice onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.[ref]
Lecture 1: Introduction. §7, Definition 11 and Lemma 12, printed p. 9: determinant and integer-inverse characterization
For an original two-dimensional example, takeIts determinant is one, and it maps to . Conversely, the integer point comes from . For instance, has new coordinates relative to the columns and . No integer point disappears, although the basis vectors and their fundamental cell change shape.
Two lattice bases generate exactly the same integer points
. Original drawings of the standard basis and the columns of . Both displayed cells have area one. The point has coordinates in the standard basis and in the sheared basis. Details.This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.
A determinant of is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.
Uniqueness of reduced row echelon form 2026-10-18
Here is a short proof that uses only the row space. For a vector subspace , let be the dimension of its projection map onto the first coordinates, with . In any reduced row echelon form with row space , counts the pivot columns among those first columns: later-pivot rows project to zero, while earlier-pivot rows remain linearly independent. Thus the positions where determine all pivot positions from alone.
If those positions are , the map sending to is an isomorphism : the reduced nonzero rows map to the standard basis. Its th row is therefore the unique vector of with pivot-coordinate values equal to the th standard basis vector. Any other reduced row echelon form with that row space has identical nonzero rows in identical order. At a fixed matrix size, the remaining rows must be zero. Together with existence by Gaussian elimination, this proves uniqueness.



