= Solution
Assume $x$ is the unique <basis pursuit> <minimizer>. Fix $0\ne v\in\ker A$ and set
$$
\alpha=\langle\operatorname{sgn}(x_S),v_S\rangle,\qquad\beta=\|v_{S^c}\|_1.
$$
There is $\varepsilon>0$ such that the <sign function> of $x_j+t v_j$ equals that of $x_j$ at every $j\in S$ whenever $|t|<\varepsilon$. To choose it, take less than the minimum of $|x_j|/|v_j|$ over the nonzero $v_j$ in $S$; if that set is empty, any positive $\varepsilon$ works. On this interval the <L1 norm> has the exact expression
$$
\|x+t v\|_1-\|x\|_1=t\alpha+|t|\beta.
$$
For $0<t<\varepsilon$, both $x+t v$ and $x-t v$ are distinct feasible <vectors>. Uniqueness forces their objective differences to be strictly positive, so $\alpha+\beta>0$ and $-\alpha+\beta>0$. Therefore
$$
\boxed{|\langle\operatorname{sgn}(x_S),v_S\rangle|<\|v_{S^c}\|_1\quad(0\ne v\in\ker A).}
$$
\b[The <fixed-sign null space condition> is necessary as well as sufficient.] This argument also covers an empty <support of a vector>: then $\alpha=0$ and the nonzero <null space> <vector> has $\beta>0$. Strictness is indispensable: equality would make a sufficiently short feasible segment have the same objective as $x$.
Back to article page
