Permutationer.sagews

Permutationer

Låt $\sigma$ vara permutationen $$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 6 & 1 & 8 & 7 & 2 & 5 & 9 & 4 \end{pmatrix}.$$ Då är till exempel $\sigma(3) = 1$ och $\sigma(7) = 5$.

typeset_mode(True)
sigma = Permutation([3, 6, 1, 8, 7, 2, 5, 9, 4])
sigma(3)

$\displaystyle 1$

Skriv permutationen som en produkt av cykler.

sigma.cycle_string()

(1,3)(2,6)(4,8,9)(5,7)

Vi kan också definiera en permutation som produkt av cykler.

rho = Permutation('(1, 5, 3)(2)(4, 9, 8, 7, 6)')
rho

$\displaystyle [5, 2, 1, 9, 3, 4, 6, 7, 8]$

Produkten av två permutationer läses från vänster till höger. Med andra ord ska $\sigma\rho(a)$ tolkas $\rho(\sigma(a))$.

sigma * rho

$\displaystyle [1, 4, 5, 7, 6, 2, 3, 8, 9]$

Vi ser att $\sigma\rho$ avbildar till exempel $2$ på $4$.

rho(sigma(2))

$\displaystyle 4$

Vi bestämmer motsvarande permutationsmatris $\mathbf{P}$ för $\sigma$.

P = sigma.to_matrix()
P

$\displaystyle \left(\begin{array}{rrrrrrrrr} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)$

Låt $\boldsymbol{v} = (1, 2, \ldots, 9)$. Bestäm $\boldsymbol{v}\mathbf{P}$ och $\mathbf{P}\boldsymbol{v}$.

v = vector(ZZ, [i for i in [1..9]])
v * P
P * v

$\displaystyle \left(3,\,6,\,1,\,8,\,7,\,2,\,5,\,9,\,4\right)$

$\displaystyle \left(3,\,6,\,1,\,9,\,7,\,2,\,5,\,4,\,8\right)$

Kan du förklara resultatet?

Låt $i$, $j$ och $n$ vara heltal sådana att $1 \leq i, j \leq n$. En elementärmatris $\mathbf{P}_{i,j}$ är en permutationsmatris som hör till en permutation $\rho$ för vilken $$\rho(i) = j,\quad \rho(j) = i \quad\text{och}\quad \rho(k) = k$$ då $k \neq i$ och $k \neq j$. Bestäm $\mathbf{P}_{1,4}$ och $\mathbf{P}_{3,8}$, då $n = 9$.

P14 = elementary_matrix(ZZ, 9, row1 = 0, row2 = 3)
P14

$\displaystyle \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$

P38 = elementary_matrix(ZZ, 9, row1 = 2, row2 = 7)
P38

