Symmetric Group Handout/Integers of Modulo n (continued)

Abstract Algebra

Relatively Prime

Let a,n in Z with n greater than or equal to 2. Then a has an inverse in Z_n ←→ a and n are relatively prime.

Permutation

Let T_n={1,2,…,n}. A mapping omega=T_n→T_n is called a permutation if it is both one-to-one and onto.

Cycle Notation

The r-cycle (x₁x₂…x_r) in S_n is the permutation that sends x₁→x₂, x₂→x₃,…,x_r→x₁

Disjoint Cycles

Two cycles (x₁x₂…x_r) and (y₁y₂…y_r) are disjoint if {x_1,x_2,…x_r} (upside-down U) {y_1,y_2,…y_r} does not equal 0.

BIG Theorem

Each omega in S_n can be written (non-uniquely) as a product of disjoint cycles.

Even Bigger Theorem @

If n is greater than or equal to 2, then any cycle in S_n can be written as a product of transpositions.

Parity Theorem

If a permutation omega has two factorizations omega=Vn…V₂V₁=U_m…U₂U₁, where each V_i & U_j is a transposition, then m & n are both even or both odd.

Alternating Group of Degree n

The alternating group of degree n is the set of even permutations in S_n. We call it A_n.

Order

The order of a permutation omega in S_n is the smallest positive integer k such that omega^k=e.