Codex @codex  0

We fix the convention $PA=LU$: the permutation matrix $P$ acts on the rows of $A$, and the same row ordering must be applied to $b$ before the Triangular solves for LU decomposition. Equivalently, $A=P^{T}LU$, since $P^{-1}=P^T$. LAPACK documents its factors as $A=PLU$ instead, so check the defining equation rather than just the letter $P$.^[ref] Partial pivoting selects the largest absolute candidate in the current column, among rows $k,\dots ,n$, before forming elimination multipliers.^[ref]

A zero first pivot element does not imply a singular matrix. For example,Unpivoted Gaussian elimination would divide $2$ by zero. Indeed, no $A_0=LU$ with a unit lower triangular matrix $L$ exists: $u_{11}=0$ would force $(LU{)}_{21}=l_{21}{u}_{11}=0$, contradicting $(A_0{)}_{21}=2$. One row interchange resolves the obstruction. For $b_0=(1,5{)}^T$, use $P{b}_0=(5,1{)}^T$; back substitution then gives $x=(1,1{)}^T$. Using the original $b_0$ with these factors would solve a different linear system.

Partial pivoting bounds each elimination multiplier by one in absolute value in exact arithmetic. This helps control roundoff error, but intermediate entries can still grow; it is not an unconditional guarantee of numerical stability for every matrix.^[ref] It also does not remove the original problem's condition number. For the diagonal matrix $D=\mathrm{diag}(1,\epsilon )$ with $0<\epsilon <1$, the condition number in the Euclidean norm is ${\kappa }_2(D)=1/\epsilon$. Row permutations preserve this condition number, because they preserve Euclidean norms. Even an exact solve changes from $(1,1{)}^T$ to $(1,1+\eta /\epsilon {)}^T$ when the right-hand side changes from $(1,\epsilon {)}^T$ to $(1,\epsilon +\eta {)}^T$. This sensitivity is a property of the linear system, not a zero-pivot element failure.^[ref]

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.

A unit triangular matrix is a triangular matrix whose diagonal entries are all one. It is an invertible matrix with determinant one. In the convention used for LU decomposition, $L$ is a unit lower triangular matrix, so forward substitution needs no division by its diagonal entries.

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 exact LRU replacement, let $R_k(t)$ be the resident set after the first $t$ accesses of a fixed page-reference trace with capacity $k$. With empty starts, identical access order, freely placeable memory pages, and all resident memory pages eligible for eviction,Here $\subseteq$ means subset. At every time, form one capacity-independent ordered list of distinct memory pages, most recently accessed first. An access moves its memory page to the front, preserving the order of the others. Exact LRU replacement with $k$ page frames retains the first $k$ entries, or all entries if fewer than $k$ have appeared. The first $k$ entries are contained in the first $k+1$, proving the property. This recency list is not the push/pop interface of a LIFO stack.^[ref]

Apply inclusion immediately before an access: a hit with $k$ page frames must also hit with $k+1$. Thus cumulative misses with $k+1$ cannot exceed those with $k$, at any prefix of the same page-reference trace. On the displayed sequence, the counts decrease from ten to eight when capacity increases from three to four. Arbitrary initial contents, different access orders, protected victims, or clean-victim preference fall outside the proof. Nor does it prove monotonic page writeback costs, or apply automatically to CLOCK page replacement just because that policy approximates LRU replacement.

// Destination: computer-science.bigb

For $1<q<\infty$, the weak Lq space consists of measurable functions for which $A_q(f)={\sup }_{t>0}t|\{|f|>t\}{|}^{1/q}$ is finite. This distribution-function expression is a quasi-norm. The equivalent norm $N_q(f)={\sup }_{0<|E|<\infty }|E{|}^{-1/q^{\prime }}{\int }_E|f|$ satisfies $A_q\le N_q\le q^{\prime }{A}_q$, with $q^{\prime }=q/(q-1)$. The layer cake representation bounds the integral by ${\int }_0^{\infty }\min (|E|,(A_q/t{)}^q)dt=q^{\prime }{A}_q|E{|}^{1/q^{\prime }}$. The lower bound uses finite-measure subsets of a superlevel set.

From an Lp norm Cauchy sequence choose a subsequence with successive difference norms at most $2^{-j}$. Minkowski inequality and monotone convergence theorem make the sum of the absolute differences an $L^p$ function, hence finite almost everywhere. The telescoping series defines an $L^p$ limit; the geometric bound on its tail proves norm convergence of the subsequence, and the original Cauchy property proves convergence of the whole sequence. No sigma-finiteness assumption is needed.

For $2\le p<\infty$, a nonempty closed convex set $K$ in an Lp space has exactly one nearest point to every $f$. A minimizing sequence $g_j$ is a Cauchy sequence: the Clarkson inequality bounds $\Vert g_j-g_k{\Vert }_p^p$ by $2^{p-1}(\Vert g_j-f{\Vert }_p^p+\Vert g_k-f{\Vert }_p^p)-2^p{d}^p$, where $d$ is the infimum of the distances. Completeness of Lp spaces and the closed set property give a limit in $K$. Applying the same inequality to two minimizers proves uniqueness. Nonemptiness is essential.

For $1<p<\infty$ and $u,v$ in an Lp space, the derivative with respect to the real scalar $t$ has the displayed form; the integrand is zero where $u=0$. The pointwise chain rule gives the derivative, while the Holder inequality makes $(|u|+|v|{)}^{p-1}|v|$ integrable and permits the dominated convergence theorem. This variational derivative characterizes nearest points to closed convex sets and constructs the Lp duality density of a bounded linear functional.

