## Isometries of the Vector p-Norms: Signed and Complex Permutation Matrices

Recall that in linear algebra, the vector p-norm of a vector x ∈ **C**^{n} (or x ∈ **R**^{n}) is defined to be

where x_{i} is the i^{th} element of x and 1 ≤ p ≤ ∞ (where the p = ∞ case is understood to mean the limit as p approaches ∞, which gives the maximum norm). By far the most well-known of these norms is the Euclidean norm, which arises when p = 2. Another well-known norm arises when p = 1, which gives the “taxicab” norm.

The problem that will be investigated in this post is to characterize what operators preserve the p-norms – i.e., what their isometries are. In the p = 2 case of the Euclidean norm, the answer is well-known: the isometries of the real Euclidean norm are exactly the orthogonal matrices, and the isometries of the complex Euclidean norm are exactly the unitary matrices. It turns out that if p ≠ 2 then the isometry group looks much different. Indeed, Exercise IV.1.3 of [1] asks the reader to show that the isometries of the p = 1 and p = ∞ norms are what are known as complex permutation matrices (to be defined). We will investigate those cases as well as a situation when p ≠ 1, 2, ∞.

### p = 1: The “Taxicab” Norm

Recall that a permutation matrix is a matrix with exactly one “1” in each of its rows and columns, and a “0” in every other position. A *signed permutation matrix* (sometimes called a *generalized permutation matrix*) is similar – every row and column has exactly one non-zero entry, which is either 1 or -1. Similarly, a *complex permutation matrix* is a matrix for which every row and column has exactly one non-zero entry, and every non-zero entry is a complex number with modulus 1.

It is not difficult to show that if x ∈ **R**^{n} then the taxicab norm of x is preserved by signed permutation matrices, and if x ∈ **C**^{n} then the taxicab norm of x is preserved by complex permutation matrices. We will now show that the converse holds:

**Theorem 1.** Let P ∈ M_{n} be an n × n matrix. Then

if and only if P is a complex permutation matrix (or a signed permutation matrix, respectively).

*Proof.* We only prove the “only if” implication, because the “if” implication is trivial (an exercise left for the reader?). So let’s suppose that P is an isometry of the p = 1 vector norm. Let e_{i} denote the i^{th} standard basis vector, let p_{i} denote the i^{th} column of P, and let p_{ij} denote the (j,i)-entry of P (i.e., the j^{th} entry of p_{i}). Then Pe_{i} = p_{i} for all i, so

Similarly, P(e_{i} + e_{k}) = p_{i} + p_{k} for all i,k, so

However, by the triangle inequality for the absolute value we know that the above equality can only hold if there exist non-negative real constants c_{ijk} ≥ 0 such that p_{ij} = c_{ijk}p_{kj}. However, it is similarly the case that P(e_{i} – e_{k}) = p_{i} – p_{k} for all i,k, so

Using the equality condition for the complex absolute value again we then know that there exist non-negative real constants d_{ijk} ≥ 0 such that p_{ij} = -d_{ijk}p_{kj}. Using the fact that each c_{ijk} and each d_{ijk} is non-negative, it follows that each row contains at most one non-zero entry (and each row must indeed contain at least one non-zero entry since the isometries of *any* norm must be nonsingular).

Thus every row has exactly one non-zero entry. By using (again) the fact that isometries must be nonsingular, it follows that each of the non-zero entries must occur in a distinct column (otherwise there would be a zero column). The fact that each non-zero entry has modulus 1 follows from simply noting that P must preserve the p = 1 norm of each e_{i}.

### p = ∞: The Maximum Norm

As with the p = 1 case, it is not difficult to show that if x ∈ **R**^{n} then the maximum norm of x is preserved by signed permutation matrices, and if x ∈ **C**^{n} then the maximum norm of x is preserved by complex permutation matrices. We will now show that the converse holds in this case as well:

**Theorem 2.** Let P ∈ M_{n} be an n × n matrix. Then

if and only if P is a complex permutation matrix (or a signed permutation matrix, respectively).

*Proof.* Again, we only prove the “only if” implication, since the “if” implication is trivial. So suppose that P is an isometry of the p = ∞ vector norm. As before, let e_{i} denote the i^{th} standard basis vector, let p_{i} denote the i^{th} column of P, and let p_{ij} denote the (j,i)-entry of P (i.e., the j^{th} entry of p_{i}). Then Pe_{i} = p_{i} for all i, so

