Question
The set of all permutations of the list of the integers \(1,{\text{ }}2,{\text{ }}3{\text{ }} \ldots {\text{ }}n\) is a group, \({S_n}\), under the operation of composition of permutations.
Each element of \({S_4}\) can be represented by a \(4 \times 4\) matrix. For example, the cycle \({\text{(1 2 3 4)}}\) is represented by the matrix
\(\left( {\begin{array}{*{20}{c}} 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \\ 1&0&0&0 \end{array}} \right)\) acting on the column vector \(\left( {\begin{array}{*{20}{c}} 1 \\ 2 \\ 3 \\ 4 \end{array}} \right)\).
(i) Show that the order of \({S_n}\) is \(n!\);
(ii) List the 6 elements of \({S_3}\) in cycle form;
(iii) Show that \({S_3}\) is not Abelian;
(iv) Deduce that \({S_n}\) is not Abelian for \(n \geqslant 3\).
(i) Write down the matrices M\(_1\), M\(_2\) representing the permutations \((1{\text{ }}2),{\text{ }}(2{\text{ }}3)\), respectively;
(ii) Find M\(_1\)M\(_2\) and state the permutation represented by this matrix;
(iii) Find \(\det (\)M\(_1)\), \(\det (\)M\(_2)\) and deduce the value of \(\det (\)M\(_1\)M\(_2)\).
(i) Use mathematical induction to prove that
\((1{\text{ }}n)(1{\text{ }}n{\text{ }} – 1)(1{\text{ }}n – 2) \ldots (1{\text{ }}2) = (1{\text{ }}2{\text{ }}3 \ldots n){\text{ }}n \in {\mathbb{Z}^ + },{\text{ }}n > 1\).
(ii) Deduce that every permutation can be written as a product of cycles of length 2.
Answer/Explanation
Markscheme
(i) 1 has \(n\) possible new positions; 2 then has \(n – 1\) possible new positions…
\(n\) has only one possible new position R1
the number of possible permutations is \(n \times (n – 1) \times \ldots \times 2 \times 1\) R1
\( = n!\) AG
Note: Give no credit for simply stating that the number of permutations is \(n!\)
(ii) \((1)(2)(3);{\text{ }}(1{\text{ }}2)(3);{\text{ }}(1{\text{ }}3)(2);{\text{ }}(2{\text{ }}3)(1);{\text{ }}(1{\text{ }}2{\text{ }}3);{\text{ }}(1{\text{ }}3{\text{ }}2)\) A2
Notes: A1 for 4 or 5 correct.
If single bracket terms are missing, do not penalize.
Accept \(e\) in place of the identity.
(iii) attempt to compare \({\pi _1} \circ {\pi _2}\) with \({\pi _2} \circ {\pi _1}\) for two permutations M1
for example \((1{\text{ }}2)(1{\text{ }}3) = (1{\text{ }}3{\text{ }}2)\) A1
but \((1{\text{ }}3)(1{\text{ }}2) = (1{\text{ }}2{\text{ }}3)\) A1
hence \({S_3}\) is not Abelian AG
(iv) \({S_3}\) is a subgroup of \({S_n}\), R1
so \({S_n}\) contains non-commuting elements R1
\( \Rightarrow {S_n}\) is not Abelian for \(n \geqslant 3\) AG
[9 marks]
(i) M\(_1 = \left( {\begin{array}{*{20}{c}} 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{array}} \right)\), M\(_2 = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \\ 0&0&0&1 \end{array}} \right)\) A1A1
(ii) M\(_1\)M\(_2 = \left( {\begin{array}{*{20}{c}} 0&0&1&0 \\ 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \end{array}} \right)\) A1
this represents \((1{\text{ }}3{\text{ }}2)\) A1
(iii) by, for example, interchanging a pair of rows (M1)
\(\det (\)M\(_1) = \det (\)M\(_2) = – 1\) A1
then \(\det (\)M\(_1\)M\(_2) = ( – 1) \times ( – 1) = 1\) A1
[7 marks]
(i) let \({\text{P}}(n)\) be the proposition that
\((1{\text{ }}n)(1{\text{ }}n – 1)(1{\text{ }}n – 2) \ldots (1{\text{ }}2) = (1{\text{ }}2{\text{ }}3 \ldots n){\text{ }}n \in {\mathbb{Z}^ + }\)
the statement that \({\text{P}}(2)\) is true eg \((1{\text{ }}2) = (1{\text{ }}2)\) A1
assume \({\text{P}}(k)\) is true for some \(k\) M1
consider \((1{\text{ }}k + 1)(1{\text{ }}k)(1{\text{ }}k – 1)(1{\text{ }}k – 2) \ldots (1{\text{ }}2)\)
\( = (1{\text{ }}k + 1)(1{\text{ }}2{\text{ }}3 \ldots k)\) M1
then the composite permutation has the following effect on the first \(k + 1\) integers: \(1 \to 2,{\text{ }}2 \to 3 \ldots k – 1 \to k,{\text{ }}k \to 1 \to k + 1,{\text{ }}k + 1 \to 1\) A1
this is \((1{\text{ }}2{\text{ }}3 \ldots k{\text{ }}k + 1)\) A1
hence the assertion is true by induction AG
(ii) every permutation is a product of cycles R1
generalizing the result in (i) R1
every cycle is a product of cycles of length 2 R1
hence every permutation can be written as a product of cycles of length 2 AG
[8 marks]