Condensación Dodgson

Método de cálculo de los determinantes.

En matemáticas , la condensación de Dodgson o método de los contratistas es un método para calcular los determinantes de matrices cuadradas . Lleva el nombre de 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 consiste en construir una ( n  − 1) × ( n  − 1) matriz, una ( n  − 2) × ( n  − 2), y así sucesivamente, terminando con una matriz de 1 × 1, que tiene una entrada, el determinante de la matriz original.

método general

Este algoritmo se puede describir en los siguientes cuatro pasos:

1. Sea A la matriz n  ×  n dada. Disponga A de manera que no aparezcan ceros en su interior. Una definición explícita de interior sería todo a _i,j con . Se puede hacer esto usando cualquier operación que normalmente se podría realizar sin cambiar el valor del determinante, como sumar un múltiplo de una fila a otra. ${\displaystyle i,j\neq 1,n}$
2. Cree una matriz B ( n  − 1) × ( n  − 1 ), que consta de 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 C ( n  − 2) × ( n  − 2 ). 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. Sean A = B y B = C. Repita el paso 3 según sea necesario hasta encontrar la matriz de 1 × 1; su única entrada es el determinante.

Ejemplos

Sin ceros

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}}.}$

Luego encontramos 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. Al dividir por el interior de la matriz de 3 × 3, que es simplemente −5, se obtiene que −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}}}$

Con ceros

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, eventualmente estaremos dividiendo entre 0. Podemos realizar cuatro intercambios de filas en la matriz inicial para preservar 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 tanto, llegamos a un determinante de 36.

Identidad Desnanot-Jacobi y prueba de corrección del algoritmo de condensación.

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, más generalmente, identidad del determinante de Sylvester (1851). ^[2]

Sea una matriz cuadrada, y para cada , denotemos por la matriz que resulta de eliminar la -ésima fila y la -ésima columna. De manera similar, para , denota por la matriz que resulta de eliminar las filas -ésima y -ésima y las columnas -ésima y -ésima. ${\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}$

Identidad Desnanot-Jacobi

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

Prueba de la exactitud de la condensación de Dodgson.

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

Ahora observe que por inducción se deduce 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 propia matriz) consta de todos los menores de orden conectados de , donde un menor conectado es el determinante de un subbloque conectado de entradas adyacentes de . En particular, en la última etapa , se obtiene una matriz que contiene un único elemento igual al único menor conectado 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}$

Prueba de la identidad Desnanot-Jacobi

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

Denota (hasta el signo, el -ésimo menor de ) y define 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 ahora se obtiene calculando de dos maneras. Primero, podemos calcular directamente el producto matricial (usando propiedades simples de la matriz adjunta, o alternativamente usando la fórmula para la expansión de un determinante matricial 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 la identidad se deriva de igualar las dos expresiones que obtuvimos para y dividir por (esto está permitido 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}}$

Referencias

1. Dodgson, CL (1866–1867). "La condensación de determinantes, un método nuevo y breve para calcular sus valores aritméticos" (PDF) . Actas de la Royal Society de Londres . 15 : 150-155. Código Bib : 1866RSPS...15..150D.
2. Sylvester, James Joseph (1851). "Sobre la relación entre los determinantes menores de funciones cuadráticas linealmente equivalentes". Revista Filosófica . 1 : 295–305.
   Citado en Akritas, AG; Akritas, EK; Malaschonok, GI (1996). "Varias pruebas de la identidad (determinante) de Sylvester". Matemáticas y Computación en Simulación . 42 (4–6): 585. doi :10.1016/S0378-4754(96)00035-3.
3. Bressoud, David (1999). Pruebas y confirmaciones: la historia de la conjetura de la matriz de signos alternos . Prensa de la Universidad de Cambridge. ISBN 9781316582756.
4. Zeilberger, Doron. "Regla de evaluación determinante de Dodgson demostrada por hombres y mujeres que actúan en dos tiempos". Electrón. J. Peine . 4 (2): artículo R22. doi : 10.37236/1337 . Consultado el 27 de octubre de 2023 .

Otras lecturas

• 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 , Pfaffianos superpuestos, Electronic Journal of Combinatorics , 3 no. 2 (1996).
• Lotkin, Mark (1959). "Nota sobre el método de los contratistas". El Mensual Matemático Estadounidense . 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 planos descendentes, 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 }$

enlaces externos

• Weisstein, Eric W. "Condensación de Dodgson". MundoMatemático .