Do disjoint cycles commute under exponentiation? (Curious)

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Induction
In summary, the conversation discusses two statements related to permutations. The first statement shows that for any positive integers $k$ and $\ell$, the equation $\pi^k\circ \pi^{\ell}=\pi^{k+\ell}$ holds for any permutation $\pi$ in the symmetric group $\text{Sym}(n)$. The second statement shows that for any permutation $\pi$ in $\text{Sym}(n)$, raising it to the power of $n!$ results in the identity permutation. The conversation also includes a discussion on whether induction is required to prove these statements and a hint for using induction on the first statement. It is determined that the hint may not hold in general and that the statement holds if the cycles
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

1. Let $1\leq n\in \mathbb{N}$ and $\pi\in \text{Sym}(n)$. For $1\leq k\in \mathbb{N}$ we define $\pi^{-k}:=\left (\pi^n\right )^{-1}$.

Show for all $k,\ell\in \mathbb{Z}$ the equation $\pi^k\circ \pi^{\ell}=\pi^{k+\ell}$. 2. Let $1\leq n\in \mathbb{N}$. Show that $\pi^{n!}=\text{id}$ for all $\pi\in \text{Sym}(n)$.
Do we show both statements using induction? (Wondering)
 
Physics news on Phys.org
  • #2
mathmari said:
Hey! :eek:

1. Let $1\leq n\in \mathbb{N}$ and $\pi\in \text{Sym}(n)$. For $1\leq k\in \mathbb{N}$ we define $\pi^{-k}:=\left (\pi^n\right )^{-1}$.

Hey mathmari!

Is that a typo? Shouldn't it be $\pi^{-k}:=\left (\pi^k\right )^{-1}$? (Wondering)

mathmari said:
Show for all $k,\ell\in \mathbb{Z}$ the equation $\pi^k\circ \pi^{\ell}=\pi^{k+\ell}$. 2. Let $1\leq n\in \mathbb{N}$. Show that $\pi^{n!}=\text{id}$ for all $\pi\in \text{Sym}(n)$.
Do we show both statements using induction?

I don't think we need induction for 1.
Instead I think we need to distinguish cases.
If k and l are positive, the relation follows from the definition of repeated application of a function.
However, if either is negative or zero, we still need to see what happens. (Thinking)

For question 2, I think we need group theory. Specifically that the order of an element divides the size of a finite group. Then we don't need induction. (Thinking)
 
  • #3
I noticed now that the hint for induction is for question 1.

There is the following hint:

$\pi\in \text{Sym}(n)$

$\pi=\pi_1\circ \pi_2\circ \ldots \circ \pi_m$, $m\leq n$

$\pi$ has maximum length $n$

We are looking for $x\in \mathbb{N}$ such that $\pi^x=(\pi_1\circ \pi_2\circ \ldots \circ \pi_m)^x\ \overset{\text{Induction}}{ =} \ \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_m^x=\text{id}$

For $1\leq i\leq m$ the $\pi_i$ is a cycle of length $m_i$.

It holds that $(\pi_i)^{m_i}=\text{id}$ so $(\pi_i)^{n!}=\text{id}$ .

Then $\pi^{n!}=\pi_1^{n!}\circ \pi_2^{n!}\circ \ldots \circ \pi_m^{n!}=\text{id}\circ \text{id}\circ \ldots \circ \text{id}=\text{id}$.

(Wondering)
 
  • #4
mathmari said:
I noticed now that the hint for induction is for question 1.

There is the following hint:

$\pi\in \text{Sym}(n)$

$\pi=\pi_1\circ \pi_2\circ \ldots \circ \pi_m$, $m\leq n$

$\pi$ has maximum length $n$

What do you mean by maximum length? (Wondering)

mathmari said:
We are looking for $x\in \mathbb{N}$ such that $\pi^x=(\pi_1\circ \pi_2\circ \ldots \circ \pi_m)^x\ \overset{\text{Induction}}{ =} \ \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_m^x=\text{id}$

