0
$\begingroup$

Let $n\in\mathbb{N}$ and consider $\sigma\in S_n$. Then $\exists k\in \mathbb{N}$ such that $\sigma^k = I$. Show this, and also that if $\sigma = \sigma_1...\sigma_m$ where $\sigma_i$'s are disjoint cycles, then the least $k$ such that $\sigma^k = I$ is the LCM of $(l_1,l_2,...,l_m)$ where $l_i$ is the length of the cycle $\sigma_i$.

For the first part, here's what I did:

Let $\sigma=\sigma_1...\sigma_m$ be the disjoint cycle decomposition of $\sigma$ where the length of each cycle $\sigma_i$ is $l_i$. Note that if $\Gamma = (a_1 a_2 a_3...a_l) \in S_{n}$ is a cycle in $S_n$, $l$ is its length. It is easily seen that $\Gamma^l = I$. Now define $t = LCM(l_1,...,l_m)$. Since disjoint cycles commute, we have $$\sigma^t = \sigma_1^t\sigma_2^t....\sigma_m^t$$ As $l_i\vert t$, each $\sigma_i^t = I$ and so $\sigma^t = I$.

To show that $t$ is the least such number, I must show that if $s\in\mathbb{N}$ and $s<t$ then $\sigma^s \neq I$.

Since $t$ is the LCM, we conclude that there exists at least one $i$ such that $l_i$ does not divide $s$, so that $\sigma_i^s \neq I$. I think I should now consider $$\sigma^s = \sigma_1^s\sigma_2^s....\sigma_i^s...\sigma_m^s$$

but I'm stuck here, what do I do next?

P.S.

I have realized that my questions boils down to: If cycles $\sigma_1, \sigma_2,....,\sigma_k$ are disjoint then $\sigma_1\sigma_2...\sigma_k = I$ iff $\sigma_i= I$ for all $1\leq i\leq k$. Any hints?

$\endgroup$
5
  • $\begingroup$ You only need to refer to a very general proposition of group theory: given commuting elements $x, y$ in an arbitrary group $G$, if they are both of finite orders $m$ and $n$ then $xy$ is of order $[m; n]$ (my notation for least common multiples). If at least one of the two is of infinite order, so is the product. This result can be inductively generalised to arbitrary finite families of pairwise commuting elements in groups. $\endgroup$ – ΑΘΩ Nov 21 '20 at 4:19
  • $\begingroup$ Interesting. I have actually not done group theory yet, and permutations were introduced to me in Linear Algebra with the intention of defining determinants in that manner. Could you post an easier answer? $\endgroup$ – epsilon-emperor Nov 21 '20 at 4:25
  • $\begingroup$ Right now I am on the road so to speak, therefore anything more than comments is a bit out of the question, I'm afraid...Nevertheless -- and I am not faulting you here, but rather the half-baked curricula of various schools -- one should not even begin discussing linear algebra before introducing more fundamental algebraic structures, such as semigroups, monoids and groups. $\endgroup$ – ΑΘΩ Nov 21 '20 at 4:36
  • $\begingroup$ @ΑΘΩ Got anything for me yet? $\endgroup$ – epsilon-emperor Dec 6 '20 at 4:27
  • $\begingroup$ I confess I had forgotten about our brief interaction, but since you ask and appear to be in need of an answer let me try to provide you with something below. Take a look at it once it's posted. $\endgroup$ – ΑΘΩ Dec 6 '20 at 6:36
1
$\begingroup$

Although the results we are going to look into can be formulated at a very general level, I shall limit the frame of the discussion to general permutation groups, since you only seem to be familiar with them. It is however very easy to see how the propositions I am about to formulate extend in the general case (of arbitrary groups).

Let us consider an arbitrary set $A$ and the general symmetric group $\Sigma(A)$, structure by which I am referring to the set $\Sigma(A)$ of all permutations of set $A$ with the implicit binary operation of composition of maps. In general, this operation takes the syntax $\sigma \circ \tau$ for two arbitrary permutations $\sigma, \tau \in \Sigma(A)$, however for simiplicity we shall employ the simplified notation $\sigma\tau$ (used for "abstract" multiplications).

To say that $\sigma$ is a permutation of finite order has a very specific meaning in the general sense of group theory, however in our given context we shall be content to understand it as there exists nonzero $n \in \mathbb{N}^{\times}$ such that $\sigma^n=\mathbf{1}_A$. We also introduce the order of the finite order permutation $\sigma$ -- denoted by $\mathrm{ord}(\sigma)$ -- to be the unique natural number $k$ rendering the following relation true: $$\left\{n \in \mathbb{N}^{\times} \mid \sigma^n=\mathbf{1}_A\right\}=k\mathbb{N}^{\times}.$$ Once again, may I point out that this is not the actual definition of the notion of order, but it is an easy to obtain equivalent description of the order of a permutation of finite order (there are also permutations of infinite order; nevertheless, the order of a permutation is always an elements of the set $\mathbb{N}^{\times} \cup \{\aleph_0\}$).

For arbitrary natural numbers $r, s \in \mathbb{N}$ let us denote their least common multiple by $[r; s]$. In case of an arbitrary family $r \in \mathbb{N}^I$ we use the notation $[r_i;]_{i \in I}$ for the least common multiple of the entire family $r$.