In other words, each entry of P has modulus at most 1, and each column has at least one element with modulus equal to 1. Also, P(e_{i} ± e_{k}) = p_{i} ± p_{k} for all i,k, so

It follows that if |p_{ij}| = 1, then p_{kj} = 0 for all k ≠ i. Because each column has an element with modulus 1, it follows that each row has exactly 1 non-zero entry. Because each column has an entry with modulus 1, it follows that each row and column has exactly 1 non-zero entry, which must have modulus 1, so P is a signed or complex permutation matrix.

### Any p ≠ 2

When p = 2, the isometries are orthogonal/unitary matrices. When p = 1 or p = ∞, the isometries are signed/complex permutation matrices, which are a very small subset of the orthogonal/unitary matrices. One might naively expect that the isometries for other values of p somehow interpolate between those two extremes. Alternatively, one might expect that the signed/complex permutation matrices are the only isometries for all other values of p as well. It turns out that the latter conjecture is correct [2,3].

**Theorem 3.** Let P ∈ M_{n} be an n × n matrix and let p ∈ [1,2) ∪ (2,∞]. Then

if and only if P is a complex permutation matrix (or a signed permutation matrix, respectively).

**References:**

- R. Bhatia,
*Matrix analysis*. Volume 169 of Graduate texts in mathematics (1997). - S. Chang and C. K. Li,
*Certain Isometries on**R*^{n}. Linear Algebra Appl.**165**, 251–265 (1992). - C. K. Li, W. So,
*Isometries of l*_{p}*norm*. Amer. Math. Monthly**101**, 452–453 (1994).

hello.I had a question!

given an example of a vector norm that is not an p-norm.

@mohadese – The following norm on $latex \mathbb{R}^2&bg=EDEFF0$ is not a p-norm: $latex \|\mathbf{x}\| = 2|x_1| + |x_2|&bg=EDEFF0$.

A demonstration for the linear isometries in the R2 plan, for any p-norm is proposed in http://lucas.borboleta.blog.free.fr/index.php?trackback/2219894

http://lucas.borboleta.blog.free.fr/index.php?post/2012/07/15/The-group-of-linear-isometries-in-R2-is-discrete-and-finite-group-any-p-norm%2C-except-for-p2%21

Hi Nathaniel,

I wonder how the picture changes if you allow the output dimension to be larger than the input dimension. For example, in the p=1 case it seems that any map that sends standard basis to unit vectors (in 1-norm) with pairwise disjoint supports would be an isometry. Do maps of this form exhaust all isometries in the p=1 case?

Thanks,

~Maris~

@Maris Ozols – You’re absolutely right that such maps exhaust all isometries in the p = 1 case. This can be proved using a modification of the argument given in the blog post (it roughly goes as follows: (1) each column has 1-norm equal to 1, (2) given any two elements in the same row, they must have the same complex phase, (3) given any two elements in the same row, they must have *opposite* complex phases, (4) notice that (2) and (3) together imply that each row has at most 1 non-zero entry).

I’m not aware of a generalization of this to the other p-norms. I would recommend e-mailing Chi-Kwong Li if you need to know about the general case, as he would likely know what’s known.

Thanks! Actually I’m interested only in the p=1 case for matrices with non-negative entries. They correspond to Markov chains and represent classical analogues of unitary isometries.

I have a probably silly question. Why are stochastic matrices not a counterexample for the p=1 norm? What am I missing?

@Brian

Do you mean, a counterexample to Theorem 1? Indeed, stochastic matrices preserve the 1-norm of vectors with non-negative entries. However, an arbitrary vector might have negative entries, in which case the 1-norm may not be preserved. For example, if n=2 and all entries of P are equal to 1/2, then x = (1, -1) is mapped to zero.

Hello,

may you please help me with this question?

given a norm that is not p-norm, max_v |q.v| where v\in\R^N, such that (1,..,1,0,…,0) and q is any vector in \R^N, so the norm is defined the overall possibility of the vector v, then we want to prove that

|Pq.v|\leq max_v |q.v|,

what could be a useful property of the permutation matrix that can be used to prove this? Thank you

To be clear, the possibility of v is such that (1,1,0,…,0), (1,1,1,1,0,…,0) and so on.