Condensación dodgson

En matemáticas , la condensación de Dodgson es un método para calcular determinantes . El método lleva el nombre de su creador , Charles Dodgson (más conocido como Lewis Carroll ). El método consiste en rebajar el orden del determinante de manera especial al orden 1, cuyo único elemento es el determinante buscado.

Método General

El algoritmo se puede describir usando los siguientes cuatro pasos:

1. Sea una matriz cuadrada dada de tamaño . Escribamos la matriz de tal manera que contenga solo elementos distintos de cero en la parte interna, es decir , si . Esto se puede hacer, por ejemplo, agregando a la fila de la matriz alguna otra fila, multiplicada por algún número. $A$ $n\veces n$ $A$ $a_{ij}\neq 0$ ${\ estilo de visualización i, j \ neq 1, n}$

2. Escriba una matriz de tamaño que consista en orden 2 menores de la matriz . Explícitamente: $B$ ${\ estilo de visualización (n-1) \ veces (n-1)}$ $A$

b_{i,j}={\begin{vmatriz}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1} \end{vmatrix}},\quad i,j=1\ldots n-1.

3. Aplicando el paso No. 2 a la matriz , escribimos una matriz de tamaño , dividiendo los elementos correspondientes de la matriz resultante en elementos internos de la matriz : $B$ $C$ ${\ estilo de visualización (n-2) \ veces (n-2)}$ $A$

c_{i,j}={\dfrac {\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j +1}\end{vmatriz}}{a_{i+1,j+1}}},\quad i,j=1\ldots n-2.

4. Sea y . Repetimos el paso No. 3 hasta obtener una matriz de orden 1. Su único elemento será el determinante deseado. ${\ estilo de visualización A = B}$ ${\ estilo de visualización B = C}$

Ejemplos

Sin ceros

Sea necesario calcular el determinante

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

Componemos una matriz de menores de orden 2: $B$

B={\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}}\\[0.5ex]{\begin{vmatrix}-1&-2\\-1&- 1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\ [0.5ex]{\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}}.

Creamos una matriz : $C$

{\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\ \[0.5ex]{\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}}.

C={\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}.

Obtuvimos los elementos de la matriz dividiendo los elementos de la matriz resultante $C$

{\begin{bmatrix}-16&2\\4&12\end{bmatrix}}

sobre los elementos internos de la matriz $A$

{\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}.

Repetimos este proceso hasta obtener una matriz de orden 1:

{\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.

Dividimos por la parte interna de la matriz de tamaño , es decir, por , obtenemos . $3 veces 3$ ${\ estilo de visualización -5}$ ${\begin{bmatriz}-8\end{bmatriz))$

$-ocho$ y es el determinante deseado de la matriz original.

Con ceros

Escribamos las matrices necesarias:

{\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{bmatriz}-30&6&-12\\0&0&6\\6&-6&8\end{bmatriz)).

Hay un problema. Si continuamos este proceso, entonces se vuelve necesaria la división por 0. Sin embargo, podemos reorganizar las filas de la matriz original y repetir el proceso:

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

Así, el determinante de la matriz original es 36.

La identidad de Dodgson y la corrección de la condensación de Dodgson

La identidad de Dodgson

La prueba del método de condensación de Dodgson se basa en una identidad conocida como la identidad de Dodgson (la identidad de Jacobi ).

Sea una matriz cuadrada, y por todas denotamos la matriz menor , que se obtiene eliminando la -ésima fila y la -ésima columna. De manera similar, para denotamos el menor, que se obtiene de la matriz eliminando las filas -ésima y -ésima y las columnas -ésima y -ésima. Después ${\displaystyle A=(m_{i,j})_{i,j=1}^{k))$ $1\leqslant i,j\leqslant k$ ${\displaystyle M_{i}^{j))$ $A$ $i$ $j$ $1\leqslant i,j,p,q\leqslant k$ ${\displaystyle M_{i,j}^{p,q))$ $A$ $i$ $j$ $pags$ $q$

\det(A)\cdot M_{1,k}^{1,k}=M_{1}^{1}\cdot M_{k}^{k}-M_{1}^{k} \cdot M_{k}^{1}.

Prueba de la identidad de Dodgson

Prueba de la exactitud de la condensación de Dodgson

Literatura

CLDodgson. Condensación de Determinantes, Siendo un Nuevo y Breve Método para Calcular sus Valores Aritméticos // Actas de la Royal Society de Londres. - 1866-1867. - T. 15 . — S. 150–155 .
A. L. Un nuevo método para calcular determinantes // Educación matemática . Segunda serie. - 1958. - Emisión. 3 . - S. 194 .
David Bressoud, Pruebas y confirmaciones: la historia de la conjetura de la matriz de signos alternos , MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
David Bressoud 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.
D. Knuth (1996) Superposición de Pfaffians , Electronic Journal of Combinatorics , 3 , no. 2.
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 planas descendentes, Journal of Combinatorial Theory, Serie A , 34 (1983), 340-359.
Robbins, David P., La historia de 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer , 13 (1991), 12-19.
Doron Zeilberger, la regla de evaluación determinante de Dodgson probada por hombres y mujeres de dos tiempos. elec. Peine J. 4 (1997).

Enlaces

Weisstein, Eric W. Condensación (inglés) en el sitio web de Wolfram MathWorld .