Expansão Laplace - Laplace expansion

${\ displaystyle B_ {i, j}}$

${\ displaystyle M_ {i, j}}$

O termo é denominado o

${\ displaystyle (-1) ^ {i + j} M_ {i, j}}$

${\ displaystyle B_ {i, j}}$

A expansão de Laplace é frequentemente útil em provas, como, por exemplo, permitir a recursão no tamanho das matrizes. Também é de interesse didático por sua simplicidade e como uma das várias maneiras de visualizar e calcular o determinante. Para matrizes grandes, torna-se rapidamente ineficiente para calcular, quando comparado à eliminação gaussiana .

Exemplos

Considere a matriz

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

O determinante dessa matriz pode ser calculado usando a expansão de Laplace ao longo de qualquer uma de suas linhas ou colunas. Por exemplo, uma expansão ao longo da primeira linha produz:

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

A expansão de Laplace ao longo da segunda coluna produz o mesmo resultado:

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

É fácil verificar se o resultado está correto: a matriz é singular porque a soma de sua primeira e terceira coluna é o dobro da segunda coluna e, portanto, seu determinante é zero.

Prova

Suponha que é um

${\ 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 os termos na expansão do que tem como fator. Cada um tem a 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 alguma permutação τ ∈ S _n com , e uma permutação única e evidentemente relacionada que seleciona as mesmas entradas secundárias que

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

onde é uma notação abreviada temporária para um

${\ displaystyle (\ leftarrow) _ {j}}$

${\ displaystyle (n, n-1, \ cdots, j + 1, j)}$

A permutação τ pode ser derivada de σ como segue. Defina por para e . Então é expresso 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 }}}$

Agora, a operação que se aplica primeiro e depois se aplica é (Observe que aplicar A antes de B é equivalente a aplicar o inverso de A à linha superior de B na

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

onde está a notação abreviada temporária para . ${\ displaystyle (\ leftarrow) _ {i}}$${\ displaystyle (n, n-1, \ cdots, i + 1, i)}$

a operação que se aplica primeiro e depois se aplica é ${\ 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}}}$

acima de dois são iguais, portanto,

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

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

onde está o inverso do qual é . ${\ displaystyle (\ rightarrow) _ {j}}$${\ displaystyle (\ leftarrow) _ {j}}$${\ displaystyle (j, j + 1, \ cdots, n)}$

Assim

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

Uma vez que os dois ciclos podem ser escritos respectivamente como e

${\ displaystyle ni}$

${\ displaystyle nj}$

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

E uma vez que o mapa é bijetivo, ${\ displaystyle \ sigma \ leftrightarrow \ tau}$

${\ displaystyle {\ begin {alinhados} \ 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 {alinhado}}}$

a partir do qual o resultado segue. Da mesma forma, o resultado é válido se o índice da soma externa for substituído por . ${\ displaystyle j}$

Expansão de Laplace de um determinante por menores complementares

A expansão do cofator de Laplaces pode ser generalizada como segue.

Exemplo

Considere a matriz

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

O determinante desta matriz pode ser calculado usando a expansão do cofator de Laplace ao longo das duas primeiras linhas como segue. Em primeiro lugar, note que existem 6 conjuntos de dois números distintos em {1, 2, 3, 4}, a saber

${\ displaystyle S = \ left \ {\ {1,2 \}, \ {1,3 \}, \ {1,4 \}, \ {2,3 \}, \ {2,4 \}, \ {3,4 \} \ right \}}$

Ao definir os cofatores complementares a serem

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

e o sinal de sua permutação para ser

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

O determinante de A pode ser escrito como

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

para onde está o conjunto complementar . ${\ displaystyle H ^ {\ prime}}$${\ displaystyle H}$

Em nosso exemplo explícito, isso nos dá

${\ displaystyle {\ begin {align} | 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 e 12 \\ 15 & 16 \ end {vmatrix}} - {\ begin {vmatrix} 1 & 3 \\ 5 & 7 \ end {vmatrix}} \ cdot { \ begin {vmatrix} 10 e 12 \\ 14 e 16 \ end {vmatrix}} + {\ begin {vmatrix} 1 e 4 \\ 5 & 8 \ end {vmatrix}} \ cdot {\ begin {vmatrix} 10 e 11 \\ 14 & 15 \ end {vmatrix}} + {\ begin {vmatrix} 2 e 3 \\ 6 e 7 \ end {vmatrix}} \ cdot {\ begin {vmatrix} 9 e 12 \\ 13 e 16 \ end {vmatrix}} - {\ begin {vmatrix} 2 e 4 \\ 6 e 8 \ end {vmatrix }} \ cdot {\ begin {vmatrix} 9 e 11 \\ 13 e 15 \ end {vmatrix}} + {\ begin {vmatrix} 3 e 4 \\ 7 & 8 \ end {vmatrix}} \ cdot {\ begin {vmatrix} 9 e 10 \\ 13 e 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 {alinhado }}}$

Como acima, é fácil verificar se o resultado está correto: a matriz é singular porque a soma de sua primeira e terceira coluna é o dobro da segunda coluna e, portanto, seu determinante é zero.

Declaração geral

Vamos ser um

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

onde é o sinal da permutação determinado por e , igual a , o quadrado menor de obtido pela exclusão de linhas e colunas com índices em e respectivamente, e (chamado de complemento de ) definido como sendo , e sendo o complemento de e 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}$

Isso coincide com o teorema acima quando . A mesma coisa vale para quaisquer colunas de

${\ displaystyle k = 1}$

Despesa computacional

A expansão de Laplace é computacionalmente ineficiente para matrizes de alta dimensão, com uma complexidade de tempo na notação grande O de O ( n !) . Alternativamente, usar uma decomposição em matrizes triangulares como na decomposição LU pode render determinantes com uma complexidade de tempo de O ( n ³ ) . O seguinte código Python implementa a expansão Laplace recursivamente:

def determinant(M):
    # Base case of recursive function: 1x1 matrix
    if len(M) == 1: 
        return M[0][0]

    total = 0
    for column, element in enumerate(M[0]):
        # Exclude first row and current column.
        K = [x[:column] + x[column + 1 :] for x in M[1:]]
        s = 1 if column % 2 == 0 else -1 
        total += s * element * determinant(K)
    return total

Veja também

• Fórmula de Leibniz para determinantes
• Regra de Sarrus para determinantes${\ displaystyle 3 \ vezes 3}$

Referências

• David Poole: Linear Algebra. Uma introdução moderna . Cengage Learning 2005, ISBN  0-534-99845-3 , pp. 265-267 ( cópia online restrita , p. 265, no Google Books )
• Harvey E. Rose: Linear Algebra. Uma abordagem matemática pura . Springer 2002, ISBN  3-7643-6905-1 , pp. 57–60 ( cópia online restrita , p. 57, no Google Books )

links externos

• Expansão da Laplace em C (em português)
• Expansão da Laplace em Java (em português)