Showing an equivalence relation

34 Views Asked by At

Let $[n]$ denote the set of all permutations. Let $R$ be the relation $$i_1 i_2\cdots i_n=j_1 j_2\cdots j_n$$ if and only if there exists a $k$ such that $j_1 j_2 \cdots j_n=i_k i_{k+1}\cdots i_n i_1 \cdots i_{k-1}.$ Show this is an equivalence relation.

I have a question about showing reflexivity. My reasoning is as follows:

Let $a=i_1\cdots i_n$. Suppose that there exists a $k$ and $k'$ such that $a=i_{k}i_{k+1}\cdots i_n i_1\cdots i_{k-1}$ and $a=i_{k'}i_{k'+1}\cdots i_n i_1\cdots i_{k'-1}.$ I want to show that $k=k'$.

I'm getting to this point where:

$$i_{k}i_{k+1}\cdots i_n i_1\cdots i_{k-1}=i_{k'}i_{k'+1}\cdots i_n i_1\cdots i_{k'-1}$$

Is it as simple as saying each $i_{k+m}=i_{k'+m}$ where $m=0,\cdots,n$?

1

There are 1 best solutions below

0
On BEST ANSWER

Given any $n \in \mathbb N$ and any $i_1 \ldots i_n, j_1 \ldots j_n \in [n]$, we are given that:

$$ (i_1\ldots i_n, j_1 \ldots j_n) \in R \iff \exists k \in \{1, \ldots, n\} \text{ such that } j_1 \ldots j_n = i_k \ldots i_n i_1 \ldots i_{k - 1} $$

In other words, we consider two permutations to be "essentially equivalent" if they are merely cyclic permutations of each other.


To prove reflexivity, choose any $i_1 \ldots i_n \in [n]$. We want to show that $(i_1 \ldots i_n, i_1 \ldots i_n) \in R$. Indeed, this is immediate, since we can take $k = 1$ to get: $$ i_1 \ldots i_n = i_1 \ldots i_n $$