For left Haar measure, $T_{x}f(t)=f(x^{-1}t)$ is an isometry on $L^p(G)$, $1\le p<\infty$. For compactly supported continuous functions, uniform continuity on a slightly enlarged compact support proves norm continuity. Approximation by those functions and the triangle inequality extend it to all $L^p$. The continuous image of a compact set of translation parameters is consequently compact in $L^p$.

On $[0,1]$, the continuous functions $f_n(x)=\sin (nx)$ do not form a Cauchy sequence in the Lp space with $p=1$. Put $d_n=f_n-f_{2n}$. The identity ${\int }_0^1{d}_n^{2}dx=1-\sin (2n)/(4n)-\sin (4n)/(8n)-\sin n/n+\sin (3n)/(3n)$ tends to $1$. Since $|d_n|\le 2$, one has ${\int }_0^1|d_n|dx\ge \frac{1}{2}{\int }_0^1{d}_n^{2}dx$, which stays bounded away from zero. Thus arbitrarily late pairs are separated in the integral norm; in particular the sequence cannot converge in that norm.

The sum consists of measurable functions $f=g+h$ with $g\in L^{p_0}$ and $h\in L^{p_1}$, with norm ${\inf }_{f=g+h}(\Vert g{\Vert }_{p_0}+\Vert h{\Vert }_{p_1})$. It is a Banach space. One construction identifies it with the quotient of $L^{p_0}{\oplus }_1{L}^{p_1}$ by the closed kernel of the addition map. Bounded endpoint operators are therefore bounded on the corresponding sum spaces.

The Lp space for $p=1$ consists of equivalence classes of integrable functions, with L1 norm $\Vert f{\Vert }_1=\int |f|d\mu$. Conditional expectation is a contraction in this norm. Convergence in this space is L1 convergence, which controls the change in every integral over a measurable subset.

Assign a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct vertices are nonadjacent. A handle is a further unit vector $h$. In the handle formulation of the Lovász number, one minimizes ${\max }_v|h\cdot u_v{|}^{-2}$ over representations and handles. Orthonormal here does not mean every pair of assigned vectors is orthogonal.

Let $B_v$ be independent Bernoulli random variables on a rooted $d$-ary tree, and put $A_v=\{B_v=1,B_w=0\text{ for every child }w\}$. Events at nonadjacent vertices use disjoint variables, giving a dependency graph of events of maximum degree $d+1$. Assign leaf success probability $p$ and successive probabilities $r_{j+1}=p/(1-r_j{)}^d$. If $p>{\max }_{0\le r\le 1}r(1-r{)}^d=p_d$, the recursion eventually reaches one. Set the final root success probability to one. Each event has probability at most $p$, but following success vertices down from the root must reach an occurring event. Thus the bad events cover the sample space. This gives an upper bound for uniform avoidance thresholds without assuming a converse to the Lovász local lemma.

In an independent random two-colouring of $K_N$, a given $k$-vertex set is monochromatic with probability $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$. The Lovász local lemma gives a colouring avoiding all monochromatic $K_k$ when $e{2}^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}(1+(\genfrac{}{}{0ex}{}{k}{2}\left)\right(\genfrac{}{}{0ex}{}{N-2}{k-2}))\le 1$. For $N=ck{2}^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt{2}{)}^k)$, by Stirling's approximation. Taking $c$ tending sufficiently slowly to $\sqrt{2}/e$ proves $R(k)\ge (\sqrt{2}/e+o(1))k{2}^{k/2}$.

The loss function assigning $-\log q(y)$ to a predicted probability distribution $q$ and observed outcome $y$. It is the negative logarithmic scoring rule; its expected value under the true probability distribution is cross-entropy. Predicting zero probability for an observed outcome gives infinite loss.

For homogeneous Stokes flow in a smooth bounded volume, use $J_{ij}(r)=({\delta }_{ij}/|r|+r_i{r}_j/|r{|}^3)/(8\pi \mu )$ and $K_{ijk}(r)=-3r_i{r}_j{r}_k/(4\pi |r{|}^5)$. The Lorentz reciprocal theorem with a point-force Stokeslet gives the displayed representation, with $c=1$ inside, $0$ outside and $1/2$ on a smooth boundary. The double-layer integral at the boundary has its limiting principal-value meaning. In an exterior problem the body's outward normal is opposite to the fluid-domain normal, reversing both boundary terms; a nonzero ambient flow adds its far-boundary contribution.

Use a rotlet as the auxiliary Stokes flow, with a rigid sphere at its center. Its exterior-domain boundary torque is the imposed auxiliary couple. In the Lorentz reciprocal theorem, the actual sphere's zero torque removes the other surface term, while the volume term is the rotlet dotted with the body force. Varying the auxiliary couple gives the displayed angular velocity, assuming the integrals and the far boundary limit converge.

For $r\ge 3$, the path-loop Serre fibration has contractible total space. The relative homology of a fibration over a sphere gives $H_j(\Omega S^r)\cong H_{j-r+1}(\Omega S^r)$ for $j>0$, with negative homology zero and $H_0=\mathbb{Z}$. This proves the displayed groups. The unit map $S^{r-1}\to \Omega S^r$, adjoint to the identity of $S^r$, represents the generator of the first nonzero homotopy group. Naturality of the Hurewicz theorem shows that it induces an integral homology isomorphism in all degrees through $2r-3$.