Skip to main content
1 of 2

This isn't a complete answer but may help you work out something.

The constraint that $||Ax||_1 = ||x||_1$ is actually a very strong constraint. It actually implies that $A$ is a signed-permutation matrix, that is the matrix $A \in \{-1,0,1\}^{n \times n}$ and $A$ has exactly one non-zero entry in each row and each column.

The additional constraint that the entries of $A$ are contained in $[0,1]$ actually forces $A$ to be a permutation matrix, that is $A \in \{0,1\}^{n \times n}$ and $A$ has exactly one 1 in each row and each column.

One implication of this is that $\|Ax\|_p = \|x\|_p$ for every $p \geq 1$. This is because if $\sigma$ is the permutation corresponding to $A$ in the sense that $Ax = (x_{\sigma(1)},...,x_{\sigma(n)})$ then $$\|Ax\|_p^p = \sum_{i=1}^n |(Ax)_i|^p = \sum_{i=1}^n |x_{\sigma(i)}|^p = \sum_{i=1}^n |x_i|^p = \|x\|_p^p.$$


We will prove that $A$ is a signed-permutation matrix in several steps.

Step 1 $A$ is full rank.

Proof: Suppose that $A$ was not full rank and let $x \neq 0$ be such that $Ax = 0$. Then we would have $$\|x\|_1 \neq 0 = \|Ax\|_1$$ which is a contradiction with the assumption on $A$.

Step 2 Let $B_1^n := \{x \in \mathbb{R}^n \ : \ \|x\|_1 \leq 1\}$. Then $x \mapsto Ax$ is a bijection from $B_1^n$ onto itself. Similarly, let $S_1^n := \{x \in \mathbb{R}^n \ : \ \|x\|_1 = 1\}$. Then $x \mapsto Ax$ is a bijection from $S_1^n$ onto itself.

Proof: To start we have for all $x \in B_1^n$ $$1 \geq \|x\|_1 = \|Ax\|_1 \implies Ax \in B_1^n$$ so that the image of the map is at least contained in $B_1^n$.

Next let $x,x' \in B_1^n$ so that $$0 < \|x - x'\|_1 = \|A(x - x')\|_1 = \|Ax - Ax'\|_1$$ which shows $Ax \neq Ax'$ and therefore $x \mapsto Ax$ is injective.

For surjectivity we will use Step 1. Since $A$ is full rank $A^{-1}$ exists. In particular for every $x \in B_1^n$ we have $$x = (AA^{-1})x = A(A^{-1}x)$$ and also $$1 \geq \|x\|_1 = \|A(A^{-1}x)\|_1 = \|A^{-1}x\|_1 \implies A^{-1}x \in B_1^n$$ In particular for every $x \in B_1^n$ it is the image of $A^{-1}x \in B_1^n$ under $A$. This shows $x \mapsto Ax$ is also surjective from $B_1^n$ onto itself.

Having established injectivity and surjectivity we conclude that $x \mapsto Ax$ is a bijection. The argument for $S_1^n$ is essentially the same.

Step 3 If $x = e_i$ for some $i=1,...,n$ then $Ax \in \{\pm e_1,...,\pm e_n\}$ where $e_1,...,e_n$ are the standard basis vectors.

Proof: Assume without loss of generality that $x = e_1$ and suppose for contradiction that $Ax \notin \{\pm e_1,...,\pm e_n\}$. Since $x \mapsto Ax$ is a bijection of $S_1^n$ onto itself there are $2n$ distinct points $z^1,...,z^{2n} \in S_1^n$ such that $\{Az^1,...,Az^{2n}\} = \{\pm e_1,...,\pm e_n\}$. Since $e_1$ is not in the set $\{z^1,...,z^{2n}\}$ and there are exactly $2n$ points in $S_1^n$ with precisely one non-zero entry, there must be a $z \in \{z^1,...,z^{2n}\}$ with two or more non-zero entries. The contradiction we will reach is that $\|Az\|_2 < 1$ and therefore $Az \notin \{\pm e_1,...,\pm e_n\}$.

Without loss of generality assume that this is $z^1$ and the non-zero entries are $z^1_1,...,z^1_k$ for some $k > 1$. Now note that we can write $z^1$ as $$z^1 = \sum_{i=1}^k z^1_i e_i.$$

Let's recall a classic inequality.

Let $b^1,...,b^k$ be non-zero vectors for $k > 1$. Then $$\left \| \sum_{i=1}^k b^i \right \|_2 \leq \sum_{i=1}^l \|b^1\|_2 $$ and there is equality if and only if $b^i = c_ib^1$ where $c^i > 0$.

Next note that since $e_1,...,e_k \in S_1^n$ and $x \mapsto Ax$ is a bijection of $S_1^n$ onto itself we have $Ae_1,...,Ae_k \in S_1^n$. In addition we can conclude that $Ae_i \neq cAe_j$ for $c \in \mathbb{R}$ for any pair $i \neq j$:

  • $c$ cannot be 1 because $Ae_i \neq Ae_j$ by injectivity
  • $c$ cannot be $-1$ since $(-1)Ae_i = A(-e_i)$ and $A(-e_i) \neq Ae_j$ by injectivity.
  • $c$ cannot be any other value because then either $\|Ae_i\|_1 \neq 1$ or $\|Ae_j\|_1 \neq 1$

From this we can conclude that for any $t_1,...,t_k \neq 0$ we have \begin{align} \left \| \sum_{i=1}^k At_ie_i \right \|_2 &= \left \| \sum_{i=1}^k t_i(Ae_i) \right \|_2 \\ &< \sum_{i=1}^k \|t_iAe_i\|_2 \end{align} and the inequality is strict because $t_iAe_i$ are all non-zero and $t_1Ae_1 \neq ct_iAe_i$ for any $i = 2,3,...,k$. In particular with $t_i = z^1_i$ we have \begin{align} \left \| \sum_{i=1}^k Az^1_ie_i \right \|_2 &< \sum_{i=1}^k \|Az^1_ie_i\|_2 \\ &= \sum_{i=1}^k |z^1_i|\|Ae_i\|_2 \\ &\leq \sum_{i=1}^k |z^1_i|\|Ae_i\|_1 \\ &\leq \sum_{i=1}^k |z^1_i|\|e_i\|_1 = \sum_{i=1}^k |z^1_i| = \|z^1\|_1 = 1 \end{align}

Overall we have established that $\|Az^1\|_2 < 1$. Finally this shows that $Az^1 \notin \{\pm e_1,...,\pm e_n\}$, which is the contradiction we sought.

Step 4 $A$ is a signed-permutation matrix.

By Step 3 we have for every $i=1,...,n$ that $Ae_i = \pm e_j$. This shows that the $i$'th column of $A$ is precisely $\pm e_j$ and therefore every column has exactly one non-zero entry, and additionally there are $n$ non-zero entries. If two non-zero entries are in the same row then there is a row with no entries, and as a result $A$ is not full rank which would contradict Step 1. This concludes the proof that $A$ is a signed permutation matrix.