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.

An algorithm for solving a linear system $Ax=b$. Tolerance and conditioning can limit a differential-equation calculation even when its time-stepping method is stable.

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.

Eliminate the first column using multipliers $3$ and $2$. The two residual rows have second entries zero and four, so interchange their order for the next pivot. One resulting Pivoted LU decomposition isThe factors below the first pivot must follow the permuted row order, which is why $L$ contains $2$ before $3$. Direct multiplication gives rows $(3,1,4)$, $(6,6,6)$ and $(9,3,1)$ in both $PA$ and $LU$. This checks the permutation convention rather than confusing $PA=LU$ with a different placement of $P$.

Write $U=E{E}_5{E}_4{E}_3{E}_2{E}_{1}M$ and put $F_i=E{E}_{i}E$. Inserting $E^2=I$ between adjacent elimination matrices givesEach $E_i^{-1}$ has the restricted lower triangular pattern in part (b)(v). Also $F_i^{-1}=E{E}_i^{-1}E$, as direct multiplication verifies. Hence every $F_i^{-1}$ is lower triangular. Their product is lower triangular by the allowed closure property, proving the required Pivoted LU decomposition with $L=F_1^{-1}\cdots F_5^{-1}$.

Explicitly,The multipliers in rows three and four of $L$ are permuted along with the rows of $M$; simply keeping the unpermuted elimination multipliers would give the wrong product. This is the mechanism in conjugating elimination matrices across a row permutation.

Choose a fixed time increment $h=\Delta t>0$, let $t_n=nh$, and approximate $\mathbf{c}(t_n)$ by ${\mathbf{c}}_n$. The Backward Euler method evaluates the transport term at the new time:Rearrange to the linear systemAlthough $A$ is a singular matrix, $B$ is an invertible matrix for every $h>0$. In each row, its diagonal entry is $1+2h$ and the sum of the absolute values of its off-diagonal entries is $2h$; hence it is a strictly diagonally dominant matrix. Its Gershgorin discs have centre $1+2h$ and radius $2h$, excluding zero. In particular, the zero eigenvalue of $A$ becomes an eigenvalue $1$ of $B$.

The algorithm uses Reusing LU factors for multiple right-hand sides:

Both triangular solves use the factors of $I-hA$. The LU factorization of the singular transport matrix $A$ from part (a) is not a solver for this new linear system. No matrix inverse needs to be formed. Since $A$ and $h$ are fixed, the same LU factorization serves every step; only the right-hand side changes. A varying $\mathbf{b}(t)$ would give $r_n={\mathbf{c}}_n-h\mathbf{b}(t_{n+1})$ without changing these factors.

As a check, multiplying the update by $1^T$ givesexactly reproducing the inventory balance at the sampled times, apart from roundoff error. The Backward Euler method has temporal global error $O(h)$ for smooth solutions, so its A-stability does not remove the need to select $h$ for accuracy.

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.

Given Pivoted LU decomposition $PA=LU$, the linear system $Ax=b$ is equivalent to $LUx=Pb$. Introduce the intermediate vector $y=Ux$: first use forward substitution to solve $Ly=Pb$, then back substitution to solve $Ux=y$. With unpivoted LU decomposition, $P=I$ is the identity matrix, so the first right-hand side is simply $b$.^[ref]

For the factors in Computed three-by-three LU decomposition and $b=(7,23,26{)}^T$, forward substitution givesThen back substitution givesDirect matrix multiplication verifies $A(1,2,3{)}^T=(7,23,26{)}^T$. More generally, the back substitution recurrence isThe direction matters: the last row contains only $x_n$, whereas the first row generally involves every unknown. No dense matrix inverse is needed for either triangular solve.