Condensación de Dodgson

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Ayúdenos a mejorar este artículo introduciendo citas más precisas. ( Enero de 2019 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En matemáticas , la condensación de Dodgson o método de contractantes es un método para calcular los determinantes de matrices cuadradas . Recibe su nombre por su inventor, Charles Lutwidge Dodgson (más conocido por su seudónimo, como Lewis Carroll, el popular autor), quien lo descubrió en 1866. ^[1] El método en el caso de una matriz n  ×  n es construir una matriz ( n  − 1) × ( n  − 1), una ( n  − 2) × ( n  − 2), y así sucesivamente, terminando con una matriz 1 × 1, que tiene una entrada, el determinante de la matriz original.

Este algoritmo se puede describir en los siguientes cuatro pasos:

1. Sea A la matriz n  ×  n dada . Ordene A de modo que no haya ceros en su interior. Una definición explícita de interior sería todo a _i,j con . Esto se puede hacer utilizando cualquier operación que se podría realizar normalmente sin cambiar el valor del determinante, como sumar un múltiplo de una fila a otra.${\displaystyle i,j\neq 1,n}$
2. Crea una matriz B ( n  − 1) × ( n  − 1), que consiste en los determinantes de cada submatriz 2 × 2 de A. Explícitamente, escribimos${\displaystyle b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}}.}$
3. Usando esta matriz ( n  − 1) × ( n  − 1), realice el paso 2 para obtener una matriz ( n  − 2) × ( n  − 2) C. Divida cada término en C por el término correspondiente en el interior de A de modo que .${\displaystyle c_{i,j}={\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{vmatrix}}/a_{i+1,j+1}}$
4. Sea A = B y B = C. Repita el paso 3 según sea necesario hasta encontrar la matriz 1 × 1; su única entrada es el determinante.

Uno desea encontrar

${\displaystyle {\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix}}.}$

Todos los elementos interiores son distintos de cero, por lo que no es necesario reorganizar la matriz.

Hacemos una matriz de sus submatrices de 2 × 2.

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1\end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\\\{\begin{vmatrix}-1&-2\\-1&-1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\\\{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.}$

Encontramos entonces otra matriz de determinantes:

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\\\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}-16&2\\4&12\end{bmatrix}}.}$

Luego debemos dividir cada elemento por el elemento correspondiente de nuestra matriz original. El interior de la matriz original es , por lo que después de dividir obtenemos . El proceso debe repetirse para llegar a una matriz de 1 × 1. Dividiendo por el interior de la matriz de 3 × 3, que es simplemente −5, obtenemos y −8 es de hecho el determinante de la matriz original.${\displaystyle {\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.}$${\displaystyle {\begin{bmatrix}-8\end{bmatrix}}}$

Simplemente escribiendo las matrices:

${\displaystyle {\begin{bmatrix}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{bmatrix}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-15&6&12\\0&0&6\\6&-6&8\end{bmatrix}}.}$

Aquí nos encontramos con problemas. Si continuamos el proceso, terminaremos dividiendo por 0. Podemos realizar cuatro intercambios de filas en la matriz inicial para conservar el determinante y repetir el proceso, con la mayoría de los determinantes precalculados:

${\displaystyle {\begin{bmatrix}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{bmatrix}}\to {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{bmatrix}}.}$

Por lo tanto, llegamos a un determinante de 36.

La prueba de que el método de condensación calcula el determinante de la matriz si no se encuentran divisiones por cero se basa en una identidad conocida como identidad de Desnanot-Jacobi (1841) o, de forma más general, identidad del determinante de Sylvester (1851). ^[2]

Sea una matriz cuadrada y, para cada , denote por la matriz que resulta de eliminar la -ésima fila y la -ésima columna. De manera similar, para , denote por la matriz que resulta de eliminar las -ésimas y -ésima filas y las -ésimas y -ésimas columnas.${\displaystyle M=(m_{i,j})_{i,j=1}^{k}}$${\displaystyle 1\leq i,j\leq k}$${\displaystyle M_{i}^{j}}$${\displaystyle M}$${\displaystyle i}$${\displaystyle j}$${\displaystyle 1\leq i,j,p,q\leq k}$${\displaystyle M_{i,j}^{p,q}}$${\displaystyle M}$${\displaystyle i}$${\displaystyle j}$${\displaystyle p}$${\displaystyle q}$

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

Reescribe la identidad como

${\displaystyle \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})}}.}$

