Welcome to our community

Be a part of something great, join today!

Do we use induction?

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,736
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)

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)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,736
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)

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)

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}$.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
What do you mean by maximum length? (Wondering)
I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.


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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,736
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)