Augmented matrix 2026-10-14
The augmented matrix of a linear system appends the right-hand side as one extra column. Elementary row operations preserve its solution set. The linear system is consistent exactly when the coefficient matrix rank equals the augmented matrix rank, because this is equivalent to lying in the span of the columns of . A larger augmented matrix rank produces a zero coefficient row with a nonzero right-hand side during Gaussian elimination.
Bareiss algorithm Created 2026-10-20 Updated 2026-11-05
The Bareiss algorithm is fraction-free Gaussian elimination for exact determinants. For an integer matrix, put and . At step , choose a nonzero pivot element and update the trailing entries by
Set the eliminated entries below the pivot to zero. The determinant identities behind the method make division by exact, so intermediate entries remain integers. Without row exchanges, the last pivot is ; row exchanges change its sign in the usual way. A zero pivot needs an exchange before continuing.
For , the first trailing block becomes . The last update is , giving the determinant without rational intermediate entries. Exact division is different from having no division at all.[ref]
At each step of Gaussian elimination, select the largest absolute entry in the uneliminated part of the current column and interchange rows to put it on the diagonal. A nonsingular trailing Schur complement has a nonzero entry in its first column, so this procedure always finds a nonzero pivot in exact arithmetic. The permutation matrix records row interchanges; earlier multipliers must be interchanged too when assembling the lower-triangular factor. This yields the LU decomposition with unit diagonal in . Searching within columns and interchanging rows is distinct from interchanging columns.
Computed three-by-three LU decomposition Created 2026-10-14 Updated 2026-10-31
Here is an original example of Gaussian elimination that can be checked entirely with integers. Start with
The first pivot element is . The elimination multipliers are and . Apply the elementary row operations and to obtain
Now the second pivot element is , and . The elementary row operation gives
Importantly, comes from the current reduced matrix, not the original entry . To reconstruct from , its second row is twice the first row of plus the second; its third row is minus the first row of plus three times the second plus the third. These are exactly the coefficients in the lower triangular matrix .
The unpivoted calculation here illustrates the structure of LU decomposition; applying partial pivoting to this particular would choose a different first row and different factors. Both procedures can represent the same linear system when their permutation matrices are handled consistently.
Every invertible square matrix is a product of elementary matrices. Gaussian elimination reduces to the identity matrix by elementary row operations, giving . Reverse their order and invert them to write . Each inverse is again elementary. Conversely every elementary matrix is invertible, so every such product is invertible. The identity may be represented by the empty product.
Elementary row operation 2026-10-14
An elementary row operation interchanges two rows of a matrix, multiplies one row by a nonzero scalar, or adds a scalar multiple of another row to it. These invertible operations are used in Gaussian elimination. For a square matrix, interchange changes the sign of its determinant, multiplication scales its determinant by the same scalar, and adding another row leaves its determinant unchanged, by multilinearity and alternation.
Elimination graph 2026-10-14
One step of symmetric Gaussian elimination removes the pivot vertex and connects its remaining neighbors into a clique. The rule follows from the Schur complement update . Repeating it predicts the generic factor sparsity; exceptional numerical cancellations can remove structurally predicted entries.
Erwin H. Bareiss 2026-11-05
Erwin H. Bareiss developed integer-preserving methods for Gaussian elimination. The Bareiss algorithm uses determinant identities to arrange divisions that are exact, reducing the growth of intermediate rational expressions.[ref]
An update combines two products and divides by a previous pivot. The reason this stays in the integers is structural: the quantities represent related minors satisfying Sylvester identity for bordered minors. This makes exact linear algebra practical without replacing the calculation by floating-point approximation.[ref]
Field Created 2026-09-24 Updated 2026-10-13
A field is a commutative ring with in which every nonzero element has a multiplicative inverse. Examples include the rational numbers, real numbers, and complex numbers. The integers are a ring but not a field: dividing by leaves them. For a prime number , the prime field is a finite example, because every nonzero residue is coprime to and hence has a modular inverse.
In , the nonzero inverse pairs are , , , and . Thus has solution in this field; the real number solution would be . Dividing by a nonzero coefficient is valid in both settings, but it means division according to the chosen field's operations.
A field has no zero divisors: if and , multiplying by gives . This short argument supports polynomial factorization arguments and pivot division in Gaussian elimination. It does not hold in every commutative ring: modulo , the nonzero residues and multiply to zero. The distinction is visible in the figure under algebraic structure.
Fill-in Created 2026-10-14 Updated 2026-10-18
Fill-in consists of new nonzero positions created by Gaussian elimination, absent from the original sparse matrix in the same ordering. For a Cholesky decomposition , compare with the lower triangle of , not with the unpermuted input. Each new undirected edge of the elimination graph contributes one structural position in . The sparse elimination of a four-leaf star gives six such positions when the center is eliminated first, and none when the leaves are eliminated first.
Symbolic factorization predicts possible nonzeros from the pattern alone. An initially zero becomes nonzero in a single scalar step if both and are nonzero; however, at later steps several contributions can cancel. For an exact example, let
Eliminate indices in that order. The first Schur complement, in order , is
The second pivot element updates the entry to . The remaining block is , so all four pivot elements are positive and is a symmetric positive-definite matrix. The elimination graph retains the structural edge , but this exact choice of coefficients makes the numerical entry vanish. A small change to generally removes the cancellation.
Such an exact zero is different from discarding a small value computed with floating-point arithmetic. The symbolic factorization deliberately reserves space for possible entries without depending on special numerical identities. A perfect elimination ordering creates no structural fill-in at all; an ordering with cancellations need not have that property.
Use the negative-exponential forward discrete Fourier transform and the -normalized inverse discrete Fourier transform:
For the circulant matrix with first column , the discrete Fourier mode is an eigenvector with eigenvalue
Indeed, substitution into circular convolution gives
The columns of are , so the diagonalization of a matrix takes the form
The roots of unity give orthogonality of these eigenvectors; dividing each by makes the basis orthonormal. Consequently, every complex circulant matrix is a normal matrix, including ones that are not Hermitian matrices.
The sign convention matters. For , the circulant matrix is
Changing the direction of the shift or the sign in the discrete Fourier transform changes which complex eigenvalue goes with which discrete Fourier mode. A real symmetric example alone would conceal that distinction.
For a linear system , put and . The equation becomes independent scalar equations
If every is nonzero, divide to find the unique vector and apply the inverse discrete Fourier transform. If some , a vector satisfying the linear system exists exactly when at every such index; the corresponding remain free. This is a concrete version of the Fredholm alternative in a finite-dimensional setting.
With an appropriate Fast Fourier transform, multiplication or a compatible solve takes arithmetic operations, instead of forming a dense matrix and applying general Gaussian elimination. The gain comes from the periodic structure; an arbitrary matrix does not have this shared basis of discrete Fourier modes.[ref]
Gaussian elimination Created 2026-09-24 Updated 2026-10-25
Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses arithmetic operations.
Gaussian elimination solves a linear system by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an augmented matrix . Apply the same elementary row operations to both parts until the coefficients form a row echelon form; for a square invertible matrix, this gives an upper triangular matrix system. Then back substitution recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.
Why do elementary row operations preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero scalar can be undone by division. Replacing equation by itself plus times equation , with , can be undone by adding times the unchanged equation . Equivalently, an elementary matrix is an invertible matrix, so if and only if . Applying an operation to without also applying it to loses this equivalence.
At step , choose a nonzero pivot element after any row interchange. For every , form the elimination multiplier and perform the elementary row operation . Its coefficient in column becomes in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general row echelon form reduction skips it; a square invertible matrix always has a candidate at each step with suitable row interchanges. Partial pivoting also considers roundoff error when selecting the candidate.[ref]
For a dense matrix with one right-hand side, the classical algorithm uses arithmetic operations over the real numbers, counting each addition, subtraction, multiplication and division as one. At step , the coefficient update has entries, each costing one multiplication and one subtraction; the elimination multipliers, right-hand-side updates and back substitution contribute lower-order terms. Searching for partial pivoting adds comparisons, and storing the dense coefficients uses space. These assumptions exclude the different storage and work patterns of sparse Gaussian elimination; the exact loop counts appear in LU factorization and solve costs. Here denotes Big O notation.
Recording the same steps as an LU decomposition makes Reusing LU factors for multiple right-hand sides possible. This is useful whenever the coefficients stay fixed while the forcing vector changes: the expensive elimination is done once. The choice of pivot element matters even when the linear system is well conditioned, as Tiny-pivot roundoff in Gaussian elimination demonstrates.
Gauss-Jordan elimination Created 2026-10-20 Updated 2026-11-05
Gauss-Jordan elimination uses elementary row operations to reduce a matrix to reduced row echelon form. After choosing and normalizing each pivot, eliminate entries both below and above it. In a consistent linear system, pivot variables are then expressed directly in terms of free variables.
For example, the augmented matrix with rows and reduces to and , giving . Applied to for an invertible square matrix, it produces . For numerical solution of one system, Gaussian elimination with back substitution usually needs less work, and pivoting is still necessary for numerical reliability.
Inconsistent linear system Created 2026-10-25 Updated 2026-10-31
A linear system is inconsistent when it has no solution. In Gaussian elimination, a row with proves inconsistency. Equivalently the matrix rank of the augmented matrix is greater than the matrix rank of the coefficient matrix.
Jacobi method Created 2026-09-24 Updated 2026-10-31
Writing , where is diagonal and are strictly triangular, the Jacobi iteration is
The Jacobi method solves a linear system by updating every coordinate from the same old vector. It requires every diagonal entry to be nonzero. Isolating coordinate in row gives the simultaneous rule
Here is the iteration matrix. A sweep computes a complete new vector before replacing the old one, so its coordinate updates can run independently.[ref]
For a sparse matrix, a sweep needs work proportional to the stored nonzero entries, while Gaussian elimination may create fill-in. The Jacobi method is therefore a simple starting point for large linear systems, and the weighted Jacobi method supplies a useful building block of a multigrid method. Its beauty is that a local row correction becomes a global eigenvalue question: the convergence criterion for a stationary iteration is exactly .
LDL decomposition Created 2026-09-24 Updated 2026-11-05
A diagonal-pivot LDL decomposition of a real symmetric matrix has the form
where is a unit lower triangular matrix and is a diagonal matrix. When the needed scalar pivots are nonzero, symmetric Gaussian elimination computes one Schur complement at a time:
In particular, nonzero leading principal minors guarantee this form, and a symmetric positive-definite matrix has positive pivots. Conversely, for every gives for every nonzero vector .
For , take and . General symmetric matrices need more care: has no such unit-lower-triangular/diagonal factorization. Symmetric indefinite numerical factorization can instead use permutations and symmetric diagonal blocks of sizes one or two.[ref]
Leibniz formula for determinants Created 2026-09-24 Updated 2026-11-05
For an matrix , the Leibniz formula for determinants is
The sum runs over all permutations of the columns. Each product chooses one entry from every row and every column, and its sign is the sign of a permutation.
For a matrix, the two permutations give . More generally, exchanging two rows pairs terms with opposite signs, while each row appears once in every product. These observations explain the formula's alternating and multilinear behavior. It is useful for symbolic arguments; direct evaluation has products, whereas Gaussian elimination gives a more efficient numerical route.
LU decomposition Created 2026-09-29 Updated 2026-10-14
An LU decomposition writes a square matrix as , with a lower triangular matrix and an upper triangular matrix. We use a unit triangular matrix , meaning . The factors record Gaussian elimination: contains the reduced equations, while stores the elimination multipliers needed to reconstruct the original equations. This makes Reusing LU factors for multiple right-hand sides inexpensive.[ref]
For an invertible matrix, unpivoted LU decomposition requires nonzero pivot elements at every elimination step; invertibility alone does not guarantee this. In general use Pivoted LU decomposition, with the explicit convention and a permutation matrix . Once the factors exist, solving a linear system needs forward substitution followed by back substitution, rather than forming a matrix inverse.
LU decomposition of an upper Hessenberg matrix Created 2026-10-31 Updated 2026-11-05
When Gaussian elimination without row interchanges is defined, an upper Hessenberg matrix needs at most one elimination per pivot column, because only its first subdiagonal can be nonzero. The LU decomposition has a unit lower bidiagonal matrix and an upper triangular matrix . If the input matrix is also symmetric, it is a tridiagonal matrix and is upper bidiagonal.
The nonzero-pivot condition is essential: is upper Hessenberg and invertible but has no such unpivoted LU decomposition. A pivoted factorization can still be computed, with its permutations recorded explicitly.
For classical dense Gaussian elimination over the real numbers, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. At step , there are elimination multipliers to divide out and remaining entries, each requiring one multiplication and one subtraction. Thus this implementation's unpivoted factorization count is
Here uses Big O notation. Partial pivoting adds comparisons and row movement, leaving the leading arithmetic count unchanged. The leading count agrees with the standard dense LU decomposition analysis.[ref]
With unit , forward substitution uses arithmetic operations. Back substitution uses another plus diagonal divisions. Together these cost per right-hand side; applying a stored row permutation moves entries and requires no scalar arithmetic. In Big O notation, Reusing LU factors for multiple right-hand sides therefore costs
whereas refactorizing for each of the right-hand sides costs . For and , the leading counts are about versus arithmetic operations, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized matrix multiplication also affect speed.[ref]