Nótese ahora que por inducción se sigue que al aplicar el procedimiento de condensación de Dodgson a una matriz cuadrada de orden , la matriz en la -ésima etapa del cálculo (donde la primera etapa corresponde a la matriz misma) consta de todos los menores conexos de orden de , donde un menor conexo es el determinante de un subbloque conexo de entradas adyacentes de . En particular, en la última etapa , se obtiene una matriz que contiene un solo elemento igual al único menor conexo de orden , es decir, el determinante de .${\displaystyle A}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k=1}$${\displaystyle A}$${\displaystyle k}$${\displaystyle A}$${\displaystyle k\times k}$${\displaystyle A}$${\displaystyle k=n}$${\displaystyle n}$${\displaystyle A}$

Seguimos el tratamiento del libro Pruebas y confirmaciones: la historia de la conjetura de la matriz de signos alternados ; ^[3] una prueba combinatoria alternativa fue dada en un artículo de Doron Zeilberger . ^[4]

Denotamos (hasta el signo, el -ésimo menor de ), y definimos una matriz por${\displaystyle a_{i,j}=(-1)^{i+j}\det(M_{i}^{j})}$${\displaystyle (i,j)}$${\displaystyle M}$${\displaystyle k\times k}$${\displaystyle M'}$

${\displaystyle M'={\begin{pmatrix}a_{1,1}&0&0&0&\ldots &0&a_{k,1}\\a_{1,2}&1&0&0&\ldots &0&a_{k,2}\\a_{1,3}&0&1&0&\ldots &0&a_{k,3}\\a_{1,4}&0&0&1&\ldots &0&a_{k,4}\\\vdots &\vdots &\vdots &\vdots &&\vdots &\vdots \\a_{1,k-1}&0&0&0&\ldots &1&a_{k,k-1}\\a_{1,k}&0&0&0&\ldots &0&a_{k,k}\end{pmatrix}}.}$

(Tenga en cuenta que la primera y la última columna de son iguales a las de la matriz adjunta de ). La identidad se obtiene ahora calculando de dos maneras. Primero, podemos calcular directamente el producto matricial (utilizando propiedades simples de la matriz adjunta, o alternativamente utilizando la fórmula para la expansión de un determinante de matriz en términos de una fila o una columna) para llegar a${\displaystyle M'}$${\displaystyle A}$${\displaystyle \det(MM')}$${\displaystyle MM'}$

${\displaystyle MM'={\begin{pmatrix}\det(M)&m_{1,2}&m_{1,3}&\ldots &m_{1,k-1}&0\\0&m_{2,2}&m_{2,3}&\ldots &m_{2,k-1}&0\\0&m_{3,2}&m_{3,3}&\ldots &m_{3,k-1}&0\\\vdots &\vdots &\vdots &&\vdots &\vdots &\vdots \\0&m_{k-1,2}&m_{k-1,3}&\ldots &m_{k-1,k-1}&0\\0&m_{k,2}&m_{k,3}&\ldots &m_{k,k-1}&\det(M)\end{pmatrix}}}$

donde usamos para denotar la -ésima entrada de . El determinante de esta matriz es . En segundo lugar, esto es igual al producto de los determinantes, . Pero claramente entonces la identidad se sigue de igualar las dos expresiones que obtuvimos para y dividir por (esto se permite si uno piensa en las identidades como identidades polinómicas sobre el anillo de polinomios en las variables indeterminadas ).${\displaystyle m_{i,j}}$${\displaystyle (i,j)}$${\displaystyle M}$${\displaystyle \det(M)^{2}\cdot \det(M_{1,k}^{1,k})}$
${\displaystyle \det(M)\cdot \det(M')}$
${\displaystyle \det(M')=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}),}$
${\displaystyle \det(MM')}$${\displaystyle \det(M)}$${\displaystyle k^{2}}$${\displaystyle (m_{i,j})_{i,j=1}^{k}}$

• Bressoud, David M. y Propp, James, Cómo se resolvió la conjetura de la matriz de signos alternos, Notices of the American Mathematical Society , 46 (1999), 637-646.
• Knuth, Donald , Pfaffians superpuestos, Revista electrónica de combinatoria , 3 no. 2 (1996).
• Lotkin, Mark (1959). "Nota sobre el método de contractantes". The American Mathematical Monthly . 66 (6): 476–479. doi :10.2307/2310629. JSTOR  2310629.
• Mills, William H., Robbins, David P., y Rumsey, Howard, Jr., Prueba de la conjetura de Macdonald, Inventiones Mathematicae , 66 (1982), 73-87.
• Mills, William H., Robbins, David P. y Rumsey, Howard, Jr., Matrices de signos alternos y particiones de plano descendente, Journal of Combinatorial Theory , Serie A , 34 (1983), 340-359.
• Robbins, David P., La historia de , The Mathematical Intelligencer , 13 (1991), 12-19.${\displaystyle 1,2,7,42,429,7436,\cdots }$

• Weisstein, Eric W. "Condensación de Dodgson". MathWorld .