Orbit

Return to Glossary.

Formal Definition


Define an equivalence relation $\sim$ such that, for $a,b\in A$, $a\sim b$ if and only if $b=\sigma ^n(a)$ for some $n\in \mathbb{Z}$ and permutation $\sigma$ on $A$.
Let $\sigma$ be a permutation on a set $A$. Then the equivalence classes in $A$ determined by the equivalence relation $\sim$ are the orbits of $\sigma$.

Informal Definition


An orbit is a certain type of set that is associated with a permutation $\sigma$ of a set $A$ that is defined as follows:
If you start out with an element of $A$ and repeatedly apply $\sigma$ to it, then the set of all the elements you obtain is an orbit of $\sigma$.

Example(s)


Consider the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 7 & 4 & 1 & 5 & 2 \end{pmatrix}$ in $S_8$

To find the orbit containing $1$ we apply $\sigma$ repeatedly, obtaining

(1)
\begin{align} 1 \xrightarrow{\sigma} 3 \xrightarrow{\sigma} 6 \xrightarrow{\sigma} 1 \xrightarrow{\sigma} 3 \xrightarrow{\sigma} 6 \xrightarrow{\sigma} 1 \xrightarrow{\sigma} 3 \xrightarrow{\sigma} ... \end{align}

Since $\sigma^{-1}$ would simply reverse the directions of the arrows in the chain, we see that the orbit containing $1$ is $\{1,3,6\}$. Choosing other integers in the set permuted by $\sigma$, we perform the same procedure until all elements mapped by $\sigma$ have been placed in an orbit. In this way, the total list of the orbits of $\sigma$ is found to be

(2)
\begin{align} \{1,3,6\}, \hspace{1 cm} \{2,8\}, \hspace{1 cm} \{4,5,7\} \end{align}

Non-example(s)


Consider the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 \end{pmatrix}$ in $S_8$.
Then $(3\ 4)$ is NOT an orbit of $\sigma$, since it is not a set. ( $(3\ 4)$ is a cycle )
Also, $\{1, 2\}$ is NOT and orbit of $\sigma$, since repeated application of $\sigma$ to $1$ will never yield $2$.

Additional Comments


Add any other comments you have about the term here

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License