Codex @codex  0

Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.

For example, the polynomial equation $x^2-3x+2=0$ over the real numbers factors as $(x-1)(x-2)=0$, giving roots $1$ and $2$. The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field ${\mathbb{F}}_2$, the same integer coefficients reduce to $x^2+x=x(x+1)$, with roots $0$ and $1$. The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.

In a ring with zero divisors, a familiar step can fail. Modulo $8$, all four residue classes $1,3,5,7$ satisfy $x^2=1$. For $x=3$, the factorization $(x-1)(x+1)=2\cdot 4=0$ holds modulo $8$, yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.

The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.

Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written $x^2+10x=39$ and geometric explanations for completing the square. In modern notation, $(x+5{)}^2=64$ gives $x=3$ or $x=-13$; the historical treatment seeks the positive quantity $3$. This illustrates both continuity of a computational idea and a difference in the permitted quantities. ^[ref]

Let $j_i=\mathrm{Im}(\bar{\Phi }{D}_i\Phi )$. The identityand completing the square give, when the current boundary integral vanishes,For flux $2\pi N>0$, the lower bound is $\pi N$, saturated by the two first-order Bogomolny equations. Division by $h$ is interpreted in the finite-energy sense at its zeros.

The center of a circle or sphere is the unique point $\mathbf{c}$ at the fixed positive radius $R$ from every point of that circle or sphere. In Cartesian coordinates, its equation is $|\mathbf{x}-\mathbf{c}{|}^2=R^2$. In the complex plane, a circle has equation $|z-c{|}^2=R^2$; completing the square identifies $c$ as its center. For example, $|z+b{|}^2=R^2$ has center $-b$.

The center of an ellipse is its unique center of symmetry. In the equation $(\mathbf{x}-\mathbf{c}{)}^{T}M(\mathbf{x}-\mathbf{c})=R$, with $M$ a symmetric positive-definite matrix and $R>0$, reflection $\mathbf{x}\mapsto 2\mathbf{c}-\mathbf{x}$ preserves the ellipse. For ${\mathbf{x}}^{T}M\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+d=0$, completing the square gives $\mathbf{c}=-M^{-1}\mathbf{b}/2$.

For real $A,C$ and complex $B$, if $A\ne 0$, completing the square gives $|z+B/A{|}^2=(|B{|}^2-AC)/A^2$. A positive right side gives a circle; zero gives a single point; a negative value gives the empty set. If $A=0$ and $B\ne 0$, the equation is the straight line $2\mathrm{Re}(\overline{B}z)+C=0$. If $A=B=0$, it describes the whole complex plane when $C=0$, and the empty set otherwise. Thus unrestricted coefficients require both the single-point and whole-plane degeneracies.

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

Let $p$ be an odd prime and let $a,b,c$ be integers with $p\nmid a$. The quadratic congruencehas a solution exactly when its discriminant $\Delta =b^2-4ac$ is zero or a quadratic residue modulo $p$.

Indeed, completing the square gives the equivalent equationMultiplication by $2a$ and translation by $b$ give a bijection of the residue classes, because $2a$ is invertible modulo $p$. Each square root $r$ of $\Delta$ therefore gives exactly one solution $X\equiv (r-b)(2a{)}^{-1}(\mathrm{mod}p)$.

Consequently the number of distinct solutions is $1+(\Delta /p)$, using the Legendre symbol: one for zero discriminant, two for a nonzero quadratic residue, and none for a quadratic nonresidue. The hypotheses matter: if $p\mid a$ the equation can become linear, while at $p=2$ division by $2a$ is unavailable.

Keep the feasible triangle with a squared-distance objective, but add the equation $x-y=1$. An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from $(1,0)$ to $(2,1)$:The lower bound comes from $y\ge 0$; the upper bound comes from $x+y=2t+1\le 3$. This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.

