Determination of multiplication table of symmetric group:S3

From Groupprops
Jump to: navigation, search
This page describes the process used for the determination of specific information related to a particular group. The information type is multiplication table and the group is symmetric group:S3.
View all pages that describe how to determine multiplication table of particular groups | View all specific information about symmetric group:S3

The purpose of this page is to give a detailed description of the construction of the multiplication table of symmetric group:S3. The survey article is meant as a walk-through of the entire process rather than a summary and is written for people relatively new to group theory. If you're looking for terse summary descriptions, check out symmetric group:S3 and element structure of symmetric group:S3.

The final table

We first provide the final multiplication table in cycle decomposition notation and also one-line notation for the group S_3 acting on the set \{1,2,3 \}. The convention followed here is that the column element is on the right and the row element is on the left, and functions act on the left. Hence, to determine the effect of the composite permutation on any element of \{ 1,2,3 \}, we must first apply the permutation given by the column element and then apply the permutation given by the row element.

Cycle decomposition notation

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) () (1, 2, 3) (1, 3, 2) (2, 3) (1, 3)
(2, 3) (2, 3) (1, 3, 2) () (1, 2, 3) (1, 3) (1, 2)
(1, 3) (1, 3) (1, 2, 3) (1, 3, 2) () (1, 2) (2, 3)
(1, 2, 3) (1, 2, 3) (1, 3) (1, 2) (2, 3) (1, 3, 2) ()
(1, 3, 2) (1, 3, 2) (2, 3) (1, 3) (1, 2) () (1, 2, 3)


One-line notation

Element 123 213 132 321 231 312
123 123 213 132 321 231 312
213 213 123 231 312 132 321
132 132 312 123 231 321 213
321 321 231 312 123 213 132
231 231 321 213 132 312 123
312 312 132 321 213 123 231


For this article, we follow the left action convention, which is standard in most introductory courses and treatments, although group theorists often uses right action because of the convenience of exponential notation.

Review of preliminaries

What multiplication of permutations means

Suppose \sigma and \tau are (possibly equal) permutations on a set S. \sigma \circ \tau is also a permutation. For i \in S, we define:

\! (\sigma \circ \tau)(i) = \sigma(\tau(i))

In other words, we first apply \tau to i, and locate the answer as an element of S. Having done this, we apply \sigma to that element. The final answer we get is where \sigma \circ \tau should send i.

Thus, to describe \sigma \circ \tau, we need to apply the above procedure to every element i \in S.

We will restrict our attention to S = \{ 1,2,\dots,n \}, and in fact to the case n = 3, though our initial remarks apply to other n.

What it means with one-line notation

It is pretty easy to multiply two permutations written in one-line notation. The first step is to convert the one-line notation to two-line notation. Recall that the one-line notation for a permutation \sigma on the set \{ 1,2,3,\dots,n \} simply lists the images \sigma(1),\sigma(2),\dots,\sigma(n). The two-line notation is:

\begin{pmatrix}1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n)\end{pmatrix}

The one-line notation is obtained by suppressing the top line of the two-line notation.

When multiplying, the two-line notation is operationally easier. To find the two-line notation for \sigma \circ \tau, we have to find \sigma(\tau(i)) for each i. We do this by first looking up the entry under i in the two-line notation for \tau. Call that j. We now look up the entry under j in the two-line notation for \sigma. Whatever answer we get, we write it as the entry under i in the two-line notation for \sigma \circ \tau. We do this for each i \in \{ 1,2,\dots,n \}. To retrieve the one-line notation, we simply remove the top line.

What it means with cycle decomposition notation

Further information: cycle decomposition, understanding the cycle decomposition

The cycle decomposition of a permutation breaks it up as a product of disjoint cycles. The permutations \sigma and \tau that we are multiplying each has its own cycle decomposition. Composing them could give a permutation that has a very different cycle decomposition from either of them. The exception occurs when both \sigma and \tau are equal, or are powers of each other -- in this case, the cycle structure of the product looks very similar to that of \sigma and \tau. For more, see Understanding the cycle decomposition#Computing the powers of a permutation.

All the 36 multiplications

We proceed column major (i.e., we do all the multiplications in a column and then move to the next column), providing full explanations with the two-line notation, along with any shortcut explanations where they exist, for each of the multiplications.

First column and first row

The first column of the multiplication table considers multiplication where the second element being multiplied is the identity element () (the permutation that sends 1 to 1, 2 to 2, and 3 to 3). By the definition of identity element, the product is just the first element. Therefore, the first column coincides with the row headers column

Similarly, the first row of the multiplication table considers multiplication where the first element is the identity (). Thus, the first row coincides with the column headers row.

The partial multiplication table constructed thus far is:

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2)  ?  ?  ?  ?  ?
(2, 3) (2, 3)  ?  ?  ?  ?  ?
(1, 3) (1, 3)  ?  ?  ?  ?  ?
(1, 2, 3) (1, 2, 3)  ?  ?  ?  ?  ?
(1, 3, 2) (1, 3, 2)  ?  ?  ?  ?  ?

Second column: multiplication with (1,2)

We need to consider multiplications where the second group element being multiplied is the permutation (1,2). In one-line notation, this is the element 213, and in two-line notation, this is the element:

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix}

We consider the multiplication of this with different elements:

Element multiplied on the left (in cycle decomposition, one-line, and two-line notation) Tracing what happens under the multiplication with (1,2) Product
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix} 1 \to 2 \to 1
2 \to 1 \to 2
3 \to 3 \to 3
() = 123 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\\end{pmatrix}
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix} 1 \to 2 \to 3
2 \to 1 \to 1
3 \to 3 \to 2
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\\end{pmatrix}
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix} 1 \to 2 \to 2
2 \to 1 \to 3
3 \to 3 \to 1
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\\end{pmatrix}
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix} 1 \to 2 \to 3
2 \to 1 \to 2
3 \to 3 \to 1
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \\\end{pmatrix}
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix} 1 \to 2 \to 1
2 \to 1 \to 3
3 \to 3 \to 2
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \\\end{pmatrix}

The multiplication table so far is:

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) ()  ?  ?  ?  ?
(2, 3) (2, 3) (1, 3, 2)  ?  ?  ?  ?
(1, 3) (1, 3) (1, 2, 3)  ?  ?  ?  ?
(1, 2, 3) (1, 2, 3) (1, 3)  ?  ?  ?  ?
(1, 3, 2) (1, 3, 2) (2, 3)  ?  ?  ?  ?

Sanity checks:

  • No two elements in the same column are equal. In particular, each completed column lists each group element exactly once.
  • No two elements in the same row are equal.

Third column: multiplication with (2,3)

We need to consider multiplications where the second group element being multiplied is the permutation (2,3). In one-line notation, this is the element 132, and in two-line notation, this is the element:

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \\\end{pmatrix}

We consider the multiplication of this with different elements:

Element multiplied on the left (in cycle decomposition, one-line, and two-line notation) Tracing what happens under the multiplication with (2,3) Product
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix} 1 \to 1 \to 2
2 \to 3 \to 3
3 \to 2 \to 1
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\\end{pmatrix}
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix} 1 \to 1 \to 1
2 \to 3 \to 2
3 \to 2 \to 3
() = 123 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\\end{pmatrix}
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix} 1 \to 1 \to 3
2 \to 3 \to 1
3 \to 2 \to 2
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\\end{pmatrix}
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix} 1 \to 1 \to 2
2 \to 3 \to 1
3 \to 2 \to 3
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix}
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix} 1 \to 1 \to 3
2 \to 3 \to 2
3 \to 2 \to 1
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix}

The multiplication table so far is:

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) () (1, 2, 3)  ?  ?  ?
(2, 3) (2, 3) (1, 3, 2) ()  ?  ?  ?
(1, 3) (1, 3) (1, 2, 3) (1, 3, 2)  ?  ?  ?
(1, 2, 3) (1, 2, 3) (1, 3) (1, 2)  ?  ?  ?
(1, 3, 2) (1, 3, 2) (2, 3) (1, 3)  ?  ?  ?

Sanity checks:

  • No two elements in the same column are equal. In particular, each completed column lists each group element exactly once.
  • No two elements in the same row are equal.

Fourth column: multiplication with (1,3)

We need to consider multiplications where the second group element being multiplied is the permutation (1,3). In one-line notation, this is the element 321, and in two-line notation, this is the element:

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \\\end{pmatrix}

We consider the multiplication of this with different elements:

Element multiplied on the left (in cycle decomposition, one-line, and two-line notation) Tracing what happens under the multiplication with (1,3) Product
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix} 1 \to 3 \to 3
2 \to 2 \to 1
3 \to 1 \to 2
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix}
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix} 1 \to 3 \to 2
2 \to 2 \to 3
3 \to 1 \to 1
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix}
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix} 1 \to 3 \to 1
2 \to 2 \to 2
3 \to 1 \to 3
() = 123 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\\end{pmatrix}
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix} 1 \to 3 \to 1
2 \to 2 \to 3
3 \to 1 \to 2
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix}
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix} 1 \to 3 \to 2
2 \to 2 \to 1
3 \to 1 \to 3
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix}

The multiplication table so far is:

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) () (1, 2, 3) (1, 3, 2)  ?  ?
(2, 3) (2, 3) (1, 3, 2) () (1, 2, 3)  ?  ?
(1, 3) (1, 3) (1, 2, 3) (1, 3, 2) ()  ?  ?
(1, 2, 3) (1, 2, 3) (1, 3) (1, 2) (2, 3)  ?  ?
(1, 3, 2) (1, 3, 2) (2, 3) (1, 3) (1, 2)  ?  ?