For $1\leq i\leq m$ the $\pi_i$ is a cycle of length $m_i$.

I don't think this is true in general.
Consider for instance $(1) \circ (1\,2) \circ (1\,2\,3) = (2\,3)$ and $x=3$.
Then:
$$\big((1) \circ (1\,2) \circ (1\,2\,3)\big)^3 = (2\,3)^3=(2\,3)
\ne (1\,2)= (1)^3 \circ (1\,2)^3 \circ (1\,2\,3)^3 $$
isn't it? (Worried)

Is it perhaps supposed to be a disjoint decomposition in cycles? (Wondering)

mathmari said:
It holds that $(\pi_i)^{m_i}=\text{id}$ so $(\pi_i)^{n!}=\text{id}$ .

Then $\pi^{n!}=\pi_1^{n!}\circ \pi_2^{n!}\circ \ldots \circ \pi_m^{n!}=\text{id}\circ \text{id}\circ \ldots \circ \text{id}=\text{id}$.
 
  • #5
Klaas van Aarsen said:
What do you mean by maximum length? (Wondering)

I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.
Klaas van Aarsen said:
I don't think this is true in general.
Consider for instance $(1) \circ (1\,2) \circ (1\,2\,3) = (2\,3)$ and $x=3$.
Then:
$$\big((1) \circ (1\,2) \circ (1\,2\,3)\big)^3 = (2\,3)^3=(2\,3)
\ne (1\,2)= (1)^3 \circ (1\,2)^3 \circ (1\,2\,3)^3 $$
isn't it? (Worried)

Is it perhaps supposed to be a disjoint decomposition in cycles? (Wondering)

Ahh ok! So if we suppose that $\pi_i\neq \pi_j$ for $i\neq j$, does the above hold? (Wondering)
 
  • #6
mathmari said:
I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.

Ahh ok! So if we suppose that $\pi_i\neq \pi_j$ for $i\neq j$, does the above hold?

That is not enough, is it?
If any pair $\pi_i$ and $\pi_j$ are cycles that overlap, the result won't hold. (Worried)

However, if the cycles are disjoint, the result does hold.
So if for instance $\pi=(1\,2\,3)(5\,6)$ with $\pi_1=(1\,2\,3)$ and $\pi_2=(5\,6)$, we have for any $x\in\mathbb Z$:
$$\pi^x = \big((1\,2\,3)\circ (5\,6)\big)^x = (1\,2\,3)^x \circ (5\,6)^x$$
Then we have $m=2$ and $m_1=3,\,m_2=2$. (Thinking)
 

FAQ: Do disjoint cycles commute under exponentiation? (Curious)

What is exponentiation?

Exponentiation is a mathematical operation where a number, called the base, is raised to a power, which is another number that represents the number of times the base is multiplied by itself.

What are disjoint cycles?

Disjoint cycles are permutations of a set of elements where each element is moved to a different position and no element is moved to the same position as another element.

Do disjoint cycles always commute under exponentiation?

No, disjoint cycles do not always commute under exponentiation. This means that the order in which disjoint cycles are applied can affect the final result.

What is an example of disjoint cycles not commuting under exponentiation?

An example of disjoint cycles not commuting under exponentiation is the permutation (1 2) and (2 3). When applied in order, (1 2)^(2 3) results in (1 3 2), while (2 3)^(1 2) results in (3 1 2).

Is there a way to determine if two disjoint cycles will commute under exponentiation?

Yes, there is a way to determine if two disjoint cycles will commute under exponentiation. If the cycles have a common element, they will not commute. However, if they do not have a common element, they will commute.

Similar threads

Replies
9
Views
1K
Replies
7
Views
2K
Replies
52
Views
3K
Replies
10
Views
1K
Replies
15
Views
1K
Replies
10
Views
1K
Replies
4
Views
990
Replies
5
Views
1K
Replies
4
Views
1K
Back
Top