Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I created a random isometry $T$ of $\mathbb{R}^3$ by generating a random orthogonal matrix $M$, uniformly distributed among all such, and a random displacement $v$, whose coordinates are drawn from a zero-mean normal distribution. For a point $p \in \mathbb{R}^3$, $T(p) = M . p + v$.

Let $T_1$ and $T_2$ be two such random isometries. Now, starting with $p_0=(0,0,0)$, I formed the sequence of points $p_1 = T_1(p_0)$, $p_2 = T_2(p_1)$, $p_3 = T_1(p_2)$, $p_4 = T_2(p_3)$, and so on, altering the two isometries one after the other, so $$p_{2i} = T_2 \cdot T_1 \cdot T_2 \cdot T_1 \cdot T_2 \cdot \ldots \cdot T_1 ( p_0 ) \;.$$ Because the isometries are random, and include a random translation, I expected the $p_i$ to wander off to infinity, and indeed this is common:
         Triangles
Above, the red segments connect $p_i$ to $p_{i+1}$. Essentially these look like two spirals of points forming an unbounded V.

However, (very) roughly 40% of the time, instead spirograph-like bounded rings are formed (or at least: apparently bounded, apparently rings):
     Rings
So far inspecting the transformations numerically has not led me to an understanding of this phenomenon. If anyone sees intuitively why this process might lead to essentially two qualitatively different shapes, I'd appreciate an explanation. A specific question is:

Is there a positive probability that $|p_i|$ remains bounded as $i \to \infty$?

I thought the answer should be No but my simulations indicate Yes.


Answered. Both Benoît Kloeckner and Ofer Zeitouni answered the question, using rather different language but ultimately equivalently. One way to summarize the computational consequence their analyses is this: If $\det(M_1 \cdot M_2)=1$, the sequences is unbounded; if instead this determinant is $-1$, the sequence is bounded. As Benoît says, the analysis holds for any number of transformations ($k$-steps rather than two-steps), in which case the $\pm 1$ determinant of the product of the $k$ matrices signifies bounded/unbounded. Here is an example of a bounded 4-step sequence.
           Rings4
Now I can generate an infinite variety of these elegant figures! Thanks for everyone's help!

share|improve this question
3  
Some days I wish there were something along the lines of a JO.joseph-o'rourke-question tag so that it would be easier for me to scroll through the front page to find interesting questions with cool pictures. –  ARupinski Jul 13 '13 at 1:40
    
:-) $\mbox{}\mbox{}$ –  Joseph O'Rourke Jul 13 '13 at 13:28

2 Answers 2

up vote 10 down vote accepted

I assume your random $M_i$s are from $O(3)$, not $SO(3)$. In fact, I suspect that the answer depends on whether $M_1M_2$ has eigenvalue $1$ or eigenvalue $-1$.

If I did not make a mistake, when you expand $p_{2i}$, you will get essentially $$\sum_{k=0}^{i-1} U^k x_1+ V\left(\sum_{k=1}^{i-1} U^i\right)^T x_2$$ Here $U=M_2M_1$ and $V$ is also an orthogonal matrix.

Now, $U$ is an orthogonal matrix, and has a conjugate pair of eigenvalues as well as an eigenvalue that is either $1$ or $-1$. Call these $r_1, r_1^*$ and $r_2$.

If $r_2=1$, obviously you run off to infinity.

If $r_2=-1$, you get an oscillating sum, which remains bounded.

I have not written down a formal proof but it seems to me that the terms due to $\sum r_1^k$ (and the conjugate of that) are essentially harmless - even if they run off to infinity, they do it VERY slowly (if the angles corresponding to the $r_1$ are rational, you would get a bounded sum; in reality you are rational with probability $0$, but on a computer....).

Note added: Of course, $\sum_{k=0}^i r_1^k$ remains bounded as long as $|1-r_1|$ is bounded below, which occurs with probability $1$. I should have noted that instead of the nonsense I wrote above concerning not writing a formal proof....

share|improve this answer
    
Oh, you are right! I can confirm this experimentally. Brilliant!! –  Joseph O'Rourke Jul 12 '13 at 21:53
2  
I guess our answers give a nice illustration of the dichotomy between using coordinates or avoiding them, that was discussed in another question. –  Benoît Kloeckner Jul 13 '13 at 6:34

This phenomenon is to be expected: the point is to recall the classification of isometries and that indirect isometries almost always have fixed points, while direct ones almost always have no fixed points.

The fact that there are two isometries is not relevant to the boundedness of the dynamic: let us look at $U=T_2\circ T_1$. This is a random isometry, whose law may be involved but is certainly absolutely continuous. Writting $U\cdot p = A\cdot p + w$, it has a fixed point if and only if $w$ is in the image of $A-I$. There are two cases.

First, $A$ is a direct isometry, aka a rotation. Then $1$ is an eigenvalue and $A-I$ has rank $2$. Then with probability $1$, $w$ is not in the image of $A-I$, $U$ has no fixed point and its orbits are all unbounded.

Second, $A$ is an indirect isometry (an anti-rotation with full (conditional) probability). Then $A-I$ is invertible and $U$ has a fixed point, so that all its orbits are bounded.

Probably more interesting things happen if you choose randomly at each step whether to apply $T_1$ or $T_2$; such random dynamical systems have already been studied in different contexts.

share|improve this answer
    
I first explored exactly what you suggest: choosing whether to apply one or the other transformation randomly. It generally just makes a growing ball of points, less interesting (aesthetically!) than what I am seeing in the process I described. –  Joseph O'Rourke Jul 12 '13 at 20:36
    
What about a deterministic, interesting sequence of 0 and 1 then? Thue-Morse for example. –  Benoît Kloeckner Jul 13 '13 at 6:31
    
Thanks, Benoît! At first I didn't see that your and Ofer's analyses were essentially equivalent, but your comment about "coordinate-free" clarified. There is more to explore here... –  Joseph O'Rourke Jul 13 '13 at 13:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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