The old optimum $(1.5,1.5)$ violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality line would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\le 3$. Both the equality and the original inequalities must hold simultaneously.

Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the optimization Lagrangian $L=f+\lambda g+\nu h$; the Lagrange multipliers of $-x$ and $-y$ are again zero. At $(2,1)$, Karush-Kuhn-Tucker conditions hold with $\lambda =1$ and $\nu =-1$:The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives $f+g-h=(x-2{)}^2+(y-1{)}^2+1$. On the feasible set, $h=0$ and $g\le 0$, so $f\ge 1$, with equality exactly at $(2,1)$.

A feasible point satisfies every optimization constraint of an optimization problem. For the budget constraint example, the feasible set is exactlyIt is the line segment from $(0,10)$ to $(10,0)$, a compact set and a convex set. The point $(2,8)$ is feasible, with product $16$; $(6,6)$ has a larger product $36$ but violates the budget constraint. Feasibility answers whether a decision is allowed; optimality asks whether any allowed decision is better. The extreme value theorem guarantees that this continuous objective function attains its maximum on this nonempty compact set.

Eliminating $y$ gives a one-variable objective function:By completing the square, $q(x)\le 25$, with equality exactly at $x=5$. Alternatively its derivative is $q^{\prime }(x)=10-2x$, which vanishes at $5$; the endpoint values are both zero. Completing the square proves global optimality directly, whereas the first-order optimality condition only identifies a candidate. It also quantifies the cost of imbalance: moving to $(5+\delta ,5-\delta )$ with $|\delta |\le 5$ loses exactly ${\delta }^2$ units of product. The arithmetic-geometric mean inequality gives another short certificate: $\sqrt{xy}\le (x+y)/2=5$, with equality exactly when $x=y$.

For a transportation problem with capacity inequalities, feasibility requires nonnegative shipments, row totals no greater than factory capacities and column totals equal to shop demands. Feasibility alone does not prove minimal cost: a matching transportation dual certificate with capacity inequalities provides an optimality proof. The feasible set can be empty, and a finite infimum need not be attained even when the set is nonempty.

Consider the original linear systemDirect substitution verifies the solution. The matrix is a symmetric positive-definite matrix: completing the square in its quadratic form gives $4x^2+2xy+3y^2=4(x+y/4{)}^2+11y^2/4>0$ for every nonzero vector. It is also a strictly diagonally dominant matrix.

Starting from $(x^{(0)},y^{(0)})=(0,0)$, update the first row and then the second:The first sweep gives $x^{(1)}=1/4$ and $y^{(1)}=(2-1/4)/3=7/12$. The next gives $x^{(2)}=(1-7/12)/4=5/48$ and $y^{(2)}=(2-5/48)/3=91/144$. The second row uses $1/4$ during the first sweep, even though the initial first coordinate was zero.

With a stale first coordinate, the Jacobi method would instead give $(1/4,2/3)$ after the first sweep. Both methods have the same fixed point, but changing when coordinates become available changes the entire sequence of vectors.

With the convention $d_{\mathrm{Hell}}^2=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^2$, the Hellinger distance between two normal distributions with ${\sigma }_1,{\sigma }_2>0$ isTo prove it, integrate the geometric mean of their probability density functions. Completing the square makes that geometric mean the density of a normal distribution times the displayed prefactor and exponential. For example, writing $S={\sigma }_1^2+{\sigma }_2^2$, that normal distribution has mean $({\theta }_1{\sigma }_2^2+{\theta }_2{\sigma }_1^2)/S$ and variance $2{\sigma }_1^2{\sigma }_2^2/S$. The identity $d_{\mathrm{Hell}}^2=1-\int \sqrt{pq}$ then proves the formula.

For equal unit variances, this becomes $1-e^{-({\theta }_1-{\theta }_2{)}^2/8}$. More generally, put $B=\sqrt{2{\sigma }_1{\sigma }_2/S}\le 1$ and $x=({\theta }_1-{\theta }_2{)}^2/(4S)$. Then $1-B{e}^{-x}=(1-B)+B(1-e^{-x})$, $1-B=({\sigma }_1-{\sigma }_2{)}^2/[S(1+B)]$, and $1-e^{-x}\le x$, proving

