Orbits of integers

Finds the orbit of a given integer

Usage

orbit_single(c1,n1)
orbit(cyc,n)

Arguments

c1,n1: In (low-level) function orbit_single(), a cyclist and an integer vector respectively
cyc,n: In (vectorized) function orbit(), cyc is coerced to a cycle, and n is an integer vector

Value

Given a cyclist c1 and integer n1, function orbit_single() returns the single cycle containing integer n1. This is a low-level function, not intended for the end-user.

Function orbit() is the vectorized equivalent of orbit_single(). Vectorization is inherited from cbind().

The orbit of a fixed point $p$ is $\left\lbrace p\right\rbrace$; the code uses an ugly hack to ensure that this is the case.

Author

Robin K. S. Hankin

Note

Orbits are useful in a more general group theoretic context. Consider a finite group $G$ acting on a set $X$, that is

$$\alpha\colon G\times X\longrightarrow X.$$

Writing $\alpha(g,x)=gx$, we define $\alpha$ to be a group action if $ex=x$ and $g(hx)=(gh)x$ where $g,h\in G$ and $e$ is the group identity. For any $x\in X$ we define the orbit $Gx$ of $x$ to be the set of elements of $X$ to which $x$ can be moved by an element of $G$. Symbolically:

$$Gx=\left\lbrace gx\colon g\in G\right\rbrace$$

Now, we abuse notation slightly. In the context of permutation groups, we consider a fixed permutation $\sigma$. We consider the group $G=\left\langle\sigma\right\rangle$, that is, the group generated by $\sigma$; the group action is that of $G$ on set $X=\left\lbrace 1,2,\ldots,n\right\rbrace$ with the obvious definition $\sigma x=\sigma(x)$ for $\sigma\in G$ and $x\in X$. This clearly is a group action as $\operatorname{id}(x)=x$ and $\sigma(\mu x)=(\sigma\mu)x$.

$$Gx=\bigcup_{i\in\mathbb{Z}}\sigma^i(x)$$

Expressing $\sigma$ in cycle form makes it easy to see that the orbit of any element $x$ of $X$ is just the other members in the cycle containing $x$. For example, consider $\sigma=(26)(348)$ and $x=4$. Then

$$G=\left\langle(26)(348)\right\rangle = \bigcup_{i\in\mathbb{Z}}[(26)(348)]^i$$

Because we are only interested in the effects on $x=4$, we only need to consider the cycle $(348)$: this is the only cycle that affects $x=4$, and the $(26)$ cycle may be ignored as it does not affect element 4. So

$$G4=\bigcup_{i\in\mathbb{Z}}(348)^i(4)=\left\lbrace 3,4,8\right\rbrace$$

[observe the slight notational abuse above: “$(348)$” means “the function $f(\cdot)$ with $f(3)=4$, $f(4)=8$, and $f(8)=3$”].

Examples