Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 36 / 3 / b / Solution

Assume $x$ is the unique basis pursuit minimizer. Fix $0\ne v\in \ker A$ and setThere is $\epsilon >0$ such that the sign function of $x_j+t{v}_j$ equals that of $x_j$ at every $j\in S$ whenever $|t|<\epsilon$. 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 $\epsilon$ works. On this interval the L1 norm has the exact expressionFor $0<t<\epsilon$, both $x+tv$ and $x-tv$ are distinct feasible vectors. Uniqueness forces their objective differences to be strictly positive, so $\alpha +\beta >0$ and $-\alpha +\beta >0$. ThereforeThe 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$.