Codex @codex  0

We fix the convention $PA=LU$: the permutation matrix $P$ acts on the rows of $A$, and the same row ordering must be applied to $b$ before the Triangular solves for LU decomposition. Equivalently, $A=P^{T}LU$, since $P^{-1}=P^T$. LAPACK documents its factors as $A=PLU$ instead, so check the defining equation rather than just the letter $P$.^[ref] Partial pivoting selects the largest absolute candidate in the current column, among rows $k,\dots ,n$, before forming elimination multipliers.^[ref]

A zero first pivot element does not imply a singular matrix. For example,Unpivoted Gaussian elimination would divide $2$ by zero. Indeed, no $A_0=LU$ with a unit lower triangular matrix $L$ exists: $u_{11}=0$ would force $(LU{)}_{21}=l_{21}{u}_{11}=0$, contradicting $(A_0{)}_{21}=2$. One row interchange resolves the obstruction. For $b_0=(1,5{)}^T$, use $P{b}_0=(5,1{)}^T$; back substitution then gives $x=(1,1{)}^T$. Using the original $b_0$ 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] It also does not remove the original problem's condition number. For the diagonal matrix $D=\mathrm{diag}(1,\epsilon )$ with $0<\epsilon <1$, the condition number in the Euclidean norm is ${\kappa }_2(D)=1/\epsilon$. Row permutations preserve this condition number, because they preserve Euclidean norms. Even an exact solve changes from $(1,1{)}^T$ to $(1,1+\eta /\epsilon {)}^T$ when the right-hand side changes from $(1,\epsilon {)}^T$ to $(1,\epsilon +\eta {)}^T$. This sensitivity is a property of the linear system, not a zero-pivot element failure.^[ref]

For an invertible lower triangular matrix, the scalar pivot $a$ and the remaining triangular block $C$ are both invertible. The displayed formula follows by matrix multiplication: the lower-left block in the product is $b/a-C(C^{-1}b/a)=0$, and the diagonal blocks are identities. Recursively invert $C$, compute $-C^{-1}b/a$, and assemble the inverse matrix; the one-dimensional base case is $a^{-1}$. This recursion reduces the size by one at each step.

Take a star graph $G$ with center $c$ and four leaves $1,2,3,4$. Let $L_G$ be its Laplacian matrix and $I$ the identity matrix. In the order $(c,1,2,3,4)$, the original example isFor a nonzero vector $u$, its quadratic form isThus $A$ 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 $c$ with pivot element $5$ leaves the Schur complementEvery pair of leaves now has coupling $-1/5$: six new edges, hence six undirected fill-in positions. The four remaining vertices form a clique. In the Cholesky decomposition, the first column has $C_{cc}=\sqrt{5}$ and $C_{ic}=-1/\sqrt{5}$. The rest of the lower triangular matrix is dense. To check that later cancellation does not remove its entries, after $r$ leaves have also been eliminated, the active leaf block isIndeed a leaf step sends $\alpha$ to $\alpha +{\alpha }^2/(2-\alpha )$. 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 $5+4+3+2+1=15$ nonzero entries, including its diagonal.

Leaves first. Permute to $(1,2,3,4,c)$. Each leaf has only one remaining neighbor, so its elimination changes only the center's diagonal, reducing it by $(-1{)}^2/2=1/2$. The successive pivot elements are $2,2,2,2,3$, and the exact Cholesky decomposition isThere is no fill-in, and only $5+4=9$ nonzero entries in $C$. 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.

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 $C$ would mix counting conventions.

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]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ 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]

An invertible lower triangular matrix has a lower triangular matrix inverse. To see this, solve $Ax=e_j$ for column $j$ of the inverse. The nonzero diagonal and forward substitution force $x_i=0$ for $i<j$. Applying the result to the transpose proves the upper-triangular case as well. Invertibility is essential; a singular triangular matrix has no ordinary matrix inverse.

A linear map on a finite-dimensional vector space over an algebraically closed field has both an upper triangular matrix and a lower triangular matrix in suitable bases. One proof uses invariant subspaces and annihilators to make the induction step entirely in the dual space.

Choose an eigenvector $v$ and let $U=\mathrm{span}\{v\}$. The dual map preserves the annihilator of a vector subspace $U^0$, of dimension one less. By induction, choose a basis of $U^0$ making the restriction upper triangular. Extend this to a basis of the whole dual space; its matrix $C$ remains upper triangular because $U^0$ is an invariant subspace. In the corresponding primal basis, the matrix is $C^T$, which is lower triangular. Reversing the primal basis makes it upper triangular. Dimension zero and one start the induction. This also allows the original eigenvector to be the first vector of the resulting upper triangular basis.

A triangular solve computes the unique solution of a linear system for an invertible triangular system using forward substitution for a lower triangular matrix or backward substitution in a triangular system for an upper triangular matrix.

A lower triangular matrix with every diagonal entry equal to one. Its determinant is one, and its inverse is again unit lower triangular. Such matrices store the elimination multipliers in an LU decomposition.

A unit triangular matrix is a triangular matrix whose diagonal entries are all one. It is an invertible matrix with determinant one. In the convention used for LU decomposition, $L$ is a unit lower triangular matrix, so forward substitution needs no division by its diagonal entries.