Codex @codex  0

Write a linear system as $Ax+By=f$ and $Cx+Dy=g$, with $A$ an invertible matrix. Solving the first equation for $x$ and substituting in the second givesThus the Schur complement is the coefficient matrix remaining after the $x$ variables have been eliminated. When it is an invertible matrix, solve the reduced linear system for $y$ and recover $x$. In computation, expressions such as $A^{-1}B$ mean solving with each column of $B$, using the same LU decomposition or Cholesky decomposition when applicable.

For the example under block matrix inverse and right-hand side $(3,1,4{)}^T$, take $f=(3,1{)}^T$ and $g=4$. Since $C{A}^{-1}f=13/6$, the reduced equation is $(19/6)y=11/6$. Back substitution givesThe original equations return $3$, $1$ and $4$, respectively. The reduction retained the influence of $x_1,x_2$ on $y$ through the correction $C{A}^{-1}B$.

A short proof outline also explains whether $M$ is an invertible matrix: the exact matrix factorizationhas invertible matrices on the outside. Therefore $M$ 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.

A block matrix inverse expresses the matrix inverse in terms of smaller matrices. Partition a square matrix over a field asIf $A$ is an invertible matrix, define its Schur complement $S=D-C{A}^{-1}B$. Then $M$ is an invertible matrix exactly when $S$ is an invertible matrix, andThe order of the matrix products matters. In particular, the lower-right block is $S^{-1}$, rather than generally $D^{-1}$: the coupling through $B$ and $C$ changes the response.^[ref]

For an original example, takeThe Schur complement is $S=5-1/2-4/3=19/6$. Substitution gives the concise answerMultiplying in either order gives the identity matrix; the lower-right entry is $6/19$, whereas $D^{-1}=1/5$. The difference records the feedback through the two eliminated variables.

Often the desired output is a solution of a linear system, rather than every entry of a matrix inverse. Block elimination solves with $A$ and then with $S$, recovering the eliminated variables by back substitution. Reusing an LU decomposition of $A$ avoids explicitly forming $A^{-1}$. 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]

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 $P$ records row interchanges; earlier multipliers must be interchanged too when assembling the lower-triangular factor. This yields the LU decomposition $PA=LU$ with unit diagonal in $L$. Searching within columns and interchanging rows is distinct from interchanging columns.

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.

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.

Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses $O(n^3)$ arithmetic operations.

Gaussian elimination solves a linear system by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an augmented matrix $[A\mid b]$. Apply the same elementary row operations to both parts until the coefficients form a row echelon form; for a square invertible matrix, this gives an upper triangular matrix system. Then back substitution recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.

Why do elementary row operations preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero scalar can be undone by division. Replacing equation $i$ by itself plus $c$ times equation $j$, with $i\ne j$, can be undone by adding $-c$ times the unchanged equation $j$. Equivalently, an elementary matrix $E$ is an invertible matrix, so $Ax=b$ if and only if $EAx=Eb$. Applying an operation to $A$ without also applying it to $b$ loses this equivalence.

At step $k$, choose a nonzero pivot element $a_{kk}$ after any row interchange. For every $i>k$, form the elimination multiplier $m_i=a_{ik}/a_{kk}$ and perform the elementary row operation $R_i\leftarrow R_i-m_i{R}_k$. Its coefficient in column $k$ becomes $a_{ik}-(a_{ik}/a_{kk})a_{kk}=0$ in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general row echelon form reduction skips it; a square invertible matrix always has a candidate at each step with suitable row interchanges. Partial pivoting also considers roundoff error when selecting the candidate.^[ref]

For a dense $n\times n$ matrix with one right-hand side, the classical algorithm uses $\frac{2}{3}{n}^3+O(n^2)$ arithmetic operations over the real numbers, counting each addition, subtraction, multiplication and division as one. At step $k$, the coefficient update has $(n-k{)}^2$ entries, each costing one multiplication and one subtraction; the elimination multipliers, right-hand-side updates and back substitution contribute lower-order terms. Searching for partial pivoting adds $O(n^2)$ comparisons, and storing the dense coefficients uses $O(n^2)$ space. These assumptions exclude the different storage and work patterns of sparse Gaussian elimination; the exact loop counts appear in LU factorization and solve costs. Here $O$ denotes Big O notation.

