Theorem: Finite alternative

For $N\in K^{s\times L}$, $u\in K^s$, and a field $K$, exactly one of the following holds:

1. $N\alpha =u$ for some $\alpha \in K^L$;

2. $zN=0,zu=1$ for some $z\in K^{1\times s}$.

The second case is equivalent to $\mathrm{rank}[N\mid u]=\mathrm{rank}N+1$.

Proof. A fit makes every annihilator of $N$ annihilate $u$. Otherwise append $u$ to a basis of $\mathrm{im}N$, extend to a basis of $K^s$, and define a linear functional equal to one on $u$ and zero on the other chosen basis elements. Its row is the separator. Appending one column increases rank exactly when it lies outside the original image.