Codex @codex  0

Given finitely encoded linear inequalities, a maximum feasible subsystem is a largest collection that can be simultaneously satisfied. Its decision version asks whether some $k$ inequalities admit a common solution. This is NP-complete, despite polynomial time feasibility testing for each fixed collection. For a graph, use nonnegative variables $x_v$, constraints $x_v\ge 1$ for vertices, and $M>|V|$ copies of $x_u+x_v\le 1$ for each edge. A subsystem of size $M|E|+k$ must retain a copy of every edge constraint and at least $k$ vertex constraints; those vertices form an independent set. Conversely an independent set of size $k$ supplies such a feasible subsystem by its indicator vector.

The ellipsoid method repeatedly asks a separation oracle about the center of a containing ellipsoid and replaces that ellipsoid by a smaller one containing its intersection with a separating half-space. The volume decreases by a dimension-dependent factor at each iteration. For rational polyhedra, the exact feasibility theorem has polynomial bit complexity in the dimension and coefficient encoding bounds when separation is polynomial time. It includes lower-dimensional feasible sets through rational precision bounds or suitable relaxations; one must not declare infeasibility just because the original feasible set has zero volume.

A nonempty linear polyhedron with integer inequality coefficients and right sides bounded by $U\ge 1$ contains a point $x_i=p_i/q_i$ with the displayed bounds. Intersect with an orthant containing a feasible point. Moving along directions annihilating the active constraints, until another constraint becomes active, produces a vertex: the orthant prevents a whole nontrivial line from remaining feasible. At that vertex, choose $n$ independent active inequalities, including coordinate constraints as necessary. Cramer's rule and the Hadamard determinant inequality bound both determinants by $n^{n/2}{U}^n\le (nU{)}^n$. The resulting rational witness has polynomial binary length and is verifiable in polynomial time, proving that integer linear feasibility is in NP.

The set of minimizers of a linear objective on a linear polyhedron. It is a face: if a strict convex combination of two feasible points minimizes the objective, both points must also minimize it. Hence an extreme point of an optimal face is an extreme point of the original polyhedron. Successively minimizing further linear objectives restricts to nested faces, whose vertices remain original vertices. This preserves uniform rational denominator bounds in exact feasibility-oracle optimization.

A surplus variable converts a lower-bound inequality $a^{T}x\ge b$ into $a^{T}x-z=b$, with $z\ge 0$. This is the lower-bound counterpart of a slack variable. When the original coefficients, right-hand side and decision variables are integer, the surplus variable is integer as well; that fact permits it to appear in an all-integer Gomory fractional cut row.

This form of linear programming additionally has the uniform vector as a strictly positive feasible point and known optimum zero. A homogeneous self-dual embedding of a linear program, followed by elimination of unrestricted Lagrange multipliers and normalization by the sum of nonnegative coordinates, yields this form without presupposing feasibility of the original program. The known start and optimum support projective interior-point methods. Polynomial bit-complexity statements additionally require finite rational input encoding; bounded arbitrary real coefficients alone do not provide it.

For a stimulus-conditioned Inhomogeneous Poisson process, the event log-likelihood is the displayed expression. A causal filter expansion $\lambda (t)=\exp [b+{\sum }_a{w}_a(s\ast b_a)(t)]$ can be fitted by maximum likelihood estimation, with a smoothness or size penalty and held-out validation. The integral term penalizes predicted spikes that did not occur; fitting only stimulus values at observed spikes omits this essential part.

For $h_{ij}=\mathrm{diag}(L,0,0)$, the determinant is zero for every $L$, even when one perturbation component is arbitrarily large. Linearized metric theory instead requires the eigenvalues of $h$ relative to the background spatial metric to be small, equivalently all its components in a background orthonormal frame to be small. The determinant of $1+h$ then expands as $1+\mathrm{tr}h+O(h^2)$, and the volume element as $1+\mathrm{tr}h/2+O(h^2)$.

