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

## Recent Comments