Paritat d'una permutació

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques, les permutacions (és a dir, les bijeccions en els conjunts finits) es poden descompondre en un producte de transposicions, és a dir en una successió d'intercanvis d'elements dos a dos.

  • Una permutació parell és una permutació que es pot expressar com el producte d'un nombre parell de transposicions;
  • Una permutació senar és una permutació es pot expressar com el producte d'un nombre senar de transposicions.

El signe d'una permutació val 1 si és parell i -1 si és senar. L'aplicació signe constitueix un morfisme de grups. Intervé en àlgebra multilineal, sobretot per al càlcul de Determinants.

Definició de la paritat[modifica | modifica el codi]

Sigui una permutació . La definició tradicional de la paritat de es fa pel recompte de les inversions.

Definició

Siguin i<j dos elements diferents compresos entre 1 i n. Es diu que la parella {i,j} queda 'invertida per quan .

Una permutació s'anomena parell quan presenta un nombre parell d'inversions, senar si no.

Exemple
Sigui la permutació
La parella {1,2} no està en inversió ja que les imatges de 1 i 2 estan conserven el mateix ordre. Tampoc ho estan 1 i 3. La llista de les parelles en inversió és {2,5}, {3,4}, {3,5}, {4,5}. N'hi ha quatre, per tant la permutació és parell.

Per definició, el signe d'una permutació parell és 1, la d'una permutació senar és -1.

Una transposició és senar[modifica | modifica el codi]

Tota transposició és una permutació senar. En efecte notant i i j, i<j, els termes intercanviats per la transposició, aquesta s'escriu

Els parells en inversió són els parells de la forma {i,k} amb k comprès entre i+1 i j i les de la forma {k,j} amb k comprès entre i+1 i j-1. En total, hi ha un nombre senar d'inversions, i d'aquí se'n desprèn que la permutació és senar.

Una fórmula per a calcular el signe[modifica | modifica el codi]

Es nota el conjunt dels parells d'elements compresos entre 1 i n (n'hi ha n(n-1)/2). Una permutació σ té per signe

Demostració
Dient P aquest producte. Examinar totes les parelles (i,j) amb i<j porta a examinar tots els parells {i,j}. Per a cadascuna d'elles, el terme que es troba al producte té un signe negatiu si el parell és en inversió, positiu si no. Això mostra que el signe de P és el de la permutació. Finalment, per bijectivitat de σ, els termes σ(i)-σ(j) del numerador són, tret del signe, els mateixos que els i-j del denominador. Això mostra que el valor absolut de P és 1 i permet concloure.

Aquesta fórmula té un cert interès algebraic però no permet un càlcul eficaç del signe a la pràctica. En efecte, respecte al senzill recompte de les inversions s'afegeix la multiplicació i la divisió per un cert nombre d'enters.

Signe d'un producte[modifica | modifica el codi]

Les permutacions verifiquen una regla dels signes per al producte: el producte de dues permutacions parells és parell, de dues permutacions senars és parell, el producte d'una permutació parell i d'una senar és senar. Utilitzant el signe, això es resumeix per la fórmula

Demostració
En el segon factor del segon membre, es reconeix directament un signe. Per al primer, cal prèviament reindexar posant {i',j'}={τ(i),τ(j)}, on es reconeix llavors igualment un signe.

En termes algebraics: el signe és un morfisme de grups del grup simètric en . El conjunt de les permutacions parells forma el grup alternat, nucli d'aquest morfisme. Finalment la permutació inversa de σ té el mateix signe que σ.

Càlcul del signe[modifica | modifica el codi]

Com a corol·lari dels resultats precedents,

  • una permutació és parell si i només si es pot expressar com el producte d'un nombre parell de transposicions;
  • una permutació és senar si i només si es pot expressar com el producte d'un nombre senar de transposicions

i aquests dos casos s'exclouen mútuament.

El càlcul del signe per la descomposició en producte de transposicions és molt més eficaç que l'aplicació de la definició inicial; en efecte per a una permutació de aquesta descomposició demanda com a màxim n-1 operacions, contra n(n-1)/2 per a la definició.

Exemples
la identitat és una permutació parell;
una transposició és una permutació senar;
una permutació circular és parell si el nombre d'elements és senar; és senar si el nombre d'elements és parell.

Vegeu també[modifica | modifica el codi]