What are the matrices preserving the $\ell^1$-norm?

Question

So I am inspired by unitary matrices which preserve the $\ell^2$-norm of all vectors, so in particular the unit norm vectors. But then I saw that the $\ell^1$-norm of probability vectors is preserved by matrices whose columns are probability vectors. And this got me thinking: But what are the matrices preserving the $\ell^1$-norm of arbitrary real unit $\ell^1$-norm vectors? So basically we extend a probability vector to also allow a sign, but ignoring the signs, this should still be a probability vector; and then we ask for the corresponding structure-preserving matrices.

It is already clear that the columns of such a matrix should be this 'extended' kind of probability vector, because we can multiply the matrix with a standard basis vector which has $\ell^1$-norm 1. But not all of such matrices preserve this, take for example

$$ M = \frac{1}{2} \left(\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right) $$

and

$$ x = \left( \begin{matrix} 0.3 \\ -0.7 \end{matrix} \right) $$

Then we have

$$ Mx = \left(\begin{matrix} -0.2 \\ 0.5 \end{matrix}\right) $$

which fails the test.

Answer 1

As pointed out by YCor in the comments, the following theorem is true:

Theorem 1 Let $p \in [1,\infty] \setminus \{2\}$. If a matrix $A \in \mathbb{R}^{n \times n}$ is an isometry on $\mathbb{R}^n$ with respect to the $p$-norm, then $A$ is a signed permutation matrix, i.e. a permutation matrix where some of the one's are replaced with $-1$.

For the proof, first note that the case $p = \infty$ follows from $p = 1$ by duality, so we only have to show the theorem for $\in [1,\infty) \setminus 2$.

Now we use the following lemma:

Lemma 2 Let $p \in [1,\infty) \setminus \{2\}$ and let $(\Omega_1,\mu_1)$ and $(\Omega_2,\mu_2)$ be two measure spaces. If $T: L^p(\Omega_1,\mu_1) \to L^p(\Omega_2,\mu_2)$ is an isometric linear mapping, then $T$ is disjointness preserving, i.e. for all $f,g \in L^p(\Omega_1,\mu_1)$ which fulfil $fg = 0$, we also have $(Tf)(Tg) = 0$.

In a more general form, this lemma goes originally back to Lamperti ("On the isometries of certain function spaces", Pacific J. Math. 8 (1958), 459–466.).

A very clear proof of the lemma in the above form can be found in Lemma 4.2.2 of S. Facklers PhD dissertation (DOI: 10.18725/OPARU-3268).

If we apply Lemma 2 to $L^p(\Omega_1,\mu_1) = L^p(\Omega_2,\mu_2) = \mathbb{R}^n$, it follows that every matrix $A \in \mathbb{R}^{n \times n}$ which is isometric with respect to the $p$-norm is automatically disjointness preserving. Hence, every row of $A$ contains exactly one non-zero entry. Since $A$ is invertible, this implies that every column of $A$ also contains exactly one non-zero entry. Thus, $A$ is of the form $A = DP$, where $P$ is a permutation matrix and $D$ is a diagonal matrix. Using again that $A$ is isometic, we can see that $D$ can only have the numbers $1$ and $-1$ on its diagonal.

Remarks:

(a) Lemma 2 is of course quite general compared to the finite dimensional question. However, I don't think that a finite dimensional version of Lemma 2 is easier to prove.

(b) Using Lemma 2 above, one can also obtain a description of isometries on general $L^p$-spaces; see Theorem 3.1 in Lamperti's article quoted above.

Answer 2

There's a very simple approach in finite dimension. Let $G$ be the linear isometry group of $(\mathbf{R}^n,\|\cdot\|_p)$, $1\le p\le\infty$. Let $W$ be the group of signed permutations.

First, since $W$ acts irreducibly on $\mathbf{R}^n$, all scalar products it preserves are collinear. Since $G$ is compact, it preserve a scalar product, and hence since $W\subset G$ we deduce $G\subset\mathrm{O}(n)$.

Hence $G$ preserve the intersection of the $\ell^2$ and $\ell^p$ unit spheres. This is precisely, for $p\neq 2$, the set $V$ of those $2n$ vectors of the form $\pm e_i$, where $(e_i)$ is the canonical basis. The stabilizer of $V$ in $\mathrm{GL}_n(\mathbf{R})$ is easily seen to be reduced to $W$.

Hence for $p\neq 2$ we deduce $G=W$.

(Note that the full isometry group is generated by $G$ and translations, by the Mazur-Ulam theorem saying that surjective self-isometries fixing 0 are linear.)

Answer 3

Here is yet another (sketch of the) proof that the matrices preserving the $p$-norm for $p\neq 2$ are generated by permutation matrices, and the diagonal ones with diagonal elements of absolute value $1$.

$\let\eps\varepsilon$I address the real case; but the complex one should be similar.

If $2<p<\infty$, then the tangent hyperplanes to the unit sphere at the points $\pm e_i$ approximate the ball uniformly with the error $\Theta(\eps^p)$. This does not happen at other points; hence these points are permuted, and the matrix is a permutation matrix (with, possibly, changed signs).

Similarly, if $1<p<2$, those tangents approximate the ball in the worst possible way, thus the same result.

For $p=1$ or $p=\infty$, the vertices of the ball map to the vertices, and the edges to the edges; hence the result follows again.