Writing the unit $\ell_1$-ball in $\mathbb{R}^n$ as the intersection of closed half-spaces

As we discussed in the comments: it is not possible to express the $\ell_1$ norm ball without an exponential number of rows, unless you allow for additional variables.

The simplest approach is to introduce new variables $y_i$, $i=1,2,\dots, n$. Then you have: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n \\ +x_i\leq y_i & i=1,2,\dots, n \\ \sum_i y_i \leq 1 \end{array} So with $n$ additional variables you can express this with $2n+1$ inequalities. However, try and convince yourself that this still produces the same result: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n \\ +x_i\leq y_i & i=1,2,\dots, n \\ \sum_i y_i = 1 \end{array} All I have done is change the last inequality to an equation. If $\|x\|_1=1$, then this obviously holds, because the only valid values of $y$ are $y_i=|x_i|$. But it will work even if $\|x\|_1<1$; for instance, you can choose $y_i=|x_i|+\frac{1 - \|x\|_1}{n}$. Once you accept the validity of this system, then, you can eliminate one of the $y_i$ values: \begin{array}{ll} -x_i \leq y_i & i = 1,2,\dots,n-1 \\ +x_i\leq y_i & i=1,2,\dots, n-1 \\ -x_n\leq 1 - y_1 - y_2 - \dots - y_{n-1} \\ +x_n\leq 1 - y_1 -y_2 - \dots - y_{n-1} \end{array} So in fact, with $n-1$ additional variables we can express the norm ball with $2n$ inequalities.