Solve the maximum-weight assignment problem forbidding fixed points, obtaining a cycle cover of a directed graph whose weight bounds every Hamiltonian cycle above. Remove a lightest edge from each graph cycle. Each graph cycle has at least two edges, so at least half its nonnegative weight survives. Connect the resulting disjoint graph paths cyclically; completeness supplies the connectors and their nonnegative weights cannot reduce the retained sum. The Hungarian algorithm and linear-time patching give a polynomial time approximation algorithm. Negative weights invalidate a universal multiplicative half guarantee: when every weight is $-1$, every tour has weight $-n<(-n)/2$.

The Harrison-Peebles-Zeldovich spectrum is the scale-invariant primordial growing-mode spectrum: in a fixed conformal time slice before cosmological horizon crossing, the matter power spectrum is proportional to ${\tau }^{4}k$ in the usual growing-mode density convention. At horizon entry ${\tau }_H\sim k^{-1}$, its dimensionless mass variance $k^{3}P(k,{\tau }_H)$ is independent of $k$. This statement fixes a spectral shape, not its amplitude. Radiation domination subsequently suppresses small-scale density growth through the Mészáros effect, producing the asymptotic matter power spectrum $P\propto k^{-3}{\ln }^2(k/k_{\mathrm{eq}})$ after matter-radiation equality.

For a statistically isotropic three-dimensional matter power spectrum $\mathcal{P}(k)=A{k}^n$, the Fourier transform gives $\xi (r)=A(2{\pi }^2{)}^{-1}{r}^{-n-3}{\int }_0^{\infty }{u}^{n+1}\sin udu$. The improper integral converges at zero precisely when $n>-3$ and at infinity when $n<-1$; it is absolutely convergent only when $n<-2$. Within this range its positive coefficient is $\Gamma (n+2)\sin [\pi (n+2)/2]$, interpreted continuously as $\pi /2$ at $n=-2$. Outside this range, cutoffs, smoothing or an explicitly stated distributional interpretation are necessary; dimensional scaling alone does not establish an ordinary positive power-law correlation function.

For an isotropic matter power spectrum $P(k)=Ak$ on $0\le k\le k_{\max }$ and zero elsewhere, put $K=k_{\max }r$. Angular integration of the Fourier transform gives $\xi (r)=A(2{\pi }^{2}r{)}^{-1}{\int }_0^{k_{\max }}{k}^2\sin (kr)dk$, and two integrations by parts yield the displayed answer. Its apparent origin singularity is removable, with $\xi (0)=A{k}_{\max }^4/(8{\pi }^2)$. The sharp cutoff creates oscillatory, including negative, correlations without violating positivity of the spectrum.

For $P_{\delta }(k)=A{k}^n$, the cosmological Poisson equation gives $P_{\phi }(k)=(4\pi G{a}^2\bar{\rho }{)}^2{P}_{\delta }(k)/k^4$. The contribution to variance per logarithmic wavenumber is $k^3{P}_{\phi }(k)/(2{\pi }^2)$, giving the displayed expression and rms scaling ${\phi }_{\mathrm{rms}}(R)\propto R^{(1-n)/2}$ for a band around $k\sim R^{-1}$. The Harrison-Zeldovich spectrum $n=1$ has equal potential variance per logarithmic interval. An uncut power law over all scales has divergent total potential variance for every $n$, so the scale-local amplitude must not be confused with a finite global rms.

The parameter ${\sigma }_8$ is the present linear rms density contrast averaged in a spherical top-hat of comoving radius $8h^{-1}\mathrm{Mpc}$, with $h=H_0/(100\mathrm{km}{\mathrm{s}}^{-1}\mathrm{Mp}{\mathrm{c}}^{-1})$. Thus ${\sigma }_8^2=(2{\pi }^2{)}^{-1}{\int }_0^{\infty }{k}^2{P}_m(k,0)|W(k{R}_8){|}^{2}dk$. It specifies an amplitude on a chosen scale rather than the complete matter power spectrum; converting cluster abundance into this parameter also requires a spectral shape and background cosmology.

For a complex $n$ by $n$ matrix, triangularization gives $\mathrm{tr}(A^k)={\sum }_j{\lambda }_j^k$. The zero power sums force a finite complex multiset to vanish criterion makes every diagonal eigenvalue zero. A strictly upper-triangular $n$ by $n$ matrix has zero $n$th power: every nonzero product entry would require $n$ strictly increasing index steps. Similarity then gives $A^n=0$.

A two-by-two matrix $M$ with zero trace satisfies $M^2=-(\det M)I$ by the Cayley-Hamilton theorem. Over the complex numbers, either $\det M\ne 0$ and its two distinct eigenvalues make it diagonalizable, or $M^2=0$. A matrix commutator has zero trace, so this alternative applies to it. Diagonalization over the real numbers need not follow when $-\det M<0$.

For any fixed real $n$-by-$n$ matrix $A$, as the real parameter $t$ tends to zero,The big O notation means the remainder is bounded in absolute value by $C{t}^2$ for some constant $C$ near zero. The determinant stays positive for sufficiently small $t$, so its oriented volume factor is also its ordinary volume factor. Thus the trace is the first-order fractional volume change, measured from the identity matrix.

