Condensation de Dodgson

En mathématiques, la condensation de Dodgson ou méthode des contractants est une méthode de calcul des déterminants des matrices carrées. Il doit son nom à son inventeur, Charles Lutwidge Dodgson (mieux connu sous son pseudonyme, Lewis Carroll, l'écrivain bien connu), qui l'a découvert en 1866. La méthode dans le cas d'une matrice n × n consiste à construire une matrice (n − 1)×(n − 1) matrice, une matrice (n − 2)×(n − 2), et ainsi de suite ; l'algorithme se termine avec une matrice 1×1, qui a donc un seul coefficient : c'est le déterminant de la matrice initiale.

Méthode générale

Cet algorithme peut être décrit en quatre étapes :

1. Soit A une matrice n×n. On commence par faire en sorte qu’aucun zéro n’apparaisse à l’intérieur. Ici, l'intérieur est formé des coefficients d'indice $(i,j)$ tels que $i,j\ne 1,n$. Pour cela, on utilise les opérations élémentaires sur les rangées qui ne modifient pas la valeur du déterminant, comme l’ajout d’un multiple d’une ligne à une autre.
2. On forme une matrice (n − 1)×(n − 1) notée B, constituée des déterminants de chaque sous-matrice 2×2 de A. Plus précisément, on pose $b_{i,j}=\left|\begin{array}{cc}{a}_{i,j}& a_{i,j+1}\\ a_{i+1,j}& a_{i+1,j+1}\end{array}\right|.$
3. À partir de cette matrice (n − 1)×(n − 1), on effectue l'étape 2 pour obtenir une matrice (n − 2)×(n − 2) notée C. On divise chaque coefficient de C par le terme correspondant à l'intérieur de A, c'est-à-dire que $c_{i,j}=\left|\begin{array}{cc}{b}_{i,j}& b_{i,j+1}\\ b_{i+1,j}& b_{i+1,j+1}\end{array}\right|÷a_{i+1,j+1}$.
4. On remplace A par B et B par C. On répète alors l'étape 3 si nécessaire jusqu'à obtenir une matrice 1×1 : son seul coefficient est le déterminant cherché.

Exemples

Sans zéros

On cherche à calculer le déterminant

$\left|\begin{array}{cccc}-2& -1& -1& -4\\ -1& -2& -1& -6\\ -1& -1& 2& 4\\ 2& 1& -3& -8\end{array}\right|.$

Tous les éléments intérieurs sont non nuls, on n'a donc pas besoin de modifier la matrice.

On forme une matrice avec les sous-matrices 2 × 2 :

$\left(\begin{array}{ccc}\left|\begin{array}{cc}-2& -1\\ -1& -2\end{array}\right|& \left|\begin{array}{cc}-1& -1\\ -2& -1\end{array}\right|& \left|\begin{array}{cc}-1& -4\\ -1& -6\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -2\\ -1& -1\end{array}\right|& \left|\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right|& \left|\begin{array}{cc}-1& -6\\ 2& 4\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -1\\ 2& 1\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ 1& -3\end{array}\right|& \left|\begin{array}{cc}2& 4\\ -3& -8\end{array}\right|\end{array}\right)=\left(\begin{array}{ccc}3& -1& 2\\ -1& -5& 8\\ 1& 1& -4\end{array}\right).$

On trouve ainsi une autre matrice de déterminant

$\left(\begin{array}{cc}\left|\begin{array}{cc}3& -1\\ -1& -5\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ -5& 8\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -5\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}-5& 8\\ 1& -4\end{array}\right|\end{array}\right)=\left(\begin{array}{cc}-16& 2\\ 4& 12\end{array}\right).$

On doit alors diviser chaque coefficient par le coefficient correspondant de la matrice initiale. L'intérieur de la matrice initiale est $\left(\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right)$ donc, après avoir divisé, on obtient $\left(\begin{array}{cc}8& -2\\ -4& 6\end{array}\right)$. On répète le processus pour arriver à une matrice 1×1 : $\left(\begin{array}{c}\left|\begin{array}{cc}8& -2\\ -4& 6\end{array}\right|\end{array}\right)=\left(\begin{array}{c}40\end{array}\right).$ En divisant par le coefficient intérieur de la matrice 3×3 précédente, qui vaut −5, on obtient $\left(\begin{array}{c}-8\end{array}\right)$ et −8 est bien le déterminant de la matrice originale.

Avec des zéros

En écrivant simplement les matrices :

$\left(\begin{array}{ccccc}2& -1& 2& 1& -3\\ 1& 2& 1& -1& 2\\ 1& -1& -2& -1& -1\\ 2& 1& -1& -2& -1\\ 1& -2& -1& -1& 2\end{array}\right)\to \left(\begin{array}{cccc}5& -5& -3& -1\\ -3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\end{array}\right)\to \left(\begin{array}{ccc}-15& 6& 12\\ 0& 0& 6\\ 6& -6& 8\end{array}\right).$

Là il y a un problème. Si l'on continue le processus, on finit par diviser par 0. On peut effectuer quatre échanges de lignes sur la matrice initiale pour préserver le déterminant et répéter le processus, avec la plupart des déterminants précalculés :

$\left(\begin{array}{ccccc}1& 2& 1& -1& 2\\ 1& -1& -2& -1& -1\\ 2& 1& -1& -2& -1\\ 1& -2& -1& -1& 2\\ 2& -1& 2& 1& -3\end{array}\right)\to \left(\begin{array}{cccc}-3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\\ 3& -5& 1& 1\end{array}\right)\to \left(\begin{array}{ccc}0& 0& 6\\ 6& -6& 8\\ -17& 8& -4\end{array}\right)\to \left(\begin{array}{cc}0& 12\\ 18& 40\end{array}\right)\to \left(\begin{array}{c}36\end{array}\right).$

