orbit {permutations}

Orbits of integers

Description

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.

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”].

Author(s)

Robin K. S. Hankin

See Also

fixed

Examples

orbit(as.cycle("(123)"),1:5)
orbit(as.cycle(c("(12)","(123)(45)","(2345)")),1)
orbit(as.cycle(c("(12)","(123)(45)","(2345)")),1:3)

data(megaminx)
orbit(megaminx,13)