SharedSage genom exempel / Permutationer.sagewsOpen in CoCalc
Author: Robert Nyqvist

Permutationer

Låt σ\sigma vara permutationen (123456789361872594). \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 σ(3)=1\sigma(3) = 1 och σ(7)=5\sigma(7) = 5.
typeset_mode(True) sigma = Permutation([3, 6, 1, 8, 7, 2, 5, 9, 4]) sigma(3)
1\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
[5,2,1,9,3,4,6,7,8]\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 σρ(a)\sigma\rho(a) tolkas ρ(σ(a))\rho(\sigma(a)).
sigma * rho
[1,4,5,7,6,2,3,8,9]\displaystyle [1, 4, 5, 7, 6, 2, 3, 8, 9]
Vi ser att σρ\sigma\rho avbildar till exempel 2244.
rho(sigma(2))
4\displaystyle 4
Vi bestämmer motsvarande permutationsmatris P\mathbf{P} för σ\sigma.
P = sigma.to_matrix() P
(001000000000001000100000000000000001000000100010000000000010000000100000000000010)\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 v=(1,2,,9)\boldsymbol{v} = (1, 2, \ldots, 9). Bestäm vP\boldsymbol{v}\mathbf{P} och Pv\mathbf{P}\boldsymbol{v}.
v = vector(ZZ, [i for i in [1..9]]) v * P P * v
(3,6,1,8,7,2,5,9,4)\displaystyle \left(3,\,6,\,1,\,8,\,7,\,2,\,5,\,9,\,4\right)
(3,6,1,9,7,2,5,4,8)\displaystyle \left(3,\,6,\,1,\,9,\,7,\,2,\,5,\,4,\,8\right)
Kan du förklara resultatet?
Låt ii, jj och nn vara heltal sådana att 1i,jn1 \leq i, j \leq n. En elementärmatris Pi,j\mathbf{P}_{i,j} är en permutationsmatris som hör till en permutation ρ\rho för vilken ρ(i)=j,ρ(j)=iochρ(k)=k \rho(i) = j,\quad \rho(j) = i \quad\text{och}\quad \rho(k) = k kik \neq i och kjk \neq j. Bestäm P1,4\mathbf{P}_{1,4} och P3,8\mathbf{P}_{3,8}, då n=9n = 9.
P14 = elementary_matrix(ZZ, 9, row1 = 0, row2 = 3) P14
(000100000010000000001000000100000000000010000000001000000000100000000010000000001)\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
(100000000010000000000000010000100000000010000000001000000000100001000000000000001)\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 vP1,4\boldsymbol{v}\mathbf{P}_{1,4} och vP3,8\boldsymbol{v}\mathbf{P}_{3,8} samt AP1,4\mathbf{A}\mathbf{P}_{1,4} och AP3,8\mathbf{A}\mathbf{P}_{3,8}, där A=(123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081). \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
(4,2,3,1,5,6,7,8,9)\displaystyle \left(4,\,2,\,3,\,1,\,5,\,6,\,7,\,8,\,9\right)
v * P38
(1,2,8,4,5,6,7,3,9)\displaystyle \left(1,\,2,\,8,\,4,\,5,\,6,\,7,\,3,\,9\right)
A = matrix(ZZ, 9, 9, [1..81]) A
(123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081)\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
(423156789131112101415161718222021192324252627312930283233343536403839374142434445494748465051525354585657555960616263676566646869707172767475737778798081)\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
(128456739101117131415161218192026222324252127282935313233343036373844404142433945464753495051524854555662585960615763646571676869706672737480767778797581)\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 Pi1,j1,Pi2,j2,,Pis,js\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 PPi1,j1Pi2,j2Pis,js=Q=I. \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 PPi1,j1,(PPi1,j1)Pi2,j2,(PPi1,j1Pi2,j2)Pi3,j3, \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 iti_t och jtj_t så att multiplikationerna efter hand sorterar kolonnerna så att 11: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
(100000000010000000001000000000100000000010000000001000000000100000000010000000001)\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 Q\mathbf{Q} enligt ovanstående. Visa att Q=P1\mathbf{Q} = \mathbf{P}^{-1}. Kommentar: Från definitionen av Q\mathbf{Q} ovan följer egentligen direkt att Q\mathbf{Q} är inversen till P\mathbf{P}.
Q = P1 * P2 * P3 * P4 * P5 Q
(001000000000001000100000000000000010000000100010000000000010000000000001000100000)\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)
True\displaystyle \mathrm{True}
Hur förhåller sig P\mathbf{P} till produkten Pis,jsPi2,j2Pi1,j1\mathbf{P}_{i_s,j_s}\cdots\mathbf{P}_{i_2,j_2}\mathbf{P}_{i_1,j_1}?
P5 * P4 * P3 * P2 * P1
(001000000000001000100000000000000001000000100010000000000010000000100000000000010)\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 P\mathbf{P}?
P5 * P4 * P3 * P2 * P1 == P
True\displaystyle \mathrm{True}