5.1 Permutations

Pour définir le déterminant d’une matrice carrée, nous devons commencer par introduire les permutations.

Une permutation est une bijection \(\sigma:S\rightarrow S\), où \(S\) est un ensemble. Nous dénotons généralement une permutation sous la forme d’un tableau à deux rangées de sorte que chaque élément de la rangée du bas représente l’image de l’élément qui se retrouve immédiatement au-dessus. En utilisant cette notation, \(\sigma = \begin{pmatrix} 1& 2 & 3\\ 3 & 1 & 2\end{pmatrix}\) est une permutation telle que \(\sigma(1) = 3,\) \(\sigma(2) = 1,\) et \(\sigma(3) = 2.\) (La notation pour les permutations ne doit pas être confondue avec celle des matrices.)

L’ensemble de toutes les permutations de l’ensemble \(\{1,2,\ldots,n\}\) est dénoté par \(S_n\). Notons que \(|S_n| = n!\). Les éléments de \(S_2\) sont \(\begin{pmatrix} 1 & 2\\ 1 & 2\end{pmatrix}\) et \(\begin{pmatrix} 1 & 2\\ 2 & 1\end{pmatrix}\), et ceux de \(S_3\) sont \(\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3\end{pmatrix},\) \(\begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2\end{pmatrix},\) \(\begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3\end{pmatrix},\) \(\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix},\) \(\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2\end{pmatrix},\) et \(\begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}.\)

La permutation \(\sigma \in S_n\) telle que \(\sigma(i) = i\) pour \(i = 1,\ldots, n\) est la permutation identité.

Soient \(\sigma,\gamma \in S_n\). Il n’est pas difficile de voir que \(\gamma \circ \sigma \in S_n\).

Exemple 5.1 Soient \(\sigma = \begin{pmatrix} 1& 2&3\\ 3&1 &2\end{pmatrix}\) et \(\gamma = \begin{pmatrix} 1& 2&3\\ 3&2 &1\end{pmatrix}\). Que donne \(\gamma \circ \sigma\)?

Notons que \[\begin{align*} (\gamma\circ\sigma)(1) & = \gamma(\sigma(1)) = \gamma(3) = 1, \\ (\gamma\circ\sigma)(2) & = \gamma(\sigma(2)) = \gamma(1) = 3, \\ (\gamma\circ\sigma)(3) & = \gamma(\sigma(3)) = \gamma(2) = 2. \end{align*}\] Ainsi, \(\gamma \circ \sigma\) est la permutation \(\left(\begin{array}{ccc} 1& 2&3\\ 1& 3 &2\end{array}\right)\).

Si \(\gamma = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}\), alors \(\gamma \circ \sigma\) est la permutation identité. (Vérifiez!) On appelle \(\gamma\) permutation inverse (ou simplement l’inverse) de \(\sigma\). Chaque permutation a un inverse.

Nous verrons plus tard que la définition du déterminant d’une matrice \(\mathbf{A}\) de taille \(n \times n\) est une somme de termes, chacun contenant un produit de la forme \(a_{1,\sigma(1)} a_{2,\sigma(2)}\cdots a_{n,\sigma(n)},\) pour une permutation \(\sigma \in S_n\), où \(a_{i,j}\) dénote l’élément \((i,j)\) de \(\mathbf{A}.\)

Rappelons que l’on utilise le premier indice pour les lignes et le second pour les colonnes. Ainsi, le produit \(a_{1,\sigma(1)} a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}\) contient exactement un élément de chacune des lignes de \(\mathbf{A}\). Puisque \(\sigma(1),\ldots,\sigma(n)\) est une permutation des nombres \(1,\ldots, n\), le produit \(a_{1,\sigma(1)} a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}\) contient aussi exactement un élément de chacune des colonnes de \(\mathbf{A}\).

Exemple 5.2 Soient \(\mathbf{A} = \begin{bmatrix} a & b & c \\ d & e & f \\ u & v & w\end{bmatrix}\) et \(\sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2\end{pmatrix}\). Alors \[a_{1,\sigma(1)} a_{2,\sigma(2)} a_{3,\sigma(3)} = a_{1,3} a_{2,1} a_{3,2} = c d v.\]

Exercices

1. Pour chacune des permutations suivantes, donnez la permutation inverse.

   1. \(\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 2 & 4\end{pmatrix}\)

   2. \(\begin{pmatrix} 1 & 2 & 3 & 4\\ 4& 3 & 2 & 1\end{pmatrix}\)

   3. \(\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 4 & 2 &3\end{pmatrix}\)

2. Soit \(\mathbf{A}=\begin{bmatrix} 6 & 2 & 3 \\ 0 & 1 & -1 \\ -5 & 7 & 4\end{bmatrix}.\) Soit \(\sigma = \begin{pmatrix}1& 2&3\\ 3& 2 &1\end{pmatrix}\). Quel valeur prend \(a_{1,\sigma(1)} a_{2,\sigma(2)} a_{3,\sigma(3)}\)?

Solutions

1. 1. La permutation inverse est \(\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 2 & 4\end{pmatrix}.\)

   2. La permutation inverse est \(\begin{pmatrix} 1 & 2 & 3 & 4\\ 4& 3 & 2 & 1\end{pmatrix}.\)

   3. La permutation inverse est \(\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 5 & 3 & 1\end{pmatrix}.\)

2. \(a_{1,\sigma(1)} a_{2,\sigma(2)} a_{3,\sigma(3)} = a_{1,3} a_{2,2} a_{3,1} = 3 \cdot 1 \cdot (-5) = - 15.\)