Posted by In a prior post I asked about the how the structure of fixed points of stochastic maps changes under composition of such maps. Robin provided an interesting comment about the setup, linking this question at least partially with zero error codes:
R has at least one fixed point. If it’s unique, there need be no relationship between fixed points of P and R. (Q can project to a single vector, which becomes the unique fixed point of R.) If R has N > 1 fixed points, then things get more interesting. The fixed points are closed under linear combination, so they’re a subspace (I’m actually assuming N is the dimension of the subspace). An N-dimensional fixed subspace gives an N-symbol noiseless code for N (not necessarily obvious, but see arxiv/0705.4282), and therefore an N-symbol correctable code for P. Q is the recovery map. So, the dimensionality of R‘s fixed-point space (N) is tightly bounded by the size of P‘s largest zero-error code, and the fixed-point set itself has to be a subspace of one of those codes. You can also transpose R and get an identical bound in terms of QT‘s zero-error codes. (Yes, I know QT isn’t necessarily stochastic, but it works anyway). The zero-error codes are independent sets of P‘s adjacency graph, so (a) there can be quite a few of them, and (b) finding the bound on N is isomorphic to Maximum Clique.
Robin scores double bonus old school points for linking to a paper by Shannon. Okay, so given that the general case seems hard (and my question was vague), maybe it’s better to work with a simpler concrete example of what I’m thinking.
Suppose that if instead of restricting to stochastic matrices, I instead insist that the matrices are permutation matrices. A square matrix is a permutation matrix if every column and every row is made up of one 1 and n-1 0s. Any permutation matrix can be expressed in cycle notation where each permutation can be expressed as a product of k disjoint cycles: 
. What are the fixed points of these matrices? Suppose you have a permutation matrix P with k disjoint cycles. Then for every one of these k disjoint cycles one can see that a uniform distribution over the letters in the particular cycle is a fixed point of the matrix. Further if you take any other distribution over a the elements in a cycle it will not be fixed. Further any convex combination of uniform distributions over different cycles is also a fixed point.
Thus for permutation matrices, the fixed points are easily enumerated: if we specify the permutation as k disjoint cycles and then associate each of these cycles with a probability, this defines a fixed point weighted by the probability associated with the cycle and then uniformly distributed across the cycle elements. For example we might be working with permutations on a four dimensional space. Then the relevant group is the symmetric on four elements. For a permutation in cycle notation 
the fixed points will be a two dimensional and given by the probability vector
Now lets see if we can make this into some sort of crazy “physical” model illuminating what I meant in terms of the structure of fixed points under these maps.
- The “state” of a system is specified by a permutation matrix P of dimension d along with a fixed point of this matrix: a vector v. This fixed point can be expressed as a vector over the disjoint cycles of the permutation matrix. Thus we can specify the state as a tuple (P,v). Implicitly there is also the dimension of the system, d.
- “Evolution” of system is given by a permutation matrix Q. This changes the state of the system as follows. If the only permutation matrix was P, the new permutation matrix is PQ. The fixed point is the fixed point which would arise if we repeatedly applied PQ to the old vector v. In other words the state (P,v) changes under evolution Q to lim<sub>n goes to infinity</sub>(PQ,PQ^n v)
- “Measurement” of a state (P,v) results in a number of outcomes given by the number of disjoint cycles in P. The probability of the outcome corresponding to the disjoint cycle is given by the sum over the vector v of the elements in this cycle. After this measurement, the new state is given by (P,w) where P is the same permutation matrix and w is the probability distribution which is uniform over the cycle corresponding to the measurement outcome.
- “Subsystems” can be defined in a natural manner using a tensor product space. In particular we can consider two systems of dimension d1 and d2 and construct a new system with dimension d1 times d2. We can then define “local” operations on each of the spaces.
Given this definition one can begin to explore what kind of world the above world would be. For example can you mock up anything that looks like interference? Does the above model violate a Bell inequality? Do we get signaling distributions using the above model? What about something similar to the Kochen-Specker theorem?
February 9, 2009
February 9, 2009
February 9, 2009
February 9, 2009
February 12, 2009