Theorem: Support at most r+1

If $\mathrm{rank}N=r$ and $\mathrm{rank}[N\mid u]=r+1$, a separator exists supported on at most $r+1$ rows.

Proof. For $r=0$, $N=0$ and one nonzero coordinate of $u$ supplies a one-row separator.

For $r>0$, choose $r$ original independent columns $B$ and $r$ rows $R$ such that $M=B_R$ is invertible. Because $u\notin \mathrm{im}B$, some $j\notin R$ satisfies

otherwise $u=B{M}^{-1}{u}_R$. Set $z_j=1$, $z_R=-b_j{M}^{-1}$, and the other entries zero. Then $zB=0$, hence $zN=0$, while $zu=\delta$. Normalize by $\delta$.