Permutations, compositions and associativity properties

Question

Let n be a positive integer, and let σ : {1, . . . , n} → {1, . . . , n} be a one-to-one and onto map. Then σ is called a permutation on n elements. The set of all permutations on n elements is denoted by S_n. The set S_n is important in understanding the determinant. Suppose τ is a permutation on n elements. If there exist i, j ∈ {1, . . . , n} with i $\ne$ j such that τ (i) = j, τ (j) = i and τ (k) = k for all k ∈ {1, . . . , n} \ {i, j}, we say that τ is a transposition.

(a) Let σ, τ ∈ S_n. Define στ := σ ◦ τ . That is, στ is τ composed with σ. Prove that στ ∈ S_n.

(b) Let σ₁, σ₂, σ₃ ∈ S_n. Prove that (σ₁σ₂)σ₃ = σ₁(σ₂σ₃).

(c) Let I : {1, . . . , n} → {1, . . . , n} denote the identity permutation. That is, I(i) := i for all i ∈ {1, . . . , n}. Show that, for all σ ∈ S_n, Iσ = σI = σ.

(d) Given σ ∈ S_n, show that there exists a unique element σ ⁻¹ ∈ S_n such that σσ⁻¹ = σ⁻¹σ = I.

My Answers:

(a)

στ(i) = σ(τ(i)) = σ(j) = m for some m $\in$ {1, . . . , n}

στ(j) = σ(τ(j)) = σ(i) = g for some g $\in$ {1, . . . , n} \ {m}

στ(k) = σ(τ(k)) = σ(k) = b for some b $\in$ {1, . . . , n} \ {m. g} $\forall$ k$\in${1, . . .,n} \ {i, j}

since σ is one-to-one and onto, therefore στ is a permutation of n elements so στ$\in$S_n

(b)

since σ₁, σ₂, σ₃ ∈ S_n, σ₁, σ₂, σ₃: {1, . . . , n} $\to$ {1, . . . , n}. For any k $\in${1, . . . , n}, then

((σ₁σ₂)σ₃)(k) = (σ₁σ₂)(σ₃(k)) = σ₁(σ₂(σ₃(k)))

and

(σ₁(σ₂σ₃))(k) = σ₁((σ₂σ₃)(k)) = σ₁(σ₂(σ₃(k)))

since ((σ₁σ₂)σ₃)(k) = (σ₁(σ₂σ₃))(k) $\forall$ k $\in${1, . . . , n}, we have (σ₁σ₂)σ₃ = σ₁(σ₂σ₃).

(c) σ : {1, . . . , n} → {1, . . . , n}, let σ(k)=m for some k, m $\in$ {1, . . . , n}, then

Iσ(k) = I(σ(k)) = I(m) = m and σI(k) = σ(I(k)) = σ(k) = m $\forall$ k$\in${1, . . . , n}

(d)

Since σ is one-to-one and onto, it is an invertible mapping, thus σ^-1 exists and is unique by the properties of the inverse. suppose σ(i)=j, then σ^-1(j)=(i), thus

σσ^-1(j)=σ(σ^-1(j))=σ(i)=j thus σσ^-1=I

σ^-1σ(i) = σ^-1(σ(i)) = σ^-1(j) = i thus σ^-1σ = I

How correct/incorrect am I? Thanks!

Answer 1

These all seem fine to me except for part a; I don't quite understand your argument for that one. You are trying to show that $\sigma\tau$ is a one-to-one and onto map from $\{1,\ldots,n\}\to\{1,\ldots, n\}$.

To show the map is one-to-one, you might suppose that $\sigma(\tau(i))=\sigma(\tau(j))$. Then since $\sigma$ is one-to-one, you have $\tau(i)=\tau(j)$, and similarly, since $\tau$ is one-to-one, it must be that $i=j$. Therefore $\sigma\tau$ is one-to-one.

To show the map is onto, let $k\in\{1,\ldots,n\}$. Then since $\sigma$ is onto, there is some $j$ such that $\sigma(j)=k$. Similarly, since $\tau$ is onto, there is some $i$ such that $\tau(i)=j$. Then $\sigma(\tau(i))=\sigma(j)=k$, so $\sigma\tau$ is onto.