Expansión de Laplace

Expresión de un determinante en términos de menores

En álgebra lineal , la expansión de Laplace , llamada así por Pierre-Simon Laplace , también llamada expansión cofactor , es una expresión del determinante de una matriz B n × n como una suma ponderada de menores , que son los determinantes de algunos ( n − 1) × ( n − 1 ) - submatrices de B . Específicamente, para cada i , la expansión de Laplace a lo largo de la i- ésima fila es la igualdad

$${\displaystyle {\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j},\end{aligned}}}$$

ijBi-jB.expansión de Laplace a lo largo de la j- ésima columna ${\displaystyle b_{i,j}}$ ${\displaystyle m_{i,j}}$

$${\displaystyle {\begin{aligned}\det(B)&=\sum _{i=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j}.\end{aligned}}}$$

identidadtranspuesta

El coeficiente de en la suma anterior se llama cofactor de en B. ${\displaystyle (-1)^{i+j}m_{i,j}}$ ${\displaystyle b_{i,j}}$ ${\displaystyle b_{i,j}}$

La expansión de Laplace suele ser útil en pruebas, como, por ejemplo, al permitir la recursividad en el tamaño de matrices. También es de interés didáctico por su simplicidad y como una de varias formas de ver y calcular el determinante. Para matrices grandes, su cálculo rápidamente se vuelve ineficiente en comparación con la eliminación gaussiana .

Ejemplos

Considere la matriz

${\displaystyle B={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

El determinante de esta matriz se puede calcular utilizando la expansión de Laplace a lo largo de cualquiera de sus filas o columnas. Por ejemplo, una expansión a lo largo de la primera fila produce:

${\displaystyle {\begin{aligned}|B|&=1\cdot {\begin{vmatrix}5&6\\8&9\end{vmatrix}}-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+3\cdot {\begin{vmatrix}4&5\\7&8\end{vmatrix}}\\[5pt]&=1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.\end{aligned}}}$

La expansión de Laplace a lo largo de la segunda columna produce el mismo resultado:

${\displaystyle {\begin{aligned}|B|&=-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+5\cdot {\begin{vmatrix}1&3\\7&9\end{vmatrix}}-8\cdot {\begin{vmatrix}1&3\\4&6\end{vmatrix}}\\[5pt]&=-2\cdot (-6)+5\cdot (-12)-8\cdot (-6)=0.\end{aligned}}}$

Es fácil comprobar que el resultado es correcto: la matriz es singular porque la suma de su primera y tercera columna es el doble de la segunda columna y, por tanto, su determinante es cero.

Prueba

Supongamos que es una matriz n × n y, para mayor claridad, también etiquetamos las entradas que componen su matriz menor como ${\displaystyle B}$ ${\displaystyle i,j\in \{1,2,\dots ,n\}.}$ ${\displaystyle B}$ ${\displaystyle i,j}$ ${\displaystyle M_{ij}}$

${\displaystyle (a_{st})}$para ${\displaystyle 1\leq s,t\leq n-1.}$

Considere los términos en la expansión de ese factor. Cada uno tiene la forma ${\displaystyle |B|}$ ${\displaystyle b_{ij}}$

${\displaystyle \operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{i,j}\cdots b_{n,\tau (n)}=\operatorname {sgn} \tau \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}}$

para alguna permutación τ ∈ S n con , y una permutación única y evidentemente relacionada que selecciona las mismas entradas menores que τ . De manera similar, cada elección de σ determina una τ correspondiente , es decir, la correspondencia es una biyección entre y. Usando la notación de dos líneas de Cauchy , la relación explícita entre y se puede escribir como ${\displaystyle \tau (i)=j}$ ${\displaystyle \sigma \in S_{n-1}}$ ${\displaystyle \sigma \leftrightarrow \tau }$ ${\displaystyle S_{n-1}}$ ${\displaystyle \{\tau \in S_{n}\colon \tau (i)=j\}.}$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))\end{pmatrix}}}$

donde hay una notación abreviada temporal para un ciclo . Esta operación disminuye todos los índices mayores que j para que cada índice encaje en el conjunto {1,2,...,n-1} ${\displaystyle (\leftarrow )_{j}}$ ${\displaystyle (n,n-1,\cdots ,j+1,j)}$

