Skip to main content
MathOverflow

Return to Answer

Added a suitable interpolation based on the first argument.
Source Link
Matt Werenski
Matt Werenski
  • 161
  • 5

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.

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.$$

Updated Complete Answer After a long think, I've come up with an interpolation of the two matrices which may be sufficient.

For $p \geq 1$ define $C(p) = (1- \lambda(p))A + \lambda(p)B$ where $$\lambda(p) = \frac{1}{n^{1/p}} - \frac{1}{pn}$$ This specifically so that it has the following properties

  1. $\lambda(1) = 0$ which ensures $C(1) = A$
  2. $\lim_{p \rightarrow \infty} \lambda(p) = 1$ which ensures $\lim_{p \rightarrow \infty} C(p) = B$
  3. $\lambda$ is smoothly monotonically increasing on $[1,\infty)$
  4. $\lambda(p) < \frac{1}{n^{1/p}}$ for all $p \in [1,\infty)$.

The last part is essential because of the inequality \begin{align}\|x\|_p &= \left ( \sum_{i=1}^n |x_i|^p \right )^{1/p} \\ &= \|x\|_\infty \left ( \sum_{i=1}^n \left(\frac{|x_i|}{\|x\|_\infty }\right)^p \right )^{1/p} \\ &\leq \|x\|_\infty \left ( \sum_{i=1}^n 1^p \right )^{1/p} = \|x\|_\infty n^{1/p} \end{align} Applying this with $\lambda(p)Bx$ gives \begin{align} \|\lambda(p)Bx\|_p &= \lambda(p)\|Bx\|_p \\ &\leq \lambda(p) n^{1/p}\|Bx\|_\infty \\ &\leq \left ( \frac{1}{n^{1/p}} \right )n^{1/p}\|x\|_\infty \\ &= \|x\|_\infty \leq \|x\|_p. \end{align} Combining these facts with Minkowski's inequality gives the bound \begin{align} \|C(p)x\|_p &= \|(1-\lambda(p))Ax + \lambda(p)Bx\|_p \\ &\leq \|(1-\lambda(p))Ax\|_p + \|\lambda(p)Bx\|_p \\ &\leq (1-\lambda(p))\|Ax\|_p + \|x\|_p \\ &= (1-\lambda(p))\|x\|_p + \|x\|_p \leq 2\|x\|_p \end{align} which shows that this choice of $C(p)$ interpolates between $A$ and $B$ and satisfies the bound with $K = 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.

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.$$

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.

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.$$

Updated Complete Answer After a long think, I've come up with an interpolation of the two matrices which may be sufficient.

For $p \geq 1$ define $C(p) = (1- \lambda(p))A + \lambda(p)B$ where $$\lambda(p) = \frac{1}{n^{1/p}} - \frac{1}{pn}$$ This specifically so that it has the following properties

  1. $\lambda(1) = 0$ which ensures $C(1) = A$
  2. $\lim_{p \rightarrow \infty} \lambda(p) = 1$ which ensures $\lim_{p \rightarrow \infty} C(p) = B$
  3. $\lambda$ is smoothly monotonically increasing on $[1,\infty)$
  4. $\lambda(p) < \frac{1}{n^{1/p}}$ for all $p \in [1,\infty)$.

The last part is essential because of the inequality \begin{align}\|x\|_p &= \left ( \sum_{i=1}^n |x_i|^p \right )^{1/p} \\ &= \|x\|_\infty \left ( \sum_{i=1}^n \left(\frac{|x_i|}{\|x\|_\infty }\right)^p \right )^{1/p} \\ &\leq \|x\|_\infty \left ( \sum_{i=1}^n 1^p \right )^{1/p} = \|x\|_\infty n^{1/p} \end{align} Applying this with $\lambda(p)Bx$ gives \begin{align} \|\lambda(p)Bx\|_p &= \lambda(p)\|Bx\|_p \\ &\leq \lambda(p) n^{1/p}\|Bx\|_\infty \\ &\leq \left ( \frac{1}{n^{1/p}} \right )n^{1/p}\|x\|_\infty \\ &= \|x\|_\infty \leq \|x\|_p. \end{align} Combining these facts with Minkowski's inequality gives the bound \begin{align} \|C(p)x\|_p &= \|(1-\lambda(p))Ax + \lambda(p)Bx\|_p \\ &\leq \|(1-\lambda(p))Ax\|_p + \|\lambda(p)Bx\|_p \\ &\leq (1-\lambda(p))\|Ax\|_p + \|x\|_p \\ &= (1-\lambda(p))\|x\|_p + \|x\|_p \leq 2\|x\|_p \end{align} which shows that this choice of $C(p)$ interpolates between $A$ and $B$ and satisfies the bound with $K = 2$.

Source Link
Matt Werenski
Matt Werenski
  • 161
  • 5

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.