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

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.

• The unit sphere for the $1$ norm is the surface of a cross-polytope. Trying to map it linearly onto itself has to preserve the extremal points (=vertices) of the cross-polytope. So we end up with just a signed permutation. There are details to be filled in, but I think this should more or less work. – Gro-Tsen Dec 8 '17 at 22:46
• I assume, a signed permutation is just a permutation matrix where some ones can be negative? Hmm they definitely preserve this, but are those really all preserving matrices? 'Cause there are only finitely many such matrices for each dimension of the vector space. – D. Rusin Dec 8 '17 at 23:03
• Yes, a signed permutation is what you said, and yes, there are only finitely many of them. The geometric argument with the cross-polytope is meant to explain why they are the only $L^1$-norm-preserving matrices. – Gro-Tsen Dec 8 '17 at 23:10
• @Gro-Tsen Just one more question: Is it also true that the signed permutations are exactly the matrices preserving the L_p-norm for all p > 2? Because the unit sphere for the p-norm for p > 2 is the surface of something with (more or less) sharp edges as well. – D. Rusin Dec 9 '17 at 0:44
• Yes it's true for all $p\neq 2$, although tricks using extremal points work only for $p=1,\infty$. It's classical but I have no optimal reference (projecteuclid.org/download/pdf_1/euclid.bams/1183538497 sounds too general) Maybe one can use extremal properties of some curvature function on the unit sphere (for $1<p<2$ one could expect the scalar curvature to be maximal on vertices of the cross-polytope, and for $p>2$ idem in the dual). – YCor Dec 9 '17 at 9:25

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.

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

• I may have missed this somewhere, but what is W? – j.c. Dec 9 '17 at 18:56
• Signed permutations of the canonical basis vectors -- it is a priori contained in the isometry group. – Denis Chaperon de Lauzières Dec 9 '17 at 19:00
• Thanks (I erased a draft longer message since I initially started using some Lie group stuff, and then forgot copying the definition of $W$, which could be guessed by people familiar with Weyl groups, or just because it's accidentally defined in the message as the stabilizer of $V$) – YCor Dec 9 '17 at 19:03
• My initial approach consisted in proving that $W$ is a maximal subgroup of $\mathrm{O}(n)$ for $n\ge 3$ (it's false for $n=2$)- I mention it as it yields a stronger conclusion. It's easy to see that $W$ acts irreducibly for the adjoint representation, so any proper subgroup containing $W$ is finite. Using the classification of groups generated by reflections (see standard treatments on Coxeter groups), $W(\simeq B_n)$ is maximal among finite subgroups with the possible exceptions $n=4,8$, which I haven't checked properly (need to discard inclusions $B_4\subset F_4$ and $B_8\subset E_8$). – YCor Dec 10 '17 at 14:16

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