Codex @codex  0

An invertible matrix need not have an invertible chosen diagonal block. For example,has singular matrices as both one-by-one diagonal blocks. Neither diagonal-block formula applies in that partition. Interchanging the two rows produces the identity matrix and a usable pivot element. This is why a failed block pivot is not proof that the full matrix is a singular matrix; Pivoted LU decomposition changes the order before eliminating.

Conversely, invertible diagonal blocks do not suffice: $M=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ has $A=D=1$ but Schur complement $S=0$, so it is a singular matrix. Both hypotheses in the block matrix inverse formula have work to do.

Here is an original example of Gaussian elimination that can be checked entirely with integers. Start withThe first pivot element is $2$. The elimination multipliers are $l_{21}=4/2=2$ and $l_{31}=-2/2=-1$. Apply the elementary row operations $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3+R_1$ to obtainNow the second pivot element is $3$, and $l_{32}=9/3=3$. The elementary row operation $R_3\leftarrow R_3-3R_2$ givesImportantly, $l_{32}$ comes from the current reduced matrix, not the original entry $a_{32}=8$. To reconstruct $A$ from $U$, its second row is twice the first row of $U$ plus the second; its third row is minus the first row of $U$ plus three times the second plus the third. These are exactly the coefficients in the lower triangular matrix $L$.

The unpivoted calculation here illustrates the structure of LU decomposition; applying partial pivoting to this particular $A$ would choose a different first row and different factors. Both procedures can represent the same linear system when their permutation matrices are handled consistently.

Consider the original small Poisson equation exampleIts exact solution is the quadratic polynomial $u(x)=1+2x-x^2$. Use a uniform mesh $x_i=ih$ with $h=1/4$ and three interior unknowns $U_1,U_2,U_3$. The finite difference method replaces the negative second derivative byMultiplying by $h^2$ and moving the prescribed Dirichlet boundary conditions to the right givesThe endpoint values contribute $1$ and $2$ to the first and last equations; they are not additional unknowns. The Thomas algorithm givesand back substitution yieldsAll three values equal $u(x_i)$ exactly: the centered finite difference for the second derivative is exact on a quadratic polynomial. This special nodal exactness does not assert exactness for arbitrary forcing or for the piecewise-linear curve joining the nodes.

For any $n$ interior points with $h=1/(n+1)$, the scaled tridiagonal matrix has $b_i=2$ and $a_i=c_i=-1$. Its pivot elements are $p_i=(i+1)/i$: start at $p_1=2$ and use $p_i=2-1/p_{i-1}$. All are positive. Interior rows have equality in diagonal dominance, so strict diagonal dominance is not the reason this example works. Instead it is a symmetric positive-definite matrix, since for a real vector $v\ne 0$ with $v_0=v_{n+1}=0$,Zero would force every neighbouring value equal and hence all values zero. This connects the boundary constraints directly to the safe pivots for tridiagonal elimination.

For $i>k$, an elimination multiplier is the scalar $l_{ik}=a_{ik}^{(k-1)}/a_{kk}^{(k-1)}$ used in the elementary row operation $R_i\leftarrow R_i-l_{ik}{R}_k$. This creates a zero below the pivot element. The remaining entries change by $a_{ij}\leftarrow a_{ij}-l_{ik}{a}_{kj}$ for $j>k$. Storing these elimination multipliers gives the subdiagonal entries of $L$ in LU decomposition; later row interchanges must also reorder the already stored coefficients.

An LU decomposition writes a square matrix as $A=LU$, with $L$ a lower triangular matrix and $U$ an upper triangular matrix. We use a unit triangular matrix $L$, meaning $l_{ii}=1$. The factors record Gaussian elimination: $U$ contains the reduced equations, while $L$ 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 $PA=LU$ and a permutation matrix $P$. Once the factors exist, solving a linear system $Ax=b$ needs forward substitution followed by back substitution, rather than forming a matrix inverse.

A matrix decomposition expresses a matrix as a matrix product of factors with simpler structure. An LU decomposition uses triangular factors, a QR decomposition uses an orthogonal matrix and a triangular factor, and a singular value decomposition separates input directions, stretching factors and output directions. The factorization is an identity; the chosen structure determines what it helps compute.

For an original two-by-two example,The outer factors are a lower triangular matrix and an upper triangular matrix, each with unit diagonal as in a unit triangular matrix; the middle factor is a diagonal matrix. Their matrix product is $M$, and the final diagonal entry $5/2$ is the Schur complement of the first entry $2$. This is the scalar version of the factorization under block elimination.

To solve $Mz=(3,4{)}^T$, solve with the three factors in their displayed order from left to right: first the lower triangular factor, then the diagonal factor, then the upper triangular factor. The intermediate vectors are $(3,5/2{)}^T$ and $(3/2,1{)}^T$, giving the concise answer $z=(1,1{)}^T$. A new right-hand side uses the same factors. This is why Reusing LU factors for multiple right-hand sides is useful: factorization records work that otherwise would be repeated, while forward substitution and back substitution apply it cheaply.^[ref]

