The minimization of the one-norm can be stated as: $$ \min_{u\in\ell_1} \|u\|_1 \qquad \text{subject to} \qquad Au=b, $$ where $u\in\mathbb{R}^m = [u_1,u_2,...,u_m]^\intercal$ is the sequence that we want to minimize the one-norm of, with the equality constraints given above, where $A\in\mathbb{R}^{n\times m}$ and $b\in\mathbb{R}^n$. This gives $n$ constraints on $u$. There is a theorem, which comes from the Hahn-Banach theorem, that states this problem is equivalent to the maximization problem in the dual space $$ \max_{\|A^\intercal x\|_{\infty}\leq 1} x^\intercal b $$ Now, the expression $\|A^\intercal x\|_{\infty}\leq 1$ gives $N$ inequality constraints and forms a polyhedron from which the optimal value $x^*$ in the dual space must adhere in. The theorem also states that if the maximum is achieved for some $x^*\in\mathbb{R}^n$, with $\|A^\intercal x\|_{\infty}=1$, and the minimum is achieved for some $u^*\in\mathbb{R}^m$, then $u^*$ and $x^*$ are aligned.
This means that whenever equality is not met (for some $k = 1,2,...,m$), the value for $u_k = 0$. I understand this in an intuitive way, but how can this be proven more rigorously? Also, what I really don't understand is how to actually find the value of $u_k$ when equality is met.
To further illustrate my point, I ran a simple code in MATLAB to solve this problem. I had the following numbers: $$ A = \begin{pmatrix} 29 & 11 & 4 & 1\\ 18 & 7 & 3 & 2\\ 29 & 11 & 4 & 1 \end{pmatrix} \qquad b = \begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}, $$ which means that $u\in\mathbb{R}^4$ and $x\in\mathbb{R}^3$. The output of the code gives the solution: $\|u^*\|_1 = x^{*\intercal}b = 0.3$, as well as $$ x^* = \begin{pmatrix} -0.2\\ 0.7\\ -0.2 \end{pmatrix} \qquad u^* = \begin{pmatrix} 0.025\\ 0\\ 0\\ 0.275 \end{pmatrix} \qquad A^\intercal x^* = \begin{pmatrix} 1\\0.5\\0.5\\1 \end{pmatrix} $$ From what I wrote before, we can see that when the components of $\|A^\intercal x^*\|_\infty = 1$, then $u^*_k$ is a constant nonzero value, but when this condition is not met, there is no alignment, and $u^*_k = 0$. My question is how do we get from $x^*$, which is easily found from a LP solver, to $u^*$. There must be something simple that I am missing here.
Let $x^*$ and $u^*$ be optimal solutions to the two problems. Strong duality means that both problems have equal objectives; so $$\|u^*\|_1 = \langle b, x \rangle = \langle A u^*, x^* \rangle = \langle u^*, A^T x^* \rangle = \langle u^*, y^*\rangle$$ where $y^*=A^Tx^*$. Note that $\|y^*\|_\infty \leq 1$—in fact, it's not hard to see that it must be true that $\|y^*\|_\infty = 1$, because otherwise I can just scale $x^*$ to make it so (implying that the original $x^*$ would not have been optimal).
Now let's keep going to the right using the Cauchy-Schwarz inequality: $$\langle u^*, y^* \rangle \leq \|u^*\|_1 \|y^*\|_\infty = \|u^*\|_1.$$ Not surprisingly we're back where we started. But this is important, because for a given nonzero $u^*$, there are only certain values of $y^*$ that can satisfy the Cauchy-Schwarz inequality with equality. Specifically, it must be the case that $$u_i^* = 0 ~\text{or}~ y^*_i = \mathop{\textrm{sign}}(u^*_i), \quad i=1,2,\dots, n$$