With the above mentions in place, let us consider two permutations of finite order $\lambda, \mu \in \Sigma(A)$ which:

  • commute, meaning that $\lambda\mu=\mu\lambda$
  • are both of finite order
  • are such that the subsets of powers of $\lambda$ and $\mu$ intersect trivially, in other words $\left\{\lambda^n\right\}_{n \in \mathbb{Z}} \cap \left\{\mu^n\right\}_{n \in \mathbb{Z}}=\{\mathbf{1}_A\}$.

Then $\lambda\mu$ is also of finite order and the relation $\mathrm{ord}(\lambda\mu)=\left[\mathrm{ord}(\lambda); \mathrm{ord}(\mu)\right]$ holds.

For simplicity, let us write $m=\mathrm{ord}(\lambda) \neq 0$, $n=\mathrm{ord}(\mu) \neq 0$ and let us introduce $p\colon=[m; n] \neq 0$. This means that $m, n \mid p$ so there exist $k, l \in \mathbb{N}$ such that $p=km=ln$. Since $\lambda$ and $\mu$ commute we have by virtue of a very general rule of algebraic calculus that $(\lambda\mu)^r=\lambda^r\mu^r$ for any $r \in \mathbb{N}$ (even for any $r \in \mathbb{Z}$, but you might not be familiar with the notion of raising to negative powers). This in particular entails that $(\lambda\mu)^{p}=\lambda^{p}\mu^{p}=\left(\lambda^m\right)^k\left(\mu^n\right)^l=\left(\mathbf{1}_A\right)^k\left(\mathbf{1}_A\right)^l=\mathbf{1}_A$. Since $p \neq 0$, this establishes $\lambda\mu$ as a permutation of finite order. Let us set $q\colon=\mathrm{ord}(\lambda\mu)$ and $M=\left\{r \in \mathbb{N}^{\times} \mid (\lambda\mu)^r=\mathbf{1}_A\right\}$.

By virtue of the characterisation of the order (in the finite case), we have $M=q\mathbb{N}^{\times}$ and since -- as we have just seen above -- $p \in M$, we gather that $q \mid p$. We now argue that the converse relation $p \mid q$ also holds in order infer that $p=q$. Since in particular $q \in M$ we have $(\lambda\mu)^q=\lambda^q\mu^q=\mathbf{1}_A$ which entails $\nu\colon=\lambda^q=\left(\mu^q\right)^{-1}=\mu^{-q}$. It is obvious that $\nu \in \left\{\lambda^n\right\}_{n \in \mathbb{Z}} \cap \left\{\mu^n\right\}_{n \in \mathbb{Z}}=\{\mathbf{1}_A\}$, whence $\lambda^q=\mu^{-q}=\mathbf{1}_A$, which is equivalent to $\lambda^q=\mu^q=\mathbf{1}_A$. Since $q \in \mathbb{N}^{\times}$ we have by virtue of the characterisation of the orders $m$ respectively $n$ of $\lambda$ respectively $\mu$ that $m, n \mid q$. By elementary arithmetic (the definition of the least common multiple), this entails $p \mid q$ and establishes our claim.

Before stating the next result, let us define the support of an arbitrary permutation $\sigma \in \Sigma(A)$ as the subset of elements of $A$ it actually permutes: $$\mathrm{Supp}(\sigma)\colon=\{x \in A \mid \sigma(x)\neq x\}.$$ It is easy to prove that two permutations $\lambda, \mu \in \Sigma(A)$ of disjoint supports necessarily commute (I will let you think about it).

The above proposition concerning finite orders generalises to finite families of permutations $\lambda \in \Sigma(A)$ such that:

  • $\lambda_i$ is of finite order for each $i \in I$
  • $\lambda_i\lambda_j=\lambda_j\lambda_i$ for each pair $(i, j) \in I$
  • $\mathrm{Supp}(\lambda_i) \cap \mathrm{Supp}(\lambda_j)=\varnothing$ for each pair of distinct indices $i, j \in I, i \neq j$. Then the product $\mu\colon=\displaystyle\prod_{i \in I}\lambda_i$ is also of finite order and the relation $\mathrm{ord}(\mu)=\left[\mathrm{ord}(\lambda_i);\right]_{i \in I}$ between the orders holds.

The way to prove this (somewhat) generalised version is by induction on $|I|$ (the cardinality of $I$). You might not find it straightforward to supply a proof for this on your own, so you can let me know. For the time being I think you have sufficient new material to digest.

The manner in which the generalised version applies to your problem at least I hope will become clear: if you have a finite family $\kappa$ of disjoint cycles then their supports satisfy the condition of pairwise disjointness in the generalised version above and their individual orders are finite, given by their lengths. Thus, their product $\pi$ is also of finite order $r$, number which is equal to the least common multiple of the family of lengths. Bearing in mind the characterisation of the order $r$ of $\pi$, $\pi^n=\mathbf{1}_A$ can only hold for nonzero natural $n$ if $n$ is a multiple of the order $r$ and therefore never in the case $n<r$ (any strictly positive multiple of $r$ being at least equal to $r$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.