Rewriting an equation as a set of inequalities

57 Views Asked by At

I have a set $\\{x_1,x_2 \dots , x_d \in \mathbb{R} : |x_1| + |x_2| + \dots + |x_d| \leq 1 \\}$ and i would like to rewrite it as $\\{ u \in \mathbb{R}^d : Au \leq \textbf{1} \\}$ , where $\textbf{1}$ is a vector with each coordinate being 1 and $A$ only has integer entries.

I do need help finding the matrix $A$.

1

There are 1 best solutions below

0
On

Maybe I oversimplify something in the question, but is this what you are looking for:

$d=1$:
$$ \begin{bmatrix} 1 \\ -1 \end{bmatrix} \begin{bmatrix} x_1 \end{bmatrix} \le \begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

$d=2$:

$$ \begin{bmatrix} 1 &1\\ -1 &1 \\ 1 &-1\\ -1 &-1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} 1 \\ 1\\ 1 \\ 1 \end{bmatrix} $$

$d=3$:

$$ \begin{bmatrix} 1 &1 &1\\ -1 &1 &1\\ 1 &-1&1\\ -1 &-1&1\\ 1 &1 &-1\\ -1 &1 &-1\\ 1 &-1&-1\\ -1 &-1&-1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \le \begin{bmatrix} 1 \\ 1\\ 1 \\ 1\\ 1 \\ 1\\ 1 \\ 1 \end{bmatrix} $$ and for general $d$, the matrix $A$ is a $d \times 2^d$ -matrix where in the $2^d$ rows you have the $2^d$ possible arrangements of $d$ values, each $\pm 1$.

The background of this is that $\{x_1,x_2 \dots , x_d \in \mathbb{R} : |x_1| + |x_2| + \dots + |x_d| \leq 1 \}$ defines a volume which is bounded by $2^d$ hyperplanes, each of which can be expressed by writing your equation in one of the $2^d$ orthants, which in turn means that for each absolute value, once $|x| = x$ holds (for positive $x$), and once $|x| = -x$ holds (for negative $x$).