Theorem: Rank–minor–left-kernel certificate

Let $M\in {\mathbb{K}}^{n\times p}$, $y\in {\mathbb{K}}^n$, and $0\le r\le \min (n,p)$. Suppose original row and column index sets $I,J$, both of size $r$, and $L\in {\mathbb{K}}^{(n-r)\times n}$ satisfy

Then

A solution $c_{\star }$ gives the complete affine family $c_{\star }+\ker M$. A nonzero component of $Ly$ gives an outside-span separator.

Proof. The minor gives $\mathrm{rank}M\ge r$. Since $\mathrm{im}M\subseteq \ker L$ and $\dim \ker L=r$, the opposite inequality holds and $\mathrm{im}M=\ker L$. This proves membership and augmented-rank equality. The affine assertion follows by subtracting two solutions. A nonzero row pairing separates the target from the image.