orbit: Orbits of integers

In RobinHankin/permutations: The Symmetric Group: Permutations of a Finite Set

Orbits of integers

Description

\loadmathjax

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 \mjseqnp is \mjeqn\left\lbrace p\right\rbraceomitted; 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 \mjseqnG acting on a set \mjseqnX, that is

\mjdeqn\alpha\colon

G\times X\longrightarrow X.omitted.

Writing \mjeqn\alpha(g,x)=gxomitted, we define \mjeqn\alphaomitted to be a group action if \mjseqnex=x and \mjseqng(hx)=(gh)x where \mjeqng,h\in Gomitted and \mjseqne is the group identity. For any \mjeqnx\in Xomitted we define the orbit \mjseqnGx of \mjseqnx to be the set of elements of \mjseqnX to which \mjseqnx can be moved by an element of \mjseqnG. Symbolically:

\mjdeqn

Gx=\left\lbrace gx\colon g\in G\right\rbraceomitted

Now, we abuse notation slightly. In the context of permutation groups, we consider a fixed permutation \mjeqn\sigmaomitted. We consider the group \mjeqnG=\left\langle\sigma\right\rangleomitted, that is, the group generated by \mjeqn\sigmaomitted; the group action is that of \mjseqnG on set \mjeqnX=\left\lbrace 1,2,...,n\right\rbraceX=1,2,...,n with the obvious definition \mjeqn\sigma x=\sigma(x)omitted for \mjeqn\sigma\in Gomitted and \mjeqnx\in Xomitted. This clearly is a group action as \mjeqn\operatornameid(x)=xid(x)=x and \mjeqn\sigma(\mu x)=(\sigma\mu)xomitted.

\mjdeqn

Gx=\bigcup_i\in\mathbbZ\sigma^i(x)omitted

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

\mjdeqn

G=\left\langle(26)(348)\right\rangle = \bigcup_i\in\mathbbZ[(26)(348)]^iomitted

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

\mjdeqn

G4=\bigcup_i\in\mathbbZ(348)^i(4)=\left\lbrace 3,4,8\right\rbraceomitted

[observe the slight notational abuse above: “\mjseqn(348)” means “the function \mjeqnf(\cdot)f(.) with \mjseqnf(3)=4, \mjseqnf(4)=8, and \mjseqnf(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)

RobinHankin/permutations documentation built on March 29, 2024, 5:34 p.m.