IB DP Further Mathematics 4.10 HL Paper 2

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\).

[9]
a.

(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)\).

[7]
b.

(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.

[8]
c.
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]

a.

(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]

b.

(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]

c.
Scroll to Top