Let $M \in \mathcal{M}_{k \times d}(\mathbb{R})$ with $\operatorname{rank}(M) = k$, $b \in \mathbb{R}^k \setminus \{0\}$, and
$$r := \inf\left\{\|x\|_1, x \in \mathbb{R}^d, Mx = b\right\}, \quad C := \left\{x \in \mathbb{R}^d : Mx = b, \|x\|_1 = r\right\}.$$
Fix $\bar{x} \in C$. Show that there exists $q \in \operatorname{Ker}(M)^\perp \setminus \{0\}$ such that for all $i \in \{1, \ldots, d\}$, we have
$$q_i \bar{x}_i = \|q\|_\infty |\bar{x}_i|.$$