On trouve finalement un déterminant de 36.

Identité de Desnanot–Jacobi et démonstration de la correction de l'algorithme de condensation

La démonstration que la méthode de condensation calcule le déterminant de la matrice si elle ne rencontre aucune division par zéro est fondée sur une identité connue sous le nom d'identité de Desnanot–Jacobi (1841) ou, plus généralement, d'identité du déterminant de Sylvester (1851).

Soit $M=(m_{i,j}{)}_{i,j=1}^k$ une matrice carrée et, pour tous $1\le i,j\le k$, soit $M_i^j$ la matrice obtenue de $M$ en supprimant la $i$-ème ligne et la $j$-ème colonne. De même, pour $1\le i,j,p,q\le k$, soit $M_{i,j}^{p,q}$ la matrice obtenue de $M$ en supprimant les $i$-ème et $j$-ème rangées et les $p$-ème et $q$-ième colonnes.

Identité de Desnanot-Jacobi

On a alors :

$\det (M)\det (M_{1,k}^{1,k})=\det (M_1^1)\det (M_k^k)-\det (M_1^k)\det (M_k^1).$

Démonstration de la correction de la condensation de Dodgson

On récrit l'identité comme

$\det (M)=\frac{\det (M_1^1)\det (M_k^k)-\det (M_1^k)\det (M_k^1)}{\det (M_{1,k}^{1,k})}.$

On remarque à présent que par récurrence, lorsque l'on applique la méthode de condensation de Dodgson à une matrice carrée $A$ d'ordre $n$, la matrice dans la $k$-ième étape du calcul (où la première étape $k=1$ correspond à la matrice $A$ elle-même) est formée de tous les mineurs connectés d'ordre $k$ de $A$, c'est-à-dire les déterminants d'une sous-matrice définie par le choix de $k$ lignes contiguës et $k$ colonnes contiguës de $A$. En particulier, dans la dernière étape $k=n$, on obtient une matrice contenant un seul élément égal à l'unique mineur connexe d'ordre $n$, à savoir le déterminant de $A$.

Démonstration de l'identité de Desnanot-Jacobi

Nous suivons la démonstration du livre Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture ; une autre preuve combinatoire a été donnée dans un article de Doron Zeilberger.

Soit $a_{i,j}=(-1{)}^{i+j}\det (M_i^j)$ (c'est, au signe près, le mineur d'indice $(i,j)$ de $M$), et soit $M^{\prime }$ la matrice $k\times k$ définie par

$M^{\prime }=\left(\begin{array}{ccccccc}{a}_{1,1}& 0& 0& 0& \dots & 0& a_{k,1}\\ a_{1,2}& 1& 0& 0& \dots & 0& a_{k,2}\\ a_{1,3}& 0& 1& 0& \dots & 0& a_{k,3}\\ a_{1,4}& 0& 0& 1& \dots & 0& a_{k,4}\\ ⋮& ⋮& ⋮& ⋮& & ⋮& ⋮\\ a_{1,k-1}& 0& 0& 0& \dots & 1& a_{k,k-1}\\ a_{1,k}& 0& 0& 0& \dots & 0& a_{k,k}\end{array}\right).$

(Remarquer que la première et la dernière colonnes de $M^{\prime }$ sont celles de la comatrice de $A$.) L'identité est maintenant obtenue en calculant $\det (M{M}^{\prime })$ de deux manières. D'une part, on peut calculer directement le produit matriciel $M{M}^{\prime }$ (en utilisant des propriétés simples de la comatrice, ou bien en utilisant la formule pour le développement d'un déterminant de matrice par rapport à une ligne ou à une colonne) pour arriver à

$M{M}^{\prime }=\left(\begin{array}{cccccc}\det (M)& m_{1,2}& m_{1,3}& \dots & m_{1,k-1}& 0\\ 0& m_{2,2}& m_{2,3}& \dots & m_{2,k-1}& 0\\ 0& m_{3,2}& m_{3,3}& \dots & m_{3,k-1}& 0\\ ⋮& ⋮& ⋮& & ⋮& ⋮& ⋮\\ 0& m_{k-1,2}& m_{k-1,3}& \dots & m_{k-1,k-1}& 0\\ 0& m_{k,2}& m_{k,3}& \dots & m_{k,k-1}& \det (M)\end{array}\right),$

où $m_{i,j}$ désigne le coefficient d'indice $(i,j)$ de $M$. Le déterminant de cette matrice est $\det (M{)}^2\cdot \det (M_{1,k}^{1,k})$.Par ailleurs le déterminant cherché est égal au produit $\det (M)\cdot \det (M^{\prime })$. Or bien sûr$\det (M^{\prime })=a_{1,1}{a}_{k,k}-a_{k,1}{a}_{1,k}=\det (M_1^1)\det (M_k^k)-\det (M_1^k)\det (M_k^1),$de sorte que l'identité résulte de l'égalité des deux expressions obtenues pour $\det (M{M}^{\prime })$, après une division par $\det (M)$ (ce qui est licite si l'on considère les identités comme des identités polynomiales sur l'anneau des polynômes en $k^2$ indéterminées $(m_{i,j}{)}_{i,j=1}^k$).

Bibliographie

• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Liens externes

• Modèle:MathWorld