Matrices de permutations
$\newcommand{\S}{\mathfrak{S}}$Bonjour
Je ne suis pas sûr de mon résultat pour la question $1$.
Question $1$. Soit $\sigma \in \S_n$.
Par définition $\det(P_{\sigma})= \displaystyle\sum_{\sigma \in \S_n} \varepsilon(\sigma) \delta_{\sigma(1) \sigma(1)} \times \delta_{\sigma(2) \sigma(2)} \times \cdots\times \delta_{\sigma(n) \sigma(n)}$
D'où $\boxed{\det(P_{\sigma})= \displaystyle\sum_{\sigma \in \S_n} \varepsilon(\sigma)}$
Je ne suis pas sûr de mon résultat pour la question $1$.
Question $1$. Soit $\sigma \in \S_n$.
Par définition $\det(P_{\sigma})= \displaystyle\sum_{\sigma \in \S_n} \varepsilon(\sigma) \delta_{\sigma(1) \sigma(1)} \times \delta_{\sigma(2) \sigma(2)} \times \cdots\times \delta_{\sigma(n) \sigma(n)}$
D'où $\boxed{\det(P_{\sigma})= \displaystyle\sum_{\sigma \in \S_n} \varepsilon(\sigma)}$
Réponses
-
Il y a un problème de variables... Il vaudrait mieux utiliser une autre lettre que $\sigma$ dans ta somme
-
Rebonjour
Encore une fois ta ligne 2 n'a pas de sens. Vas tu dire de nouveau que c'est une erreur de frappe?
D'autre part soit un peu moins paresseux. Mille fois on t'a dit de travailler avec des exemples,
mille fois tu n'écoutes pas les conseils car tu préfères écrire vite fait n'importe quoi.
Prend n=2 et fait le travail : regardes l'absurdité de ton résultat. -
Merci j'ai compris l'erreur. Une histoire de variable muette.
-
Soit $\sigma \in \S_n$.
Par définition $\det(P_{\sigma})= \displaystyle\sum_{\sigma' \in \S_n} \varepsilon(\sigma') \delta_{\sigma'(1) \sigma(1)} \times \delta_{\sigma'(2) \sigma(2)} \times \cdots\times \delta_{\sigma '(n) \sigma(n)}$
Si $\sigma' \ne \sigma$ alors le déterminant est nul par injectivité d'une permutation, il reste une seule possibilité $\sigma = \sigma'$
Donc $$\det(P_{\sigma})= \displaystyle\sum_{\sigma' \in \S_n \\ \sigma'=\sigma} \varepsilon(\sigma') \delta_{\sigma'(1) \sigma(1)} \times \delta_{\sigma'(2) \sigma(2)} \times \cdots\times \delta_{\sigma '(n) \sigma(n)}.
$$ D'où $\boxed{\det(P_{\sigma})= \varepsilon(\sigma)}$ -
Os a écrit:Si $\sigma' \ne \sigma$ alors le déterminant est nul par injectivité d'une permutation, il reste une seule possibilité $\sigma = \sigma'$
Même si à la fin c'est bon, est-ce que tu as conscience que ci-dessus c'est n'importe quoi ?
C'est-à-dire que tu n'es pas capable de dire ce qui est nul correctement et pourquoi c'est nul. -
Oui ma justification c'est du n'importe quoi.
Le produit est non nul si et seulement pour tout $i$ dans $[1,n]$ on a $\sigma(i) =\sigma'(i)$
C'est-à-dire si et seulement si $\sigma =\sigma'$. -
Voilà. Autant dire les choses correctement dès le départ.
-
Question $2a$ :
Soient $(u,v) \in [|1,n|]^2$.
J'ai calculé : $[P_{\sigma} P_{\sigma'} ]_{u \ v}= \displaystyle\sum_{k=1}^n \delta_{u \ \sigma(k)} \delta_{k \ \sigma'(v)} = \boxed{ \delta_{u \ \sigma \circ \sigma'(v)}}$
Et $[P_{\sigma \circ \sigma'}]_{uv} =\boxed{ \delta_{u \ \sigma \circ \sigma'(v)}}$
Question $2b$ :
D'après la question $1$, le déterminant d'une matrice de permutation vaut $1$ ou $-1$ donc elle est inversible.
Montrons que $G$ est un sous-groupe de $GL_n(\R)$.- $I_n$ est dans $G$
- Soient $P_{\sigma}$ et $P_{\sigma'}$ des éléments de $G$. Alors leur produit est dans $G$ d'après la question précédente.
- L'inverse de $P_{\sigma}$ est $P_{\sigma^{-1}}$ et est dans $G$.
Montrons que $G$ est isomorphe à $\S_n$. Introduisons le morphisme de groupe surjectif $\begin{array}[t]{cccl}
\phi :& \S_n &\rightarrow &G \\
& \sigma &\mapsto& P_{\sigma}
\end{array}$
$\ker(\phi)= \{ \sigma \in \S_n \mid P_{\sigma}=I_n \} = \{ I_d \}$
Donc $\phi$ est un isomorphisme de groupe surjectif.
Question $3$ :
On trouve après calcul $\boxed{[A P_{\sigma}]_{u v} = a_{u \ \sigma(v)}}$. Cela revient à permuter les colonnes de $A$ suivant la permutation $\sigma$.
Question $4$ :
Soit $\sigma \in \S_n$. Alors il existe des cycles $c_1, \cdots, c_r$ à supports disjoints tels que $\sigma= \displaystyle\prod_{k=1}^r c_k$
Après je bloque pour déterminer les valeurs propres. -
Ca devient vraiment excessif l'acharnement sur O'shine, limite de la méchanceté gratuite.
J'ai l'impression que OS est devenu le punching bag de tout le monde, ça doit faire du bien de se défouler sur quelqu'un après une journée stressante... (ou après s'être fait engueulé par sa femme)
Personne n'est obligé de l'aider si il est agacé par ce qu'il écrit. -
Bonjour @Os.
Pour moi tes réponses sont bonnes et la rédaction aussi mais il y a peut-être une erreur que je ne vois pas, juste une remarque: c'est quoi un isomorphisme de groupe surjectif ?
Pour la question 4), avec cette indication j'ai bien envie de connaître les valeurs propres d'un $\mathcal{l}$-cycle, pas toi ? -
Un isomorphismes de groupes est un morphisme de groupe bijectif. Le "surjectif" est en trop ici.
Oui on a $P_{\sigma}= P_{c_1} \times P_{c_2} \times \cdots \times P_{c_r}$
Le souci est que je dois calculer $\det(XI_n -P_{c_1})$ et je ne sais pas faire. -
Tu as montré récemment que les valeurs propres sont nécessairement racines de tout polynôme annulateur, dans le cas de la matrice d'un l-cycle, ne peux tu pas trouver un tel polynôme ?
Désolé après m'être penché plus sérieusement sur la question, cet indication ne me semble plus pertinente. -
Hello Oshine! Peux tu reorganiser les vecteurs de base en pensant à la décomposition en cycle tel que P soit semblable à une matrice par blocs?
Par exemple pour
sigma =
(1 2 3 4 5 6)
(5 2 1 6 3 4)
Ensuite pour chaque bloc de cette nouvelle matrice quelles sont les valeurs propres?
Indication : pas besoin de calculer le polynome caractéristique, c'est possible mais tu vas galérer à moins que tu sois à l'aise en calcul de déterminant. Pense plutôt à qu'est ce qu'un cycle.
Fais tout ça sur l'exemple plus haut et ça sera généralisable facilement -
Bonjour
Pour avancer avec un exemple relativement simple
Supposons que $n=4 $ et que $\sigma$ soit un cycle, c'est à dire que
$$P_\sigma = \begin{pmatrix}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{pmatrix}
$$ alors
$$\det( P_\sigma- x I_4) = \begin{vmatrix}
-x & 0 & 0 & 1 \\
1 & -x & 0 & 0 \\
0 & 1 & -x & 0 \\
0 & 0 & 1 & -x
\end{vmatrix}=....$$ doit se calculer assez facilement je pense... -
@Bastien
Pas grave. Il me semble que cette question est difficile sans aide.
@Noobey
Merci. Un exemple concret permet de bien comprendre B-) J'avais lu cette méthode théorique dans un sujet de Centrale mais je n'avais rien compris.
Je suis à l'aise en calcul de polynôme caractéristique normalement. Quand je fais les exos du livre j'ai toujours bon au polynôme caractéristique, après ils sont rarement compliqués c'est maxi des matrices d'ordre 3. Un déterminant 6x6 c'est fastidieux.
On a $\boxed{\sigma= (1 \ 5 \ 3) \circ (4 \ 6)}$ qui est une décomposition en cycles à supports disjoints.
Notons $c_1 = (1 \ 5 \ 3)$ et $c_2= (4 \ 6)$. $2$ est un point fixe de $\sigma$.
On a $P_{\sigma}=\begin{pmatrix}
0 & 0 & 1 & 0& 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0& 1 & 0\\
0 & 0 & 0 & 0& 0 & 1 \\
1 & 0 & 0 &0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{pmatrix}$
Notons $\mathcal B =(e_1,e_2,e_3,e_4,e_5,e_6)$ la base canonique de $\R^6$.
Notons $\mathcal B_0 =(e_2)$ , $\mathcal B_1=(e_1,e_5,e_3)$ et $\mathcal B_2=(e_1,e_6)$
Posons $\mathcal B'=(B_0,B_1,B_2)$. Par changement de base, on a :
$\boxed{P^{-1} P_{\sigma} P = \begin{pmatrix}
1 & O_{1,3} & O_{1,2} \\
O_{3,1} & A & O_{3,2} \\
O_{2,1} & O_{2,3} & B \\
\end{pmatrix}}$
C'est une matrice diagonale par blocs avec $A=\begin{pmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{pmatrix}$
Et $B=\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}$
Deux matrices semblables ayant le même polynôme caractéristique on a : $\chi_{P_{\sigma}} (X)= (X-1) \chi_A(X) \chi_B(X)$
Ce qui fournit $\boxed{\chi_{P_{\sigma}} (X)= (X-1) (X^3-1) (X^2-1)}$
On conjecture la formule $\boxed{\chi_{P_{\sigma}} (X)= \displaystyle\prod_{k=1}^{3} \left( X^{l(c_k)}-1 \right)=\displaystyle\prod_{k=1}^{3} (X^k -1)^{c_k}}$ où les $l(c_k)$ désignent les longueurs des cycles.
Ainsi $\boxed{sp(P_{\sigma})= \{-1,1\}}$
Pour tout $k \in [|1,n|]$, les racines de $X^k-1$ sont les $\{\exp(\dfrac{2 i q \pi}{k}) \ | \ 0 \leq q \leq k-1 \}$ -
@Bd2017, je viens de voir ton exemple, je suis parti sur celui de Noobey en utilisant le changement de base.
C'est pour ça que je me dis que la question est très difficile sans aucune aide.
En fait, j'avais lu un passage dans le sujet de Centrale MP 2020, ils utilisent cette méthode, mais c'est détaillé en plusieurs questions. Et avant ils définissent les permutations conjuguées. Si $\sigma$ et $\tau$ sont conjuguées alors $P_{\sigma}$ et $P_{\tau}$ sont semblables. -
Mais, si je peux me permettre OShine, tu n’avais pas déjà posé cette question dans un ancien long fil sur les matrices de permutation?
-
J'avais posé la question 25 oui. Je n'avais pas compris.
Mais ici l'exercice était différent.
Maintenant j'ai bien compris Q24 et Q24 avec l'exemple de Noobey. -
Tu n'as pas bon pour le spectre de Psigma que je t'avais donné mais t'y es presque quand même
Comment calculer sinon le polynôme caractéristique de la matrice associé à un cycle style (12...n) ? C'est un petit peu pénible à faire mais je te conseille de faire le calcul -
Remarque. J'aurais voulu faire un lien sur une partie de ton message mais je ne sais pas le faire !
[Pour obtenir l'adresse d'un message, mets la souris sur la recopie du titre du fil, sous le nom de l'auteur du message, Clic droit > Copier l'adresse du lien, que tu colles où tu veux. AD]
Sinon @Os, dans l'exemple de @Noobey que tu as traité le polynôme caractéristique est bon. Mais par contre ensuite " on conjecture ..." je n'y comprends rien.
D'autant plus que le spectre est faux.
Tu dois abandonner pour l'instant la référence que tu cites. Il faut construire la solution par toi même:
C'est-à-dire finir de traiter correctement l'exemple de @Noobey.
Puis traiter celui que j'ai donné pour n=4 et puis pour n=5.
Ensuite cela sera suffisant pour écrire la bonne conjecture.
Une fois la conjecture écrite il faut la démontrer dans le cas général mais c'est un simple jeu d'écriture car les exemples donnés ci-dessus sont suffisamment parlant pour généraliser.
P.S pas vu la réponse de @Noobey -
Rebonjour
Je reviens sur mon conseil de laisser tomber le sujet sur lequel tu t'es basé pour ta conjecture. Une autre bonne raison de tenir compte de mon conseil c'est que la question Q25 est fausse car le polynôme caractéristique donné est degré supérieur à n. -
@Bd2017
Je suis d'accord pour l'erreur d'énoncé mais fait étrange le rapport du jury n'en parle pas...
Pour la permutation $\sigma=(1 \ 2 \ 3 \ 4) \in S_4$, je trouve $\chi(X)=X^4-1$
Si on pose $\sigma =c_1 \circ c_2 \circ \cdots \circ c_r$ et qu'on note $l_i$ la longueur du cycle $c_i$ on a :
Je conjecture la formule $\boxed{\chi(X)=(X-1)^{nombre de points fixes} (X^{l_1}-1) \times (X^{l_2}-1) \times \cdots \times (X^{l_r}-1)}$
Je ne comprends pas pourquoi mon spectre est faux. Les racines de $(X-1)(X^2-1)(X^3-1)=0$ sont $-1$ et $1$.
Pour le déterminant du cycle $\gamma=(1 \ 2 \ 3 \ \cdots \ n)$ je développe par rapport à la première ligne et je trouve :
$\chi_l(X)=X \times X^{l-1}+(-1) \times (-1)^{l+1} \times (-1)^{l-1}=\boxed{X^l-1}$ -
Mais non reflechis pour les racines!!!!!
-
J'ai réfléchi je trouve toujours les mêmes racines, je ne comprends pas le problème.
-
Oui c'est ça pour la conjecture.
Maintenant pourquoi tu as faux? Comment résous- tu $ X^3-1=0?$
Et dans le cas général il faudra résoudre $x^n-1=0$ -
$0=x^3-1=(x-1)(x^2+x +1)$....
ou alors cela ne te dit rien racines n-ième de l'unité. -
J'ai résolu dans $\R$ et non dans $\C$.
Les racines de $X^3-1=0$ sont les $\{ \exp(\dfrac{ 2i k \pi}{3}) \ k \in [|0,2|] \}$
Donc $R=\{1,\dfrac{-1}{2}+i \dfrac{\sqrt{3} }{2},\dfrac{-1}{2}-i \dfrac{\sqrt{3}}{2} \}$
D'où $\boxed{Sp(P_{\sigma})= \{-1,1,\dfrac{-1}{2}+i \dfrac{\sqrt{3} }{2},\dfrac{-1}{2}-i \dfrac{\sqrt{3}}{2} \}}$
Pourquoi dans le cas général il faut résoudre $X^n-1=0$ ? -
regardes ta conjecture. Le polynôme caractéristique est sous la forme de produit de la forme
$x^l-1.$ Ainsi les valeurs propres sont des racines de l'unité.
D'autre part le spectre doit indiquer la multiplicité des valeurs propres, ce que tu n'as pas fait. Dans l'exemple de @noobey n=6 donc tu dois retrouver 6v.p en tenant compte de la multiplicité. -
Le spectre est un ensemble où la multiplicité ne figure pas. La multiplicité apparaît dans la liste des valeurs propres.
Es-tu sûr que la formule de Q25 est fausse ? Il doit y avoir des cycles de longueur nulle... La somme des longueurs des cycles vaut n- nombres de points fixes.
Les racines de $X^l-1$ sont les $\{ e^{ 2i k \pi / l} \ | \ k \in [|0,l-1|] \}$. Ce sont les racines l-ièmes de l'unité. Les racines du polynôme caractéristique sont simples donc un endomorphisme de permutation est diagonalisable. -
Bon je n'ai pas les notations alors c'est peut être correct.
Mais toi quand tu recopies ton travail c'est d'expliquer les notations. mais de toute façon il
faut un peu de cohérence. C'est pas la peine d'extraire une formule sans le contexte...
Maintenant le spectre d'une matrice c'est l'ensemble des valeurs propres avec leur multiplicité. -
Ce n'est pas la définition du spectre que j'ai. J'ai : ensemble de valeurs propres.
Il y a peut être plusieurs versions de la notion de spectre suivant les ouvrages :-S
Oui tu n'as pas le contexte du sujet en entier donc normal.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 22
+15 Invités