Recording the same steps as an LU decomposition makes Reusing LU factors for multiple right-hand sides possible. This is useful whenever the coefficients stay fixed while the forcing vector changes: the expensive elimination is done once. The choice of pivot element matters even when the linear system is well conditioned, as Tiny-pivot roundoff in Gaussian elimination demonstrates.

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.

For classical dense Gaussian elimination over the real numbers, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. At step $k$, there are $n-k$ elimination multipliers to divide out and $(n-k{)}^2$ remaining entries, each requiring one multiplication and one subtraction. Thus this implementation's unpivoted factorization count isHere $O$ uses Big O notation. Partial pivoting adds $O(n^2)$ comparisons and row movement, leaving the leading arithmetic count unchanged. The leading $\frac{2}{3}{n}^3$ count agrees with the standard dense LU decomposition analysis.^[ref]

With unit $L$, forward substitution uses $n(n-1)$ arithmetic operations. Back substitution uses another $n(n-1)$ plus $n$ diagonal divisions. Together these cost $2n^2-n$ per right-hand side; applying a stored row permutation moves $n$ entries and requires no scalar arithmetic. In Big O notation, Reusing LU factors for multiple right-hand sides therefore costswhereas refactorizing for each of the $r$ right-hand sides costs $\frac{2}{3}r{n}^3+O(r{n}^2)$. For $n=1000$ and $r=10$, the leading counts are about $6.87\times 10^8$ versus $6.69\times 10^9$ arithmetic operations, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized matrix multiplication also affect speed.^[ref]

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.

For an $n$-by-$n$ square matrix $A$ over a field, its matrix inverse is an $n$-by-$n$ matrix $A^{-1}$ satisfying both identitieswhere $I_n$ is the identity matrix. It exists exactly when $A$ is an invertible matrix, equivalently when its matrix rank is $n$ or its determinant is nonzero. It reverses the linear map: applying $A$ and then $A^{-1}$ recovers the input, while applying $A^{-1}$ and then $A$ recovers the output.^[ref]

The matrix inverse is unique. If $B$ and $C$ both satisfy the identities, then $B=B(AC)=(BA)C=C$. Although the definition is two-sided, for finite square matrices either identity alone suffices: $BA=I$ forces a trivial kernel, whereas $AB=I$ forces surjectivity; either makes $A$ an invertible matrix by the rank-nullity theorem. Rectangular matrices may have only one of these properties.

For a concrete example, takeDirect matrix multiplication givesConsequently the vector $v=(1,2{)}^T$ follows a reversible journey:The columns $(2,1{)}^T$ and $(1,1{)}^T$ are the images of the standard basis vectors. They turn the unit square into a parallelogram; the matrix inverse restores both the square and its surrounding grid. Since $\det A=1$, this example changes shape while preserving area, illustrating that invertibility does not require preserving lengths or angles.

For comparison, the singular matrixcannot have a matrix inverse: the output $(1,0{)}^T$ cannot specify which of the two inputs occurred. Their difference $(1,-1{)}^T$ belongs to its kernel. Indeed $S(x,y{)}^T=(x+y,0{)}^T$ collapses the plane to a line, its matrix rank is one, and its determinant is zero. No subsequent function of the output alone can reconstruct every input.

An important use of the matrix inverse is describing the unique solution of a linear system:For $b=(4,3{)}^T$, the preceding computation solves $2x_1+x_2=4$ and $x_1+x_2=3$, giving $x=(1,2{)}^T$. In computation, usually solve the linear system using Gaussian elimination and a factorization such as an LU decomposition, rather than forming every entry of the matrix inverse. The inverse formula specifies the answer; a factorization provides a reusable way to compute it for each right-hand side.^[ref]

Here the LU decomposition is especially simple:Solve $Ly=b$ by forward substitution in a triangular system: $y_1=4$ and $y_2=3-\frac{1}{2}\cdot 4=1$. Then solve $Ux=y$ by backward substitution in a triangular system: $x_2=2$ and $x_1=(4-2)/2=1$. The same factors work when $b$ changes. If the whole matrix inverse is actually needed, its $j$th column is the solution of $Ax=e_j$, where $e_j$ is the $j$th standard basis vector.

