En matemáticas , la condensación de Dodgson o método de contractantes 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). 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 1 × 1 matriz, que tiene una entrada, el determinante de la matriz original.
Método general
Este algoritmo se puede describir en los siguientes cuatro pasos:
- Sea A la matriz n × n dada. Disponga A de modo 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.
- Cree una matriz B ( n - 1) × ( n - 1), que consta de los determinantes de cada submatriz de 2 × 2 de A. Explícitamente, escribimos
- 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 .
- 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.
Ejemplos
Sin ceros
Uno desea encontrar
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.
Luego encontramos otra matriz de determinantes:
Luego debemos dividir cada elemento por el elemento correspondiente de nuestra matriz original. El interior de la matriz original es
, así 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 solo −5, da y −8 es de hecho el determinante de la matriz original.
Con ceros
Simplemente escribiendo las matrices:
Aquí nos metemos en problemas. Si continuamos el proceso, eventualmente estaremos dividiendo por 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:
Por tanto, llegamos a un determinante de 36.
Identidad de 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 entre cero se basa en una identidad conocida como la identidad Desnanot-Jacobi (1841) o, más generalmente, la identidad determinante de Sylvester (1851).
Sea una matriz cuadrada, y para cada una , denote por la matriz que resulta de eliminar la -ésima fila y la -ésima columna. Del mismo modo, para
, denotamos por la matriz que los resultados de suprimiendo las -ésimos y filas -ésimos y los -ésimos y columnas -ésimos.
Identidad Desnanot-Jacobi
Prueba de la corrección de la condensación de Dodgson
Reescribe la identidad como
Ahora observe que por inducción se deduce que cuando se aplica 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 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 solo elemento igual al único menor conectado de orden , a saber, el determinante de .
Prueba de la identidad Desnanot-Jacobi
Seguimos el tratamiento en el libro de Bressoud; para una prueba combinatoria alternativa, consulte el artículo de Zeilberger. Denote (hasta el signo, la -ésima menor de ) y defina una
matriz por
(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 computando de dos formas. Primero, podemos calcular directamente el producto de la matriz (usando propiedades simples de la matriz adjunta, o alternativamente usando la fórmula para la expansión de un determinante de matriz en términos de una fila o columna) para llegar a
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 sigue de igualar las dos expresiones para las que obtuvimos y dividirlas (esto está permitido si se piensa en las identidades como identidades polinomiales sobre el anillo de polinomios en las variables indeterminadas ).
Notas
Referencias y lectura adicional
-
Bressoud, David M. , Pruebas y confirmaciones: la historia de la conjetura de la matriz de signos alternos , MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
-
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.
-
Dodgson, CL (1866–1867). "Condensación de determinantes, siendo un método nuevo y breve para calcular sus valores aritméticos" (PDF) . Actas de la Royal Society de Londres . 15 : 150-155.
-
Knuth, Donald , Pfaffians superpuestos , Revista electrónica de combinatoria , 3 no. 2 (1996).
-
Lotkin, Mark (1959). "Nota sobre el método de los contratistas". 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 signo alterno 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.
-
Zeilberger, Doron , la regla de evaluación determinante de Dodgson probada por hombres y mujeres en dos tiempos , Electronic Journal of Combinatorics , 4 no. 2 (1997).
enlaces externos