Codex @codex  0

Every group $G$ is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element $g$ becomes a permutation of all the group elements, given byFor a finite group of group order $n$, labeling these elements by $1,\dots ,n$ gives a group embedding into $S_n$. The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.^[ref]

The beauty is that the multiplication rule itself supplies a concrete model. Whatever the group elements originally represent, each one rearranges the entire group by multiplication. A product becomes function composition, and no distinctions between group elements are lost. For a finite group, a row of its Cayley table lists the images under one $L_g$: the multiplication table is already a catalogue of permutations.

Throughout this construction, products of permutations act rightmost first:Thus $L_g{L}_h$ first multiplies by $h$, then by $g$. This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_g{R}_h=R_{hg}$ with this convention; replacing it by $x\mapsto x{g}^{-1}$ restores the group homomorphism law.^[ref]

For an explicit cyclic group example, take $C_4=\mathbb{Z}/4\mathbb{Z}$ under addition, using modular arithmetic. Its left regular action consists of $L_k(x)=k+x(\mathrm{mod}4)$. In permutation cycles on the labels $0,1,2,3$,The function composition $L_1{L}_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point permutation cycle produces two disjoint permutation cycles. Also $L_1{L}_3=L_0$. These four permutations form a cyclic subgroup of $S_4$, reproducing addition in $C_4$ exactly.

For a nonabelian group example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its identity element. The six group elements are $e,r,r^2,s,rs,r^{2}s$, where $r^3=s^2=e$ and $sr=r^{2}s$. Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, $L_s(r)=sr=r^{2}s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that $L_r{L}_s\ne L_s{L}_r$. The group generators $r,s$ become group generators $L_r,L_s$ of a six-element subgroup of $S_6$.

Why does a group action here produce a group embedding? Any group action on a set $X$ gives a group homomorphism $\rho :G\to \mathrm{Sym}(X)$; it is a group embedding precisely when it is a faithful group action. The group kernel consists of the group elements fixing every point of $X$. In the left regular action, $L_g(e)=g$, so fixing the identity element already forces $g=e$. In fact every stabilizer subgroup is trivial, since $gx=x$ forces $g=e$; this stronger property makes the left regular action a regular group action.^[ref]

Compare two group actions of the same cyclic group $C_4$. Its left regular action on four labels distinguishes all four group elements. On $X=\{0,1\}$, the rule $k\cdot x=k+x(\mathrm{mod}2)$ defines a transitive group action, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its group kernel is $\{0,2\}$, so it is not a faithful group action. Its image is a two-element subgroup of $S_2$, isomorphic to the quotient group $C_4/\{0,2\}$ rather than to $C_4$.

The guaranteed number $|G|$ of labels need not be the smallest possible for a faithful group action. The symmetric group $S_3$ naturally acts faithfully on $\{1,2,3\}$: a permutation fixing all three labels is the identity element. Its left regular action uses six labels instead. Three is the smallest possible here, since $S_1$ and $S_2$ have fewer than six elements and cannot contain an isomorphic copy of $S_3$. Moreover, in the natural three-point group action, the stabilizer subgroup of $1$ is $\{e,(23)\}$: a faithful group action can have nontrivial point stabilizer subgroups. Cayley's construction supplies a universal model, while a smaller model can reveal particular symmetries.

The proof is short. Each $L_g$ is a bijection with inverse $L_{g^{-1}}$. Associativity givesso $\lambda$ is a group homomorphism. If $L_g=L_h$, evaluating both at the identity element gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ is injective, and its image is the required isomorphic subgroup. No finiteness assumption entered the argument.

The historical connection is unusually close to the notation. The opening paragraph of Arthur Cayley's 1854 paper already treats permutations as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on associativity. The modern left regular action shows how that viewpoint reaches every abstract group, by choosing the group itself as the set to be acted on.^[ref]

For an element $x$ of a group $G$, its conjugacy class is its orbit of a group action under the conjugation action:Thus conjugate group elements describe the same operation after a change of labels. In a symmetric group, conjugation renames the entries of every permutation cycle:For example, with $g=(123)$ and the transposition $t=(12)$, this gives $gt{g}^{-1}=(g(1)g(2))=(23)$. Products use function composition of permutations, with the rightmost factor applied first. The complete six-element example is conjugacy classes of the symmetric group on three letters.

