It's easy to show that orthogonal/unitary matrices preserve the $L_2$ norm of a vector, but if I want a transformation that preserves the $L_1$ norm, what can I deduce about the matrices that do this? I feel like it should be something like the columns sum to 1, but I can't manage to prove it.


To be more explicit, I'm looking at stochastic transition matrices that act on vectors that represent probability distributions, i.e. vectors whose elements are positive and sum to 1. For instance, the matrix

$$ M = \left(\begin{array}{ccc}1 & 1/4 & 0 \\0 & 1/2 & 0 \\0 & 1/4 & 1\end{array}\right) $$

acting on

$$ x=\left(\begin{array}{c}0 \\1 \\0\end{array}\right) $$

gives $$ M \cdot x = \left(\begin{array}{c}1/4 \\1/2 \\1/4\end{array}\right)\:, $$ a vector whose elements also sum to 1.

So I suppose the set of vectors whose isometries I care about is more restricted than the completely general case, which is why I was confused about people saying that permutation matrices were what I was after.

Sooo... given the vectors are positive and have entries that sum to 1, can we say anything more exact about the matrices that preserve this property?

  • 2
    $\begingroup$ Look at the extremal points of the unit ball. $\endgroup$ – t.b. Apr 6 '12 at 14:51
  • $\begingroup$ My first guess is that such matrices need to correspond to signed permutations of the coordinates, i.e. a finite group. $\endgroup$ – Jyrki Lahtonen Apr 6 '12 at 14:54
  • $\begingroup$ @Jyrki: your first guess is perfectly right and in fact it holds for all $\ell^p$-spaces (and in an appropriate reformulation also for $L^p[0,1]$) with $p \neq 2$, of course -- this is a theorem due to Banach and Lamperti, see also here. $\endgroup$ – t.b. Apr 6 '12 at 14:57
  • $\begingroup$ Thanks @t.b., the unit ball does it in this case. I will study your link for the general $\ell^p, p\neq 2$. $\endgroup$ – Jyrki Lahtonen Apr 6 '12 at 14:59
  • 2
    $\begingroup$ Thanks for your comments -- I saw that thread and another one talking about isometries, but wasn't sure if this was exactly the same question, because the answers for those seemed to talk about permutation matrices, and I'm not sure if that's what I'm after. Sorry if I'm misusing technical terms; I'll edit my question to provide an example of what I'm talking about. $\endgroup$ – Rory Apr 6 '12 at 16:03

The matrices that preserve the set $P$ of probability vectors are those whose columns are members of $P$. This is obvious since if $x \in P$, $M x$ is a convex combination of the columns of $M$ with coefficients given by the entries of $x$. Each column of $M$ must be in $P$ (take $x$ to be a vector with a single $1$ and all else $0$), and $P$ is a convex set.

  • $\begingroup$ Thanks for your answer. I don't think I quite see why it's obvious though, as I'm not handy with convexity arguments. Can you explain a bit more why each column of $M$ must be in $P$? $\endgroup$ – Rory Apr 6 '12 at 16:39
  • 1
    $\begingroup$ For example, the first column of $M$ is $M e$ where $e_1 = 1$ and $e_2 = \ldots = e_n = 0$. $\endgroup$ – Robert Israel Apr 6 '12 at 16:44
  • 1
    $\begingroup$ Hi Robert. Thanks. I guess I see why that example works, but not why it's necessarily the most general case. Sorry if I'm being obtuse. $\endgroup$ – Rory Apr 6 '12 at 16:48
  • 1
    $\begingroup$ Another way to put it is that the columns of $P$ are discrete distributions. Multiplying such a matrix by another distribution will yield a mixture of the columns, where the mixture weights sum to 1, hence that mixture must also be a discrete distribution. $\endgroup$ – ely Apr 6 '12 at 17:37
  • 1
    $\begingroup$ Once you know each column of $M$ is in $P$, for any $x \in P$ you have $Mx \in P$ because a convex set contains all convex combinations of its members. $\endgroup$ – Robert Israel Apr 7 '12 at 0:56

Since you originally asked about $L^1$ spaces I dared to add this comment.

If one wants to preserve the integral in (finite-dimensional and with finite measure ) $L^1$ spaces rather than the norm of $\ell^p$, the matrices $M$ that do this are more general than the stochastic matrices.

One can define these matrices with two components, labeled $S$ (for the stochastic component) and $G$ (for the generalized permutation matrix component) such that that $M= S * G$, where * represents the Hadamard product.

The $S$ matrices are effectively stochastic matrices as shown by Robert Israel.

The $G$ matrix is given by the unique matrix resulting of the outer product $u_{\mu} \otimes \frac{1}{u_{\mu}} := | u_{\mu} \rangle \langle \frac{1}{u_{\mu}} |$ of the unique column vector $u_{\mu} :=\left(\begin{array}{c}\mu_1 \\ \mu_2 \\ \ldots \\ \mu_2\end{array}\right)$ and the also unique row vector $\frac{1}{u_{\mu}} :=\left(\frac{1}{\mu_1} \ \frac{1}{\mu_2} \ \ldots \ \frac{1}{\mu_n}\right)$:

$G:=u_{\mu} \otimes \frac{1}{u_{\mu}} = \left(\begin{array}{cccc} 1 & \frac{\mu_2}{\mu_1} & \ldots & \frac{\mu_n}{\mu_1} \\ \frac{\mu_1}{\mu_2} & 1 & \ldots & \frac{\mu_n}{\mu_2} \\ \ldots & \ldots & \ldots & \ldots \\ \frac{\mu_1}{\mu_n} & \frac{\mu_2}{\mu_n} & \ldots & 1 \end{array}\right)$

where $\mu_i$ are the measures of the generating family of subsets $\{ A_i \}$ of the underlying sigma algebra, i.e. $\mu_i := \mu(A_i)$ and $n = |\{ A_i \}|$.

To give you an example of where the stochastic component $S$ is absent, take the stochastic matrix $S$ to be simply a permutation matrix. In this case your $M$ that preserves the integral is a generalized permutation matrix whose non-zero elements are of the form $A_{i,j} =\frac{\mu_{j}}{\mu_i}$.

To see why the measure values $\mu_i$ are needed in the definition of $M$ recall that a $L^p$ space is defined given a measure space $(X,\Sigma,\mu)$. So if the $L^1$ space is finite dimensional then the vectors $v$ in $L^1$ are simple functions, whose integral is defined as the product $\langle u_{\mu}|v\rangle$. And if the measure is finite, then this integral is always well defined.

I hope I made myself clear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.