Today I Learned

Some of the things I've learned every day since Oct 10, 2016

108: Generating Set for the Symmetric Group

There are many possible choices of a generating set for S_n, the symmetric group. However, one particularly simple one is the set

\{(0, 1, 2, \dots, n-1), (0, 1)\}

where 0, 1, 2, \dots, n-1 is an ordering of the elements being permutated by the elements of S_n, (0, 1, 2, \dots, n-1) is the permutation ‘shifting’ all these elements to their successor, and (0, 1) is the permutation swapping the first 2 of these.

I won’t provide a formal proof here as it’s a little tedious, but you can easily convince yourself that every permutation of these n elements is a combination of these 2 permutations, because alternating between them in succession allows you to move any of the n elements to an arbitrary position in the ordering.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: