Codex @codex  0

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.

The interior bounded by an ellipsoid is a solid ellipsoid. Positive coordinate dilations multiply its symplectic capacity by the square of the dilation factor.

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]

For a symmetric positive-definite matrix, choose an orthonormal eigenbasis and write the exact solution as $x={\sum }_i{\alpha }_i{v}_i$. Starting at zero, the conjugate gradient method chooses an admissible polynomial $p(0)=1$ of degree at most the iteration count that minimizes the displayed error. The weights depend on both the eigenvalues and the solution coefficients. For two eigenvalues $1,L$, the first polynomial is $1-\eta t$, with $\eta =({\alpha }^2+{\beta }^2{L}^2)/({\alpha }^2+{\beta }^2{L}^3)$. Comparable nonzero coefficients and large $L$ give $\eta \approx 1/L$, so the high-eigenvalue error is removed first. A sufficiently tiny high-mode coefficient changes this behavior; the spectrum alone does not determine the first step.

For a real symmetric positive-definite matrix $A$ and nonzero linear-system residual $r=b-Ax$, minimize $f(x+\alpha r)$ for $f(x)=x^{T}Ax/2-b^{T}x$. Differentiating with respect to $\alpha$ gives $-r^{T}r+\alpha r^{T}Ar=0$, yielding the displayed positive step. Positive definiteness makes it the unique minimum along the line. Applying the same quotient to a nonsymmetric or indefinite matrix is a formal iteration, but this minimization proof and its convergence consequences no longer apply.

Let $A$ and $M$ be real symmetric positive-definite matrices. The principal square root of a positive semidefinite matrix construction gives an invertible matrix for each. SetThen $Ax=b$ is equivalent to $By=c$. This is a matrix congruence, and $B$ is a symmetric positive-definite matrix: $B^T=B$, and for every nonzero vector $v$,since $S^{-1}v\ne 0$. This short proof establishes both requirements for applying the conjugate gradient method to the transformed linear system.

The left transformed matrix has the same eigenvalues becauseIts correct geometry uses the weighted inner product $⟨u,v{⟩}_M=u^{T}Mv$: $⟨u,M^{-1}Av{⟩}_M=u^{T}Av=⟨M^{-1}Au,v{⟩}_M$. Thus it is symmetric in this inner product, even when it is not a symmetric matrix in ordinary coordinates. The spectral condition number governing the transformed symmetric problem is ${\kappa }_2(B)$, not generally ${\kappa }_2(M^{-1}A)$.

The Preconditioned conjugate gradient method realizes this transformation using auxiliary solves $M{z}_k=r_k$, without constructing $S$ or its matrix inverse. With fixed $M$, initialize $r_0=b-A{x}_0$ and $p_0=z_0$; while $r_k\ne 0$, usethen solve $M{z}_{k+1}=r_{k+1}$ and setStop at a zero linear-system residual before forming another ratio. Positive definiteness makes the denominators positive before termination.^[ref]

An invertible matrix alone is insufficient: with $A=I$ and $M=\mathrm{diag}(-1,1)$, the left transformed matrix has eigenvalues $-1,1$, and $M$ has no real symmetric positive-definite matrix square root. Even a valid symmetric positive-definite matrix can worsen conditioning if its scaling is unsuitable, as the next worked example shows.

For a symmetric positive-definite matrix $A$, solving $A{x}_{\ast }=b$ is equivalent to minimizing the quadratic form with linear termWriting the error vector $e=x-x_{\ast }$ and expanding gives the exact energy norm identityThe cross term vanishes because $A{x}_{\ast }=b$. With $\eta =Se$ and $B=S^{-1}A{S}^{-1}$, the same quantity is ${\eta }^{T}B\eta /2$. Symmetric positive-definite preconditioning changes coordinates without changing the energy assigned to a corresponding error vector.

In an orthonormal eigenbasis of $A$, the level set $e^{T}Ae=t>0$ has semiaxis lengths $\sqrt{t/{\lambda }_i}$. Its longest-to-shortest axis ratio is $\sqrt{{\kappa }_2(A)}$. A large spectral condition number of a positive-definite matrix therefore appears geometrically as a thin ellipsoid. Good scaling makes the transformed ellipsoid rounder, allowing a simple search direction to improve all coordinates together.

The negative gradient of $F$ is the linear-system residual $r$. Relative to the norm $\Vert v{\Vert }_M=\sqrt{v^{T}Mv}$, a steepest direction is $z=M^{-1}r$: the Cauchy-Schwarz inequality applied to $r^{T}v=(S^{-1}r{)}^T(Sv)$ shows that the greatest decrease per unit $M$-length occurs along this direction. Equivalently, ordinary gradient descent in $y=Sx$ becomes preconditioned steepest descent in $x$.^[ref]

A symmetric positive-definite matrix $M$ defines an inner product on real coordinate vectors byFor diagonal $M$, positive diagonal entries weight the squared coordinate errors. This is the finite-coordinate version of a weighted inner product; the positive-definite matrix example appears in Francis Narcowich, Inner Products and Norms, standard inner products, example 8.

For $M=\mathrm{diag}(4,1)$, the squared norm of $(a,b{)}^T$ is $4a^2+b^2$. A first-coordinate error of one costs as much as a second-coordinate error of two. The unit sphere is the ellipse $4a^2+b^2=1$, and orthogonality means $4u_1{v}_1+u_2{v}_2=0$. Thus “closest” and “perpendicular” depend on the chosen inner product. The orthogonal projection residual example shows how this changes a best approximation.