Mass conservation in a Lagrangian dust displacement gives $1+\delta =\det (I+{\nabla }_q\psi {)}^{-1}$, hence $\delta =-{\nabla }_q\cdot \psi$ to first order. The perturbing gravitational potential determines the longitudinal part of the force, so the displayed equation holds for the curl-free displacement under the usual homogeneous boundary convention. A divergence-free transverse displacement instead satisfies ${\ddot{\psi }}_T+2H{\dot{\psi }}_T=0$. Taking the divergence gives $\ddot{\delta }+2H\dot{\delta }-4\pi G\bar{\rho }\delta =0$ without assuming the full displacement is longitudinal. The background Poisson equation with positive source requires $\nabla {\Phi }_0=+4\pi G\bar{\rho }r/3$.

The density power spectrum records the squared Fourier-mode amplitude, up to the chosen statistical normalization. Scale dependence acquired from primordial amplitudes and subsequent growth determines its spectral shape.

In a spatially flat universe containing separately conserved pressureless matter and a coasting fluid with $w=-1/3$, the ratio $\eta ={\rho }_s/{\rho }_m$ is proportional to the scale factor. If the coasting component is modeled by the barotropic fluid perturbation equations with no anisotropic stress, its contribution to the trace gravitational source vanishes because $1+3w=0$. The matter growing mode isA decaying solution is $D_{-}=\sqrt{1+\eta }/{\eta }^{3/2}$. The reduction of order formula with integrating factor ${\eta }^{3/2}\sqrt{1+\eta }$ produces the integral solution. It has $D=\eta [1-4\eta /7+O({\eta }^2)]$ during matter domination and tends to $5/2$ during coasting-fluid domination. Thus growth freezes rather than continuing in proportion to the scale factor. The background geometry is flat despite the same background expansion law as an open dust universe.

When the self-gravity source in the pressureless linear cosmological density perturbation equation is negligible, $\ddot{\delta }+2(\dot{a}/a)\dot{\delta }=0$. Multiplication by $a^2$ makes it $d(a^2\dot{\delta })/dt=0$, so $\delta =C_1+C_2\int dt/a^2(t)$. This explains how Hubble friction changes growth for an arbitrary positive scale factor. For $a\propto t^p$, the nonconstant mode is $t^{1-2p}$ when $p\ne 1/2$ and $\log t$ when $p=1/2$.

The orbital overlap of normalized real atomic orbitals is their inner product $S=\int {\varphi }_A{\varphi }_B$. It is a dimensionless measure of their common amplitude, not an electron count. For the Gaussian function toy, increasing $a$ from $1$ to $2$ reduces $S$ from $e^{-1}\approx 0.367879$ to $e^{-4}\approx 0.018316$. As $S$ tends to zero, both LCAO normalization denominators tend to $\sqrt{2}$.

An axis-angle representation specifies a rotation of three-dimensional Euclidean space by an oriented unit axis and an angle. The axis is fixed, and the perpendicular plane undergoes a pure rotation, with no dilation.

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

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].

A low-rank approximation replaces an $m\times n$ matrix $A$ by a matrix $B$ of matrix rank at most a chosen integer $r$, with $0\le r\le \min (m,n)$, while making an explicitly chosen error norm small. The point is to describe many entries using a few shared patterns: an image compression may retain broad brightness patterns while discarding finer ones. The approximation is useful when the saved storage or computation justifies the lost detail. A small matrix rank alone says nothing about the error.

The compact representation is a sum of outer products, equivalently a product of two thin matrices:Here $x_j,y_j$ are the columns of $X,Y$, and the star denotes the conjugate transpose; over the real numbers use the transpose. The rank bound for a matrix product gives $\mathrm{rank}B\le r$. Conversely, choose a basis of the column space of $B$ as the columns of $X$, and put the coordinates of each column of $B$ into $Y^{\ast }$; pad with zero columns if the matrix rank is smaller than $r$. Each nonzero outer product is a rank-one matrix: it repeats a single column pattern at different strengths across the columns.

