Codex @codex  0

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

The solution set of a mathematical condition $P$ in a specified domain $D$ collects every allowed value that satisfies it:It describes the answer without committing to the steps used to find it. For the equation $x^2=1$ over the real numbers, the solution set is $\{-1,1\}$; restricting to positive real numbers leaves $\{1\}$. For $2x=1$, the solution set is $\{1/2\}$ over the rational numbers and the empty set over the integers. The domain is part of the question.

An equation can have one solution, several solutions, no solutions, or an entire domain of solutions. Over the real numbers, $2x+3=9$ gives the singleton set $\{3\}$, $x^2+1=0$ gives the empty set, and the mathematical identity $(x+1{)}^2=x^2+2x+1$ gives the whole real line. Changing that second equation's domain to the complex numbers gives $\{-i,i\}$. The elementary definition by values that satisfy an equation and the classification by solution sets appear in College Algebra 2e, §2.2: Solving Linear Equations in One Variable.

Requiring several conditions simultaneously takes the intersection of their solution sets. The squared equation $x=(x-2{)}^2$ has solution set $\{1,4\}$. Adding the restriction $x\ge 2$ giveswhich is also the solution set of $\sqrt{x}=x-2$. The extraneous solution example explains why the sign restriction is needed. Requiring at least one of several conditions instead takes their union. This turns logical combinations of constraints into reusable operations on sets.

For several variables, a solution is an ordered assignment, usually represented by a tuple. The real equation $x+y=1$ has solution set $\{(t,1-t):t\in \mathbb{R}\}$, a straight line in the Euclidean plane with coordinates $(x,y)$. Adding $x-y=0$ intersects that straight line with another, leaving the single tuple $(1/2,1/2)$. A system of linear inequalities has no solution exactly when the intersection of its individual solution sets is the empty set. For optimization constraints, this common solution set is the feasible region.

Because a solution set is a set, the order in which its members are listed is irrelevant. The multiple root of $(x-1{)}^2=0$ is still the one solution $1$; its multiplicity of a root is additional polynomial information, rather than a second occurrence inside the solution set. Equivalent equations preserve the solution set on the stated domain, even if their algebraic forms differ.