La permutación τ se puede derivar de σ de la siguiente manera. Definir por para y . Entonces se expresa como ${\displaystyle \sigma '\in S_{n}}$ ${\displaystyle \sigma '(k)=\sigma (k)}$ ${\displaystyle 1\leq k\leq n-1}$ ${\displaystyle \sigma '(n)=n}$ ${\displaystyle \sigma '}$

${\displaystyle \sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}}$

Ahora, la operación que se aplica primero y luego se aplica es (Observe que aplicar A antes de B es equivalente a aplicar el inverso de A a la fila superior de B en notación de dos líneas) ${\displaystyle (\leftarrow )_{i}}$ ${\displaystyle \sigma '}$

${\displaystyle \sigma '(\leftarrow )_{i}={\begin{pmatrix}1&2&\cdots &i+1&\cdots &n&i\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}}$

¿ Dónde está la notación abreviada temporal para ? ${\displaystyle (\leftarrow )_{i}}$ ${\displaystyle (n,n-1,\cdots ,i+1,i)}$

la operación que se aplica primero y luego se aplica es ${\displaystyle \tau }$ ${\displaystyle (\leftarrow )_{j}}$

${\displaystyle (\leftarrow )_{j}\tau ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &n&\cdots &(\leftarrow )_{j}(\tau (n-1))&(\leftarrow )_{j}(\tau (n))\end{pmatrix}}}$

los dos anteriores son iguales, por lo tanto,

${\displaystyle (\leftarrow )_{j}\tau =\sigma '(\leftarrow )_{i}}$

${\displaystyle \tau =(\rightarrow )_{j}\sigma '(\leftarrow )_{i}}$

¿ Dónde está la inversa de cuál es ? ${\displaystyle (\rightarrow )_{j}}$ ${\displaystyle (\leftarrow )_{j}}$ ${\displaystyle (j,j+1,\cdots ,n)}$

De este modo

${\displaystyle \tau \,=(j,j+1,\ldots ,n)\sigma '(n,n-1,\ldots ,i)}$

Dado que los dos ciclos se pueden escribir respectivamente como y transposiciones , ${\displaystyle n-i}$ ${\displaystyle n-j}$

${\displaystyle \operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {sgn} \sigma .}$

Y como el mapa es biyectivo, ${\displaystyle \sigma \leftrightarrow \tau }$

${\displaystyle {\begin{aligned}\sum _{i=1}^{n}\sum _{\tau \in S_{n}:\tau (i)=j}\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{n,\tau (n)}&=\sum _{i=1}^{n}\sum _{\sigma \in S_{n-1}}(-1)^{i+j}\operatorname {sgn} \sigma \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}\sum _{\sigma \in S_{n-1}}\operatorname {sgn} \sigma \,a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}M_{ij}\end{aligned}}}$

de donde se sigue el resultado. De manera similar, el resultado es válido si el índice de la suma externa se reemplazó por . ${\displaystyle j}$

Expansión de Laplace de un determinante por menores complementarios

La expansión del cofactor de Laplace se puede generalizar de la siguiente manera.

Ejemplo

Considere la matriz

${\displaystyle A={\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}}.}$

El determinante de esta matriz se puede calcular utilizando la expansión del cofactor de Laplace a lo largo de las dos primeras filas de la siguiente manera. En primer lugar, tenga en cuenta que hay 6 conjuntos de dos números distintos en {1, 2, 3, 4}, es decir, sea el conjunto antes mencionado. ${\displaystyle S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}}$

Al definir los cofactores complementarios como

${\displaystyle b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},}$

${\displaystyle c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},}$

y el signo de su permutación será

${\displaystyle \varepsilon ^{\{j,k\},\{p,q\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ where }}p\neq j,q\neq k.}$

El determinante de A se puede escribir como

${\displaystyle |A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},}$

¿ Dónde está el conjunto complementario ? ${\displaystyle H^{\prime }}$ ${\displaystyle H}$

En nuestro ejemplo explícito esto nos da

