Signature d'une permutation
Bonjour,
J'ai un peu de mal à comprendre la démonstration de wikipedia de cette page :
https://fr.wikipedia.org/wiki/Signature_d'une_permutation#Signature_d.27un_produit
C'est la démonstration du fait que la signature de la composée de deux permutations est le produit des signatures de ces permutations. Il y a une transformation qui me choque.
$\prod_{1 \leq i < j \leq n} f(i, j) = \prod_{\{i, j\} \in \mathcal{P}} f(i, j)$
Cette formule n'est vraie que si $f(i,j)=f(j,i)$ pour tout couple $(i, j)$ n'est-ce pas ?
Et il me semble bien que ce n'est pas le cas avec la fonction qui nous concerne :
$\mathrm{sgn}(\sigma_1(\sigma_2(j))-\sigma_1(\sigma_2(i)))\mathrm{sgn}(\sigma_2(j)-\sigma_2(i))$
Qu'en pensez-vous ?
J'ai un peu de mal à comprendre la démonstration de wikipedia de cette page :
https://fr.wikipedia.org/wiki/Signature_d'une_permutation#Signature_d.27un_produit
C'est la démonstration du fait que la signature de la composée de deux permutations est le produit des signatures de ces permutations. Il y a une transformation qui me choque.
$\prod_{1 \leq i < j \leq n} f(i, j) = \prod_{\{i, j\} \in \mathcal{P}} f(i, j)$
Cette formule n'est vraie que si $f(i,j)=f(j,i)$ pour tout couple $(i, j)$ n'est-ce pas ?
Et il me semble bien que ce n'est pas le cas avec la fonction qui nous concerne :
$\mathrm{sgn}(\sigma_1(\sigma_2(j))-\sigma_1(\sigma_2(i)))\mathrm{sgn}(\sigma_2(j)-\sigma_2(i))$
Qu'en pensez-vous ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Merci...
[Inutile de recopier le message précédent. AD]
Def 1 : Soit $p$ le nombre d'orbites distinctes de $\sigma$
$\epsilon(\sigma) = (-1)^{n-p}$
Def 2 : Si la permutation se décompose en $p$ cycles disjoints de taille $k_1$, $k_2$, ..., $k_p$, alors $\epsilon(\sigma) = (-1)^{k_1 - 1} (-1)^{k_2 - 2} ... (-1)^{k_p - 1} = (-1)^{(k_1-1)+(k_2-1)+...+(k_p-1)}$
Def 3 : Si la décomposition en cycles disjoints comporte $p$ cycles pairs alors $\epsilon(\sigma) = (-1)^p$
Def 4 : Si la permutation est le produit de q transpositions, alors $\epsilon(\sigma) = (-1)^q$
Def 5 : $\epsilon(\sigma) = (-1)^{\nu(\sigma)}$
avec $\nu(\sigma) = Card \{ (i, j) | 1 \leq i < j \leq n | \sigma(j) < \sigma(i) \}$
(nombre d'inversions)
Def 6 : $\epsilon(\sigma) = \prod_{1 \leq i < j \leq n} sgn(\sigma(j) - \sigma(i))$
Def 7 : $\epsilon(\sigma) = \prod_{1 \leq i < j \leq n} \dfrac{\sigma(j) - \sigma(i)}{j-i}$
Si vous avez en prime, un bon document à conseiller sur le sujet... je vous en serais très reconnaissant !
Def 8 ; $\epsilon(\sigma)=$ le déterminant de la matrice de permutation associée à $\sigma$.
Avec les propriétés déjà démontrées du déterminant (antisymétrie) et le fait facile que toute permutation est produit de transpositions, on a immédiatement que la parité du nombre de transpositions ne dépend pas de la décomposition.
Tu dois > définir le déterminant.
> établir l'existence par récurrence sur la dimension.
> définir la signature d'une permutation indépendamment du déterminant
> montrer la relation déterminant-signature
> déduire l'unicité du déterminant.
Et là tu peux parler de "le" déterminant.
et à ce moment tu établis la relation pour la signature de la composée...
On peut très bien définir la signature de $\sigma$ comme $\det(e_{\sigma(1)},\ldots, e_{\sigma(n)})$. Ça permet de faire très vite, et on n'a pas besoin de ce que zenxbear raconte (pas besoin de définir la signature indépendamment du déterminant).
C'est donc pertinent comme le ressent l'auteur du fil de vouloir collecter toutes les clés de ce mastodonte labyrinthique.
La preuve la plus "valable" (autrement dit qui n'introduit pas un ordre ad hoc) est celle que gb avait signalée il y a longtemps. Soit un ensemble fini et on prend n'importe quel élément $\infty$ dedans. Je colorie en bleu les transpositions qui le laissent fixes et en rouge les autres. Le produit de 2 transpositions rouges est toujours égal au produit d'une bleue par une rouge bien choisies ou de deux bleues bien choisies. Le produit d'une rouge par une bleue est toujours égal au produit d'une bleue par une rouge bien choisies.
De la sorte, si un produit de transpositions est égal à l'identité, on obtient un produit de transpositions de même parité (nombre de facteur) qui donne aussi l'identité et qui n'est composé que de bleues, sauf une éventuelle rouge à la fin, mais ça c'est pas possible. Par récurrence, cela signifie qu'il faut forcément un nombre pair de transpositions pour obtenir l'identité en en faisant le produit.
du coup, je dois établir que la permutation est produit de transposées avant de poser cette définition de la signature.
et donc déduire de cette définition les histoires de parité d'une permutation.
puis déduire la formule du déterminant avec la signature, et donc l'unicité du déterminant comme forme multi linéaire alternée...
Ok ca marche. (tu)
Et ce qui est amusant c'est que si je me suis intéressé à la signature d'une permutation parce qu'elle interviens dans une des formules du déterminant ;-)
On utilise
Théorème. Toute permutation est un produit d'un nombre fini de transpositions.
Démonstration. Soit $\sigma$ une permutation de $\{1,\ldots,n\}$. On construit par récurrence une suite de permutations $\rho_0,\rho_1,\ldots,\rho_n$ telles que, pour tout $k$, $0\leq k\leq n$ et tout $i$, $1\leq i\leq k$, on a $\rho_k(i)=\sigma(i)$ (autrement dit, $\rho_k$ coincide avec $\sigma$ sur les $k$ premiers éléments). On construit les $\rho_k$ comme des produits de transpositions. Comme à la fin $\rho_n=\sigma$, on aura montré la proposition.
$\bullet$ On initialise en posant $\rho_0=Id$.
$\bullet$ Supposons $k>0$ et que $\rho_{k-1}$ a déjà été construite. Si $\rho_{k-1}(k)=\sigma(k)$, on prend $\rho_k=\rho_{k-1}$. Sinon, on prend $\rho_k=\tau_{\sigma(k)\leftrightarrow\rho_{k-1}(k)}\,\rho_{k-1}$. Ceci amène $\sigma(k)$ à la $k$-ème place, et ne dérange pas les $k-1$ premières places occupées par $\sigma(1),\ldots,\sigma(k-1)$.
Ensuite, avec le fait que toute transposition de colonnes change le signe du déterminant (antisymétrie), on obtient :
La signature d'une permutation est $1$ si cette permutation est le produit d'un nombre pair de transpositions, $-1$ si elle est le produit d'un nombre impair de transpositions.
Le fait que la signature est un morphisme de groupes du groupe des permutations dans $\{\pm1\}$ suit immédiatement.
$\det(e_1, \ldots, e_n) = \det(I_n) = 1$
$\mathrm{sgn}\left ( \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 4 & 1 & 6 & 2 & 5 & 3\end{pmatrix} \right ) = \det(e_4, e_1, e_6, e_2, e_5, e_3) = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0 & 0
\end{vmatrix}$
Pour ma part mais c'est affaire de gout je préfère partir des permutations et signatures connues ou prouvées et définir directement le déterminant par la formule polynômiale bien connue (ou abstraitement par les formes linéaires alternées mais dans ce cas la preuve D'EXISTENCE D'UNE NON NULLE ramène de toute façon à l'avoir défini avant. Puis ensuite prouver ses nombreuses propriétés quasi-magiques.
Par contre il faut bien reconnaitre que la signature vue avec lui prend un supplément de robustesse très clair
tu vas écrire d'abord:
$$\det(E^{\sigma\sigma'(1)} ... E^{\sigma\sigma'(n)}) = \epsilon(\sigma \sigma')\det(E^{1} ... E^{n})$$
et par ailleurs
$$\det(E^{\sigma\sigma'(1)} ... E^{\sigma\sigma'(n)}) = \epsilon(\sigma )\det(E^{ \sigma'(1)} ... E^{ \sigma'(n)})= \epsilon(\sigma ) \epsilon(\sigma' )\det(E^{1} ... E^{n})$$
et à ce moment tu identifies les 2 expressions pour avoir ton résultat.
Du coup il te faut bien établir que $\epsilon(\sigma)=\frac{\det(F^{\sigma (1)} ... F^{\sigma (n)}) }{\det(F^{1} ... F^{n}) }$, que ta base $F^1, ..., F^n$ soit canonique ou pas. Le determinant $\det(E^{ \sigma'(1)} ... E^{ \sigma'(n)})$ n'est pas forcément égal à 1. :-D
Du coup, peut être @GBZM voit pourquoi ceci est trivial via les propriétés du déterminant que l'on a à notre portée, à ce stade...
@cc parfois ca me perturbe de voir des raisonnements plus brefs que les miens. Est ce que j'avais fait ces choix par question de goût en imitant untel, ou pour un impératif logique.
Il en découle immédiatement que le déterminant de la matrice $I_n$, c.-à-d. $\det(e_1,\ldots,e_n)$ est égal à $1$ (je te répète que les $e_j$ sont les vecteurs colonnes de la base canonique, $e_j$ est le vecteur colonne avec $1$ en $j$-ème ligne et $0$ partout ailleurs).
Ce qui est modérément pénible à établir (par récurrence bien sûr) est que le déterminant ainsi défini est multilinéaire alterné en les colonnes.
Je te répète encore que la signature d'une permutation $\sigma$ se définit comme $\epsilon(\sigma)=\det(e_{\sigma(1)},\ldots,e_{\sigma(n)})$.
On démontre que toute permutation est produit d'un nombre fini de transpositions (ce que j'ai fait plus haut). Ceci fait, les propriétés déjà établies du déterminant (la caractère alterné, donc l'antisymétrie) montrent qu'une permutation a pour signature $1$ quand elle est le produit d'un nombre pair de transpositions et $-1$ quand elle est le produit d'un nombre impair de transpositions ; en passant ceci montre que la parité de ce nombre ne dépend pas de la décomposition en produit de transpositions.
Le fait que $\epsilon(\sigma \sigma') = \epsilon(\sigma) \epsilon(\sigma')$ est immédiat à partir que ce qu'on vient de dire sur la parité.
@zenxbear, j'ai déjà remarqué à propos de la discussion sur la récurrence que tu as tendance à t'enferrer dans tes a priori et à ne pas prendre en compte ce qu'on t'écrit. Fais l'effort de comprendre vraiment ce qu'on t'écrit, ça raccourcira les discussions pour le bien de tous.
Ce n'est pas ce que je lis dans ce que GBZM te dit. Il ne faut confondre "trivial" avec "trivialement conséquence de". Oui, moi-même je peux te le confirmer et je suis au dessus de tout soupçon d'être super-compétent dans les maitrises des thématiques déterminant-signature-permutations-transpositions, l'existence d'une signature robuste (ie le fait qu'un nombre impair de transpositions ne peut pas donner l'identité quand on les compose) est trivialement conséquence de la "déterminant-story" et pour autant absolument pas du tout trivial prise seule. Sa découverte et la découverte du déterminant sont à mon sens d'ailleurs les découvertes hors-logique les plus importantes de tous les temps en mathématique et je pèse mes mots (j'ai des heures de vol dans l'évaluation des richesses que regorge le déterminant)
Une fois défini $\mathrm{sgn}\left(\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 4 & 1 & 6 & 2 & 5 & 3 \end{pmatrix}\right)$ par $\det\begin{vmatrix}0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 \end{vmatrix}$, va-t-on vraiment calculer ce déterminant pour obtenir la signature ? Et si l'on utilise $\prod_{i<j}\left(\sigma\left(j\right)-\sigma\left(i\right)\right)\times\prod_{i<j}\left(j-i\right)$, va-t-on vraiment calculer ces produits ? En outre, cela revient à enseigner "prenons n'importe quels axiomes, il en résultera bien quelque chose". Voyons voir comment procéder de façon raisonnable, c'est à dire autrement.
$\,$- Notion fondamentale: les orbites. Ce sont les classes de transitivité de l'action d'une substitution $\sigma\in\mathfrak{S}_{n}$. L'algorithme de calcul de ces orbites est évident à comprendre et à écrire. Et il est linéaire par rapport à n. Pour l'exemple, cela donne $\sigma=\left(142\right)\left(36\right)\left(5\right)$.
- Digression: écriture de Foata-Schutzenberger. On fait commencer chaque orbite par son "chef de classe" et on ordonne les chefs de classes dans le sens croissant. Ici, cela donne $4,2,1,5,6,3$. Tant que l'on ne dépasse pas le chef de classe, on est dans la même orbite, et quand cela remonte, on entre dans une nouvelle orbite.
- Une décomposition orbitale est le produit des plongements dans $\mathfrak{S}_{n}$ des actions de $\sigma$ sur ses orbites. Cette "décomposition orbitale" est unique à l'ordre près. Lorsque l'on décide de ne pas écrire les orbites des éléments fixes, on obtient l'écriture usuelle "en un produit de cycles à supports disjoints", qui est invariante par plongement dans un groupe plus gros.
- Écriture transpositoire. Toute substitution peut s'écrire sous forme d'un produit de transpositions. En effet, toute action mono-orbitale concernant $p$ éléments peut s'écrire comme le produit de $p-1$ transpositions.
- On cherche un morphisme multiplicatif $s$ de $\mathfrak{S}_{n}$ sur le groupe à deux éléments représenté par $\left\{ +1,-1\right\} $. Cette application est nécessairement constante sur les classes de conjugaison, tandis que choisir $\sigma\left(1,2\right)=+1$ conduirait à l'application constante. Et donc la signature $s$ d'une écriture transpositoire $t_{1}\circ t_{2}\circ\cdots t_{m}$ est, nécessairement: \[ s\left(\prod_{1}^{m}t_{i}\right)=\left(-1\right)^{m} \] .
- La signature d'un cycle de longueur $p$ est donc nécessairement $\left(-1\right)^{p-1}$ et donc la signature d'une décomposition orbitale agissant sur $n$ objets et comprenant $k$ orbites est, nécessairement: \[ S\left(\prod_{1}^{k}c_{j}\right)=\left(-1\right)^{n-k} \]
- Maintenant, nous recollons les morceaux en montrant que, définissant $s$ et $S$ comme ci-dessus, on a $S\left(\prod_{1}^{k}c_{j}\right)\times s\left(\prod_{1}^{m}t_{i}\right)=+1$ pour toute substitution $\sigma$ et toute écriture transpositoire de $\sigma$. Il est clair que le produit (dans cet ordre) des $\left[c_{1},c_{2},\cdots,c_{k},t_{m},t_{m-1},\cdots,t_{1}\right]$ est l'identité. Faisons diminuer de 1 la longueur de liste des transpositions en faisant agir $t_{m}$ sur la décomposition orbitale. Si cette transposition a les deux pieds dans la même orbite, elle agit comme une restrictase et coupe cette orbite en deux. Si cette transposition a un pied dans chacune de deux orbites différentes, elle agit comme une polymérase et réunit les deux orbites en une seule. Et ce processus commute avec tous les cycles dont les orbites sont disjointes de la transposition agissante.
- En itérant ce processus, le nombre de $t$ diminue de $1$ à chaque fois, tandis que la parité du nombre de $c$ change à chaque fois. Par conséquent, $S\left(\prod c\right)\times s\left(\prod t\right)$ est invariant. A la fin, il n'y a plus de transpositions et il reste la décomposition orbitale de l'identité: l'invariant de boucle valait donc $+1$.
- On a donc montré que la valeur de $s$ est la même pour toute écriture transpositoire d'une substitution donnée (autrement dit, $s$ est bien définie pour une substitution donnée). La formule $s$ rend évident le fait qu'il y a morphisme, tandis que la formule $S$ fournit l'algorithme de calcul le plus efficace.
- Au passage on a enseigné le processus suivant: (1) on identifie les besoins (2) on identifie les axiomes nécessaires (3) on montre qu'ils ne sont pas contradictoires et on y va. Mathématiques générales, isn't it ?
$\,$
$\,$
$\,$
$\,$
$\,$
$\,$
$\,$
Cordialement, Pierre.
Edit: Evidemment, une fois que l'on a un morphisme multiplicatif de l'ensemble des matrices $n\times n$ vers le corps de base, il est assez immédiat de voir que cela induit un morphisme multiplicatif du groupe des matrices de substitution dans... suspense insoutenable... un groupe de petite taille, oh combien: et l'on retrouve la signature!
Comme je ne l'ai pas, dit, je le dis:
1) Pour ce qui est du fait que toute permutation est obtensible par un produit de transpositions, c'est la chose la plu spopulaire du monde, puisque tout le monde "sait" qu'on peut trier une liste par échange 2 à 2
2) Pour ce qui est de l'invariance de la parité, en dehors de la preuve "championne du monde" à mon sens due à gb que j'ai redite un peu plus haut, la seule concurrente sérieuse que je lui vois, c'est une preuve souvent évoquée par GBZM sur le forum dans le passé qu'il qualifie, sauf erreur, du jeu du saute-mouton et qui est, hélas, soumise à ordonner préalablement "physiquement" le petit monde concerné, mais que je redonne:
2.1) pour permuter deux lettres dans un mot, il suffit de faire une succession de transpositions (je les appelle vertes) particulières à savoir permuter deux voisins
2.2) il est "trivial" que :
2.2.1) une transposition quelconque se décompose en au moins un produit impair de transpositions vertes (et en fait tous les produits possibles qui la donnent sont impairs)
2.2.2) qu'un produit de transpositions vertes avec un nombre impair de facteur ne peut pas donner l'identité (ie partir d'un mot et revenir au mot de départ)
(Tout ceci étant bien sûr dit en admettant que le mot ne contient pas plusieurs occurrences d'une même lettre)
@pldx : toi aussi, tu préfères rester avec tes a priori plutôt que de comprendre ce que d'autres racontent. Si tu avais réfléchi deux secondes à la démarche que j'ai décrite, tu aurais vu que ce n'est pas en utilisant que le déterminant est un morphisme multiplicatif qu'on prouve que la signature est un morphisme de groupes dans $\{\pm1\}$ (je l'ai même écrit explicitement).
Pour tout dire, le fait que le déterminant est un morphisme multiplicatif vient après : le travail sur les permutations et leur signature permet d'établir la formule du déterminant avec les signatures. Plus exactement, on établit cette formule pour n'importe quelle forme multilinéaire alternée sur les colonnes, avec en facteur le déterminant de la matrice identité. Ceci donne l'"unicité" du déterminant. Cette unicité appliquée à la forme multilinéaire alternée $M\mapsto \det(AM)$ donne $\det(AM)=\det(A)\det(M)$.
c'est plutôt toi qui me sors la décomposition de la permutation en transposées transpositions par récurrence. J'ai dit dès le départ que l'existence du déterminant est donnée par récurrence. Je voyais bien que la signature prend les valeurs 1 ou -1, que je prenne la base canonique, ou une base quelconque comme moi. Mon problème était juste après.
Pour moi la parité d'une permutation découlait de ce théorème et de cette propriété de la signature de la composée (que je devais donc établir au préalable). Mais tu viens de me montrer que non, c'est établi en passant, à partir du moment que le determinant est alterné. J'avais mal compris ce passage dans cette démo.
En ce qui concerne la récurrence, si j'ai retenu quelque chose, c'est que je l'ai vue quelque part., J'ai même retrouvé le livre ou l'auteur marque l'initialisation. Donc oui, je dois prendre des précautions avant de refuter une chose pareille.
PS: En ce moment je dois faire la proba, car je n'ai toujours pas saisis le contresens important que j'ai fait à l'oral du CAPES.
S'il n'y avait que ça à reprocher à son post (que je viens de lire intégralement pour essayer de vraiment voir)... :-D
Sur le contenu de fond ce qu'il dit est probablement tout à fait valable voire esthétique sur cette question de groupe agissant dans le cas particulier des groupes de permutation, mais je ne comprends pas comment il peut introduire son propos en disant que ça s'adresse aux néophites en réparation des tortures que leur auraient fait subir les intervenants précédents. C'est totalement hallucinant. Pour moi, son post n'est accessible qu'aux gens déjà au courant de tout ça dans le moindre détail (donc qui liront comme on corrige une copie pour lui mettre une note en comprenant que pldx veut une bonne note), aux gens extrêmement brillants en lettres (car l'usage de mots soutenu est intensif) qui de plus ont une familiarité avec le monde des programeurs geek (des argots de ce milieu sont emplooyés) ou des étudiants qui passeront pas moins de 5H à essayer de cécrypter le texte. En outre, mais j'ai la flemme de vérifier en détails, je ne le trouve pas mathématiquement probant, l'aspect analyse-synthèse qui voudrait se fonder sur les cycles est particulièrement embouteillé dans le style littéraire volontairement affiché.
Evidemment, je tiens à rappeler que j'a-do-re les trolls de pldx et son harcèlement, je ne suis pas en train de "me venger" de toutes interventions HS dans mes fils autres. J'écris ce post pour réellement te donner (pldx) un témoignage de mon ressenti de lecture car j'ai apprécié que tu te donnes du mal pour taper tout ça (avec des <<bullet>> encadrés par des dollars, etc)
Ca n'enlève pas évidemment que la décomposition d'une permutation en produit commutatif de cycles est un phénomène intéressant!!! (Dont je crois que les programmes d'algèbre linéaire du post-bac étendent largement aux matrices et que la "diagonalisation ou trigonalisation" des matrices émergeraient des mêmes phénomènes sous-jacents (??) )
Permuter deux voisins change la parité du NOMBRE SUIVANT: le nombre de paire {u;v} "mal rangées" île u est avant v dans le mot alors qu'il était après dans l'ordre initial. Attention ce n'est trivial que pour les transpositions vertes (voir mon post).
Et maintenant, une question simple: comment calculer rapidement la signature de la permutation: $$ \left( \begin {array}{cccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12
\\ 12&8&11&5&4&3&1&2&7&9&10&6\end {array} \right)
$$
Cela semble quand même être le minimum de ce qu'un étudiant devrait avoir retenu à ce sujet, non ?
Un cycle de longueur 2 est une transposition.
Un cycle de longueur n est composé de n-1 transpositions.
Donc ta permutation a une signature -1
Je pense que ce que tu présentes est trop habillée de dentelles... Démontrer que la permutation est décomposable en produit de transpositions, en passant d'abord par une décomposition en cycles, est certes utile, pour justifier la méthode pratique de calcul d'une décomposition.
En même temps, le faire sur quelques exemples suffit, et je n'ai pas besoin de savoir des choses sur "l'unicité" à l'ordre près.
CC te donne l'argument dénudé. On court-circuite en donnant directement que la permutation est décomposable. Tout ce qui reste est de prouver que l'identité est paire mais pas impaire. Ce que CC te dit dans son 2.2.2. Et c'est terminé, la signature est bien définie. La méthode sur les cas pratique va aboutir.
$$\begin{array}{cccccccccccc}
1&2&3&4&5&6&7&8&9&10&11&12\\
12&8&11&5&4&3&1&2&7&9&3&1&\\
&&&&&&&&&&6&7\\
&&&&&&&&&&10&9\\
&&&&&&&&&&&10\\
&&&&&&&&&&&6
\end{array}$$
Dix-huit nombres ajoutés à la première ligne, Neuf transpositions, permutation impaire.
PS. On peut se demander : y a-t-il une différence de complexité (quand $n\to \infty$) entre cette méthode de calcul de la signature et la décomposition en cycles disjoints ?
Vues la complexité scripturale de tes posts, je crains que seuls certains professionnels typiques ne te suivent sur le forum, mais je trouve quand-même un peu contrariant les messages mathématiques (la philosophie derrière) que tu envoies, d'autant que je ne suis pas sûr que c'est ce que tu voudrais envoyer. Bon, le présent fil n'est pas le pire, tu t'époumones pas mal pluss dans certains autres et plus "gravement" si j'ose dire, mais il se trouve que j'ai cliqué sur celui-là. Donc je me force à quelques remarques, sans grand plaisir car ça demande de taper sur le clavier:
1) Calculer quelque chose avec une méthode toute faite ne donne pas "l'unicité de ce quelque chose"
2) Certains intervenants ne vont pas forcément se taper toutes les artilleries tout de même souvent très fournies (redondantes ou pas, je n'ai pas forcément évalué, je ne sais pas) que tu balances lorsqu'ils veulent répondre à une question bien précise. Par exemple, ici, s'infuser un cours de fac complet sur les permutations pour juste recevoir l'information de pourquoi il est sûr que la parité du nombre de transpositions est un invariant..
3) Je répondrai plus en détails dans l'autre fil, mais il faut que j'y pense, donc je te le signale en passant: tu as à de nombreuses reprises tenté d'évoquer des ordres préférables ou des exigences de non boucles. Cet impératif est très dangereux quand il est pris au pied de la lettre. Les maths ne produisent que des implications "locales" ou des équivalences telles quelles et le nombre de définitions qui sont bouclantes sont ultramajoritaires. Tu n'es pas le seul à "croire" ou "vouloir faire croire" qu'il n'y a pas de boucles.
Bref, attention à une tendance peut-être pas consciente au despotisme qui émane parfois des propos mathématiques (au sens large) que tu tiens.
Ta passion pour l'informatique fait que le calcul de la signature d'une permutation est un truc passionnant (et que les cycles sont la méthode la plus connue comme rapide), mais c'est quand-même une question relativement différente de son existence à travers la définition IMPOSEE de la parité du nombre de transpositions pour l'obtenir. On ne demande pas si on peut "trouver un autre*** morphisme qui marche de $S_n$ dans $F_2$, mais si celui obtenu en prétendant l'invariance du nombre de transpo existe", et comme il est tautologique ( :-D j'ai esquivé le mot "évident") que l'invariance suffit seule à garantir le caractère morphique, on est vraiment sur cette découverte centrale qu'on ne peut obtenir l'identité avec un nombre impair, il n'y a rien de plus à prouver. Il est d'ailleurs heureux qu'il n'y ait rien à faire de plus qu'à prouver cette unicité et c'est ce qui fait toute l'élégance de ne parler que de transpositions et non de cycles (qui ont leur utilité).
** seuls les avions en l'air risquent de s'écraser
*** "défini autrement"
Celastus demande pourquoi signature(ab) = signature(a) + signature(b).
La question mal posée en ce sens que la réponse est que c'est évident une fois admis que la signature existe. L'ensemble des couples $(s,i)\in S_n\times F_2$ tels qu'il existe un produit de k transpositions qui vaut $s$ et tel que $k==i$ dans $F_2$ ne pose pas de problème et s'appelle "signature" et il est célèbre parce que:
Théorème: c'est une fonction!
[small](c'est ça qui a été redocumenté principalement dans le fil, ce post de rappel récapitulatif me paraissait utile, vus les échanges experts entre personne discutant de méthodes diverses pour "calculer" et non établir l'existence du truc)[/small]
Dès lors, il n'y a rien à faire de plus, c'est forcément un morphisme. Je laisse Celastus rédiger*** s'il a envie. Donc il faut faire attention aux messages qu'on envoie, parce qu'in fine, l'étudiant de passage dans 6-10 mois 5ans, etc pourra croire que les gens se sont pliés en 4 pour écrire 40 lignes établissant que c'est .. un morphisme
*** en blanc: si une liste de longueur k donne s et une liste de longueur k' donne s' alors la concaténation des deux listes est une liste qui donne ss' (et sa longueur est k+k' modulo $F_2$).
Donc c'est une complexité $O(n^2)$
l'algorithme avec les cycle, je ne sais pas l'écrire. T'as l'impression qu'il est plus rapide car tu parcours les n éléments de la liste, mais en fait, il faut taguer les éléments entre 1 et n, qui sont déjà comptabilisé dans un précédent cycle ou le cycle en cours. Ceci a une complexité d'ordre nombre d'éléments resistant. Du coup je m'attends à une complexité en $n+ (n-1) + .... + 1 = O(n^2)$ aussi.
On en déduit que pour tous $a,b,c,d\in \{1,...,n\}$ tels que $a\neq b$ et $c\neq d$, les transpositions $\tau_{a,b}$ et $\tau_{c,d}$sont conjuguées ($\tau_{c,d}=\sigma \circ \tau_{a,b} \circ \sigma^{-1}$ pour toute permutation $\sigma$ telle que $\sigma(a)=c$ et $\sigma (b)=d$ et une telle permutation existe trivialement dès que $n\geq 2$).
Comme $\mathfrak S_n$ est engendré par les transpositions lorsque $n\geq 2$, on voit donc que pour tout groupe abélien $G$, un morphisme quelconque de groupes de $\mathfrak S_n$ dans $G$ ne dépend que de sa restriction à $\{\tau_{1,2} \}$...
La difficulté est de montrer pourquoi un tel morphisme existe, ce qui est l'objet du théorème d'existence de la signature.
Pour l'humain (pas pour l'ordi) les.cycles c'est largement le plus confortable. Pour que ça le soit pour l'ordi faut lui donner la permutation sous un format qui consisterait à avoir déjà fait le travail avant ce qui est tricher car je ne pense pas qu'on s'intéresse beaucoup aux permutations comme étant des fonctions (qui est le format le plus confortable pour les cycles)
C'est un sujet que tu as dû croiser non durant ta longue vie de savant? Je me demande si phi(1) n'est pas un pseudo idéal de IN. Y a-til forcément un entier non nul n tel que Z/nZ soit dans une aussi bonne relation que ne l'est (Sp, transpositions, Z/2Z), cet entier fut-il 1 auquel cas on est face à Z/1Z ce qui n'est pas grave?
La complexité de la décomposition en cycles disjoints est aussi visiblement en $O(n)$.
> Entrée $\sigma$ liste de longueur n
> sortie $\rho$ de longueur n, et compteur c
initialiser $\rho(k)=k$. pour k de 1 à n.
initialiser c à 0
pour k= 1 à n
___ si $\rho(k)!=\sigma(k)$
_________ trouver la position $k'$ tel que $\rho(k')=\sigma(k)$
_________ $ \rho(k')\leftarrow\rho(k)$ et $\rho(k)\leftarrow\sigma(k)$
_________ $c \leftarrow c+1$
___ finsi
cas donné $\sigma=(12,8,11,5,4,3,1,2,7,9,10,6)$
initialisation
$\rho_0=(1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12)$
$\rho_1=(12, 2, 3, 4, 5, 6, 7, 8, 9,10,11,1)$
$\rho_2=(12, 8, 3, 4, 5, 6, 7, 2, 9,10,11,1)$
$\rho_3=(12, 8, 11, 4, 5, 6, 7, 2, 9,10,3,1)$
$\rho_4=(12, 8, 11, 5, 4, 6, 7, 2, 9,10,3,1)$
$\rho_5=$ inchangée, car ici ca coincide.
$\rho_6=(12, 8, 11, 5, 4, $3$, 7, 2, 9,10,$6$ ,1)$ le 6 est en position $k'$ et pas $\sigma(k)$.
$\rho_7=(12, 8, 11, 5, 4, 3, 1, 2, 9,10,6,7)$ inchangée.
$\rho_8=(12, 8, 11, 5, 4, 3, 1, 2, 7,10,6,9)$
$\rho_9=(12, 8, 11, 5, 4, 3, 1, 2, 7,9,6,10)$
$\rho_{10}=(12, 8, 11, 5, 4, 3, 1, 2, 7,9,10,6)$
mon algo, malheureusement me demande de faire une recherche de $k'$.
Je ne vois pas la formule simple pour avoir $k'$ directement depuis ma récurrence.
Si je vais chercher $k'$ à chaque itération, autant faire un argument récursif en modifiant l'algorithme de tri. Et je travaille sur des listes de plus en plus courtes, au lieu de parcourir toute la liste $\rho$.
Peut-être je n’embrouille pour le $k'$. Je ne sais pas. Je vais essayer l'autre
> Sortie: les cycles de $\sigma$ sous formes de listes $\rho_i$.
initialiser une liste "TAG" de taille n, formé de 1.
initialiser i=1
initialiser n listes $\rho_j$ toutes vides.
TANT QUE la liste "TAG" n'est pas entièrement que des 0.
______ choisir un k tel que TAG(k)=1.
______ TANT QUE $TAG(k) =1$
_____________ ajoute k à la liste $\rho_i$
_____________ $TAG(k)=0$, % on tague le terme déjà pris dans un cycle.
_____________ $k\leftarrow \sigma(k)$ % on prend le suivant
______ $i\leftarrow i+1$ % la cycle est complet, on commence à remplir le suivant.
mon problème ici, une fois que j'ai un cycle, je dois rechercher un élément de ma liste TAG qui n'est pas nul.
Moi je sais pas programmer efficacement. Je ne comprend pas très bien comment on calcule une complexité.
Au premier coup d'oil, ce que j'ai ne ressemble pas à un O(n).
J'hésite à te le dire, ça nécessite une petite inspiration (mais vraiment petite).
En accès direct tu vas avoir par exemple : 1;6;11;3;2;4;9;5;1. Or ton souci est d'obtenir "le 7" (ou un autre!!!) pas encore géré sans consommer de temps de calcul.
Je te mets en blanc la solution, comme ça c'est toi qui choisis:
Lorsque tu apprends que l'image de 1 est 6, tu mets le 6 en case 2 et ce qu'il y avait en case 2, tu le mets en case 6. (2 impulse consommés disons). Puis quand tu apprends que l'image de 6 est 11, tu mets le 11 en case 3 et vire ce qu'il y a dans la case 3 en case 11. Etc... Attention, tu dois avoir conservé en mémoire un tableau en lecture seule qui décrit ta permutation.
$$\begin{align}
\rho_k&=\tau_{\sigma(k)\leftrightarrow\rho_{k-1}(k)}\,\rho_{k-1}=\rho_{k-1}\,\tau_{\rho_{k-1}^{-1}(\sigma(k))\leftrightarrow k}\\
\rho_k^{-1}&=\rho_{k-1}^{-1}\,\tau_{\sigma(k)\leftrightarrow\rho_{k-1}(k)}\;.
\end{align}$$
PS. Composer à droite par $\tau_{a\leftrightarrow b}$, c'est juste échanger les contenus des cases $a$ et $b$ du tableau.
$$\begin{align}
\rho_k&=\tau_{\sigma(k)\leftrightarrow\rho_{k-1}(k )}\,\rho_{k-1}=\rho_{k-1}\,\tau_{\rho_{k-1}^{-1}(\sigma(k))\leftrightarrow k}\\
\rho_k^{-1}&=\rho_{k-1}^{-1}\,\tau_{\sigma(k)\leftrightarrow\rho_{k-1}(k)}
\end{align}$$
Excellent. En résumé, si l'on s'arrange pour faire le cours sur $\mathfrak S _n$ à un autre moment, on n'est plus obligé de prendre le cours sur les déterminants comme prétexte !
Par ailleurs, la liste de transpositions que tu obtiens est de longueur minimale (c'est à dire $n$ moins le nombre d'orbites), ce qui revient à factoriser chaque cycle.
Cordialement, Pierre.
Pour ce qui est d'obtenir la liste des orbites, as-tu mieux que $n \ln n$ en moyenne ?
Cordialement, Pierre.
Je ne comprends pas ta dernière question. S'il s'agit de calculer la décomposition en cycles disjoints, j'ai déjà dit que la complexité est en $O(n)$ (avec des tableaux, sans prendre en compte la taille des entiers à écrire).
1) à part GBZM et moi je soupconne que personne n'a lu ton exposé long sur les cycles: les uns parce que c'est long justement, les autres parce que c'edt trop simple et bien connu. Dire que c'est ça qui a poussé GBZM à préciser des points qui sont essentiellement des réponses à zen dans leur aparté me parait en minimum irréaliste.
2) O(n) suffit trivialement pour lister les cycles (ce que tu appelles orbites) comme je l'ai signalé à zen hier soir
3) il y a de la cabalistique dans les posts de GBZM je ne les ai pas lus précisément donc je ne sais de quel algo il parle mais si tu prétends que l'algorithme suivant très simple et evident a été écrit sous ta pression par un GBZM tremblant de peur devant ton regard instituteur tu es un grand comique :-D (et dire les cycles sont derrière c'est aussi du routage de gueule).
AlGO: demander image de 1. On obtient 8. Mettre 1 en case 1 et 8 en case 8. Calculer signature de la permut représentée par les cases allant de 2 à fin et multiplier résultat par -1 (complétion évidente si obtention de 1 comme image de 1)
Cette procédure récursive en O(n) est LA PROCEDURE NAIVE issue de la connaissance que signature existe.
Je souhaite remercier tous les intervenants pour leurs échanges que j'ai trouvé très instructifs, et qui illustrent bien les multiples approches pédagogiques, toutes très intéressantes, qu'on peut mettre en œuvre dans un cours sur le groupe symétrique, ou sur le groupe symétrique et les déterminants.
Je tiens également à préciser que j'ai lu intégralement et avec énormément de plaisir le plan de cours que pldx s'est donné la peine de détailler. C'est, de tous ceux qui ont été évoqués ci-dessus, celui qui me convainc le plus personnellement. Il n'y a pas de vérité universelle en pédagogie : un cours passera d'autant mieux qu'il est adapté à son public et au professeur qui l'enseigne, je comprends donc très bien qu'on puisse en préférer un autre, d'autant que, je le répète, tous ceux qui sont présentés ou évoqués ici sont très intéressants.
Je n'avais pas l'intention de poster mais je prends conscience que si on ne remercie pas les intervenants lorsqu'ils prennent le temps de poster, ils ne réalisent pas nécessairement que leurs posts sont lus et appréciés. Merci encore, donc, à vous tous, et tout particulièrement à pldx.
Bonjour,
Si tu as une version électronique de ton cours que tu enseignais sur les déterminants et signatures, ça m’intéresse de le lire intégralement
Merci