A proof follows directly from multilinearity of the determinant. Each column of $I+tA$ is $e_j+tA{e}_j$. The constant term chooses all the standard basis columns and equals one. A term containing exactly one factor $t$ replaces just column $j$ by $A{e}_j$; expanding that vector in the standard basis leaves only its $e_j$ component, $a_{jj}$, because every other choice repeats a column. Summing gives $\mathrm{tr}A$. Terms with two or more replacements have order $t^2$ or higher. This also proves the derivative of the determinant at the identity matrix.

This coefficient has a direct visual meaning. At the point $e_j$, the linear map $x\mapsto Ax$ has component $a_{jj}$ along direction $e_j$. In a small step $x\mapsto x+tAx$, these are the first-order changes of the square's or box's sides in their own directions. Summing them gives its fractional area or volume change; the off-diagonal entries initially change shape rather than contributing to this first-order total.

For the constant-coefficient linear system of differential equations $x^{\prime }=Ax$, the exact linear flow is $x(t)=e^{tA}x(0)$, using the matrix exponential. Its volume factor isThis is the matrix exponential determinant identity. One can derive it without diagonalization: set $E(t)=e^{tA}$, whose matrix inverse is $E(-t)$, and use $E^{\prime }=AE$ in Jacobi's formula to get $V^{\prime }=\det E\mathrm{tr}(E^{-1}AE)=(\mathrm{tr}A)V$. The scalar differential equation with initial value one gives the displayed exponential function. Thus positive trace causes volume expansion, negative trace causes contraction, and zero trace preserves volume, even when individual directions behave differently.

In two dimensions, compare four generators at $t=0.4$:The first and third diagonal matrices expand or contract both directions. The second expands horizontally and contracts vertically by reciprocal factors, making a rectangle of unchanged area. For the last nilpotent matrix, $A^2=0$, so its matrix exponential is exactly $I+tA$; it sends $(x,y)$ to $(x+ty,y)$, a shear mapping. Zero trace allows substantial shape change and does not mean the flow map is stationary.

The first-order statement and the exact flow map should be distinguished. For $A=\mathrm{diag}(1,-1)$, $\det (I+tA)=1-t^2$, whereas $\det (e^{tA})=1$ for all real $t$. Zero trace eliminates the first-order change in the approximate step, and it preserves volume exactly in the matrix exponential flow. The examples use an abstract parameter $t$ and coordinate vectors; no physical units are assumed.

The action $(A,B):M\mapsto AM{B}^{-1}$ preserves the quadratic form $-\det M$ on real two-by-two matrices. Its kernel consists of the simultaneous scalar pairs $(I,I)$ and $(-I,-I)$. The differential $(a,b):M\mapsto aM-Mb$ is injective on the two traceless Lie algebras, and both source and target have dimension six. Its image is therefore open and, since the source is connected, equals the identity component of a Lie group $S{O}_0(2,2)$. This gives a two-sheeted covering map onto the identity component, not onto the disconnected full special orthogonal group $SO(2,2)$.

The assertion assumed for earlier cases during an induction proof. It is a conditional assumption inside the induction step, not an assumption that all cases already hold.

The starting instance of a mathematical induction proof, established directly before the inductive step is applied. The implication $P(n)\Rightarrow P(n+1)$ alone can be true when every instance is false. For example, ${\sum }_{j=1}^{n}j=n(n+1)/2+C$ with $C\ne 0$ has a formally correct successor calculation but a false base case.

Assuming the induction hypothesis for a fixed integer, establish the next instance. Together with the induction base case, this proves every succeeding instance by mathematical induction. The hypothesis is conditional within this argument, rather than an unsupported assumption that the desired theorem is already true.

An objective spatial second-rank tensor transforms by the displayed rule under every rigid observer change $x^{\ast }=c(t)+Q(t)x$. This permits time-dependent rotations, not merely constant rotations. Cauchy stress tensor is objective because contact traction and surface normal both rotate by Q. The symmetric rate-of-strain tensor is objective because the additional observer spin in the velocity gradient is antisymmetric.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

The coefficient $m_k$ counts matchings in a graph with $k$ edges. For a bipartite graph with $n$ vertices on each side, $m_n$ counts perfect matchings and equals the permanent of a matrix of its bipartite adjacency matrix. Positive activity $\lambda$ makes $Z_G$ the normalizing constant of the weighted matching Markov chain.

The term near-perfect matching in a graph depends on the parity convention. On an odd-order graph, it commonly means a matching in a graph leaving exactly one vertex unmatched. For example, a single edge of a triangle in a graph has this property.

For the even-order convention used in matching in a graph sampling, a graph with $2n$ vertices has a near-perfect matching in a graph when it has $n-1$ edges and exactly two unmatched vertices in a matching. In a bipartite graph with equal parts, those unmatched vertices are one in each part. A perfect matching leaves none unmatched; the convention must be fixed when defining a weighted matching Markov chain.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.

For a symmetric stress-energy tensor with compact support and ${\partial }_b{T}^{ab}=0$ in Minkowski spacetime, let $I^{ij}=\int T^{00}{x}^i{x}^j{d}^{3}x$. Two integrations by parts give ${\dot{I}}^{ij}=\int (T^{0i}{x}^j+T^{0j}{x}^i)d^{3}x$ and the displayed identity. Compact support removes the boundary fluxes. The support should stay bounded over the time interval used when differentiating the integrals.

The number of neutrons in an atomic nucleus. Two isotopes of the same chemical element differ in neutron number while sharing an atomic number.