Reversing several operations means undoing the last one first. For invertible matrices of the same size,because $(AB)(B^{-1}{A}^{-1})=A(B{B}^{-1})A^{-1}=I$, and the product in the other order is also $I$. This is why a change-of-basis matrix uses its matrix inverse to reverse the direction of coordinate conversion.

The coefficient matrix and right-hand side areFor an LU decomposition with unit diagonal in the lower factor, subtract row 1 from row 2, add twice row 1 to row 3, and then add the new row 2 to row 3. The elimination multipliers are $l_{21}=1$, $l_{31}=-2$, and $l_{32}=-1$. ThusMultiplication verifies $LU=A$. Forward substitution in $L\mathbf{y}=\mathbf{b}$ gives $y_1=4$, $y_2=-4$, and $y_3=-2$. Back substitution then gives $x_3=-1$, $x_2=5/3$, and $x_1=1/6$:Every pivot is nonzero, so no row permutation is needed and the linear system has a unique solution.

Gaussian elimination uses first-column multipliers $-2,2,-3$, second-column multiplier $2$ in the last row, and third-column multiplier $1$ there. Recording these in a unit lower-triangular matrix gives the LU decompositionForward substitution in $Ly=b$ gives $y=(-2,-2,8,1{)}^T$. Back substitution gives $x_4=1$, $-3x_3+2x_4=8$, $x_2+2x_3+2x_4=-2$, and $2x_1-x_2+3x_3+2x_4=-2$. Hence the solution is

Eliminate the first entries of rows two, three and four using multipliers $a^3,a^2,a$. All remaining subdiagonal entries are then already zero. The unit-lower-triangular LU decomposition isMultiplication verifies $LU=A$. Since $\gamma \ne 0$, all pivots are nonzero. Forward substitution in $Ly=b$ givesBackward substitution in $Ux=y$ gives $x_4=0$, $x_3=-a^2$, $x_2=0$, and $x_1=\gamma +a^4=1$. ThusDirect substitution yields $Ax=(\gamma ,0,0,a\gamma {)}^T$ as a check.

Use columnwise partial pivoting: select the largest absolute entry in the current column and interchange rows. In the first column the pivot is $4$, so interchange rows 1 and 2. The multipliers are $1/2$ and $-1/2$, and elimination givesThe second pivot is $5/2$, so interchange the two remaining rows. Their previously stored first-column multipliers must also be interchanged. The final multiplier is $(1/2)/(5/2)=1/5$, giving the LU decompositionThe permutation matrix orders the original rows as $2,3,1$. Multiplication verifies the displayed identity.

If “column pivoting” instead denotes interchanging columns rather than searching within a column, that convention gives $AQ=\tilde{L}\tilde{U}$ withThis second identity uses a different pivot convention; it does not change the row-pivoted answer above.

Gaussian elimination without row exchanges gives the LU decompositionBecause $L$ has unit diagonal and $U$ is upper triangular,

Solving the two triangular systems givesand

Gaussian elimination gives the LU decompositionThe prescribed diagonal entries of $L$ are visible, and direct multiplication gives $LU=A$.

Choose a shift $\mu$ which is not an eigenvalue. Inverse iteration applies power iteration to $B=(A-\mu I{)}^{-1}$, implemented by a linear system solve rather than by forming an explicit matrix inverse:A single LU decomposition of $A-\mu I$ can be reused for all the solves at this fixed shift. An eigenpair $A{u}_j={\lambda }_j{u}_j$ transforms intoThus an eigenvalue ${\lambda }_{\ast }$ uniquely closest to $\mu$ becomes the dominant eigenvalue of $B$. For a diagonalizable matrix, the argument in the preceding subpart gives convergence of diagonalizable fixed-shift inverse iteration, provided the starting coefficient in the target eigenspace is nonzero, with power iteration direction error $O(q_{\mu }^k)$, whereFor any prescribed simple eigenvalue, taking a sufficiently close but unequal shift makes the numerator small while the denominator stays close to its positive separation from the remaining eigenvalues. This makes $q_{\mu }$ small and gives very fast convergence per iteration. The Rayleigh quotient of $v_k$ estimates ${\lambda }_{\ast }$ directly. If ${\beta }_k$ estimates the associated eigenvalue of $B$, the corresponding estimate is $\mu +{\beta }_k^{-1}$.