The conjugacy classes form a partition of a set of $G$, since conjugacy is an equivalence relation. In a symmetric group, two permutations lie in the same conjugacy class precisely when they have the same cycle type: renaming preserves the lengths of permutation cycles, and matching equal-length permutation cycles constructs a renaming in the other direction. This compresses many labelled permutations into a few structural types. See McKernan, Conjugation in Sn, lemma 6.2 and proposition 6.6.

The stabilizer subgroup of $x$ under the conjugation action is its centralizer $C_G(x)$. Consequently the orbit-stabilizer theorem givesThe counting mechanism is the bijection $g{C}_G(x)\mapsto gx{g}^{-1}$ from left cosets onto the conjugacy class: two choices of $g$ give the same result exactly when they differ on the right by an element of the centralizer. A large centralizer means many choices of labels leave the operation unchanged, hence a small conjugacy class. A conjugacy class has size one precisely when its element belongs to the center of a group. The class equation counts these orbits of a group action together.

The symmetric group $S_3$ has exactly six permutations, written using permutation cycles:Here $e$ is the identity element; $(12)$, $(13)$ and $(23)$ are transpositions; and $(123)$ and $(132)$ are permutation cycles of length three. With $t=(12)$ and $r=(123)$, rightmost-first function composition gives $r^2=(132)$ and $r^{-1}=r^2$. The conjugacy classes and representative centralizers are

An explicit check of the conjugation $gt{g}^{-1}$ with $g=r=(123)$ sends $1\mapsto 3\mapsto 3\mapsto 1$, $2\mapsto 1\mapsto 2\mapsto 3$, and $3\mapsto 2\mapsto 1\mapsto 2$, where each chain applies $g^{-1}$, then $t$, then $g$. Thus $1$ is fixed and $2,3$ are exchanged: $gt{g}^{-1}=(23)$. Relabelling also produces $(13)$, so the three transpositions share one conjugacy class. A transposition reverses the length-three permutation cycle, since $tr{t}^{-1}=(213)=(132)=r^{-1}$, putting both length-three permutation cycles in one conjugacy class.

Checking each of the six possible permutations against $gx=xg$ gives the displayed centralizers. Only $e$ has a one-element conjugacy class, so the center of a group here is $Z(S_3)=\{e\}$. The class equation is $6=1+3+2$. The second diagram in centralizer and normalizer uses the same $r$ and $t$ to show how preserving a cyclic subgroup differs from fixing its group generator.

Two permutations in the same symmetric group are conjugate if $\tau =\pi \sigma {\pi }^{-1}$ for some permutation $\pi$. Conjugation relabels every permutation cycle, so it preserves cycle type. Conversely, equal cycle types permit a relabelling between corresponding cycles, establishing conjugacy.

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

The number $d_n$ of derangements of an $n$-element set satisfies $d_0=1$, $d_1=0$, $d_2=1$ and the displayed recurrence relation for $n\ge 2$. Choose the image $j$ of a distinguished element, in $n-1$ ways. If those two elements form a two-cycle, removing them leaves $d_{n-2}$ choices. Otherwise remove the distinguished element from its longer permutation cycle, leaving a derangement on $n-1$ elements. The inverse operation inserts it immediately before $j$. Thus the two disjoint cases contribute $d_{n-2}+d_{n-1}$ for each $j$.

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

For a prime number $p$ and $p\nmid a$, multiplication by $a$ gives a permutation of the $p-1$ nonzero residue classes. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.

For $a=2$ modulo seven, the permutation cycles are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.

More generally, every permutation cycle of this map has length equal to the multiplicative order of $a$: starting at a nonzero residue class $x$, a return means $a^{k}x\equiv x(\mathrm{mod}p)$, and its modular multiplicative inverse allows cancellation of $x$. Thus the $p-1$ nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into $p-1$.

The product argument gives a short proof outline. Since multiplication by $a$ is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves $a^{p-1}\equiv 1(\mathrm{mod}p)$. The whole argument works for $p=2$, where the product is just one.^[ref]

