# 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. Dec 8, 2017 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. Dec 8, 2017 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. Dec 8, 2017 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. Dec 9, 2017 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, 2017 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.

• +1. Nice. Would you care to answer this question math.stackexchange.com/q/4418122/64809, where I query about a different proof in a paper for this very same theorem which I cannot make sense of?
– Hans
Apr 6, 2022 at 7:09

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, 2017 at 18:56
• Signed permutations of the canonical basis vectors -- it is a priori contained in the isometry group. Dec 9, 2017 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, 2017 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, 2017 at 14:16
• This looks great. But the information is a bit dense. Would you please be so kind as to unpack and expand out the details or provide references for the intermediate propositions? 1) Specifically, could you please write out the derivation for paragraph 2, e.g., what you mean by "scalar products are colinear"? Is $O(n)$ the orthogonal group? 2) Why does "Hence $G$ preserve the intersection of the $\ell^2$ and $\ell^p$ unit spheres"?
– Hans
Apr 2, 2022 at 0:51

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.

• This seems to be a sketch of an interesting proof. Would you please write out the details?
– Hans
Apr 5, 2022 at 10:23