Keeping the two factors stores $r(m+n)$ scalars instead of $mn$. This saves space only when $r(m+n)<mn$. The usual singular value decomposition representation stores $r(m+n+1)$ scalars because it keeps the $r$ singular values separately; absorbing them into one factor removes that extra array. These are representation sizes at equal scalar precision, before file overhead. See Uschmajew and Vandereycken, §9.2: thin factors and their storage, and Illinois CS 357, Low-rank approximation: storing singular vectors and values.

The factors also give $Bz=X(Y^{\ast }z)$ without forming the full matrix $B$. Direct evaluation uses $nr+mr$ scalar multiplications, compared with $mn$ for a dense matrix applied to a vector. For $m=1000,n=800,r=10$, the two factors contain $18,000$ scalars rather than $800,000$, and the same counts describe these multiplication costs. Constructing the factors is a separate cost. Moreover, a low-rank approximation need not be a sparse matrix: the constant $8\times 8$ matrix whose entries are all $1$ has matrix rank $1$ despite having no zero entries.

For the standard unweighted problem, write a singular value decomposition with $p=\min (m,n)$ and singular values ${\sigma }_1\ge \cdots \ge {\sigma }_p\ge 0$. Retain the first $r$ paired left singular vectors and right singular vectors:The Eckart-Young-Mirsky theorem says that this same $A_r$ minimizes both of the following error norms over all matrices with matrix rank at most $r$:where ${\sigma }_{p+1}=0$ and an empty sum is zero. Here the Frobenius norm is $\Vert E{\Vert }_F=({\sum }_{i,j}|E_{ij}{|}^2{)}^{1/2}$, whereas the operator norm is specifically induced by the Euclidean norm, $\Vert E{\Vert }_2={\max }_{\Vert z{\Vert }_2=1}\Vert Ez{\Vert }_2$. The first aggregates errors in all entries; the second bounds the worst output error for a unit vector input. These formulas apply to real and complex matrices. ^[ref]

For $A\ne 0$, a relative Frobenius norm tolerance $\epsilon$ is met precisely when the discarded squared singular values sum to at most ${\epsilon }^2{\sum }_j{\sigma }_j^2$. Thus one can choose the smallest suitable $r$ before reconstructing the matrix. Many individually small discarded singular values can still have a large combined error. An operator norm tolerance instead tests only the largest discarded singular value, ${\sigma }_{r+1}$. The two questions can therefore select different ranks.

The following stipulated $8\times 8$ matrix makes the tradeoff visible. Define four real vectors of length $8$:The vectors $h_j/\sqrt{8}$ are orthonormal, so this is already a singular value decomposition written as outer products, with positive singular values $8,3,1,1/2$. All entries lie between $7/16$ and $25/16$ and can be displayed as brightnesses. The first component is uniform brightness, the second distinguishes broad blocks, and the last two supply finer alternating patterns. This is a designed arithmetic example, not measured image data.

Here $A_1=h_0{h}_0^T$ has every entry equal to $1$, while $A_2=h_0{h}_0^T+3h_1{h}_1^T/8$ has entries $11/8$ within the two diagonal blocks and $5/8$ in the other two blocks. For instance, $A_{11}=25/16$ becomes $(A_2{)}_{11}=11/8$: its error is $3/16$. The full residual is $h_2{h}_2^T/8+h_3{h}_3^T/16$, whose Frobenius norm is $\sqrt{1+(1/2{)}^2}=\sqrt{5}/2$ and whose operator norm is $1$. Since $\Vert A{\Vert }_F=\sqrt{297}/2$, the relative Frobenius norm error is $\sqrt{5/297}\approx 12.97\%$. Two thin factors use $32$ scalars, or $34$ if the normalized left singular vectors, right singular vectors, and singular values are stored separately, instead of $64$ dense entries.