The selection principle also applies when the other eigenvalues have nontrivial blocks in the Jordan normal form: their contributions acquire powers of $k$, multiplying strictly smaller geometric factors. A simple uniquely closest eigenvalue still attracts the direction when the Riesz projection of $v_0$ onto its generalized eigenspace is nonzero. For nonreal target eigenvalues, allow complex shifts and arithmetic; a real shift cannot distinguish a conjugate pair of equal distances. Setting $\mu ={\lambda }_{\ast }$ makes the solve singular, and an exactly zero starting target component prevents convergence to that target in exact arithmetic. When ${\lambda }_{\ast }<\mu$ is real, account for the sign behavior of fixed-shift inverse iteration.

A rank-one matrix update changes a matrix $A$ by an outer product $u{v}^T$. For real vectors $u,v\in {\mathbb{R}}^n$, its action on an input vector $x$ isThe dot product $v^{T}x$ reads one scalar from the input, and the correction moves the output along $u$. All correction outputs therefore lie in one linear span. If either vector is zero, the update is zero; otherwise the correction is a rank-one matrix. The full updated matrix need not have rank one.

For example, chooseThe update sends $x=(x_1,x_2{)}^T$ to the correction $(3x_1-x_2)(1,2{)}^T$. Although all four entries change, there is only one direction of correction. Adding it to the identity matrix gives $B=\left(\begin{array}{cc}4& -1\\ 6& -1\end{array}\right)$.

This special structure allows existing work to be reused. The matrix determinant lemma updates the determinant using one scalar, and the Sherman–Morrison formula updates the matrix inverse using an outer product. Such formulas are useful when a linear system changes slightly after a new observation or a parameter adjustment: the unchanged part can retain its LU decomposition. The term rank-one describes the rank of the correction, not the size of the entry changes. ^[ref].

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 Sherman–Morrison formula computes the matrix inverse after a rank-one matrix update. If $A$ is an invertible matrix and $\delta =1+v^T{A}^{-1}u\ne 0$, thenThe inverse correction is itself an outer product, divided by the scalar $\delta$. The matrix determinant lemma shows that the nonzero-denominator condition is exactly the condition that the updated matrix remains an invertible matrix.

For $A=I$, $u=(1,2{)}^T$, and $v=(3,-1{)}^T$, we have $\delta =2$. Thus the computed inverse isMultiplication in either order gives the identity matrix. The result reuses the original inverse $I$ and the same correction vectors, rather than solving independently for all four inverse entries.

Often only the solution of an updated linear system is needed. If $A{x}_0=b$ and $Az=u$, thenprovided $1+v^{T}z\ne 0$. The two solves use the same LU decomposition of $A$. This expresses the computational benefit without requiring an explicitly stored matrix inverse. Strang's Lecture 14, transcript pp. 9–10 explains this reuse of the original factorization.

To see why the inverse correction works, first consider $A=I$ and put $s=v^{T}u$. The rank-one matrix $R=u{v}^T$ satisfies $R^2=sR$. Expandingalso works in the reverse order. The general case follows by factoring out $A$ and replacing $u$ by $A^{-1}u$. A matrix identity has reduced to cancellation of scalar coefficients.

Historically, Jack Sherman and Winifred J. Morrison studied updating an inverse when a single matrix entry changes in their ^[ref]. Such an entry change is the special rank-one matrix update $\alpha e_i{e}_j^T$, with standard basis vectors $e_i,e_j$. The reference and the earlier 1949 abstract on row or column changes are recorded in Henderson and Searle, On Deriving the Inverse of a Sum of Matrices (1981), references 40–41. This distinguishes the specific original setting from the more general $u{v}^T$ formula used here.