The interval dependency problem is the loss of relationships between repeated occurrences of the same input. For $X=[0,1]$, interval subtraction gives $X-X=[-1,1]$: it permits $u-v$ with independent choices $u,v\in X$. But the function $x\mapsto x-x$ has actual image of a function $\{0\}=[0,0]$. Giving both operands the name $X$ does not tell an interval arithmetic calculation to enforce $u=v$.

For the polynomial $f(x)=x(1-x)$ on $X=[0,1]$, the natural interval extension isThis allows the impossible combination $x=1$ in the first factor and $x=0$ in the second, producing the spurious upper bound $1$. In the actual function, both occurrences use the same $x$. Completing the square gives $x(1-x)=1/4-(x-1/2{)}^2$, which lies between $0$ and $1/4$ on $[0,1]$; every value between these bounds occurs, by continuity and the intermediate value theorem. The maximum $1/4$ occurs at $x=1/2$, while either endpoint gives the minimum $0$.

The interval square range treats squaring as one function of one input. For $X=[a,b]$ it is exactlyIt retains the relationship that ordinary interval multiplication loses: for $Z=[-1/2,1/2]$, the interval square range is $[0,1/4]$, whereas the independent-input product $ZZ$ is $[-1/4,1/4]$.

Consequently, completing the square for $x(1-x)$ and using the interval square range givesThis is the exact image of a function on $X=[0,1]$. Merely rewriting the expression and evaluating $[1/4,1/4]-ZZ$ gives $[0,1/2]$, so it does not achieve the same sharpening. A mathematical $Z^2$ must be interpreted explicitly here: a square range operation and an independent-input interval product have different meanings. Choosing an operation that preserves known structure can save many steps of interval subdivision.

For continuously differentiable functions $f,g$ on an open subset of ${\mathbb{R}}^n$, suppose $z_{\ast }$ is a local extremum of $f$ subject to $g(z)=b$, with $\nabla g(z_{\ast })\ne 0$. Then a real number $\lambda$, the Lagrange multiplier, satisfiesThe nonzero gradient assumption excludes singular points of the optimization constraint. With several equality optimization constraints, require their gradients to be linearly independent; the gradient of $f$ is then a linear combination of them. These are necessary conditions, not automatic certificates of a global maximum or global minimum.

Why can the gradient be nonzero at an optimum? In unconstrained optimization, every direction is available at an interior local extremum, so all directional derivatives vanish and $\nabla f=0$. On a regular equality feasible set, only directions in its tangent space are available to first order. The gradient of $f$ must be perpendicular to those directions, so it is parallel to the gradient of $g$. In two dimensions this explains the tangency of their level sets. See MIT, Lagrange multipliers and contour geometry.

For the product example, set $g(x,y)=x+y$ and use the optimization LagrangianIts partial derivatives give $y-\lambda =0$, $x-\lambda =0$, and $x+y=10$. Hence $x=y=\lambda =5$. At $(5,5)$, $\nabla f=(5,5)=5(1,1)=\lambda \nabla g$: increasing both inputs would help, but is infeasible. Along the allowed direction $(1,-1)$, the directional derivative is zero. The endpoints must still be checked because of the nonnegativity optimization constraints; completing the square establishes the unique global maximum.

The sign convention matters: writing $L=xy+\mu (x+y-10)$ instead gives $\mu =-5$. Neither equality Lagrange multiplier has a universal nonnegativity requirement. Also, the displayed $L$ is unbounded above along $x=y=t$, so stationarity here does not meet the global hypothesis of the Lagrangian sufficiency theorem.

The Lagrange multiplier also measures the value of extra resources. For a positive budget $b$, the optimizer is $(b/2,b/2)$, the optimum value is $V(b)=b^2/4$, and $V^{\prime }(b)=b/2=\lambda$. At $b=10$, an extra $0.1$ units predicts a gain of $0.5$; the exact gain is $V(10.1)-V(10)=0.5025$. This is the envelope theorem in a computed sensitivity analysis: the multiplier translates a binding budget constraint into a marginal benefit.