Compose permutations from right to left. Tracking the four symbols through the two permutation cycles gives $1\mapsto 2\mapsto 1$ and $3\mapsto 4\mapsto 3$. Thus the cycle decomposition of a permutation isThe disjoint transpositions commute, and squaring their product gives the identity element, while the product itself is nonidentity. Its order of a group element is therefore two. Each transposition has negative sign of a permutation, so the product has sign $(-1{)}^2=\boxed{+1}$: it is an even permutation.

Let $p$ be a permutation of the finite set. Starting from $a$, repeatedly apply $p$. Some iterate repeats; because $p$ is invertible, the first repeat closes the sequence at $a$. More explicitly, if $p^i(a)=p^j(a)$ with $0\le i<j$, applying $p^{-i}$ gives $p^{j-i}(a)=a$. If $r$ is the least positive return time, the elements $a,p(a),\dots ,p^{r-1}(a)$ are distinct and form one permutation cycle. If the set is not exhausted, start again at an unused element. Two such sets cannot overlap: an overlap lets an inverse iterate express either starting point as an iterate of the other, making the sets identical. Thus this process partitions the set into disjoint permutation cycles. On each part its cycle acts exactly as $p$ and the other cycles fix the elements. Their product therefore equals $p$. This proves existence of the cycle decomposition of a permutation, including one-cycles for fixed points.

Use the composition convention that the rightmost permutation acts first. For the specified product, the images areHenceThe order of a group element here is the least positive exponent making every cycle return to the identity. It must be divisible by each cycle length, and any common multiple does make every cycle return. The least common multiple of $3,2,3$ is six.

The symmetric group $S_5$ has cardinality $5!=120=3\cdot 40$, so its Sylow subgroups for $p=3$ have cardinality $3$. One example isEvery nonidentity permutation of order of a group element $3$ in $S_5$ is a single permutation cycle of length $3$: two disjoint length-three permutation cycles would require six letters. Choose the three moved letters in $\left(\genfrac{}{}{0ex}{}{5}{3}\right)$ ways, then one of their two length-three permutation cycles, giving $20$ such elements. Each subgroup of cardinality $3$ has exactly two nonidentity elements, and distinct such subgroups have no nonidentity element in common. ConsequentlyThis also satisfies the numerical Sylow theorem restrictions $10\mid 40$ and $10\equiv 1(\mathrm{mod}3)$.

For a permutation $\sigma \in S_n$, let $P_{\sigma }$ be its permutation matrix, defined by $P_{\sigma }{e}_j=e_{\sigma (j)}$. Define the signature of a permutation by $ϵ(\sigma )=\det P_{\sigma }$. A permutation matrix is orthogonal, so $(\det P_{\sigma }{)}^2=1$ and its permutation sign lies in $\{1,-1\}$. A transposition exchanges two columns of the identity and therefore has determinant $-1$. Every permutation is a product of transpositions, by decomposing each permutation cycle asHence $ϵ(\sigma )=(-1{)}^m$ for any expression as $m$ transpositions; the determinant definition proves that this parity of a permutation is independent of the expression. Equivalently the permutation sign is positive for an even permutation and negative for an odd permutation.

Composition is taken rightmost first. Since $P_{\sigma \tau }{e}_j=e_{\sigma (\tau (j))}=P_{\sigma }{P}_{\tau }{e}_j$, we have $P_{\sigma \tau }=P_{\sigma }{P}_{\tau }$. Multiplicativity of the determinant therefore proves the sign homomorphism identityThe alternating group consists of the even permutations:It contains the identity. If $\sigma ,\tau \in A_n$, their product has permutation sign $1$, and $ϵ({\sigma }^{-1})=ϵ(\sigma {)}^{-1}=1$, so their inverses also belong to $A_n$. This proves it is a subgroup. Finally, for every $g\in S_n$ and $a\in A_n$,Thus $A_n$ is a normal subgroup of $S_n$. This also exhibits directly why a kernel of a group homomorphism is normal.

