Recall that in linear algebra, the vector p-norm of a vector x ∈ Cⁿ (or x ∈ Rⁿ) 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ⁿ then the taxicab norm of x is preserved by signed permutation matrices, and if x ∈ Cⁿ 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_ijkp_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_ijkp_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ⁿ then the maximum norm of x is preserved by signed permutation matrices, and if x ∈ Cⁿ 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:

1. R. Bhatia, Matrix analysis. Volume 169 of Graduate texts in mathematics (1997).
2. S. Chang and C. K. Li, Certain Isometries on Rⁿ. Linear Algebra Appl. 165, 251–265 (1992).
3. C. K. Li, W. So, Isometries of l_p norm. Amer. Math. Monthly 101, 452–453 (1994).