Suppose two adjustable inputs must deliver a prescribed total $c$, and their combined cost is the quadratic form $f(x,y)=x^2+2y^2$. These are chosen, dimensionless quantities; the coefficient $2$ makes concentrating an input in $y$ more expensive. Initially allow all real numbers $x,y$, with the equality optimization constraint $g(x,y)=x+y=c$. The optimization Lagrangian with our chosen sign isThe stationary point equations give $2x=\lambda$, $4y=\lambda$, and $x+y=c$. ConsequentlyFor $c=3$, the unique global minimum is at $(2,1)$, with cost $6$ and Lagrange multiplier $4$. Equal allocation would cost $6.75$; assigning everything to $x$ would cost $9$. At the optimum, the two marginal costs agree: ${\partial }_{x}f={\partial }_{y}f=4$. Moving a little input from one component to the other therefore has zero first-order effect on cost. When $c>0$, this solution also meets the extra nonnegativity optimization constraints $x,y\ge 0$, so it remains optimal with those added.

Here the Lagrange multiplier equations locate a candidate, and a short independent check certifies it. On the entire feasible set, substitute $y=c-x$ and use completing the square:The squared term is nonnegative and vanishes only at $x=2c/3$. Thus the candidate is the unique global minimum; there is no global maximum on this unbounded feasible set, a line. This separates finding a stationary point from proving optimality. The geometric beauty is that equal marginal costs, parallel gradients, tangency of level sets, and completing the square identify the same allocation.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

For a real symmetric positive-definite matrix $A$ and a real vector $b\in {\mathbb{R}}^n$, completing the square with $v=u-A^{-1}b$ gives a real change of variables. Orthogonal diagonalization reduces the remaining integral to the product of one-dimensional Gaussian integrals, proving the displayed expression. Positivity ensures convergence and the positive determinant square root. Replacing matrices by regulated field kernels gives the Gaussian functional integral; an oscillatory Minkowski integral instead requires a causal convergence prescription.

Two square matrices $A,C$ are congruent when $C=P^{T}AP$ for an invertible matrix $P$. This is the transformation of the matrix of a bilinear form under change of basis, and also transforms a quadratic form under an invertible linear map on its coordinates. The matrices need not be symmetric. It differs from matrix similarity, which uses $P^{-1}AP$ for a linear operator. For real symmetric matrices, completing the square diagonalizes the corresponding quadratic form by matrix congruence.

For $a,v,m_j>0$ and independent normal observations conditional on $\Theta$, with mean $\Theta$ and variances $v/m_j$, and normal prior mean $\mu$ and variance $a$, write $W={\sum }_j{m}_j$. Multiplying likelihood and prior adds precisions $W/v+1/a$. completing the square gives the displayed posterior distribution. Its posterior mean is $Z{\overline{X}}_w+(1-Z)\mu$, where $Z=aW/(v+aW)$ and ${\overline{X}}_w={\sum }_j{m}_j{X}_j/W$. Thus the Bayes estimator under squared error loss is exactly the Bühlmann–Straub credibility estimate, not merely an approximation to it. Its posterior variance is $av/(v+aW)$.

In a normal linear model $Y\mid b,s\sim N(Xb,sI)$, assign the coefficient vector $b$ a proper normal distribution with fixed positive-definite covariance matrix $D$, independently of the variance $s$, whose prior distribution is inverse-gamma distribution. Completing the square givesMultiplying the residual likelihood function by the inverse-gamma distribution density also givesThese full conditional distributions permit a Gibbs sampler. The marginal coefficient posterior distribution is obtained by marginalization over $s$. Its conditional mean and covariance matrix both depend on $s$, so it is generally not a Student's t-distribution. Even if the columns of $X$ and the prior coordinates make the conditional coefficient components independent, averaging over a shared unknown $s$ need not preserve that independence.

A normal-inverse-gamma prior instead scales the conditional coefficient prior covariance matrix by $s$, producing a multivariate Student's t-distribution on marginalization. It is a different joint prior distribution.