$\displaystyle \left(\begin{array}{rrrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$

Beräkna $\boldsymbol{v}\mathbf{P}_{1,4}$ och $\boldsymbol{v}\mathbf{P}_{3,8}$ samt $\mathbf{A}\mathbf{P}_{1,4}$ och $\mathbf{A}\mathbf{P}_{3,8}$, där $\mathbf{A} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 \\ 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \\ 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 \\ 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 \\ 64 & 65 & 66 & 67 & 68 & 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 \end{pmatrix}.$

v * P14

$\displaystyle \left(4,\,2,\,3,\,1,\,5,\,6,\,7,\,8,\,9\right)$

v * P38

$\displaystyle \left(1,\,2,\,8,\,4,\,5,\,6,\,7,\,3,\,9\right)$

A = matrix(ZZ, 9, 9, [1..81])
A

$\displaystyle \left(\begin{array}{rrrrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 \\ 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \\ 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 \\ 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 \\ 64 & 65 & 66 & 67 & 68 & 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 \end{array}\right)$

A * P14

$\displaystyle \left(\begin{array}{rrrrrrrrr} 4 & 2 & 3 & 1 & 5 & 6 & 7 & 8 & 9 \\ 13 & 11 & 12 & 10 & 14 & 15 & 16 & 17 & 18 \\ 22 & 20 & 21 & 19 & 23 & 24 & 25 & 26 & 27 \\ 31 & 29 & 30 & 28 & 32 & 33 & 34 & 35 & 36 \\ 40 & 38 & 39 & 37 & 41 & 42 & 43 & 44 & 45 \\ 49 & 47 & 48 & 46 & 50 & 51 & 52 & 53 & 54 \\ 58 & 56 & 57 & 55 & 59 & 60 & 61 & 62 & 63 \\ 67 & 65 & 66 & 64 & 68 & 69 & 70 & 71 & 72 \\ 76 & 74 & 75 & 73 & 77 & 78 & 79 & 80 & 81 \end{array}\right)$

A * P38

$\displaystyle \left(\begin{array}{rrrrrrrrr} 1 & 2 & 8 & 4 & 5 & 6 & 7 & 3 & 9 \\ 10 & 11 & 17 & 13 & 14 & 15 & 16 & 12 & 18 \\ 19 & 20 & 26 & 22 & 23 & 24 & 25 & 21 & 27 \\ 28 & 29 & 35 & 31 & 32 & 33 & 34 & 30 & 36 \\ 37 & 38 & 44 & 40 & 41 & 42 & 43 & 39 & 45 \\ 46 & 47 & 53 & 49 & 50 & 51 & 52 & 48 & 54 \\ 55 & 56 & 62 & 58 & 59 & 60 & 61 & 57 & 63 \\ 64 & 65 & 71 & 67 & 68 & 69 & 70 & 66 & 72 \\ 73 & 74 & 80 & 76 & 77 & 78 & 79 & 75 & 81 \end{array}\right)$

Bestäm en följd av elementärmatriser $\mathbf{P}_{i_1,j_1}, \mathbf{P}_{i_2,j_2}, \ldots, \mathbf{P}_{i_s,j_s}$ för vilka gäller att $$\mathbf{P} \cdot \underbrace{ \mathbf{P}_{i_1,j_1} \mathbf{P}_{i_2,j_2} \cdots \mathbf{P}_{i_s,j_s} }_{=\mathbf{Q}} = \mathbf{I}.$$ Ledning: Studera successivt multiplikationerna $$\mathbf{P} \mathbf{P}_{i_1,j_1},\qquad (\mathbf{P} \mathbf{P}_{i_1,j_1}) \mathbf{P}_{i_2,j_2},\qquad (\mathbf{P} \mathbf{P}_{i_1,j_1}\mathbf{P}_{i_2,j_2})\mathbf{P}_{i_3,j_3},$$ och så vidare. Vid varje multiplikation gäller det att välja $i_t$ och $j_t$ så att multiplikationerna efter hand sorterar kolonnerna så att $1$:orna hamnar i diagonalen.

P1 = elementary_matrix(ZZ, 9, col1 = 0, col2 = 2)
P2 = elementary_matrix(ZZ, 9, col1 = 1, col2 = 5)
P3 = elementary_matrix(ZZ, 9, col1 = 3, col2 = 8)
P4 = elementary_matrix(ZZ, 9, col1 = 4, col2 = 6)
P5 = elementary_matrix(ZZ, 9, col1 = 7, col2 = 8)

P * P1 * P2 * P3 * P4 * P5

$\displaystyle \left(\begin{array}{rrrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$

Bestäm matrisen $\mathbf{Q}$ enligt ovanstående. Visa att $\mathbf{Q} = \mathbf{P}^{-1}$. Kommentar: Från definitionen av $\mathbf{Q}$ ovan följer egentligen direkt att $\mathbf{Q}$ är inversen till $\mathbf{P}$.

Q = P1 * P2 * P3 * P4 * P5
Q

$\displaystyle \left(\begin{array}{rrrrrrrrr} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right)$

P * Q == identity_matrix(9)

$\displaystyle \mathrm{True}$

Hur förhåller sig $\mathbf{P}$ till produkten $\mathbf{P}_{i_s,j_s}\cdots\mathbf{P}_{i_2,j_2}\mathbf{P}_{i_1,j_1}$?

P5 * P4 * P3 * P2 * P1

$\displaystyle \left(\begin{array}{rrrrrrrrr} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)$

Samma matris som $\mathbf{P}$?

P5 * P4 * P3 * P2 * P1 == P

$\displaystyle \mathrm{True}$