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?
I think Jon’s right. What’s described in 2. is reminiscent of what is sometimes called the ‘contractive mapping principle’ (CMP) in analysis. But the map itself must be contractive in order to get the fixed point and just because a mapping is contractive does not mean it obeys the CMP.
“Would something like this work instead?
v->w = lim_(n->infty) 1/n(sum_{k=1}^{n}(PQ)^k).v”
Doh, yes that is much better.
I have to think about the joint systems a bit more, but you’re right the way I have it setup doesn’t feel satisfactory.
Suppose that if instead of restricting to stochastic matrices, I instead insist that the matrices are permutation matrices.
Are we just dealing with classical matrices here? If so, any doubly stochastic matrix can be written as a convex combination of permutation matrices anyway (Birkhoff’s theorem). Granted this doesn’t always hold in the quantum case, but I guess I’m not sure what you’re getting at. Because if all you’re interested in initially is how this “classical” world looks, why not consider doubly stochastic matrices instead of permutation matrices alone?
Hi Dave,
Unless I’m missing something, the limit in (2) might not converge. Consider P=Identity, Q=sigma_x, v=(1,0).
Would something like this work instead?
v->w = lim_(n->infty) 1/n(\sum_{k=1}^{n}(PQ)^k).v
Also, it’s not completely clear to me how joint systems work. Consider a 4d system, which is two 2d systems. Label the 4 basis elements 00,01,10,11. Consider the state corresponding to the permutation (00,01,10)(11) and the vector (1/6,1/6,1/6,1/2). If we measure this system, there are two possible outcomes. It seems most reasonable to say that this is a joint measurement that neither Alice nor Bob can do on their own. Is that right?
Consider now the same bipartite system, with state corresponding to permutation (00,01)(10,11) and v=(1/2q,1/2q,1/2r,1/2r). There is again a two outcome measurement, and it seems reasonable to suppose that Alice can perform it on her own, but not Bob. Is that right?
Finally, consider a 3×3 bipartite system, with state corresponding to permutation (00,11,02)(10,01,12)(20,21,22) and some value for v. Here, a measurement should have 3 outcomes, and I think Alice should not be able to perform it on her own. But it looks like she should at least be able to do a more limited thing – namely, to distinguish one value for the outcome from the other two. What do we say here?
The thing is, if we don’t allow Alice to do anything in the last case, then we may end up saying that the only time Alice and Bob can both do a measurement is when the state’s permutation matrix is the identity. Which would preclude interesting things like Bell violation.
Cheers, Jon
I had the same thought as Ian Durham, but he published first. Now the hammer that I’m holding, itching for a nail, is the Lefschetz Trace Formula, which counts the number of fixed points for a topological transformation.
There’s probably another tool in these old boxes:
Shashkin, Yu. A. Fixed Points. Providence, RI: Amer. Math. Soc., 1991.
Tabor, M. “Linear Stability Analysis.” §1.4 in Chaos and Integrability in Nonlinear Dynamics: An Introduction. New York: Wiley, pp. 20-31, 1989.
Any chance that this is useful?
arXiv:0902.1290 [ps, pdf, other]
Title: Boolean Inner product Spaces and Boolean Matrices
Authors: Stan Gudder, Frederic Latremoliere
Comments: 36 pages
Subjects: Rings and Algebras (math.RA)
This article discusses the concept of Boolean spaces endowed with a Boolean valued inner product and their matrices. A natural inner product structure for the space of Boolean n-tuples is introduced. Stochastic boolean vectors and stochastic and unitary Boolean matrices are studied. A dimension theorem for orthonormal bases of a Boolean space is proven. We characterize the invariant stochastic Boolean vectors for a Boolean stochastic matrix and show that they can be used to reduce a unitary matrix. Finally, we obtain a result on powers of stochastic and unitary matrices.
Let K be a finite complex, let h:|K|->|K| be a continuous map. If Lambda(h)!=0, then h has a fixed point.
Munkres, J. R. “Application: The Lefschetz Fixed-Point Theorem.” §22 in Elements of Algebraic Topology. New York: Perseus Books Pub.,pp. 121-128, 1993.
Jonathan, regarding your last post, I’m assuming since it’s a theorem (as opposed to a conjecture or something) that the book includes a proof? This could prove quite useful, if not for this possibly for something else I’m working on.
I don’t have a copy of the book at this time, to double check. I lend books, and sometimes don’t get them back. And I make notes from library books, and I no longer have access to all the libraries I’ve used. And please don’t assume that I’m any good at Algebraic Topology.
But there’s an elementary (not necessarily easy) explicit proof of the Lefschetz fixed point theorem for compact mappings of open subsets of locally convex topological vector spaces, in “The Lefschetz Fixed Point Theorem and Asymptotic Fixed Point Theorems”
Lecture Notes in Mathematics, Berlin/Heidelberg: Springer
ISSN 0075-8434 (Print) 1617-9692 (Online)
Volume 446/1975
Book: Partial Differential Equations and Related Topics
Copyright 1975
ISBN 978-3-540-07148-8
Given any partition of {1…d}, there exists a permutation whose disjoint cycles are that partition. Furthermore, given any permutation P, and any other permutation P’, there exists a permutation Q so that PQ=P’.
So, if you’re interested in what’s possible in the theory (rather than the particular dynamics that stem from particular permutation matrices), it boils down to this:
1. A system at any given time is defined by an arbitrary coarse-graining of an underlying d-element sample space;
2. At each timestep, the coarse-graining can change arbitrarily;
3. If you look at the system, you observe the coarse-grained state.
The most important conclusion I can think of is that this a hidden-variable theory, except that the variables aren’t necessarily hidden. Restricting the allowable coarse-grainings (permutations) would yield epistemic restrictions. For instance, with d=4, restricting to 2-cycle permutations like (12)(34) would give you the Spekkens model. However, this is tough to justify using permutations — if P is allowed, then it seems like P^n would be allowed, which will eventually get you the identity permutation, which reveals everything. But maybe there’s some reason why the allowed permutations shouldn’t be a group?
Anyway, unless I’m missing something, it seems like Bell and Kochen-Specker violation is ruled out by the [explicit] HV model.
Jonathan, thanks for the reference. I’ll look it up.