For any permutation $\tau$, conjugating a permutation cycle relabels its entries:Indeed, the conjugate sends $\tau (a_j)$ to $\tau (a_{j+1})$ and fixes the other relabeled entries exactly as the original permutation cycle does. Therefore conjugation preserves the multiset of permutation cycle lengths. Conversely, if two permutations have the same cycle type, pair their permutation cycles of each length and let $\tau$ carry the $j$th entry of each first permutation cycle to the $j$th entry of its partner. Include one-cycles for fixed points. This defines a bijection of all labels, and the displayed relabeling identity makes the permutations conjugate. ThusFor $n\ge 2$, the alternating conjugacy class splitting criterion says that an even permutation has the same class in $A_n$ and $S_n$ precisely when its type is not a collection of pairwise distinct odd lengths. Equivalently, there is an even-length permutation cycle or a repeated permutation cycle length, counting each fixed point as a length-one permutation cycle. Distinct odd lengths instead give two alternating-group classes. For $n=1$, $A_1=S_1$ and the sole class is the same; the index-two splitting criterion is not applicable.

Squaring an odd-length permutation cycle keeps one permutation cycle of that length, since advancing by two visits all of its entries. Squaring an even-length permutation cycle splits it into two permutation cycles, each of half that length. Thus any even-length permutation cycle strictly increases the total permutation cycle count on squaring, while odd permutation cycles leave that count unchanged. The cycle type can agree with its square exactly when every length is odd. This proves permutation conjugate to its square:The final equivalence follows because the order of a group element that is a permutation is the least common multiple of its permutation cycle lengths.

The possible even types on five labels are the identity, a three-cycle, a product of two disjoint transpositions and a five-cycle. The identity and the double transpositions are their own inverses. For a three-cycle $(abc)$ with unused labels $d,e$, the even permutation $(bc)(de)$ conjugates it to its inverse. For a five-cycle $(abcde)$, the even permutation $(be)(cd)$ reverses its order. Therefore every element of $A_5$ is conjugate to its inverse within $A_5$. Inverting a five-cycle uses two transpositions, in agreement with inversion of an odd cycle in an alternating group.

A small counterexample elsewhere isThe alternating group $A_3=\{e,(123),(132)\}$ is cyclic and therefore abelian. Every conjugacy class in an abelian group is a singleton, while $\sigma \ne {\sigma }^{-1}$. Thus these two elements are not conjugate in $A_3$.

Use rightmost-first composition of permutations, and letFor $n\ge 2$, direct evaluation gives $ab=(1n)$. Conjugating this transposition by powers of $a$ yields the transpositions between consecutive letters around the cycle, including $(12),(23),\dots ,(n-1n)$.

Put $s_i=(ii+1)$. For $i<j$,Thus the adjacent transpositions generate every transposition, and permutation cycle decomposition shows that transpositions generate the symmetric group. Therefore $⟨a,b⟩=S_n$.

For the final lower bound, associate a graph to a family of transpositions: its vertices are the letters and its edges are the swapped pairs. Every generator preserves every connected component, so generation of $S_n$ requires that graph to be connected. A connected graph on $n$ vertices needs at least $n-1$ edges: adding an edge can reduce the number of components by at most one, starting from $n$ isolated vertices. The adjacent transpositions supply exactly $n-1$ edges. Equivalently, transpositions on a connected graph generate the symmetric group. Hence

For a permutation $g$, start with a letter $i$ and follow $i,g(i),g^2(i),\dots$. Finiteness gives a repetition; since $g$ is invertible, the first return is to $i$. The visited letters form a permutation cycle on which $g$ acts by moving to the next letter. If there are letters left, repeat the construction starting with one of them. Its trajectory cannot meet an earlier one, because applying a suitable inverse power of $g$ would put its starting letter in that earlier trajectory. Continuing partitions the letters into disjoint cycles, including fixed points as cycles of length one.

The resulting disjoint permutation cycles have disjoint supports, and their product agrees with $g$ on every letter. This proves the cycle decomposition of a permutation. A power $g^m$ fixes a cycle of length $l$ exactly when $l\mid m$, so if the cycle lengths are $l_1,\dots ,l_t$,The least common multiple is essential: multiplying the lengths would overcount whenever cycles share a factor.