Sanity checks:

  • No two elements in the same column are equal. In particular, each completed column lists each group element exactly once.
  • No two elements in the same row are equal.

Fifth column: multiplication with (1,2,3)

We need to consider multiplications where the second group element being multiplied is the permutation (1,2,3). In one-line notation, this is the element 231, and in two-line notation, this is the element:

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\\end{pmatrix}

We consider the multiplication of this with different elements:

Element multiplied on the left (in cycle decomposition, one-line, and two-line notation) Tracing what happens under the multiplication with (1,2,3) Product
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix} 1 \to 2 \to 1
2 \to 3 \to 3
3 \to 1 \to 2
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix}
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix} 1 \to 2 \to 3
2 \to 3 \to 2
3 \to 1 \to 1
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix}
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix} 1 \to 2 \to 2
2 \to 3 \to 1
3 \to 1 \to 3
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix}
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix} 1 \to 2 \to 3
2 \to 3 \to 1
3 \to 1 \to 2
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix}
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix} 1 \to 2 \to 1
2 \to 3 \to 2
3 \to 1 \to 3
() = 123 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\\end{pmatrix}

The multiplication table so far is:

Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) () (1, 2, 3) (1, 3, 2) (2, 3) (1, 3)
(2, 3) (2, 3) (1, 3, 2) () (1, 2, 3) (1, 3) (1, 2)
(1, 3) (1, 3) (1, 2, 3) (1, 3, 2) () (1, 2) (2, 3)
(1, 2, 3) (1, 2, 3) (1, 3) (1, 2) (2, 3) (1, 3, 2) ()
(1, 3, 2) (1, 3, 2) (2, 3) (1, 3) (1, 2) () (1, 2, 3)

Sanity checks:

  • No two elements in the same column are equal. In particular, each completed column lists each group element exactly once.
  • No two elements in the same row are equal.

Sixth column: multiplication with (1,3,2)

We need to consider multiplications where the second group element being multiplied is the permutation (1,3,2). In one-line notation, this is the element 312, and in two-line notation, this is the element:

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\\end{pmatrix}

We consider the multiplication of this with different elements:

Element multiplied on the left (in cycle decomposition, one-line, and two-line notation) Tracing what happens under the multiplication with (1,3,2) Product
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix} 1 \to 3 \to 3
2 \to 1 \to 2
3 \to 2 \to 1
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix}
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix} 1 \to 3 \to 2
2 \to 1 \to 1
3 \to 2 \to 3
(1,2) = 213 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \\\end{pmatrix}
(1,3) = 321 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\\end{pmatrix} 1 \to 3\to 1
2 \to 1 \to 3
3 \to 2\to 2
(2,3) = 132 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2\\\end{pmatrix}
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix} 1 \to 3 \to 1
2 \to 1 \to 2
3 \to 2 \to 3
() = 123 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\\end{pmatrix}
(1,3,2) = 312 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\\\end{pmatrix} 1 \to 3 \to 2
2 \to 1 \to 3
3 \to 2 \to 1
(1,2,3) = 231 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\\end{pmatrix}

The multiplication table is now complete:


Element () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
() () (1, 2) (2, 3) (1, 3) (1, 2, 3) (1, 3, 2)
(1, 2) (1, 2) () (1, 2, 3) (1, 3, 2) (2, 3) (1, 3)
(2, 3) (2, 3) (1, 3, 2) () (1, 2, 3) (1, 3) (1, 2)
(1, 3) (1, 3) (1, 2, 3) (1, 3, 2) () (1, 2) (2, 3)
(1, 2, 3) (1, 2, 3) (1, 3) (1, 2) (2, 3) (1, 3, 2) ()
(1, 3, 2) (1, 3, 2) (2, 3) (1, 3) (1, 2) () (1, 2, 3)


Post-completion sanity checks

Latin square

  • Every column has each group element exactly once.
  • Every row has each group element exactly once.

Inverses

  • Each of the transpositions ((1,2), (2,3), and (1,3)) is equal to its own inverse. This makes natural sense.
  • The two 3-cycles are inverses as well as squares of each other.

Alternating group as subgroup

The identity element and the two 3-cycles form the subgroup A3 in S3, i.e., the alternating group of degree three, which is isomorphic to cyclic group:Z3 (these are the even permutations). The non-identity coset of this subgroup comprises the three 2-transpositions (these are the odd permutations). It's easy to eyeball and see that:

  • The product of any two even permutations is even.
  • The product of any two odd permutations is even.
  • The product of an even permutation and an odd permutation is odd.
  • The product of an odd permutation and an even permutation is odd.

This is easiest to see if we reorder the rows and columns so that the even permutations appear first and the odd permutations appear later:

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]