Om te kunnen omgaan met hoger-dimensionale determinanten, bespreken we kort de essentiële eigenschappen van permutaties.
Een permutatie van #\{1,\ldots,n\}# is een lijst van de getallen #1,\ldots,n# in een bepaalde volgorde. De permutatie #\sigma# wordt beschouwd als een afbeelding van #\{1,\ldots,n\}# naar zichzelf bepaald door #\sigma(i) = \sigma[i]#.
Dit betekent dat het beeld van #i# onder #\sigma# het #i#-de getal van de lijst #\sigma# is. Zo is #\sigma = \rv{1,2}# de identiteit op #\{1,2\}# en verwisselt #\sigma = \rv{2,1}# de getallen #1# en #2#. We duiden deze permutatie aan met #(1,2)#.
Meer in het algemeen geven we met #(i,j)# de permutatie van #\{1,\ldots,n\}# aan die #i# en #j# verwisselt en alle andere getallen op hun plaats houdt. (Dus de notatie specificeert het aantal elementen #n# niet.) Het wordt een transpositie genoemd. Er geldt #(i,j)=(j,i)#.
Als #\sigma(i) = i#, dan zeggen we dat #\sigma# het getal #i# vast houdt; als dit niet het geval is, dan zeggen we dat #\sigma # het getal #i# beweegt.
De permutatiematrix #P_\sigma# behorende bij #\sigma# is de #(n\times n)#-matrix waarvan de #(\sigma(i),i)#-elementen voor #i=1,\ldots,n# gelijk zijn aan #1# en alle andere elementen gelijk aan #0#.
Bijvoorbeeld, #\rv{1,5,3,4,2}# is de transpositie #(2,5)#, maar #\rv{5,4,3,2,1}# is geen transpositie. Deze laatste permutatie is de samenstelling #(1,5)(2,4)# van twee transposities.
De permutatie #\rv{5,4,1,3,2}# is de samenstelling #(1,5)(2,4)(3,5)(4,5)# van vier transposities. De bijbehorende matrix is \[P_{\rv{5,4,1,3,2}}= \matrix{0&0&1&0&0\\0&0&0&0&1\\0&0&0&1&0\\0&1&0&0&0\\1&0&0&0&0}\]
We zullen veel spreken over de samenstelling van permutaties. Dit is de gewone samenstelling van afbeeldingen. Zo is bijvoorbeeld
\[\rv{2,3,1} =\rv{2,1,3} \rv{1,3,2}= (1,2) (2,3)\]
We verwijzen vaak naar de samenstelling als een product. In het bijzonder is het gebruikelijk te spreken van een permutatie als een product van transposities in plaats van een samenstelling.
De inverse van een transpositie #\tau=(i,j)# is gelijk aan zichzelf \[\tau^{-1}=\tau\] waaruit volgt dat de inverse van een product van #k# transposities #\tau_1\tau_2\cdots\tau_k# gelijk is aan: \[ \left(\tau_1\tau_2\cdots\tau_{k-1}\tau_k\right)^{-1}=\tau_k\tau_{k-1}\cdots\tau_2\tau_1\]
Voorbeeld:\[[2,3,1]^{-1} = \left((1,2)(2,3)\right)^{-1} = (2,3)(1,2) = [3,1,2]\]
Transposities voldoen aan de volgende commutatieregels: \[\begin{array}{rclccc}(i,j)(k,l)&=&(k,l)(i,j)&\phantom{xx}&\text{ als }& k,l\neq i,j\\ (i,k)(i,j)&=&(i,j)(j,k)=(j,k)(i,k)&\phantom{}&\text{ als }&k\neq i,j\end{array}\] We kunnen dus de volgorde van twee transposities zodanig verwisselen dat ten minste één van de transposities ongewijzigd blijft. In het eerste geval blijven zelfs beide transposities gelijk en spreken we van commuterende transposities.
Voorbeeld: \[\begin{array}{rcl}(1,2)(2,3) &=& (2,3)(1,3) = (1,3)(1,2)\\ &&\phantom{xx}\color{blue}{(1,2)\text{ en }(2,3)\text{ commuteren niet}}\\ (1,2)(3,4) &=& (3,4)(1,2)\\ &&\phantom{xx}\color{blue}{(1,2)\text{ en }(3,4)\text{ commuteren wel}}\end{array}\]
De permutatiematrix #P_{\sigma}# voldoet aan #P_{\sigma}(\vec{e}_i) = \vec{e}_{\sigma(i)}#, waarbij #\basis{\vec{e}_1,\ldots,\vec{e}_n}# de standaardbasis voor #\mathbb{R}^n# is. Hieruit volgt meteen dat het product van twee permutatiematrices gelijk is aan de permutatiematrix behorende bij het product van de twee permutaties: als #\sigma# en #\tau# beide permutaties van # \{1,\ldots,n\} # zijn, dan geldt \[ P_\sigma\, P_\tau = P_{\sigma\,\tau} \] Immers, \[P_\sigma\,P_\tau (\vec{e}_i) = P_\sigma(\vec{e}_{\tau (i)}) = \vec{e}_{\sigma\,\tau(i)} = P_{\sigma\,\tau}(\vec{e}_i)\] voor #i=1,\ldots,n#. Omdat #P_\sigma\,P_\tau # en #P_{\sigma\,\tau}# dezelfde beelden hebben op de vectoren van de standaardbasis, vallen ze samen. Overigens volgt deze wet ook onmiddellijk uit de stelling
Samenstelling van afbeeldingen bepaald door matrices.
In deze cursus kiezen we ervoor om de permutatiematrix behorende bij #\sigma# te definiëren als de #(n\times n)#-matrix waarvan de #(\sigma(i),i)#-elementen voor #i=1,\ldots,n# gelijk zijn aan #1# en alle andere elementen gelijk aan #0#. Het voordeel van deze keuze is dat #P_{\sigma}# voldoet aan #P_{\sigma}(\vec{e}_i) = \vec{e}_{\sigma(i)}# zodat we de beelden van de standaardbasisvectoren van #\mathbb{R}^n# makkelijk kunnen opschrijven. Kolom #i# van #P_\sigma# is gelijk aan #\vec{e}_{\sigma(i)}#.
Buiten deze cursus kun je echter ook de conventie tegenkomen waarin de permutatiematrix behorende bij #\sigma# gedefinieerd wordt als de matrix waarvan de #(i,\sigma(i))#-elementen voor #i=1,\ldots,n# gelijk zijn aan #1# en alle andere elementen gelijk aan #0#. In dat geval is niet kolom #i#, maar rij #i# van #P_\sigma# gelijk aan #\vec{e}_{\sigma(i)}#. Het voordeel van deze keuze is dat #P_\sigma# voldoet aan #\left(P_{\sigma}(\vec{v})\right)_i=v_{\sigma(i)}# voor een vector #\vec{v}=\rv{v_1,v_2,\ldots,v_n}#.
De permutatiematrix in één conventie is gelijk aan de getransponeerde van de permutatiematrix in de andere conventie.
We kunnen #\{1,\ldots,n\}# vervangen door willekeurig welke andere verzameling #X# van #n# elementen en spreken van een permutatie van #X#. Nadat we de elementen van #X# genummerd hebben met #1,2,\ldots,n# komen we weer uit op een permutatie van #\{1,\ldots,n\}#. Net als bij de keuze van een basis voor coördinatisering van lineaire afbeeldingen kunnen verschillende nummeringen tot geconjugeerde permutaties leiden. Hier gaan we nu niet nader op in.
We moeten onderscheid kunnen maken tussen producten van transposities van even en van oneven lengte.
- Een afbeelding #\{1,\ldots,n\}\to\{1,\ldots,n\}# is dan en slechts dan een permutatie van #\{1,\ldots,n\}# als ze een bijectieve afbeelding is.
- Het aantal permutaties van #\{1,\ldots,n\}# is gelijk aan #1\cdot 2\cdots (n-1)\cdot n#. Dit getal schrijven we vaak als #n!# en heet de faculteit van #n#.
- Elke permutatie kan worden geschreven als een product van transposities. (De samenstelling van #0# permutaties is per definitie de identieke afbeelding #\rv{1,2,\ldots,n}#.)
- Als een permutatie op twee manieren geschreven kan worden als een product van transposities, dan hebben beide producten even lengte of beide producten oneven lengte.
Het teken van een permutatie #\sigma# is #1# als #\sigma# het product is van een even aantal transposities en #-1# anderszins. Het wordt aangeduid met #\text{sg}(\sigma)#.
1. Volgens Inverteerbaarheid bij gelijke dimensies voor domein en codomein is een afbeelding #f: \{1,\ldots,n\}\to\{1,\ldots,n\}# dan en slechts dan bijectief als ze surjectief is, in welk geval de lijst \[\rv{f(1),f(2),\ldots,f(n)}\]bestaat uit #n# verschillende getallen in #\{1,\ldots,n\}#. Dit is dan en slechts dan het geval als #f# een permutatie is.
2. We gebruiken de notatie #n!=1\cdot 2\cdots (n-1)\cdot n# en laten met volledige inductie naar #n# zien dat #n!# het aantal manieren is om een lijst van lengte #n# te vullen met elementen uit #\{1,2,\ldots,n\}#, waarbij elk element precies één keer gebruikt wordt. Dit volstaat voor het bewijs.
Voor #n=1# is #1!=1# inderdaad het aantal manieren om een lijst van lengte #1# te vullen met #1#.
Voor de inductie stap in ons bewijs met volledige inductie naar #n# veronderstellen we nu #n\gt 1#. Er zijn #n# mogelijkheden om een getal #k\in \{1,\ldots,n\}# op de eerste plaats te zetten. Als we dat gedaan hebben voor een bepaalde #k#, dan kunnen we de lijst ter lengte #n-1# van de overige plaatsen vullen door elk van de #n-1# getallen #1,\ldots,k-1,k+1,\ldots,n# op één plaats te zetten. Dit aantal is, vanwege de inductiehypothese, #(n-1)!# (het doet er immers niet toe hoe de #n-1# getallen heten, als ze onderling maar verschillen). We concluderen dat \[n! = n\cdot (n-1)! = n\cdot (n-1)\cdot (n-2) \cdots 2 \cdot 1\] het aantal manieren is om een lijst van lengte #n# te vullen met elementen uit #\{1,2,\ldots,n\}#, waarbij elk element precies één keer gebruikt wordt.
3. Laat #\sigma# een permutatie zijn. Als #\sigma# de identiteit is, dat wil zeggen: #\sigma =\rv{1,2,\ldots,n}#, dan is #\sigma# het product van #0# transposities.
Zo niet, dan zijn er getallen die bewogen worden door #\sigma#. Laat #v# het aantal getallen in #\{1,\ldots,n\}# zijn dat bewogen wordt door #\sigma#. We bewijzen de uitspraak met inductie naar #v#. Als #v=0#, dan moet #\sigma# de identiteit zijn, en die hebben we al behandeld. Stel nu #v\gt0#. Dan is er een #\ell \in \{1,\ldots,n\}# met # \sigma(\ell)\ne \ell#. Schrijf #m=\sigma(\ell)#. Dan geldt ook #\sigma(m)\ne m#, want anders zou #\sigma(m)=m=\sigma(\ell)# en #m\ne\ell# gelden, wat tegenspreekt dat #\sigma# injectief is. Dus zowel #\ell# als #m# dragen bij aan de #v# bewogen getallen door #\sigma#. Bekijk nu het product \[\tau=\sigma\,(\ell,m)\]van #\sigma# met de transpositie #(\ell,m)#. Als #k\in\{1,\ldots,n\}# ongelijk is aan #\ell# en #m#, dan geldt #\tau(k)=\sigma(k)#, zodat de #v-2# bewogen getallen van #\sigma# ongelijk aan #\ell# en #m# ook de bewogen getallen van #\tau# ongelijk aan #\ell# en #m# zijn. Bovendien geldt \[\tau[m]=\sigma\,(\ell,m)[m]=\sigma[\ell]=m\] zodat #m# een vast punt van #\tau# is. Dus #\tau# beweegt minder getallen dan #\sigma#. Volgens de inductiehypothese is #\tau# dus een product van transposities. Daaruit volgt dat #\sigma=\tau \,(\ell,m)# ook een product van transposities is.
4. Stel dat de permutatie #g# kan worden geschreven als het product van transposities #\mu_1\cdots\mu_p# met #p# even, en stel dat #g# ook kan worden geschreven als het product van transposities #\nu_1\cdots\nu_q# met #q# oneven. Dan kan de identiteit #e# worden geschreven als \[e=gg^{-1}=\mu_1\cdots\mu_p\left(\nu_1\cdots \nu_q\right)^{-1}=\mu_1\cdots\mu_p\nu_q\cdots \nu_1\] waarin het aantal transposities in het laatste product oneven is. We laten zien dat dit onmogelijk is.
Stel dat we de identiteit kunnen schrijven als het product van #m\geq 2# transposities: \[e=\tau_1\cdots \tau_m\] waarin #m# zowel even als oneven mag zijn. We laten zien dat er een algoritme bestaat om dit product te vereenvoudigen tot een product van #m-2# transposities. Als #m# even is, dan kunnen we het product door herhaaldelijke toepassing van het algoritme vereenvoudigen tot een product van nul transposities, wat per definitie gelijk is aan de identiteit. Als #m# oneven is, dan zouden we het product door herhaaldelijke toepassing van het algoritme kunnen vereenvoudigen tot een enkele transpositie, wat in tegenspraak is met de aanname dat het product gelijk is aan de identiteit. In de rest van het bewijs beschrijven we het genoemde algoritme.
We mogen aannemen dat #\tau_1=(1,2)#. Immers, als #\tau_1 = (i,j)# ongelijk is aan #(1,2)# dan definiëren we #\kappa\equiv(1,i)(2,j)# en schrijven we: \[\begin{array}{rcl}e&=& \kappa\kappa^{-1}\\&=& \kappa e\kappa^{-1}\\ &=&\kappa\tau_1\cdots \tau_m\kappa^{-1}\\&=&\kappa\tau_1e\tau_2e\tau_3\cdots e\tau_{m-1}e\tau_m\kappa^{-1}\\&=&\kappa\tau_1\left(\kappa^{-1}\kappa\right)\tau_2\left(\kappa^{-1}\kappa\right)\tau_3\cdots\left(\kappa^{-1}\kappa\right)\tau_{m-1}\left(\kappa^{-1}\kappa\right)\tau_m\kappa^{-1}\\&=&\left(\kappa\tau_1\kappa^{-1}\right)\left(\kappa \tau_2\kappa^{-1}\right)\left(\kappa \tau_3\kappa^{-1}\right)\cdots \left(\kappa\tau_{m-1}\kappa^{-1}\right)\left(\kappa\tau_m\kappa^{-1}\right)\\ &=&\rho_1\cdots\rho_m\end{array}\] waarin we #\rho_k\equiv\kappa\tau_k\kappa^{-1}# hebben gedefinieerd voor alle #k# in #\{1,\ldots,m\}#. Voor elke mogelijke waarde van #k# passen we de commutatieregels toe op #\kappa# en #\tau_k# waarbij we de transposities in #\kappa# ongewijzigd laten zodat, dankzij #\kappa\kappa^{-1}=e#, elke permutatie #\rho_k# met #1\leq k\leq m# vereenvoudigt tot één transpositie. In het bijzonder (we volgen de veranderingen van #\tau_1# in het groen): \[\begin{array}{rcll}\rho_1&=&\kappa\color{green}{\tau_1}\kappa^{-1}&\phantom{xyzuvw}\color{blue}{\text{definitie }\rho_1}\\ &=&(1,i)(2,j)\color{green}{(i,j)}(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{\kappa\equiv(1,i)(2,j), \tau_1=(i,j)}\\ &=&(1,i)\color{green}{(2,i)}(2,j)(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(i,j)=(2,i)(2,j)}\\ &=&(1,i)\color{green}{(2,i)}(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(2,j)=e}\\ &=&\color{green}{(1,2)}(1,i)(1,i)&\phantom{xyzuvw}\color{blue}{(1,i)(2,i)=(1,2)(1,i)}\\&=&\color{green}{(1,2)}&\phantom{xyzuvw}\color{blue}{(1,i)(1,i)=e}\end{array}\]Een product van transposities kunnen we dus altijd herschrijven tot een product van hetzelfde aantal transposities waarvan de eerste gelijk is aan #(1,2)#. We mogen daarom aannemen dat dit al gebeurd is in het oorspronkelijke product #\tau_1\cdots\tau_m# zodat we mogen aannemen dat #\tau_1=(1,2)#.
We mogen verder aannemen dat er een natuurlijk getal #\ell# in #\{1,\ldots,m\}# bestaat waarvoor elk van de transposities #\tau_1,\ldots,\tau_\ell# het getal #1# bewegen (dat wil zeggen: de vorm #(1,a)# hebben met #a# in #\{2,\ldots,n\}#) en, indien #\ell\lt m#, elk van de transposities #\tau_{\ell+1},\ldots,\tau_m# het getal #1# vast houden. We kunnen immers de commutatieregels herhaaldelijk toepassen op naastgelegen transposities in het product #\tau_1\cdots\tau_m# zodat alle transposities die #1# bewegen links komen te staan ten opzichte van alle transposities die #1# vast houden. We laten het totale aantal transposities in het product ongewijzigd door geen mogelijke vereenvoudigingen toe te passen. We nemen aan dat deze scheiding al heeft plaatsgevonden in het oorspronkelijke product #\tau_1\cdots \tau_m#.
Er geldt #\ell\geq 2#. Immers, voor #\ell=1# vinden we \[\begin{array}{rcll}\tau_1(1)&=&\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{m\geq 2\text{ en }\tau_2,\ldots,\tau_m\text{ houden }1\text{ vast}}\\&=&e(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&1&\phantom{xyzuvw}\color{blue}{\text{identiteit houdt elk getal vast}}\end{array}\] in tegenspraak met #\tau_1(1)=2#.
Omdat #\ell\geq 2# is het product #\tau_2\cdots\tau_\ell# goed gedefinieerd, zodat we de werking daarvan op #1# kunnen bekijken:\[\begin{array}{rcll}\tau_2\cdots\tau_\ell(1)&=& \tau_1\tau_1\tau_2\cdots\tau_\ell(1)&\phantom{xyzuvw}\color{blue}{\tau_1\tau_1=e}\\&=&\tau_1\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{\ell=m\text{ of }\tau_{\ell+1},\ldots,\tau_m\text{ houden }1\text{ vast}}\\&=&\tau_1(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&2&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2)}\end{array}\] Er bestaat dus ten minste één index #j# met #2\le j \le\ell# zodat #\tau_j=(1,2)=\tau_1#. Laat #j# de kleinste index zijn waarvoor dit geldt. Als #j=2#, dan volgt:\[\begin{array}{rcll}e&=&\tau_1\tau_1\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_2=\tau_1\text{ ingevuld}}\\&=&\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\end{array}\] zodat het totale aantal transposities met twee vermindert. Voor #j\geq 3# geldt:\[\begin{array}{rcll}e&=&\tau_1\cdots \tau_{j-1}\tau_1\tau_{j+1}\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_j=\tau_1\text{ ingevuld}}\\&=&\left(\tau_1\tau_2\tau_1\right)\left(\tau_1\tau_3\tau_1\right)\cdots \left(\tau_1\tau_{j-1}\tau_1\right)\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\\&=&\sigma_2\sigma_3\cdots \sigma_{j-1}\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\sigma_i\equiv\tau_1\tau_i\tau_1}\end{array}\] waarin we #\sigma_i\equiv\tau_1\tau_i\tau_1# hebben gedefinieerd voor alle #i# in #\{2,\ldots,j-1\}#. Wanneer we voor al deze waarden van #i# de commutatieregels toepassen op #\tau_1# en #\tau_i# waarbij we #\tau_1# ongewijzigd laten, dan volgt uit #\tau_1\tau_1=e# dat elke #\sigma_i# vereenvoudigt tot één transpositie. Dat laten we nu expliciet zien. Uit #i\lt j\leq\ell# volgt dat er #j-2# getallen #a_i\neq 2# bestaan zodat #\tau_i=(1,a_i)# en \[\begin{array}{rcll}\sigma_i&\equiv&\tau_1\tau_i\tau_1&\phantom{xyzuvw}\color{blue}{\text{definitie }\sigma_i\text{ voor }i\in\{2,\ldots,j-1\}}\\&=&(1,2)(1,a_i)(1,2)&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2),\tau_i=(1,a_i)\text{ want }i\lt\ell}\\&=&(2,a_i)(1,2)(1,2)&\phantom{xyzuvw}\color{blue}{a_i\neq 2\text{ want }i\lt j}\\&=&(2,a_i)&\phantom{xyzuvw}\color{blue}{(1,2)(1,2)=e}\end{array}\]We zien dat de identiteit in alle gevallen geschreven kan worden als een product van #m-2# transposities:\[e=\underbrace{\sigma_2\sigma_3\cdots \sigma_{j-1}}_{j-2\text{ factoren}}\underbrace{\tau_{j+1}\cdots\tau_m}_{m-j\text{ factoren}}\qquad 2\leq j\leq m\]Immers, #(j-2)+(m-j)=m-2#.
Dankzij de punten drie en vier is het begrip "teken van een permutatie" goed gedefinieerd.
Als #\sigma# en #\tau# permutaties zijn van dezelfde verzameling, dan geldt \[ \text{sg} (\sigma\,\tau ) = \text{sg}(\sigma) \cdot \text{sg} (\tau ) \] Dit volgt uit de definitie van een permutatie in termen van een uitdrukking voor de permutatie als een product van transposities.
Schrijf de permutatie #\sigma=\left[ 2 , 4 , 5 , 1 , 3 \right] # als een product van transposities.
Geef je antwoord als een product van transposities zonder vermenigvuldigingstekens.
#\left[ 2 , 4 , 5 , 1 , 3 \right] = # #(1,2)(2,4)(3,5)#
Omdat #\sigma# het element #1# afbeeldt op #2#, is #\sigma# het product van de transpositie #(1,2)# en de permutatie #\tau=[1,4,5,2,3]# die #1# vast houdt. Schrijf #\tau# als een product van een transpositie van de vorm #(2,a)# voor geschikte #a# en een permutatie die #1# en #2# vast houdt, enzovoorts. Zo kun je #\left[ 2 , 4 , 5 , 1 , 3 \right] # als het product van hooguit #4# transposities schrijven.
We vinden
\[\begin{array}{rcl}
\left[ 2 , 4 , 5 , 1 , 3 \right] &=& (1,2)\,[1,4,5,2,3]\\ &=& (1,2)\,(2,4)\,[1,2,5,4,3]\\ &=& (1,2)\,(2,4)\,(3,5)\,[1,2,3,4,5] \\
&=& (1,2)(2,4)(3,5)
\end{array}
\]
Er zijn vele manieren om de permutatie als product van transposities te schrijven.
Permutaties
