The Grassmann field is odd and the adjoint scalar field is even. The two printed signs are consistent with a right-acting BRST differential, whose graded Leibniz rule is
The bracket between two odd fields is graded, so . Applying this rule to the ordinary Lie bracket gives
The second bracket here is graded because both its entries are odd. The graded Jacobi identity gives . Therefore
The side of the odd derivation is essential. With the usual left graded Leibniz rule and the same two printed signs, the result would be , which is generally nonzero. A left-acting convention must reverse one of those signs. All subsequent BRST symmetry formulas here use the right-acting convention.
Choose an anti-Hermitian basis with , an invariant positive invariant bilinear form on a Lie algebra, and the adjoint covariant derivative . Couplings are absorbed into this convention; restoring multiplies each ghost interaction vertex below by . The associated BRST charge acts as , , and .
Write . For the gauge-fixing fermion , the right graded Leibniz rule gives
The Gaussian functional integral over the Nakanishi-Lautrup field produces the positive gauge fixing term . The ghost operator is .
Now use the canonical free kinetic terms . At nonzero momentum in Euclidean space , put . The quadratic kernel for , per color, is
The transverse gauge-field kernel plus the gauge-fixing longitudinal term has become . The scalar quantum field theory propagator is the inverse Schur complement, not merely the inverse of the scalar diagonal entry:
Hence the free adjoint-scalar propagator in scalar-dependent gauge fixing is
For completeness the mixed quantum field theory propagator is ; ignoring this mixing would give an incorrect scalar answer.
The scalar propagator is independent of the gauge vector , not of the momentum component parallel to . For a unit , , and the free scalar quantum field theory propagator still depends on . Thus the literal momentum-independence clause in the PDF is false for the standard minimally coupled massless scalar action; the cancellation above establishes the natural gauge-vector-independence statement. The usual massless zero mode in field theory at needs a separate infrared prescription.
Finally, integration by parts gives the ghost action in an unambiguous convention:
Use for the Fourier transform of every field, with all momenta incoming. Let the antighost carry color and momentum , the boson color and momentum , and the ghost color and momentum , so . Expansion of gives the ghost vertices in scalar-dependent gauge fixing
The free Faddeev-Popov ghost field propagator is and every closed ghost loop contributes a minus sign. There are no further ghost interaction vertices in this gauge. Factors of and an overall ghost-vertex sign depend on the Fourier transform and ghost-ordering conventions; the displayed ghost action fixes both here.
Let be the all-ones matrix. Every feasible block matrix in the first formulation has , because its principal submatrix on indices is and is a positive semidefinite matrix. In particular, .
By the Schur complement,
Set . Then , , and on every edge. Conversely, for a feasible in the second formulation, its nonnegative diagonal gives , and has , on edges, and .
Both transformations preserve the objective . Hence the two semidefinite programs defining the complement theta number have the same feasible objective values and the same minimum.
Put . The noises required by a joint trajectory are and . Their independent Gaussian white noise weights give the joint path probability of an order parameter and its flux:
For the physically reversed path, is time-even and the transport flux is time-odd. Therefore , , and
The common factor includes the two noise normalizations and the midpoint Jacobian determinant. Its calculation must include both relaxation channels. On a finite spatial grid, let and represent the divergence and gradient, with the discrete Laplacian, and let be the Hessian matrix of at the midpoint of time step . Differentiating the two required noises with respect to the next configuration and the interval flux gives the Jacobian matrix
Using the Schur complement, its Jacobian determinant, apart from the path-independent power of , is
Reversal visits the same midpoint configurations in reverse order, so the product of these factors is unchanged. The joint time-reversal invariance of a path Jacobian therefore involves the complete relaxation operator .
Taking the action difference gives
Repeated component indices are summed. The second squared norm sums over both flux indices. This is mixed conserved and nonconserved order-parameter dynamics; reversing the order parameter history while leaving the flux unreversed would give the wrong probability ratio.
Apply symmetric Gaussian elimination without row exchanges. At step , let be the leading diagonal entry of the remaining symmetric Schur complement. If , stop and report that is not positive definite. If , use it to eliminate the rest of its row and column. If all steps succeed, this constructs an LDL decomposition
where is unit lower triangular and has positive diagonal.
The test is correct from first principles. If all , then for every nonzero ,
because is invertible. Conversely, if is positive definite, its first pivot is , and completing the square gives
Choosing shows that the Schur complement is positive definite. Induction forces every pivot to be positive. This is also Sylvester's criterion.
At step , updating the remaining matrix costs arithmetic operations. Hence the total is
which proves the existence of the required algorithm.
The assertion uses the positive parameters required for to be a preconditioner: assume and . For and , complete the square:
The matrix 2-norm bound shows that
for when . If and , the square contributes . Thus . Equivalently, the Schur complement of the lower-right block is .
Taken literally without the positivity inherited from part b, the product condition alone is insufficient: and is a counterexample. Thus is a necessary implicit hypothesis.
Root the graph at and let be the transition matrix of simple random walk killed on hitting , indexed by the remaining vertices. Its Green matrix is . Successively eliminating vertices in an order takes Schur complements; the corresponding diagonal pivot at step is exactly . The product of the pivots is therefore
which is invariant under the elimination order.
Put
After ordering before , the only nonzero off-diagonal entries between the two blocks occur at and , where they equal . Thus
where the coordinate vectors in the two blocks are understood. Expanding the determinant according to whether neither or both cross-block entries are selected gives
The minus sign is the sign of the transposition pairing the two cross-block entries. This formula remains valid when either diagonal block is singular, so no inverse or Schur complement is needed.
Stationarity of the equality-constrained quadratic subproblem gives . Together with feasibility, this is
Multiplying the bottom block row by gives a symmetric indefinite saddle-point matrix, with right side .
One solution strategy uses the Schur complement. From obtain
This is an positive-definite system when has full row rank; factor and solve with it rather than forming its inverse.
A second strategy uses a nullspace basis for . Choose one particular with , write , and solve the reduced system
The reduced Hessian is positive definite. These range-space and nullspace reductions exploit different relative sizes of and .
Stationarity of the equality-constrained quadratic model gives , while feasibility gives . A symmetric system linking the step and new multiplier is
Let have columns forming a basis of . The saddle-point matrix is nonsingular exactly when has full row rank and is nonsingular. Full row rank is necessary because a nonzero vector in would give a null vector of the block matrix. Under full row rank, solving a homogeneous system forces and then ; this proves sufficiency and the converse. Positive definiteness of the reduced Hessian is sufficient for a constrained minimum but is stronger than the nonsingularity condition asked here.
A null-space method first finds with , then solves
and recovers from . It needs the stated full row rank and nonsingular reduced matrix; Cholesky decomposition is available when the latter is positive definite.
A range-space method additionally assumes is invertible. It solves the Schur complement equations
If is positive definite and has full row rank, the Schur matrix is positive definite and both solves can use Cholesky decomposition. An indefinite but invertible instead requires a suitable indefinite factorization; the Schur matrix must remain nonsingular.
The following R code implements the given recursion for the Cholesky decomposition. The input is assumed to be a real symmetric matrix that is a positive-definite matrix.
mychol <- function(A) {
  n <- nrow(A)
  if (n == 1L) return(matrix(sqrt(A[1L, 1L]), 1L, 1L))
  j <- 2L:n
  L <- matrix(0, n, n)
  L[1L, 1L] <- sqrt(A[1L, 1L])
  b <- A[j, 1L, drop = FALSE] / L[1L, 1L]
  L[j, 1L] <- b
  S <- A[j, j, drop = FALSE] - tcrossprod(b)
  L[j, j] <- mychol(S)
  L
}
Here tcrossprod(b) is the outer product . The drop = FALSE arguments preserve matrix dimensions, including the final one-by-one subproblem, and the base case also returns a matrix.
To verify correctness, partition . The code sets , and recursively factors . This Schur complement is a positive-definite matrix: for ,
If is the recursive answer, then the returned lower triangular matrix satisfies
The one-dimensional identity starts this mathematical induction proof. Each recursive call reduces the matrix size by one and therefore terminates.
A perfect elimination ordering of a finite simple graph is a permutation of its vertices such that each set of later graph neighbours
is a clique. Thus is a simplicial vertex in the remaining induced subgraph . Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: goes first.
The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.[ref]
In the square-plus-diagonal chordal graph above, is a perfect elimination ordering, with later graph neighbourhoods , , , and . Starting instead with fails: its graph neighbours do not form a clique, because is absent. Thus even a chordal graph can have a poor elimination ordering.
For a larger example, join three triangles along shared edges, using
The exact graph neighbourhoods are , , , , and . The ordering has later graph neighbourhoods , , , , and , all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques , , form a junction tree in that order, with intersections and .
Figure 1.
A perfect elimination ordering removes three overlapping triangles without fill-in; choosing the central vertex first adds three edges
. Details.
To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is , with scores at selection ; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give recognition.[ref]
The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is , eliminating pivot applies the Schur complement update
Only pairs of remaining graph neighbours of can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.[ref] In the three-triangle graph, deleting first instead connects every pair in and adds exactly . The graph was already a chordal graph; the extra fill-in comes from the ordering.
One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number colors; any clique of that size requires at least that many. In the three-triangle graph, coloring gives colors , so both the chromatic number and the clique number are three. Every maximal clique also occurs among : take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.
Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.[ref]
For and , the Quasi-Newton secant equation requires . It reproduces the observed change of gradient along the latest step. If is a positive-definite symmetric matrix and , necessarily . A line search satisfying the weak Wolfe conditions ensures this: with ,
This necessary curvature condition is also sufficient for the existence of some positive-definite symmetric matrix mapping to . In an orthonormal basis whose first vector is , its first column must be , with . The block matrix with first row and lower-right block has a positive Schur complement, so is positive-definite.
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 . Equivalently, the initial principal minors are positive, and with .
For strict diagonal dominance, a short induction shows . The first row gives . Assuming the preceding bound, the triangle inequality gives
In particular . 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.
Schur complement Created 2026-09-24 Updated 2026-10-14
For a block matrix with an invertible matrix, the Schur complement of in is . It is the effective coefficient matrix for the remaining variables after block elimination. The definition requires invertibility of , but not of or . Its size is that of , even when and are rectangular matrices.
In the original example under block matrix inverse, becomes because changing the remaining variable also changes the two variables solved through . This is what makes a Schur complement more informative than simply deleting rows and columns. It retains their mediated effect, and its matrix inverse is the corresponding block of when the block matrix inverse exists.
The same elimination appears when minimizing a quadratic form. The Schur complement as a minimized quadratic form gives a geometric example; the Schur complement determinant identity gives an exact test for an invertible matrix.
Let be a real symmetric matrix with a positive-definite matrix. Its quadratic form satisfies the completing the square identity
For each fixed vector , the unique minimizing vector is , so the minimized value is . Also, is a positive-definite matrix exactly when is a positive-definite matrix, under the stated assumption on .[ref]
An original scalar example is
Here , , , and the Schur complement is . Holding would give , but letting relax to reduces the quadratic form to . At the respective values are and . Eliminating a variable therefore changes the effective cost of the retained variable.
Figure 1.
A Schur complement measures the quadratic form left after another variable relaxes
. Original contours of and the two resulting costs. The minimizing line picks the least value at each fixed ; the plotted profiles are exact model values, not experimental measurements. Details.
Schur complement covariance Created 2026-09-24 Updated 2026-11-05
For finite second moments and , the residual variance after affine projection onto one predictor is , a covariance Schur complement.
When is an invertible matrix, the factorization in block elimination has outer triangular factors with determinant one. Hence , without a symmetry assumption. For the original example under block matrix inverse, this gives . An invertible block therefore reduces the question of whether the full matrix is an invertible matrix to the smaller Schur complement; a singular makes a singular matrix.
At a nondegenerate critical point placed at the origin, integral Taylor theorem gives , where is a smooth symmetric matrix and . A constant linear change makes diagonal with entries . Successive completion of squares, with the Schur complement at each step, produces a smooth invertible triangular matrix such that . The pivots keep their nonzero signs near zero. The map has invertible derivative at zero, so the inverse function theorem makes it a coordinate system. The signs are the Hessian matrix signature by Sylvester's law of inertia.
Take a star graph with center and four leaves . Let be its Laplacian matrix and the identity matrix. In the order , the original example is
For a nonzero vector , its quadratic form is
Thus 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 complement
Every 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 is
Indeed 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, are
The 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 is
There 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.
Figure 1.
Eliminating the center of a four-leaf star graph creates a clique; eliminating leaves creates no fill-in
. Details.
Figure 2.
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]
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]