Theorem: Finite membership–separation alternative

Exactly one of the following alternatives holds:

1. $q_S=N_{S}c$ for some $c\in {\mathbb{R}}^L$;

2. there is $z\in {\mathbb{R}}^s$ such that

   $$z^{\mathsf{T}}{N}_S=0,z^{\mathsf{T}}{q}_S\ne 0.$$

In the second case $z$ may be chosen with $z^{\mathsf{T}}{q}_S>0$.

Proof. Let $W=\mathrm{im}{N}_S$. If $q_S\in W$, every vector orthogonal to $W$ annihilates $q_S$, so (ii) is impossible. If $q_S\notin W$, set $z=q_S-{\mathrm{proj}}_W{q}_S$. Then $z\ne 0$, $z\perp W$, and $z^{\mathsf{T}}{q}_S={\Vert z\Vert }^2>0$.