Theorem: Finite certificate alternative

Let $N\in {\mathbb{K}}^{s\times L}$ and $q\in {\mathbb{K}}^s$, where $\mathbb{K}$ is a field. Exactly one of the following holds:

1. $q=Nc$ for some $c\in {\mathbb{K}}^L$;

2. there is $z\in {\mathbb{K}}^{1\times s}$ such that

   $$zN=0,zq=1.$$

The second alternative is equivalent to

Proof. If $q=Nc$, every functional annihilating $\mathrm{im}N$ annihilates $q$. Thus the alternatives are disjoint.

If $q\notin \mathrm{im}N$, append $q$ to a basis of $\mathrm{im}N$, extend to a basis of ${\mathbb{K}}^s$, and define a linear functional equal to zero on the contact basis and all additional basis elements except $q$, where it equals one. Its coordinate row is $z$. The rank characterization is the elementary criterion for appending an independent column.