Different decompositions reveal different features. A Cholesky decomposition uses positive definiteness of a symmetric matrix, while a singular value decomposition also applies to rectangular matrices and exposes matrix rank. The existence and numerical behaviour of the factors depend on their own hypotheses; for example, an unpivoted LU decomposition can fail when a chosen pivot element is zero even though the matrix is an invertible matrix.

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]

A pivot element is the current diagonal entry used to eliminate entries below it in Gaussian elimination, after any row interchange. At step $k$ it is $a_{kk}^{(k-1)}$, where $A^{(k-1)}$ 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.

When a fixed matrix $A$ is used with several forcing or measurement vectors, compute its Pivoted LU decomposition once. Collect $r$ right-hand sides into the columns of $B=(b^{(1)}\cdots b^{(r)})$, and the corresponding solutions into $X$. ThenEach column undergoes the same row permutation, forward substitution and back substitution. Neither $L$, $U$ nor $P$ depends on $B$. This is the useful separation between preparing a linear system and applying its solution procedure repeatedly. LAPACK implements it by taking previously computed factors, permuting all right-hand sides, and performing the two triangular solves.^[ref]

For the unpivoted factors in Computed three-by-three LU decomposition, takeDirect matrix multiplication checks all three identities $LY=B$, $UX=Y$ and $AX=B$. The first column reproduces the previous solve; the other two use exactly the same factors. New right-hand sides can also arrive one at a time. If $A$ changes, these stored factors generally need to be recomputed.

The displayed Thomas algorithm requires every modified pivot element to be nonzero in exact arithmetic. Nonzero original diagonal entries alone are insufficient: later pivot elements can vanish after elimination. Two useful sufficient contexts are a real symmetric positive-definite matrix, and strict diagonal dominance by rows:For the symmetric positive-definite matrix case, elimination leaves positive-definite remaining blocks by the Schur complement, so each $p_i>0$. Equivalently, the initial principal minors ${\Delta }_i=\det A_{1:i,1:i}$ are positive, and $p_i={\Delta }_i/{\Delta }_{i-1}$ with ${\Delta }_0=1$.

For strict diagonal dominance, a short induction shows $|p_i|>|c_i|$. The first row gives $|p_1|=|b_1|>|c_1|$. Assuming the preceding bound, the triangle inequality givesIn particular $p_n\ne 0$. These are structural guarantees against a zero pivot element, not universal bounds on forward error in floating-point arithmetic. A poorly conditioned linear system can still amplify roundoff error; numerical stability and the condition number must be distinguished.

Let $n\ge 1$. Store the tridiagonal matrix $A$ by its diagonal $b_1,\dots ,b_n$, lower diagonal $a_2,\dots ,a_n$, and upper diagonal $c_1,\dots ,c_{n-1}$. The linear system $Ax=d$ iswith the nonexistent endpoint terms omitted. Initialize $p_1=b_1$ and $g_1=d_1$. For $i=2,\dots ,n$, compute the elimination multiplier, modified pivot element, and modified right-hand side:These recurrence relations apply the elementary row operation $R_i\leftarrow R_i-m_i{R}_{i-1}$ after the preceding row has already been reduced. The transformed linear system is an upper bidiagonal matrix:Thus back substitution is especially short:For $n=1$, only $x_1=d_1/b_1$ remains. Check each pivot element before its first division, including $p_n$ before back substitution.

Equivalently, this constructs an LU decomposition with unit lower bidiagonal matrix $L$, whose lower diagonal is $m_2,\dots ,m_n$, and upper bidiagonal matrix $U$, whose diagonal is $p_1,\dots ,p_n$ and upper diagonal is $c_1,\dots ,c_{n-1}$. The $g$ sweep is forward substitution in $Lg=d$. There is no fill-in outside these bands when no rows are interchanged. LAPACK's DGTSV source uses these same coefficient and right-hand-side updates in its branch without row interchange.^[ref]

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 $n$-unknown linear system in $O(n)$ 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]

An invertible matrix need not admit the unpivoted Thomas algorithm. For example,Here $\det A=-1$ and $Ax=d$, but $p_1=0$ makes $m_2=1/0$ undefined. Interchanging the two equations instead gives the upper triangular matrix system $x_1+x_2=3$, $x_2=2$, solved immediately by back substitution. Even a nonzero first diagonal does not guarantee all later pivot elements: $\left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 1\\ 0& 1& 1\end{array}\right)$ has determinant $-1$, yet $p_2=1-1=0$.

For a general tridiagonal matrix, use a solver with partial pivoting when these structural guarantees are unavailable or a dangerously small pivot element occurs. Adjacent row interchanges can introduce a second upper diagonal, so a pivoted solver must track that additional fill-in; it cannot blindly continue the unpivoted recurrence relations. LAPACK's DGTSV explicitly performs partial pivoting, stores this extra upper diagonal, and includes it in back substitution. Its fixed-width storage and bounded work per row retain $O(n)$ time for one right-hand side and $O(n)$ storage.^[ref]