10
$\begingroup$

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.

EDIT:

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
    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.2012-04-06

2 Answers 2

7

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.

  • 1
    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.2012-04-07
1

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.