Linear inconsistency certificate check

linear-inconsistency-certificate-check · version 1.0.0 · Numbers & math · free, no key needed

Check a witness y that A x = b has no solution (yA = 0, yb != 0) or no x >= 0 solution (Farkas: yA >= 0, yb < 0).

Use when you need to: verify a certificate that a linear system has no solution · check a Farkas witness for A x = b with x >= 0 · prove inconsistent simultaneous equations with multipliers.

Decide before calling

Read the versioned contract and the supported scope below. Reuse linear-inconsistency-certificate-check@1.0.0 when your input, required output and limits match it. Choose another approach for an unsupported operation.

Explain the choice

"I can use linear-inconsistency-certificate-check@1.0.0 for verify a certificate that a linear system has no solution. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

Supported

• verify a certificate that a linear system has no solution
• check a Farkas witness for A x = b with x >= 0
• prove inconsistent simultaneous equations with multipliers
• does this combination of equations give 0 = 1
• validate an infeasibility proof for equality constraints
• theorem of alternatives witness check
• בדיקת הוכחה שאין פתרון למערכת משוואות

Not supported

• finding a witness or solving the system (it only checks a supplied witness)
• inequality rows or implied bounds (see linear-inequality-certificate-check)
• integer infeasibility (no integer solution) proofs
• floating-point witnesses given as JSON numbers

Behavior

• Exact rationals are strings: an integer, a fraction p/q with q >= 1 or a finite decimal; JSON numbers, exponents, NaN and Infinity are rejected; outputs are canonical (reduced p/q, or an integer).
• matrix is m x n (1-64 each) with equal row lengths; rhs and witness have m entries; dimensions are checked before any dot product. Column j of yA is sum_i y_i a_ij and yb = sum_i y_i b_i, exact.
• variant free (x unrestricted, theorem of alternatives): valid when every column of yA is 0 and yb != 0. variant nonnegative (x >= 0, Farkas lemma): valid when every column of yA is >= 0 and yb < 0. There is no default variant.
• Check order: columns j = 0..n-1 (combination_not_zero for free, sign_condition_violated for nonnegative; check column, index j, computed (yA)_j, required_relation = or >=, required_value 0), then the right-hand side (rhs_combination_zero with !=, or rhs_not_negative with <; check rhs, index null).
• A valid free witness proves free-variable inconsistency; either it or its negation passes the nonnegative variant. The converse does not hold. Every output carries reference_version.

Input

• matrix (array of array of string, required): min items 1; max items 64; each min items 1; each max items 64; each each min length 1; each each max length 64; each each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• rhs (array of string, required): min items 1; max items 64; each min length 1; each max length 64; each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• variant (one of "free", "nonnegative", required)
• witness (array of string, required): min items 1; max items 64; each min length 1; each max length 64; each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$

Output

• valid (boolean, required)
• reason (one of "combination_not_zero", "sign_condition_violated", "rhs_combination_zero", "rhs_not_negative", null, required)
• first_discrepancy (object or null, required)
• reference_version (constant "r49-linear-inconsistency-1.0.0 (theorem of alternatives for Ax = b and Farkas lemma for Ax = b, x >= 0, Schrijver 1986 sections 3.1 and 7.3; exact rational arithmetic)", required)

Limits

• max rows: 64
• max columns: 64
• max number chars: 64

Example

Request input:

{
  "matrix": [
    [
      "1",
      "1"
    ],
    [
      "1",
      "1"
    ]
  ],
  "rhs": [
    "1",
    "2"
  ],
  "variant": "free",
  "witness": [
    "1",
    "-1"
  ]
}

Response:

{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "reference_version": "r49-linear-inconsistency-1.0.0 (theorem of alternatives for Ax = b and Farkas lemma for Ax = b, x >= 0, Schrijver 1986 sections 3.1 and 7.3; exact rational arithmetic)"
  }
}

How to call it

MCP

Connect https://computefirst.net/mcp (setup), then call execute with:

{
  "id": "linear-inconsistency-certificate-check",
  "version": "1.0.0",
  "input": {
    "matrix": [
      [
        "1",
        "1"
      ],
      [
        "1",
        "1"
      ]
    ],
    "rhs": [
      "1",
      "2"
    ],
    "variant": "free",
    "witness": [
      "1",
      "-1"
    ]
  }
}

HTTP (no key)

curl -X POST https://computefirst.net/v1/tools/linear-inconsistency-certificate-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"matrix":[["1","1"],["1","1"]],"rhs":["1","2"],"variant":"free","witness":["1","-1"]}'

The machine-readable contract is at /v1/tools/linear-inconsistency-certificate-check/versions/1.0.0.

CLI

node cli.mjs run linear-inconsistency-certificate-check 1.0.0 --input input.json --base-url https://computefirst.net

Get the client at /clients/cli/.

Related tools

• Lp primal feasibility check: Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.
• Lp dual feasibility check: Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.
• Linear solution check: Check that a proposed solution x satisfies A x = b exactly over the rationals and report the first row that fails.
• Lp optimality certificate check: Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
• Maximum flow certificate check: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
• Linear residual check: Check a claimed residual r = b - A x (per component and/or its max norm) exactly for an approximate solution x.