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

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.

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.

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.

The discriminant of a binary quadratic form is $d=b^2-4ac$. If the form is positive-definite, evaluating it at $(1,0)$ gives $a>0$. For $a\ne 0$, completing the square givesEvaluating along $x=-by/(2a)$ shows that positivity also requires $d<0$. Conversely these two inequalities make both displayed coefficients positive, provingA reduced positive definite binary quadratic form satisfies $|b|\le a\le c$, with $b\ge 0$ if $|b|=a$ or $a=c$. The last convention avoids counting both boundary representatives. For fixed negative discriminant, these inequalities implyThere are finitely many such integers $a$, finitely many integers $b$ with $|b|\le a$, and then $c=(b^2-d)/(4a)$ is determined. Hence the number of reduced forms is finite. If no admissible integer coefficients have the given discriminant, this number is zero.

For $d=-39$, the bound gives $a=1,2,3$. The integrality of $c=(b^2+39)/(4a)$ and the boundary sign convention give respectivelyThese are all the reduced positive definite binary quadratic forms of discriminant minus thirty-nine. Thusrepresented by $x^2+xy+10y^2$, $2x^2+xy+5y^2$, $2x^2-xy+5y^2$, and $3x^2+3xy+4y^2$.

The equality-constrained Lagrangian sufficiency theorem says: if $x^{\ast }$ is feasible and, for some fixed multipliers, it globally minimizes the optimization Lagrangian over all $x$, then it globally minimizes the objective over feasible $x$. On the feasible set the constraint terms vanish, so the two minimizations agree. No convexity assumption is needed for this version once global minimization of the optimization Lagrangian has been established.

Let $S_1={\sum }_i{a}_i$, $S_2={\sum }_i{a}_i^2$, and $\Delta =n{S}_2-S_1^2$. Sincethe two constraints are independent. For the squared Euclidean norm objective in the original PDF, takeCompleting the square shows that its unique global minimizer has $x_i=\lambda +\mu a_i$. The constraints become $n\lambda +S_1\mu =1$, $S_1\lambda +S_2\mu =0$, giving $\lambda =S_2/\Delta$, $\mu =-S_1/\Delta$. The Lagrangian sufficiency theorem therefore givesFor the value, use ${\sum }_i(x_i^{\ast }{)}^2=\lambda {\sum }_i{x}_i^{\ast }+\mu {\sum }_i{a}_i{x}_i^{\ast }=\lambda$. Uniqueness also follows directly: for every feasible $x$, the cross term in ${\sum }_i(x_i-x_i^{\ast }{)}^2$ vanishes, so the difference of objectives equals that strictly positive sum unless $x=x^{\ast }$. This is the minimum squared norm under two affine constraints.

Use completing the square in the Hermitian form $x^{\ast }Ax$, rather than unitary diagonalization of a normal matrix. The first pivot is one, soA second square completion givesTherefore one answer isThe diagonal entries of $D$ are rational, $\det T=1$, and the displayed identity for every $x$ proves $T^{\ast }DT=A$.

If $T$ were a unitary matrix, this matrix congruence would also be a similarity transformation, so the diagonal entries of $D$ would be the eigenvalues of $A$. Its characteristic polynomial isThus its eigenvalues are $3,3+\sqrt{10},3-\sqrt{10}$, two of which are irrational. A unitary factor cannot give a rational diagonal here. Alternatively, the permitted rational root theorem implies that three rational eigenvalues would all be integers, whereas the quadratic factor has no integer roots.

Because $A$ is a real symmetric positive-definite matrix, its inverse exists and all its eigenvalues are positive. Completing the square givesThe translation $v=u-A^{-1}b$ has unit Jacobian determinant. Choose an orthogonal matrix $O$ with $O^{T}AO=\mathrm{diag}(a_1,\dots ,a_n)$, where $a_i>0$. The change $v=Oz$ also has absolute Jacobian one. The remaining integral is the product of $n$ one-dimensional Gaussian integrals, each equal to $\sqrt{2\pi /a_i}$. Consequently the linear-source multivariate Gaussian integral isThe determinant square root is the positive one, as required by convergence of the original real integral.