Manuscript X-L-ST@1 · X-L-ST.tex · theorem · 20a32a22

Theorem: Exact finite feasibility certificate

Master residuals, reciprocity, and finite certificates › When a finite matrix test is legitimate · lines 1439–1469 · proof included or linked

X-L-ST@1#thm:finitecertificate

Back to manuscript

Under Assumption ass:coverage, the complete linear cancellation problem is equivalent to

M z = b .

It is solvable if and only if

rank M = rank [M ∣ b],

equivalently if and only if

λ^{T} b = 0 for every λ with λ^{T} M = 0.

A nonzero $rank M$ -minor and a spanning left kernel give an exact algebraic certificate. If $z_{*}$ is a solution, all solutions are $z_{*} + ker M$ .

Proof. Injective coverage makes zero evaluated residual equivalent to zero residual in $W$ . The matrix statement follows by choosing bases. The left-kernel condition is the finite-dimensional criterion $b \in im M$ . The affine solution description follows by subtraction.

Displayed formulas in this passage

unlabeled · line 1443
$M z = b .$
unlabeled · line 1447
$rank M = rank [M ∣ b],$
unlabeled · line 1451
$λ^{T} b = 0 for every λ with λ^{T} M = 0.$

Theorem: Exact finite feasibility certificate

Displayed formulas in this passage

Nearby in this section