Fall 2017, problem 51
Let $f$ be a bijective function from $A = \left\{1,2, \cdots, n \right\}$ to itself. Show that there is a positive integer $M$ such that $f^M(i) = f(i)$ for each $i$ in $A$, where $f^M$ denotes the composition $f \circ f \circ \cdots \circ f$ $M$ times.
Comments
lucianosantos
4 years ago
This set of functions under composition makes a finite group, as it's known. Thus, given a function $f$, there is $k\in \mathbb{N}$ such that $f^{k}= i_{A}$ (identity function).
Then $f^{k+1}=f$ . And $M=k+1$.
# Sorry, I do not know why my answer appears indented.
$f$ is nothing but a permutation, and property (1) of Hubert is a proof that any permutation is a product of disjoint cycles. This allows to evaluate the minimal value of $M$: one has $M=LCM(l_1,l_2,\dots,l_k)$ where the $l_j$ are the lengths of the cycles.
1) First we show by strong induction that $f$ is a product of disjoint finite cycles:
(consider the first cycle $A_n=\big\{f^j(n), \; 0\le j\le q_n\big\}, \; q_n=|A_n|-1$ being the biggest such that all the elements are different, and repeat it with $(A-A_n)$).
2) now $\forall i\in A_n, \; f^{q_n}(i)=i$ and $N$ as the product of all the $q_n$ of each cycle works because any $i \in A$ belongs to a cycle.