Block elimination 2026-10-14
Write a linear system as and , with an invertible matrix. Solving the first equation for and substituting in the second gives
Thus the Schur complement is the coefficient matrix remaining after the variables have been eliminated. When it is an invertible matrix, solve the reduced linear system for and recover . In computation, expressions such as mean solving with each column of , using the same LU decomposition or Cholesky decomposition when applicable.
For the example under block matrix inverse and right-hand side , take and . Since , the reduced equation is . Back substitution gives
The original equations return , and , respectively. The reduction retained the influence of on through the correction .
A short proof outline also explains whether is an invertible matrix: the exact matrix factorization
has invertible matrices on the outside. Therefore is an invertible matrix precisely when the central block diagonal matrix is one. Reversing the factors gives the block matrix inverse, while taking determinants gives the Schur complement determinant identity.
Block matrix inverse Created 2026-09-24 Updated 2026-10-18
A block matrix inverse expresses the matrix inverse in terms of smaller matrices. Partition a square matrix over a field as
If is an invertible matrix, define its Schur complement . Then is an invertible matrix exactly when is an invertible matrix, and
The order of the matrix products matters. In particular, the lower-right block is , rather than generally : the coupling through and changes the response.[ref]
For an original example, take
The Schur complement is . Substitution gives the concise answer
Multiplying in either order gives the identity matrix; the lower-right entry is , whereas . The difference records the feedback through the two eliminated variables.
Figure 1.
A block matrix inverse computed from the smaller Schur complement
. Original exact example. Colours mark the two-by-two block , the coupling blocks , and the scalar block . The same partition is retained in the matrix inverse; its blocks are not the entrywise inverses of the original blocks. Details.
Often the desired output is a solution of a linear system, rather than every entry of a matrix inverse. Block elimination solves with and then with , recovering the eliminated variables by back substitution. Reusing an LU decomposition of avoids explicitly forming . A favourable block diagonal matrix or tridiagonal matrix block can make this useful; merely partitioning an unstructured dense matrix does not guarantee a faster solve.[ref]
For a nondegenerate isometry direction and initially zero two-form, the local T-dual fields in alpha-prime-one units are , , , and . Gauging the isometry and eliminating its auxiliary connection derives these rules. The spectator metric is a Schur complement. The sign of the mixed two-form follows the multiplier and dual-coordinate orientation convention.
Cholesky decomposition Created 2026-09-28 Updated 2026-10-25
Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition , where is a lower triangular matrix with positive diagonal entries.[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is , with the conjugate transpose and the diagonal of positive and real.[ref] The factorization turns a linear system into two triangular systems.
For example, matching entries in gives
Choose the positive square roots in order: , and . Therefore
The second radicand, , is the scalar Schur complement remaining after eliminating the first variable. A positive diagonal of alone would not guarantee that this quantity is positive; Sylvester's criterion explains the relevant leading principal minors.
Figure 1. . Original exact two-by-two example. Multiplying the displayed lower triangular matrix by its transpose recovers ; forward substitution and backward substitution in a triangular system give for . Details.
For that right-hand side, first use forward substitution to solve : and , so . Then use backward substitution in a triangular system to solve : and , giving . No matrix inverse is required. For several right-hand sides with the same , keep the same factor and repeat only these triangular solves.
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: has but Schur complement , so it is a singular matrix. Both hypotheses in the block matrix inverse formula have work to do.
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.
Complement theta number Created 2026-10-05 Updated 2026-10-14
For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulations
and
The Schur complement and prove the equivalence; any feasible is at least one, so division by is valid. For a graph with an edge, is the Gram matrix of a strict vector coloring. Consequently is the strict vector chromatic number, and an ordinary -graph colouring gives by assigning the colors the vertices of a regular simplex.
The condensed mechanical load vector is the effective forcing on retained coordinates after mechanical dynamic condensation eliminates internal coordinates. It includes the effect of forces applied to the eliminated coordinates; it is not simply the retained subset of the original load vector. With partitioned mechanical dynamic-stiffness matrix and invertible internal block ,
and the retained equation is . This follows by solving the internal block equation and substituting it into the retained equation, using the same Schur complement that constructs the reduced dynamic stiffness. Coupled force/response models require their boundary conditions to be stated.[ref]
For an illustrative two-coordinate system at one frequency, let diagonal entries of be175N/m and off-diagonal entries be . Eliminating coordinate2 gives
If and , then and . Discarding the eliminated-coordinate force would incorrectly remove this response.
Conversely, choose simultaneous real complex amplitudes and . The condensed load vanishes and , even though neither applied force is zero. The recovered internal displacement is , which satisfies both original equations. This is a frequency-specific response cancellation, rather than a vanishing total physical force: .
Because the elimination uses , the effective load can depend on frequency and phase even when the original force amplitudes are simple. An arbitrary change of load or frequency therefore requires recomputing that transformation; a reduced matrix alone does not preserve every forced-response problem.
Conditional multivariate normal distribution Created 2026-09-24 Updated 2026-11-05
Partition a jointly multivariate normal distribution into vectors and with means and covariance blocks . If is invertible, then the Conditional multivariate normal distribution is
The covariance is a Schur complement. To see why, subtract the linear prediction from : . Direct covariance calculation gives . Since and are jointly Gaussian, they are independent; the covariance of is exactly the displayed Schur complement. Conditioning therefore changes the mean but leaves that residual covariance fixed.
For two standard normal variables with correlation , has mean and variance . If , the conditional law is degenerate: the same formula still gives a zero variance. A singular requires conditioning on its supported subspace rather than taking an ordinary matrix inverse.
A correlated-channel update of pressure-map information measures what a new pressure channel adds after accounting for noise that it shares with the old channels. The rank-one update of pressure-map information for independent noise is a special case. An extra channel may be a precise-looking duplicate of an existing noisy signal and contribute almost no new information.
Write the old and new observations as and . Suppose their known joint error covariance matrix is positive definite,
Subtract the part predicted from old noise by defining
Direct multiplication gives and , a Schur complement. Thus the invertible residual transformation separates the weighted residual objective into its old term and one scalar innovation term:
For jointly normal random variables, uncorrelatedness here also gives independence, and the matrix is the parameter Fisher information. For more general zero-mean errors with this fixed covariance, the displayed algebra still describes the generalized least squares information matrix. This is a partial whitening transformation; the primary covariance interface documents whitening and its identity-covariance check.[ref]
An original scalar example observes the same pressure twice, with unit error variances and error correlation . Then , , so
At , the true estimator variance is , whereas an independent-noise calculation would claim . At , the variance is : opposite noise contributions can cancel. Correlation can reduce or increase the benefit relative to the independent case; it does not make the correctly computed added information negative.
The effective sensitivity is , not merely the original . If and , the new residual carries no additional pressure information. A zero-innovation-variance pressure channel requires separate treatment: division by is invalid, and the limiting relation may be a redundant duplicate or an exact constraint, depending on .
A proposed array characterization measures simultaneous repeated readings under fixed known loads, estimates the complete cross-channel covariance, and tests reconstruction on withheld repetitions. A common reference offset can survive indefinitely despite more channels. The derivation assumes known, unchanged sensitivities and covariance; estimating them from few samples adds uncertainty not included by this update.
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.
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.
Free adjoint-scalar propagator in scalar-dependent gauge fixing Created 2026-10-05 Updated 2026-11-05
For gauge fixing with , integrating out the Nakanishi-Lautrup field produces gauge-scalar mixing. The Schur complement of the free gauge-field kernel cancels the extra in the scalar kernel, leaving . This is independent of the gauge vector , but still depends on the full momentum .
In the intermediate-index range, if an attaching sphere meets a belt sphere at exactly one transverse point, handle slides can remove the intersections of every other attaching sphere with . The dual slides then remove the intersections of with the other belt spheres. Each move uses a band to the unique pivot sheet and a local isotopy removing the old and new intersections. If and , the remaining incidence block is , the Schur complement of the pivot. Extreme-index cases need separate hypotheses.
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]
Leaf elimination of a tree-pattern positive-definite matrix Created 2026-10-14 Updated 2026-10-18
Associate an undirected graph with a symmetric matrix's off-diagonal nonzero pattern. Eliminating vertex updates the remaining matrix by . Only pairs of neighbors of can acquire fill-in. If the graph is a tree, remove leaves successively: each eliminated vertex has at most one remaining neighbor, so only a diagonal entry can change. Every Schur complement of a positive-definite matrix is positive definite, so no zero pivot forces a different ordering. Leaf removal therefore constructs a perfect elimination ordering and a fill-free factorization.
Matrix decomposition 2026-10-14
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 , and the final diagonal entry is the Schur complement of the first entry . This is the scalar version of the factorization under block elimination.
To solve , 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 and , giving the concise answer . 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.
Mechanical dynamic condensation eliminates selected coordinates from a frequency-dependent mechanical response while retaining their effect on the remaining coordinates. It is exact algebraic elimination at the chosen transform variable when the eliminated block is invertible. It is not equivalent to clamping those coordinates. Starting from the partitioned mechanical dynamic-stiffness matrix,
solve the internal equation as . Substitution gives
The effective matrix is a Schur complement; the right side is the condensed mechanical load vector. Both matter when the internal coordinate is externally forced. The coupled dynamic equations and measurement boundary conditions are the starting model, rather than independent scalar stiffness reciprocals.[ref]
For the two-mass example at , take and . With and , eliminating coordinate2 gives effective stiffness and effective load . Hence . Omitting the load correction would incorrectly predict no response at coordinate1.
For constant original mass matrix, damping and mechanical stiffness matrix, the condensed matrix is generally a rational function of frequency, not simply a smaller constant mass–damping–stiffness triple. A low-frequency approximation requires its own justification. The elimination can also become singular at an internal-block frequency even when the complete system matrix remains invertible. For example, has invertible full matrix for , but its lower-right scalar block cannot be inverted. One must then retain that coordinate or choose a different elimination.
A mechanical dynamic-stiffness matrix maps displacement coordinates to applied forces in a linear structural dynamics model at a specified transform variable or frequency. Starting with constant mass matrix , damping matrix and mechanical stiffness matrix ,
zero initial conditions give with . For the convention, . Its matrix inverse, when it exists, is the complete mechanical receptance matrix. Models and measured responses must use matching coordinates and boundary conditions.[ref]
Consider two masses, each grounded by a spring and joined by another spring, with no damping. At angular frequency ,
A force amplitude with gives and . Clamping coordinate2 instead gives , because the clamp supplies a reaction force.
Partitioning retained and internal coordinates gives mechanical dynamic condensation. With and invertible ,
The effective matrix is a Schur complement, generally frequency dependent even when the original mass matrix, damping and mechanical stiffness matrix are constant. In the example its scalar value is , rather than175. A reduced force-free internal coordinate and a clamped coordinate describe different experiments. At a singular block, that particular elimination is unavailable; it does not establish that the full mechanical system lacks a valid solution.
Minimum degree algorithm 2026-10-14
At each step choose a remaining vertex of minimum degree in the current elimination graph. This heuristic reduces the size of the immediate Schur complement update and often reduces fill-in, but does not guarantee a globally optimal ordering. Its degrees must reflect earlier fill, rather than just the original graph.