${\displaystyle {\begin{aligned}|A|&=b_{\{1,2\}}c_{\{3,4\}}-b_{\{1,3\}}c_{\{2,4\}}+b_{\{1,4\}}c_{\{2,3\}}+b_{\{2,3\}}c_{\{1,4\}}-b_{\{2,4\}}c_{\{1,3\}}+b_{\{3,4\}}c_{\{1,2\}}\\[5pt]&={\begin{vmatrix}1&2\\5&6\end{vmatrix}}\cdot {\begin{vmatrix}11&12\\15&16\end{vmatrix}}-{\begin{vmatrix}1&3\\5&7\end{vmatrix}}\cdot {\begin{vmatrix}10&12\\14&16\end{vmatrix}}+{\begin{vmatrix}1&4\\5&8\end{vmatrix}}\cdot {\begin{vmatrix}10&11\\14&15\end{vmatrix}}+{\begin{vmatrix}2&3\\6&7\end{vmatrix}}\cdot {\begin{vmatrix}9&12\\13&16\end{vmatrix}}-{\begin{vmatrix}2&4\\6&8\end{vmatrix}}\cdot {\begin{vmatrix}9&11\\13&15\end{vmatrix}}+{\begin{vmatrix}3&4\\7&8\end{vmatrix}}\cdot {\begin{vmatrix}9&10\\13&14\end{vmatrix}}\\[5pt]&=-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\[5pt]&=16-64+48+48-64+16=0.\end{aligned}}}$

Como arriba, es fácil verificar que el resultado es correcto: la matriz es singular porque la suma de su primera y tercera columna es el doble de la segunda columna y, por tanto, su determinante es cero.

Declaración general

Sea una matriz n × n y el conjunto de k subconjuntos de elementos de {1, 2, ..., n } , un elemento en ella. Entonces el determinante de se puede expandir a lo largo de las k filas identificadas de la siguiente manera: ${\displaystyle B=[b_{ij}]}$ ${\displaystyle S}$ ${\displaystyle H}$ ${\displaystyle B}$ ${\displaystyle H}$

${\displaystyle |B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}}$

donde es el signo de la permutación determinado por y , igual a , el cuadrado menor de obtenido eliminando de filas y columnas con índices en y respectivamente, y (llamado complemento de ) definido como , y siendo el complemento de y respectivamente. ${\displaystyle \varepsilon ^{H,L}}$ ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle (-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}}$ ${\displaystyle b_{H,L}}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle c_{H,L}}$ ${\displaystyle b_{H,L}}$ ${\displaystyle b_{H',L'}}$ ${\displaystyle H'}$ ${\displaystyle L'}$ ${\displaystyle H}$ ${\displaystyle L}$

Esto coincide con el teorema anterior cuando . Lo mismo vale para cualquier k columnas fijas. ${\displaystyle k=1}$

Gasto computacional

La expansión de Laplace es computacionalmente ineficiente para matrices de alta dimensión, con una complejidad temporal en notación O grande de O ( n !) . Alternativamente, usar una descomposición en matrices triangulares como en la descomposición LU puede producir determinantes con una complejidad temporal de O ( n ³ ) . ^[1] El siguiente código Python implementa la expansión de Laplace de forma recursiva ^{[ cita necesaria ]} :

 determinante def ( M ):  # Caso base de la función recursiva: matriz 1x1  si  len ( M )  ==  1 :  devolver  M [ 0 ][ 0 ] total  =  0  para  columna ,  elemento  en  enumerar ( M [ 0 ]):  # Excluir la primera fila y la columna actual.  K  =  [ x [: columna ]  +  x [ columna  +  1  :]  para  x  en  M [ 1 :]]  s  =  1  si  columna  %  2  ==  0  else  - 1  total  +=  s  *  elemento  *  determinante ( K )  return  total

Ver también

• Portal de matemáticas

• Fórmula de Leibniz para determinantes
• Regla de Sarrus para determinantes ${\displaystyle 3\times 3}$

Referencias

1. Stoer Bulirsch: Introducción a las matemáticas numéricas

• David Poole: Álgebra lineal. Una introducción moderna . Cengage Learning 2005, ISBN  0-534-99845-3 , págs. 265–267 ( copia restringida en línea , pág. 265, en Google Books )
• Harvey E. Rose: Álgebra lineal. Un enfoque matemático puro . Springer 2002, ISBN 3-7643-6905-1 , págs. 57–60 ( copia restringida en línea , pág. 57, en Google Books )