Exercices math sup : groupe symétrique et déterminant

1. On cherche l'image de chaque élément. Les éléments différents de $a,b,c,d$ ne sont pas modifiés. Pour $a,b,c$ et $d$, on a : $$ \begin{array}{ccccccc} a&\mapsto_{(d\ a)}&d&\mapsto_{(c\ d)}&c&\mapsto_{(a\ b)}&c\\ b&\mapsto_{(d\ a)}&b&\mapsto_{(c\ d)}&b&\mapsto_{(a\ b)}&a\\ c&\mapsto_{(d\ a)}&c&\mapsto_{(c\ d)}&d&\mapsto_{(a\ b)}&d\\ d&\mapsto_{(d\ a)}&a&\mapsto_{(c\ d)}&a&\mapsto_{(a\ b)}&b.\\ \end{array}$$ La permutation est donc un cycle de longueur 4, $(a\ c\ d\ b)$.
2. Une permutation étant une bijection, le dernier élément de $\{1,\dots,n\}$ ne peut être envoyé que sur lui-même. Une telle permutation est donc nécessairement l'identité.
3. Non, du moins si $n\geq 4$. En effet, la composée de deux transpositions à support disjoint vérifie elle-même que $s^2=Id$.
4. Pour énumérer tous les éléments de $\mathcal S_4$, on peut partir du fait qu'une permutation se décompose de manière unique en produit de cycles à supports disjoints. On trouve alors que les permutations sont
   • l'identité (correspond à des produits de cycle de longueur 1);
   • les 4 cycles, ce sont : $$(1\ 2\ 3\ 4),\ (1\ 2\ 4\ 3),\ (1\ 3\ 2\ 4),\ (1\ 3\ 4\ 2),\ (1\ 4\ 2\ 3),\ (1\ 4\ 3\ 2);$$
   • les 3 cycles (qui correspondent à un produit d'un cycle de longueur 3 par un cycle de longueur 1); ces 3 cycles sont $$(1\ 2\ 3),\ (1\ 3\ 2),\ (1\ 2\ 4),\ (1\ 4\ 2),\ (1\ 3\ 4),\ (1\ 4\ 3),\ (2\ 3\ 4),\ (2\ 4\ 3).$$
   • les transpositions (qui correspondent à un produit d'un cycle de longueur 2 et de deux cycles de longueur 1), ces transpositions sont : $$(1\ 2),\ (1\ 3),\ (1\ 4),\ (2\ 3),\ (2\ 4),\ (3\ 4)$$
   • les produits de deux transpositions à support disjoint (produit de deux cycles de longueur 2). Ces produits sont : $$(1\ 2)\circ (3\ 4),\ (1\ 3)\circ(2\ 4),\ (1\ 4)\circ(2\ 3).$$
   On a ainsi énuméré les 24 éléments de $\mathcal S_4$.

1. On commence par étudier les images successives de $1$. Ce sont 3,4,6. On étudie ensuite les images successives de 2. On trouve 5 (ensuite on revient à 2). On a épuisé tous les éléments de $1,\dots,6$. La décomposition canonique de $\sigma_1$ en produits de cycles disjoints est $$\sigma_1=(1,3,4,6)\circ(2,5).$$ Pour décomposer $\sigma_1$ en produit de transpositions, il suffit de décomposer chacun des cycles en produits de transposition. Pour le second, c'est facile car il s'agit déjà d'une transposition. Pour le premier, on écrit $$(1,3,4,6)=(1,3)\circ (3,4)\circ (4,6)$$ et donc $$\sigma_1=(1,3)\circ (3,4)\circ (4,6)\circ(2,5).$$ L'ordre du cycle $(1,3,4,6)$ est 4, l'ordre du cycle $(2,5)$ est 2, l'ordre de la permutation est donc le ppcm de 2 et 4, à savoir 4. En particulier, puisque $4|100$, on en déduit que $\sigma_1^{100}=Id$. Enfin, puisqu'on a décomposé $\sigma_1$ en produit de transpositions, il est facile de déterminer sa signature. Elle vaut $$\veps(\sigma_1)=(-1)^4=1.$$
2. Par la même méthode, on trouve $$\sigma_2=(1,4,7,8)\circ(2,6,5)\circ(3,9),$$ $$\sigma_2=(1,4)\circ (4,7)\circ (7,8)\circ (2,6)\circ (6,5)\circ (3,9).$$ L'ordre de $\sigma_2$ est le ppcm de 4,3 et 2, soit 12. La signature de $\sigma_2$ est $(-1)^6=1$. Enfin, puisque $100\equiv 0[2]$, $100\equiv 1[3]$ et $100\equiv 0[4]$, on en déduit que $$\sigma_2^{100}=(2,6,5)^1=(2,6,5).$$

Un $k$-cycle s'écrit $(a_1\ a_2\ \dots\ a_k)$. On doit donc choisir dans $\{1,\dots,n\}$ $k$ élements ordonnés parmi $n$. Mais l'écriture $(a_1\ a_2\ \dots\ a_k)$ n'est pas unique. Il y a en effet $k$ façons d'écrire le même $k$-cycle, suivant le choix que l'on fait pour le premier terme - par exemple, $(a_2\ a_3\dots a_k\ a_1)$ représente le même $k$-cycle que $(a_1\ a_2\ \dots\ a_k)$. On conclut finalement que le nombre de cycles de longueur $k$ est égal à $$\frac{A_n^k}{k}=\frac{n(n-1)\dots (n-k+1)}{k}.$$

Notons $\veps_n$ la signature de $\sigma_n$. Pour $n\geq 3$, on peut décomposer $\sigma_n$ en $\tau_n\circ s_n$ où $\tau_n$ est la transposition $(1\ n)$ et $s_n$ est la permutation $$s_n=\left(\begin{array}{ccccc} 2&3&\dots&n-2&n-1\\ n-1&n-2&\dots&3&2 \end{array}\right).$$ Mais il est clair que la signature de $s_n$ vaut celle de $\sigma_{n-2}$ (il s'agit de la même permutation, mais en renumérotant les éléments). On obtient donc la formule de récurrence $$\veps_n=-\veps_{n-2}.$$ En particulier, $\veps_n=\veps_{n-4}$ pour $n\geq 4$, et il suffit donc de regarder la congruence modulo 4 de $n$ pour trouver la valeur de $\veps_n$. On en déduit que $$\left\{ \begin{array}{rcl} \veps_{4k+1}&=&\veps_1=1\\ \veps_{4k+2}&=&\veps_2=-1\\ \veps_{4k+3}&=&\veps_3=-1\\ \veps_{4k+4}&=&\veps_4=1\\ \end{array}\right. $$ Une autre façon de procéder est de remarquer que $\sigma_n$ est le produit des transpositions suivantes : $(1\ \ n)$, $(2\ \ n-1)$, etc... Il suffit alors de compter le nombre de transpositions pour déterminer la signature.

1. Puisque les transpositions engendrent $S_n$, il suffit de démontrer que toute transposition $(i\quad j)$, avec $i<j$, s'écrit comme produit des transpositions $(1\quad k)$. Mais si $i=1$, c'est déjà fait, et si $1<i$, on a $(i\quad j)=(1\quad i)\circ (1\quad j)\circ (1\quad i)$.
2. On va utiliser la question précédente et démontrer que toute transposition $(1\quad k)$ s'écrit comme produit de transpositions de la forme $(i\quad i+1)$. On procède par récurrence finie sur $k\in\{2,\dots,n\}$, la propriété étant vraie si $k=2$. Supposons la propriété vraie au rang $k$. Pour la prouver au rang $k+1$, il suffit d'écrire que $$(1\quad k+1)=(k\quad k+1)\circ (1\quad k)\circ (k\quad k+1).$$
3. 1. On va prouver par récurrence finie sur $k\in\{0,\dots,n-2\}$ que $c^k \circ t\circ c^{-k}=(k+1\quad k+2)$. La propriété est vraie si $k=0$. Supposons la prouvée au rang $k$. Alors $$c^{k+1} \circ t\circ c^{-(k+1)}=c\circ (k+1\quad k+2)\circ c^{-1}=(k+2\quad k+3).$$
   2. D'après la question précédente, toute transposition de la forme $(k\quad k+1)$ s'écrit en fonction de $c$ et de $t$. De plus, ces transpositions engendrent $S_n$. Ainsi, $c$ et $t$ engendrent $S_n$.

Lorsqu'on réalise un déplacement horizontal d'un jeton, on ne change par l'ordre des numéros, et la permutation correspondante est simplement l'identité. Lorsqu'on réalise un déplacement vertical d'un jeton, que ce soit vers le haut ou vers le bas, on produit un cycle de longueur 3, donc une permutation de signature égale à 1. La position finale étant obtenue comme suite de déplacements horizontaux ou verticaux, la permutation obtenue correspond à un produit de cycles de longueur 3, donc à un produit de permutations de signature égale à 1. C'est donc aussi une permutation de signature égale à 1.
Ces jeux de taquin sont souvent utilisés pour réaliser des puzzles. Cet exercice prouve que toutes les positions possibles des jetons ne sont pas atteignables.

On a \begin{eqnarray*} \Delta_1&=&\left|\begin{array}{cccc} {0}&{1}&0&0\\ 1&0&0&1\\ 1&1&-1&1\\ 1&1&0&0 \end{array}\right|\quad\quad {C_3\leftarrow C_3-C_2}\\ &=&{(-1)}\times \left|\begin{array}{ccc} 1&0&1\\ 1&-1&1\\ 1&0&0 \end{array}\right|\\ &=&(-1)\times\left| \begin{array}{cc} 0&1\\ -1&1 \end{array} \right| \\ &=&-1. \end{eqnarray*} \begin{eqnarray*} \Delta_2&=&\left|\begin{array}{cccc} a&b&c&d\\ a&a&b&c\\ a&a&a&b\\ a&a&a&a \end{array}\right|\\ &=&\left|\begin{array}{cccc} a&b-a&c-a&d-a\\ a&0&b-a&c-a\\ a&0&0&b-a\\ a&0&0&0 \end{array}\right| \quad\quad \begin{array}{l} {C_2\leftarrow C_2-C_1}\\ {C_3\leftarrow C_3-C_1}\\ {C_4\leftarrow C_4-C_1} \end{array} \end{eqnarray*} On développe par rapport à la dernière ligne, où le seul terme non nul est le premier. En suivant la règle d'alternance de signes, on doit multiplier par $-a$ le déterminant restant : \begin{eqnarray*} \Delta_2&=&{(-a)}\times \left|\begin{array}{ccc} b-a&c-a&d-a\\ 0&b-a&c-a\\ 0&0&b-a \end{array}\right|\\ &=&(-a)(b-a)^3. \end{eqnarray*}

On ne change pas un déterminant en ajoutant à une ligne une combinaison linéaire des autres. Ici, on ajoute à la troisième ligne 10 fois la seconde et 100 fois la première. On obtient : $$\left| \begin{array}{ccc} 5&2&1\\ 4&7&6\\ 546&273&169\\ \end{array} \right|.$$ Maintenant, tous les éléments de la dernière ligne sont divisibles par 13, et le déterminant vaut : $$13\times \left| \begin{array}{ccc} 5&2&1\\ 4&7&6\\ 42&21&13\\ \end{array} \right|.$$ C'est bien un entier divisible par 13.

On commence par faire l'opération $L_1+L_2+L_3\to L_1$. On obtient \begin{align*} D&=\left| \begin{array}{ccc} 1+a+b+c & 1+a+b+c & 1+a+b+c \\ b & 1+b & b \\ c & c & 1+c \end{array} \right|\\ &=(1+a+b+c) \left| \begin{array}{ccc} 1 & 1 & 1 \\ b & 1+b & b \\ c & c & 1+c \end{array} \right|. \end{align*} On retire ensuite $b$ fois la première ligne à la seconde, et $c$ fois la première ligne à la troisième. On obtient alors $$D=(1+a+b+c) \left| \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right|.$$ Il reste une matrice triangulaire supérieure, avec des 1 sur la diagonale. Celle-ci est de déterminant 1 et donc $D=1+a+b+c$.

On commence par faire apparaitre des 0 sur la première colonne, puis on transforme la troisième colonne en utilisant la formule $$\cos 2b-\cos 2a=2\cos^2 b-2\cos^2 a.$$ On trouve successivement : $$D=\left|\begin{array}{ccc} 1&\cos a&\cos 2a\\ 0&\cos b-\cos a&\cos 2b-\cos 2a\\ 0&\cos c-\cos a&\cos 2c-\cos 2a\\ \end{array}\right|=\left|\begin{array}{ccc} 1&\cos a&\cos 2a\\ 0&\cos b-\cos a&2\cos^2b-2\cos^2a\\ 0&\cos c-\cos a&2\cos^2c-2\cos^2a\\ \end{array}\right|.$$ On obtient alors, en utilisant que $\cos b-\cos a$ (resp. $\cos c-\cos a$) est un facteur commun de la deuxième (resp. troisième) ligne : \begin{eqnarray*} D&=&\left|\begin{array}{ccc} 1&\cos a&\cos 2a\\ 0&\cos b-\cos a&2(\cos b-\cos a)(\cos b+\cos a)\\ 0&\cos c-\cos a&2(\cos c-\cos a)(\cos c+\cos a)\\ \end{array}\right|\\ &=&(\cos b-\cos a)(\cos c-\cos a) \left| \begin{array}{ccc} 1&\cos a&\cos 2a\\ 0&1&2(\cos b+\cos a)\\ 0&1&2(\cos c+\cos a)\\ \end{array}\right|. \end{eqnarray*} On fait apparaitre un dernier zéro en soustrayant la deuxième ligne à la troisième, puis on développe le déterminant d'une matrice triangulaire supérieure : \begin{eqnarray*} D&=&(\cos b-\cos a)(\cos c-\cos a)\left|\begin{array}{ccc} 1&\cos a&\cos 2a\\ 0&1&2(\cos b+\cos a)\\ 0&0&2(\cos c-\cos b)\\ \end{array}\right|\\ &=&2(\cos b-\cos a)(\cos c-\cos a)(\cos c-\cos b). \end{eqnarray*} Remarquer la symétrie (prévisible) entre les variables $a,b,c$ dans cette expression.

On commence par remarquer que $3A-6I_3=3(A-2I_3)$ et donc $$\det(3A-6I_3)=3^3\det(A-2I_3).$$ D'autre part, on a $$(A-2I_3)^2=A^2-4A+4I_3=I_3.$$ Ainsi, $\big(\det(A-2I_3)\big)^2=\det\big((A-2I_3)^2\big)=1.$ Puisque $\det(A-2I_3)=\det(3A-6I_3)/27\geq 0$, on en déduit que $\det(A-2I_3)=1$ et que $$\det(3A-6I_3)=27.$$

Posons $f(x)=\det(A+xJ)$. On commence par démontrer que $f$ est un polynôme de degré inférieur ou égal à 1. En effet, dans la matrice $A+xJ$, retranchons la première colonne à toutes les autres colonnes. Alors le déterminant de $A+xJ$ est égal au déterminant d'une matrice dont la première colonne est constituée par des termes du type $a_{i,1}+x$ et tous les autres coefficients sont des constantes (ne dépendent pas de x). Si on développe ce déterminant par rapport à la première colonne, on trouve que $$f(x)=\sum_{i=1}^{2n} (-1)^{i+1}(a_{i,1}+x)\det(A_i)$$ où $A_i$ est une matrice à coefficients réels et donc $\det(A_i)$ est une constante (ne dépend pas de $x$).
On démontre ensuite que, pour tout $x\in\mathbb R$, $f(x)=f(-x)$. En effet, on a \begin{align*} f(x)&=\det(A+xJ)\\ &=\det ( (A+xJ)^T)\\ &=\det ( -A+xJ)\\ &=\det ( (-1)\times (A-xJ))\\ &=(-1)^{2n}\det(A-xJ)\\ &=\det(A-xJ)\\ &=f(-x). \end{align*} On conclut car les seuls polynômes de degré inférieur ou égal à $1$ qui sont pairs sont les polynômes constants.

Notons $D_n(s_1,\dots,s_n)$ ce déterminant. Prouvons par récurrence sur $n$ que, pour tous réels $s_1,\dots,s_n$, $$D_n(s_1,\dots,s_n)=s_1(s_2-s_1)(s_3-s_2)\dots (s_n-s_{n-1}).$$ On vérifie cette relation facilement pour les premières valeurs de $n$. Si la propriété est vraie au rang $n-1$, prouvons la au rang $n$ en retranchant la première colonne à toutes les autres. On trouve $$D_n(s_1,\dots,s_n)=\left| \begin{array}{cccc} s_1&0&\dots&0\\ s_1&s_2-s_1&\dots&s_2-s_1\\ \vdots&\vdots&\ddots&\vdots\\ s_1&s_2-s_1&\dots&s_n-s_1\\ \end{array}\right|= s_1\left| \begin{array}{cccc} s_2-s_1&\dots&\dots&s_2-s_1\\ s_2-s_1&s_3-s_1&\dots&s_3-s_1\\ \vdots&\vdots&\ddots&\vdots\\ s_2-s_1&s_3-s_1&\dots&s_n-s_1 \end{array}\right|.$$ On en déduit que $$D_n(s_1,\dots,s_n)=s_1D_{n-1}(s_2-s_1,s_3-s_1,\dots,s_n-s_1).$$ Utilisant l'hypothèse de récurrence, on trouve \begin{eqnarray*} D(s_1,\dots,s_n)&=&s_1 (s_2-s_1)(s_3-s_1-s_2+s_1)\dots(s_n-s_1-s_{n-1}+s_1)\\ &=&s_1(s_2-s_1)(s_3-s_2)\dots (s_n-s_{n-1}). \end{eqnarray*}

On commence par ajouter toutes les autres colonnes à la première colonne de $B$, ce qui ne change pas le déterminant. On a \begin{align*} \det(B)&=\det(B_1+\cdots+B_n,B_2,\dots,B_n)\\ &=\det\big( (n-1)S,B_2,\dots,B_n\big)\\ &=(n-1)\det(S,B_2,\dots,B_n\big). \end{align*} On retire ensuite la première colonne à toutes les autres colonnes : \begin{align*} \det(B)&=(n-1)\det(S,B_2-S,\dots,B_n-S)\\ &=(n-1)\det(S,-A_2,\dots,-A_n)\\ &=(-1)^{n-1}(n-1)\det(S,A_2,\dots,A_n). \end{align*} On conclut en soustrayant toutes les autres colonnes à la première colonne pour trouver : \begin{align*} \det(B)&=(-1)^{n-1}(n-1)\det(S-(A_2+\cdots+A_n),A_2,\dots,A_n)\\ &=(-1)^{n-1}(n-1)\det(A_1,\dots,A_n)\\ &=(-1)^{n-1}(n-1)\det(A). \end{align*}

On passe de $A$ à $B$ en multipliant toutes les lignes impaires par $-1$, puis toutes les colonnes impaires par $-1$. Si on note $p$ le nombre de lignes impaires et $q$ le nombre de colonnes impaires, alors on sait que $$\det(B)=(-1)^{p+q}\det(A).$$ Mais la matrice comporte autant de lignes impaires que de colonnes impaires, et donc $p=q$, ce qui entraine que $\det(B)=\det(A)$.

On note $\Delta_n(x)$ le déterminant recherché. On remarque, en écrivant la formule qui donne la définition du déterminant, que $\Delta_n(x)$ est un polynôme de degré exactement égal à $2n$. De plus, le terme en $x^{2n}$ ne peut s'obtenir qu'en faisant le produit des termes diagonaux. On en déduit que le coefficient devant $x^{2n}$ est égal à 1. Calculons ensuite $\Delta_n(x)$ en effectuant un développement suivant la première ligne. On trouve $$\Delta_n(x)=(1+x^2)\Delta_{n-1}(x)+x \left| \begin{array}{cccccc} -x&-x&0&\dots\\ 0&1+x^2&-x&0&\dots&0\\ \vdots&-x&1+x^2&-x&\ddots&\vdots\\ &0&\ddots&\ddots&\ddots&0\\ &\vdots&\ddots&-x&1+x^2&-x\\ 0&0&\dots&0&-x&1+x^2 \end{array} \right|.$$ On continue en effectuant un développement suivant la première colonne du déterminant restant. On trouve $$\Delta_n(x)=(1+x^2)\Delta_{n-1}(x)-x^2\Delta_{n-2}(x).$$ Pour trouver vraiment la valeur de $\Delta_n(x)$, on calcule les premières itérations. On a $$\Delta_1(x)=1+x^2,\ \Delta_2(x)=1+x^2+x^4,\dots$$ On conjecture que $\Delta_n(x)=1+x^2+\dots+x^{2n}$. Démontrons ceci par récurrence double. La propriété est vraie aux rangs $n=1$ et $n=2$. Si elle est vraie simultanément aux rangs $n-2$ et $n-1$, la formule de récurrence précédente montre qu'elle est aussi vraie au rang $n$. On obtient donc $\Delta_n(x)=1+x^2+\dots+x^{2n}$.

Notons $\Delta_p$ ce déterminant (de taille $p+1$), et prouvons que $\Delta_p=\Delta_{p-1}$ pour tout $p\geq 1$. En effet, on effectue successivement les opérations suivantes : $$L_{p+1}-L_{p}\to L_{p+1},\ L_{p}-L_{p-1}\to L_{p},\dots, L_2-L_1\to L_2.$$ Clairement, on fait apparaître des zéros dans la première colonne, excepté sur la première ligne. Pour les autres colonnes, le coefficient du déterminant à la $i$-ème ligne et à la $j$-ème colonne vaut initialement $\binom{n+i-1}{j-1}$. Après les opérations, il vaut $$\binom{n+i-1}{j-1}-\binom{n+i-2}{j-1}=\binom{n+i-2}{j-2}$$ où la dernière égalité vient de la formule du triangle de Pascal. Autrement dit, on a prouvé que $$\Delta_p=\left| \begin{array}{ccccc} 1&*&\dots&\dots&\dots\\ 0&\binom{n}0&\binom n1&\dots&\binom n{p-1}\\ 0&\binom{n+1}0&\binom{n+1}1&\dots&\binom{n+1}{p-1}\\ 0&\vdots&\vdots&&\vdots\\ 0&\binom{n+p-1}0&\binom{n+p-1}1&\dots&\binom{n+p-1}{p-1} \end{array} \right|. $$ En développant par rapport à la première colonne, on trouve bien comme annoncé que $\Delta_p=\Delta_{p-1}$. Puisque $\Delta_0=1$, le déterminant recherché est égal à 1.

On met $i$ en facteur dans chaque ligne de la matrice. On voit alors apparaitre le déterminant de Vandermonde $V(1,2,\dots,n)$. Le déterminant recherché vaut donc : \begin{eqnarray*} D&=&n!\prod_{1\leq i< j\leq n }(j-i)\\ &=&n!\prod_{1< j\leq n}\prod_{1\leq i<j}(j-i)\\ &=&n!\prod_{1<j\leq n}(j-1)!\\ &=&1!2!\dots n! \end{eqnarray*}

On a, en développant par rapport à la dernière colonne : \begin{eqnarray*} \det(A-xI_n)&=&\left|\begin{array}{ccccc} -x&\dots&\dots&0&a_0\\ 1&\ddots&&\vdots&a_1\\ 0&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&-x&\vdots\\ 0&\dots&0&1&a_{n-1}-x \end{array}\right|\\ &=&(-x)^{n-1}(a_{n-1}-x)+\sum_{k=0}^{n-2}(-1)^{n+k-1}a_k\Delta_k \end{eqnarray*} où $\Delta_k$ est le déterminant suivant ($-x$ est répété $k$ fois sur la diagonale) : $$\Delta_k= \left| \begin{array}{cccccccc} -x&0&\dots&0&*&\dots&\dots&*\\ *&\ddots&\ddots&\vdots&\vdots&&&\vdots\\ \vdots&\ddots&\ddots&\vdots&\vdots&&&\vdots\\ *&\vdots&\vdots&-x&*&\dots&\dots&*\\ 0&\dots&\dots&0&1&*&\dots&*\\ \vdots& & & \vdots&0&\ddots&\ddots&\vdots\\ \vdots& & & \vdots&\vdots&\ddots&\ddots&*\\ 0&\dots&\dots&0 & 0&\dots&0&1 \end{array}\right|.$$ Ce déterminant $\Delta_k$ se calcule par blocs (on a une matrice triangulaire supérieure par blocs). De plus, chacun des blocs diagonaux est lui-même triangulaire (inférieur pour le premier, supérieur pour le second). On en déduit que $$\Delta_k=(-x)^k 1^{n-1-k}$$ et donc que \begin{eqnarray*} \det(A-xI_n)&=&(-x)^{n-1}(a_{n-1}-x)+\sum_{k=0}^{n-2}(-1)^{n+k-1}(-1)^k a_kx^k\\ &=&(-1)^n\left(x^n-\sum_{k=0}^{n-1}a_kx^k\right). \end{eqnarray*}

Effectuons le calcul demandé. Pour $i\geq 2$, la $i$-ème ligne de $A$ est $$(a_{n-i+2}\ \dots\ a_n\ a_1\ \dots\ a_{n-i+1}).$$ Si on multiplie cette ligne par la $j$-ième colonne de $M$, on obtient le coefficient $$a_{n-i+2}+a_{n-i+3}w^{j-1}+\dots+a_1w^{(j-1)(i-1)}+a_2 w^{(j-1)i}+\dots+ a_{n-i+1}w^{(j-1)(n-1)}.$$ Si on factorise ce coefficient par $w^{(j-1)(i-1)}$, on trouve qu'il est égal à $$w^{(j-1)(i-1)}\times\left(a_1+a_2\omega^{j-1}+\dots+a_n\omega^{(j-1)(n-1)}\right).$$ Ceci est encore vrai pour $i=1$ puisque $w^0=1$. En notant $$P(x)=a_1+a_2x+\dots+a_nx^{n-1},$$ on a donc obtenu que la $j$-ème colonne de $AM$ est égale à la $j$-ème colonne de $M$ multipliée par $P(\omega^{j-1})$. Ceci entraîne que $$\det(AM)=P(1)P(\omega)\dots P(\omega^{n-1})\det(M).$$ Comme d'autre part $$\det(AM)=\det(A)\det(M)$$ et que le déterminant de $M$ est non nul (c'est un déterminant de Vandermonde et les $w^j$, $0\leq j\leq n-1$ sont distincts), on a : $$\det(A)=P(1)P(\omega)\dots P(\omega^{n-1}).$$

On a : $$\rang(AB)\leq \rang(A)$$ (car l'image de $AB$, vue comme application linéaire, est contenue dans l'image de $A$). Maintenant, le théorème du rang garantit que $$\rang(A)\leq p<n.$$ Puisque $AB\in\mnr$, on a $\det(AB)=0$.

$\mnr$ est la somme directe du sous-espace vectoriel des matrices symétriques et des matrices antisymétriques. Soit $(A_1,\dots,A_p)$ et $(B_1,\dots,B_q)$ une base respective de l'espace vectoriel des matrices symétriques et antisymétriques. $(A_1,\dots,A_p,B_1,\dots,B_q)$ forme une base de $\mnr$, et il suffit de calculer le déterminant dans cette base. Mais $\phi(A_i)=A_i$ tandis que $\phi(B_j)=-B_j$. On a donc $\det(\phi)=(-1)^q$. Il suffit ensuite de se souvenir que $p=\frac{n(n+1)}{2}$, ou $q=\frac{n(n-1)}{2}$.

Trouvons d'abord une condition nécessaire. Puisque $M\in \mathcal M_n(\mathbb Z)$, $\det(M)\in \mathbb Z$. D'autre part, si $M^{-1}\in \mathcal M_n(\mathbb Z)$, son déterminant est un entier et donc $\det(M^{-1})=\frac{1}{\det M}\in\mathbb Z$. Ceci entraine que $\det(M)=\pm 1$.
Réciproquement, si $\det(M)=\pm 1$, alors $M$ est inversible. De plus, toutes les entrées de sa comatrice, qui sont obtenues comme déterminants de sous-matrices de $M$, sont des entiers. De la formule de Cramer, on déduit que $M^{-1}=\frac{1}{\det(M)}\ ^t\!\textrm{comat}(M)$ est une matrice à coefficients dans $\mathbb Z$.

Il suffit de calculer le déterminant. Il faut le calculer de façon suffisamment intelligente pour qu'il apparaisse immédiatement sous forme factorisée. Pour la première matrice, commencer par tout ajouter sur la première colonne. \begin{eqnarray*} \det(A)&=&\left|\begin{array}{cccc} a&-1&0&-1\\ -1&a&-1&0\\ 0&-1&a&-1\\ -1&0&-1&a \end{array}\right|\\ &=&\left|\begin{array}{cccc} a-2&-1&0&-1\\ a-2&a&-1&0\\ a-2&-1&a&-1\\ a-2&0&-1&a \end{array}\right|\\ &=&(a-2)\left|\begin{array}{cccc} 1&-1&0&-1\\ 1&a&-1&0\\ 1&-1&a&-1\\ 1&0&-1&a \end{array}\right|\\ &=&(a-2)\left|\begin{array}{cccc} 1&0&0&0\\ 1&a+1&-1&1\\ 1&0&a&0\\ 1&1&-1&a+1 \end{array}\right|\\ &=&(a-2)\left|\begin{array}{ccc} a+1&-1&1\\ 0&a&0\\ 1&-1&a+1 \end{array}\right|\\ &=&(a-2)a\left|\begin{array}{cc} a+1&1\\ 1&a+1\end{array}\right|\\ &=&a(a-2)\big((a+1)^2-1\big)=a^2(a-2)(a+2). \end{eqnarray*} La matrice $A$ est donc inversible si et seulement si $a\neq 0,2,-2$.
Pour la matrice $B$, on procède de la même façon, en commençant par mettre $m^2-m=m(m-1)$ en facteur sur la dernière colonne. \begin{eqnarray*} \det(B)&=&m(m-1)\left|\begin{array}{cccc} 0&m&m&1\\ 1&m-1&2m-1&1\\ 0&m&m&0\\ 1&m&3m-1&0 \end{array}\right|\\ &=&m(m-1)\left|\begin{array}{cccc} 0&m&m&1\\ 1&m-1&2m-1&1\\ 0&m&m&0\\ 0&1&m&-1 \end{array}\right|(L4-L2\to L4)\\ &=&-m(m-1)\left|\begin{array}{ccc} m&m&1\\ m&m&0\\ 1&m&-1\\ \end{array}\right|\\ &=&-m^2(m-1)\left|\begin{array}{ccc} m&m&1\\ 1&1&0\\ 1&m&-1\\ \end{array}\right|\\ &=&-m^2(m-1)\left|\begin{array}{ccc} m&0&1\\ 1&0&0\\ 1&m-1&-1\\ \end{array}\right|(C2-C1\to C2)\\ &=&m^2(m-1)\left|\begin{array}{cc} 0&1\\ m-1&-1 \end{array}\right|\\ &=&-m^2(m-1)^2 \end{eqnarray*} La matrice est inversible si et seulement si $m\neq 0,1$.

Puisqu'on est en dimension 3, la famille $(e_1,e_2,e_3)$ est une famille libre si et seulement si c'est une base. Soit $M$ la matrice de ses trois vecteurs, ie $$M=\left(\begin{array}{ccc} 1&1&t\\ 1&t&1\\ t&1&1 \end{array}\right).$$ La famille $(e_1,e_2,e_3)$ est une base de $\mathbb R^3$ si et seulement si la matrice $M$ est inversible, c'est-à-dire si et seulement si $\det(M)\neq 0$. Mais on a \begin{eqnarray*} \left|\begin{array}{ccc} 1&1&t\\ 1&t&1\\ t&1&1\end{array}\right|&=&\left|\begin{array}{ccc} t+2&1&t\\ t+2&t&1\\ t+2&1&1\end{array}\right|\\ &=&(t+2)\left|\begin{array}{ccc} 1&1&t\\ 1&t&1\\ 1&1&1\end{array}\right|\\ &=&(t+2)\left|\begin{array}{ccc} 1&1&t\\ 0&t-1&1-t\\ 0&0&1-t\end{array}\right|\\ &=&-(t+2)(t-1)^2. \end{eqnarray*} La famille est donc une base si et seulement si $t\neq -2$ et $t\neq 1$.

Soit $(\lambda_i)_{1\leq i\leq n}$ une famille de scalaires telle qu'on ait la relation $\sum_{j=1}^n \lambda_j (u_j+s)=0$. Développant, on trouve que cette relation est équivalente à $\sum_{j=1}^n \big(\lambda_j+(\lambda_1+\dots+ \lambda_n)\alpha_j\big)u_j=0$. La famille $(u_1,\dots,u_n)$ est libre, ceci est équivalent à $$\forall j\in\{1,\dots,n\},\ \lambda_j+(\lambda_1+\dots+\lambda_n)\alpha_j=0.$$ On reformule ces conditions en tant que système d'inconnues $\lambda_1,\dots,\lambda_n$. $$\left(\begin{array}{ccccc} (1+\alpha_1)&\alpha_1&\alpha_1&\dots&\alpha_1\\ \alpha_2&1+\alpha_2&\alpha_2&\dots&\alpha_2\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ \alpha_n&\dots&\dots&\alpha_n&1+\alpha_n \end{array}\right)\left(\begin{array}{c} \lambda_1\\ \lambda_2\\ \vdots\\ \vdots\\ \lambda_n \end{array}\right)= \left(\begin{array}{c} 0\\0\\ \vdots\\ \vdots\\0 \end{array}\right).$$ La famille $(u_i+s)_{1\leq i\leq n}$ est libre si et seulement si ce système admet pour seule solution la solution identiquement nulle, $\lambda_1=\dots=\lambda_n=0$. Autrement dit, si et seulement si la matrice $$A=\left(\begin{array}{ccccc} (1+\alpha_1)&\alpha_1&\alpha_1&\dots&\alpha_1\\ \alpha_2&1+\alpha_2&\alpha_2&\dots&\alpha_2\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ \alpha_n&\dots&\dots&\alpha_n&1+\alpha_n \end{array}\right)$$ est inversible. Pour déterminer si $A$ est inversible, on calcule son déterminant, en commençant par retirer la dernière colonne à toutes les précédentes, puis en ajoutant toutes les lignes à la dernière : \begin{eqnarray*} \det(A)&=&\left| \begin{array}{cccc} 1&0&\dots&\alpha_1\\ 0&1&\dots&\alpha_2\\ \vdots&\ddots&\ddots&\vdots\\ -1&-1&\dots&1+\alpha_n \end{array}\right|\\ &=&\left| \begin{array}{cccc} 1&0&\dots&\alpha_1\\ 0&1&\dots&\alpha_2\\ \vdots&\ddots&\ddots&\vdots\\ 0&0&\dots&1+\alpha_1+\dots+\alpha_n \end{array}\right|\\ &=&1+\alpha_1+\dots+\alpha_n. \end{eqnarray*} En résumé, on a prouvé que $(u_i+s)_{1\leq i\leq n}$ est une famille libre si et seulement si $1+\alpha_1+\dots+\alpha_n\neq 0$.

Calculons le déterminant de cette famille (de $(n+1)$ vecteurs dans un espace de dimension $n+1$) par rapport à la base canonique $(1,X,\dots,X^n)$. On a $$(X-z_i)^n=\sum_{j=0}^n \binom{n}{j}(-1)^{n-j}z_i^{n-j}X^j.$$ Le déterminant recherché est donc \begin{eqnarray*} \Delta&=&\left| \begin{array}{cccc} \binom{n}{0}(-z_0)^n&\binom{n}{0}(-z_1)^n&\dots&\binom{n}{0}(-z_n)^n\\ \binom{n}{1}(-z_0)^{n-1}&\binom{n}{1}(-z_1)^{n-1}&\dots&\binom{n}{1}(-z_n)^{n-1}\\ \vdots&\vdots&\vdots&\vdots\\ \binom{n}{n}&\binom{n}{n}&\dots&\binom{n}{n}\\ \end{array}\right|\\ &=&\binom{n}{0}\binom{n}{1}\dots\binom{n}{n}\left| \begin{array}{cccc} (-z_0)^n&(-z_1)^n&\dots&(-z_n)^n\\ (-z_0)^{n-1}&(-z_1)^{n-1}&\dots&(-z_n)^{n-1}\\ \vdots&\vdots&\vdots&\vdots\\ 1&1&\dots&1\\ \end{array}\right|. \end{eqnarray*} On reconnaît un déterminant de Vandermonde, qui est non-nul puisque les $z_i$ sont supposés tous distincts. La famille considérée est effectivement une base de $\mathbb C_n[X]$.

Écrivons $A=PBP^{-1}$ sous la forme $AP=PB$. Soit $P_1$ la partie réelle de $P$, et $P_2$ sa partie imaginaire. Alors, prenant la partie réelle puis la partie imaginaire de l'équation précédente, et puisque $A$ et $B$ sont à coefficients réels, on obtient $AP_1=P_1B$ et $AP_2=P_2B$. Ainsi, pour tout réel $x$, on a $A(P_1+xP_2)=(P_1+xP_2)B$. Il suffit donc de prouver qu'il existe un réel $x$ tel que $P_1+xP_2$ est inversible. Posons $Q(X)=\det(P_1+XP_2)$. $Q$ est un polynôme qui n'est pas identiquement nul puisque $Q(i)=\det(P)\neq 0$. Ainsi, il existe un réel $x$ tel que $Q(x)\neq 0$. Pour ce réel, la matrice $M=(P_1+xP_2)\in GL_n(\mathbb R)$, et $A=MBM^{-1}$.