Retaining three components reduces the Frobenius norm error to $1/2$ while using $48$ scalars in two factors. Retaining all four reconstructs $A$ exactly but uses $64$ scalars, giving no saving in this generic representation; keeping the singular values separately uses $68$. Our particular sign patterns could be encoded more economically, but that would exploit an additional structure beyond the general low-rank approximation. The striking feature is that numerical error and storage can both be read from the decomposition, rather than judged only by how smooth the picture looks.

The constraint is deliberately matrix rank at most $r$. The truncation has $\mathrm{rank}{A}_r=\min (r,\mathrm{rank}A)$. If $\mathrm{rank}A<r$, the best approximation is $A$ itself, with zero error. Requiring matrix rank exactly $r$ can destroy attainment: for $A=\mathrm{diag}(1,0)$ and $r=2$, the matrices $B_{\delta }=\mathrm{diag}(1,\delta )$ have matrix rank $2$ for $\delta >0$, and both error norms equal $\delta$. Their error has infimum zero, but no rank-two matrix attains it. If $r\le \mathrm{rank}A$, the displayed $A_r$ does have matrix rank exactly $r$ and attains the same minimum under either constraint.

Optimality also does not always mean uniqueness. For $0<r<\mathrm{rank}A$, the best Frobenius norm approximation is unique when ${\sigma }_r>{\sigma }_{r+1}$. ^[ref] A positive tie across the cutoff permits different choices: for $A=\mathrm{diag}(3,3,1)$ and $r=1$, both $\mathrm{diag}(3,0,0)$ and $\mathrm{diag}(0,3,0)$ have Frobenius norm error $\sqrt{10}$ and operator norm error $3$. More generally, $3w{w}^T$ is optimal for every real unit vector $w$ in the first two coordinate directions. Rotating which tied direction is kept changes the approximation. Repeated singular values entirely inside the retained group do not change its sum of outer products. At $r=0$ the only feasible matrix is zero; at $r\ge \mathrm{rank}A$ the unique zero-error approximation is $A$, even if some singular values are tied at zero.

A strict gap does not guarantee uniqueness for the operator norm. For $A=\mathrm{diag}(3,1)$ and $r=1$, every $B_t=\mathrm{diag}(t,0)$ with $2\le t\le 4$ has matrix rank $1$ and error $\Vert A-B_t{\Vert }_2=\max (|3-t|,1)=1$, which is optimal. Only $t=3$ minimizes the Frobenius norm, since $\Vert A-B_t{\Vert }_F=\sqrt{(3-t{)}^2+1}$. An unchanged worst direction can hide extra error in another direction under the operator norm.

Finally, these guarantees concern the stated norms and the sole matrix rank constraint. They do not establish that a discarded pattern is noise or irrelevant to a particular task: the finer patterns in our constructed example were put there intentionally. Adding entrywise weights or restrictions on the factors changes the problem, so the Eckart-Young-Mirsky theorem above does not automatically solve it. For historical context, the original 1936 matrix problem is documented in the existing Eckart-Young-Mirsky theorem section.

Two vectors spanning a hyperbolic plane. For an alternating bilinear form, choose $B(e,f)=1$; then their span is nondegenerate. For a quadratic form with polar form $B$, require also $Q(e)=Q(f)=0$. The analogous definition for a Hermitian form uses two isotropic vectors of pairing one. Extending such pairs to adapted bases is useful for constructing form-preserving maps.

An aperture in a rigid plane with prescribed harmonic normal displacement $f(x^{\prime })e^{i\omega t}$ radiates into a half-space. Superposing acoustic monopoles, each doubled by its same-sign rigid-wall image, gives the stated integral, where $R$ is the distance from aperture element to observer. In the acoustic far field, expanding $R$ to first order across the aperture identifies the angular radiation amplitude with the aperture's Fourier transform.

Linearizing inviscid barotropic flow about uniform rest gives ${\partial }_t(\nabla \times u)=0$, not automatically $\nabla \times u=0$. Irrotational linear acoustics therefore requires zero initial vorticity or restriction to the longitudinal acoustic mode. A time-independent divergence-free field, with zero pressure and density perturbations, is a nonacoustic solution of the linearized equations.