The alternating group is the subgroup of the symmetric group consisting of even permutations:For a permutation cycle of length $l$,using rightmost-first composition. Its sign of a permutation is therefore $(-1{)}^{l-1}$. Multiplicativity of the sign homomorphism givesThusEquivalently, $n-t$ is even when $t$ counts all cycles, including fixed points. Odd-length cycles contribute positive sign and impose no further restriction.

A permutation cycle $(a_1{a}_2\cdots a_p)$ sends $a_1$ to $a_2$, each successive listed point to the next, and $a_p$ to $a_1$, fixing every unlisted point. Its length is $p$. For any permutation $h$,Thus conjugate group elements in the symmetric group have the same cycle length. Conversely, two cycles of the same length are conjugate: send their entries, in cyclic order, to one another and extend this bijection arbitrarily to the unused points. Length-one cycles represent the identity and cause no exception to this conclusion.

An odd-length permutation cycle is an even permutation, since its sign is $(-1{)}^{p-1}$. Let $c,d$ be such cycles on $p+2$ points and choose $h\in S_{p+2}$ with $hc{h}^{-1}=d$. If $h$ is odd, let $t$ be the transposition of the two points unused by the listed cycle $c$. Then $tc=ct$, and $ht$ is even withHence all the $p$-cycles are conjugate within $A_{p+2}$. The two spare letters supply the parity correction; they are the reason the same argument need not work with only one spare letter.

In $A_4$ the answer is no. For example, $(123)$ and $(132)$ are conjugated by the odd transposition $(23)$ in $S_4$. The centralizer of $(123)$ in $S_4$ is exactly its order-three cyclic subgroup: a commuting permutation fixes the unique fixed point $4$ and acts as a power of the cycle on the other three points. All these centralizing elements are even. Every other conjugating element differs from $(23)$ by a centralizing element, so it is also odd. There is no conjugator in $A_4$. Equivalently, the eight three-cycles split into two conjugacy classes of size $12/3=4$, illustrating the alternating conjugacy class splitting criterion.

Write $D_n=\det [K(x_i,x_j){]}_{i,j=1}^n$ and expand it by permutations. The assumptions ensure that the indicated single-variable integrals exist; the finite-rank projection kernel constructed above satisfies them with $r=m$. No symmetry of a general kernel is needed for the following argument.

If a permutation fixes $n$, its product contains the separate factor $K(x_n,x_n)$. Integration gives $r$ times the term of the corresponding permutation of $\{1,\dots ,n-1\}$. These terms contribute $r{D}_{n-1}$.

Otherwise $n$ belongs to a longer permutation cycle. Let $i$ precede $n$ and let $j$ follow it. The only factors containing $x_n$ are $K(x_i,x_n)K(x_n,x_j)$, whose integral is $K(x_i,x_j)$ by the reproducing assumption. Delete $n$ from the cycle to obtain a permutation $\tau$ on $n-1$ letters. Inserting $n$ back after any of the $n-1$ possible letters reconstructs exactly one permutation; its sign of a permutation is $-\mathrm{sgn}(\tau )$, since increasing a cycle length by one reverses its sign. Thus the nonfixed terms contribute $-(n-1)D_{n-1}$.

Combining these two disjoint classes proves projection kernel determinant integration:For $n=1$, use the empty determinant $D_0=1$, and the statement is precisely the assumed diagonal integral. For our kernel, orthonormality directly yieldsso every step of the marginal integration is justified.

The order of a group element represented by a permutation is the least common multiple of its disjoint cycle lengths. An order divisible by nine therefore requires a permutation cycle whose length is divisible by nine. In $S_9$ that must be a nine-cycle, which uses every letter and has order nine, not eighteen. There is no element of $S_9$ of order eighteen.

Take two disjoint permutation cycles of lengths five and four:Disjoint permutation cycles commute, and their powers act independently on their supports. Thus ${\sigma }^k=1$ exactly when both $5$ and $4$ divide $k$, so its order of a group element is $\mathrm{lcm}(5,4)=20$.