Разложение Лапласа - Laplace expansion

В линейная алгебра, то Разложение Лапласа, названный в честь Пьер-Симон Лаплас, также называемый расширение кофактора, является выражением для детерминант |B| из п × п матрица B это взвешенная сумма детерминантов п подматрицы (или несовершеннолетние ) из B, каждый размером (п − 1) × (п - 1). Разложение Лапласа представляет дидактический интерес своей простотой и одним из нескольких способов просмотра и вычисления определителя. Для больших матриц вычисления быстро становятся неэффективными по сравнению с методами, использующими матричное разложение.

При вычислении определителя разложением Лапласа используется кофактор и незначительный. В я, j кофактор матрицы B это скаляр C_ij определяется

{displaystyle C_ {ij} = (- 1) ^ {i + j} M_ {ij} ,,}

куда M_ij это я, j незначительный из B, то есть определитель (п − 1) × (п - 1) матрица, полученная в результате удаления я-й ряд и j-й столбец B.

Тогда разложение Лапласа дается следующим

Теорема. Предполагать

{displaystyle B = [b_ {ij}]}

является

{displaystyle n imes n}

матрицу и выберите любую фиксированную

{displaystyle i, jin {1,2 ... n}}

. Предполагать

{displaystyle i ^ {'}}

фиксированный выбор

{displaystyle iin {1,2 ... n}}

. Тогда его определитель

{displaystyle left | Bight | = det (B)}

дан кем-то:

{displaystyle {egin {выровнено} det (B) & = left [(- 1) ^ {i ^ {'} + 1} b_ {i ^ {'} 1} det (M_ {i ^ {'} 1}) ight] + left [(- 1) ^ {i ^ {'} + 2} b_ {i ^ {'} 2} det (M_ {i ^ {'} 2}) ight] cdots + left [(- 1) ^ {i ^ {'} + n} b_ {1n} det (M_ {i ^ {'} n}) ight] & = sum _ {j = 1} ^ {n} (- 1) ^ {i ^ {'} + j} b_ {i ^ {'} j} det (M_ {i ^ {'} j}) end {выровнено}}}

куда

{displaystyle det (M_ {ij})}

минор элемента

{displaystyle B_ {ij}}

, т.е. определитель подматрицы

{displaystyle M_ {ij}}

сформированный путем удаления

{displaystyle i ^ {th}}

ряд и

{displaystyle j ^ {th}}

столбец матрицы

{displaystyle B}

.

Примеры

Рассмотрим матрицу

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

Определитель этой матрицы может быть вычислен с помощью разложения Лапласа по любой из ее строк или столбцов. Например, расширение по первой строке дает:

{displaystyle {egin {align} | B | & = 1cdot {egin {vmatrix} 5 & 6 8 & 9end {vmatrix}} - 2cdot {egin {vmatrix} 4 & 6 7 & 9end {vmatrix}} + 3cdot {egin {vmatrix} 4 & 5 7 & 8end { vmatrix}} [5pt] & = 1cdot (-3) -2cdot (-6) + 3cdot (-3) = 0.end {выровнено}}}

Разложение Лапласа по второму столбцу дает тот же результат:

{displaystyle {egin {align} | B | & = - 2cdot {egin {vmatrix} 4 & 6 7 & 9end {vmatrix}} + 5cdot {egin {vmatrix} 1 & 3 7 & 9end {vmatrix}} - 8cdot {egin {vmatrix} 1 & 3 4 & 6end {vmatrix}} [5pt] & = - 2cdot (-6) + 5cdot (-12) -8cdot (-6) = 0.end {выровнено}}}

Убедиться в правильности результата несложно: матрица единственное число потому что сумма его первого и третьего столбца вдвое больше, чем второй столбец, и, следовательно, его определитель равен нулю.

Доказательство

Предполагать ${displaystyle B}$ является п × п матрица и ${displaystyle i, jin {1,2, dots, n}.}$ Для ясности мы также помечаем записи ${displaystyle B}$ которые составляют его ${displaystyle i, j}$ малая матрица ${displaystyle M_ {ij}}$ в качестве

${displaystyle (a_ {st})}$ за ${displaystyle 1leq s, tleq n-1.}$

Рассмотрим слагаемые в разложении ${displaystyle | B |}$ который имеет ${displaystyle b_ {ij}}$ как фактор. Каждый имеет форму

{displaystyle operatorname {sgn} au, b_ {1, au (1)} cdots b_ {i, j} cdots b_ {n, au (n)} = имя оператора {sgn} au, b_ {ij} a_ {1, sigma (1)} cdots a_ {n-1, sigma (n-1)}}

для некоторых перестановка $τ \in S п$ с ${displaystyle au (i) = j}$ , и уникальная и очевидно связанная перестановка ${displaystyle sigma in S_ {n-1}}$ который выбирает те же второстепенные записи, что и $τ$ . Подобным образом каждый выбор $σ$ определяет соответствующий $τ$ то есть соответствие ${displaystyle sigma leftrightarrow au}$ это биекция между ${displaystyle S_ {n-1}}$ и ${displaystyle {au in S_ {n} двоеточие au (i) = j}.}$ Явная связь между ${displaystyle au}$ и ${displaystyle sigma}$ можно записать как

{displaystyle sigma = {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & au (i + 1) (leftarrow) _ {j} & cdots & au (n) (стрелка влево) _ {j} конец {pmatrix}}}

куда ${displaystyle (leftarrow) _ {j}}$ временное сокращенное обозначение цикл ${displaystyle (n, n-1, cdots, j + 1, j)}$ . Эта операция уменьшает все индексы, большие, чем j, так что каждый индекс помещается в набор {1,2, ..., n-1}

Перестановка $τ$ может быть получено из $σ$ следующим образом. ${displaystyle sigma 'в S_ {n}}$ к ${displaystyle sigma '(k) = sigma (k)}$ за ${displaystyle 1leq kleq n-1}$ и ${displaystyle sigma '(n) = n}$ . потом ${displaystyle sigma '}$ выражается как

{displaystyle sigma '= {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 & n au (1) (стрелка влево) _ {j} & au (2) (стрелка влево) _ {j} & cdots & au (i + 1) (стрелка влево) _ {j} & cdots & au (n) (стрелка влево) _ {j} & nend {pmatrix}}}

Теперь операция, которая применяется ${displaystyle (leftarrow) _ {i}}$ сначала, а затем применить ${displaystyle sigma '}$ is (Обратите внимание, что применение A перед B эквивалентно применению обратного A к верхней строке B в Двухстрочная запись Коши )

{displaystyle sigma '(leftarrow) _ {i} = {egin {pmatrix} 1 & 2 & cdots & i + 1 & cdots & n & i au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & au ( i + 1) (стрелка влево) _ {j} & cdots & au (n) (стрелка влево) _ {j} & nend {pmatrix}}}

куда ${displaystyle (leftarrow) _ {i}}$ временное сокращенное обозначение ${displaystyle (n, n-1, cdots, i + 1, i)}$ .

операция, которая применяется ${displaystyle au}$ сначала, а затем применить ${displaystyle (leftarrow) _ {j}}$ является

{displaystyle (leftarrow) _ {j} au = {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 & n au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & n & cdots & au ( n-1) (стрелка влево) _ {j} & au (n) (стрелка влево) _ {j} конец {pmatrix}}}

выше двух равны, таким образом,

{displaystyle (leftarrow) _ {j} au = sigma '(leftarrow) _ {i}}

{displaystyle au = (ightarrow) _ {j} sigma '(leftarrow) _ {i}}

куда ${displaystyle (ightarrow) _ {j}}$ является инверсией ${displaystyle (leftarrow) _ {j}}$ который ${displaystyle (j, j + 1, cdots, n)}$ .

Таким образом

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

Поскольку два циклы можно записать соответственно как ${displaystyle n-i}$ и ${displaystyle n-j}$ транспозиции,

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

А поскольку карта ${displaystyle sigma leftrightarrow au}$ биективен,

{displaystyle {egin {align} sum _ {au in S_ {n}: au (i) = j} имя оператора {sgn} au, b_ {1, au (1)} cdots b_ {n, au (n)} & = сумма _ {i = 1} ^ {n} сумма _ {сигма в S_ {n-1}} (- 1) ^ {i + j} имя оператора {sgn} сигма, 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}} имя оператора {sgn} sigma, a_ {1, sigma (1)} cdots a_ {n-1, sigma (n-1)} & = sum _ {i = 1} ^ {n} b_ {ij} (- 1) ^ {i + j} M_ {ij} конец {выровнено}}}

из чего следует результат. Точно так же результат сохраняется, если индекс внешнего суммирования был заменен на ${displaystyle j}$ .

Лапласовское разложение определителя дополнительными минорами

Разложение кофактора Лапласа можно обобщить следующим образом.

Пример

Рассмотрим матрицу

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

Определитель этой матрицы может быть вычислен с помощью разложения кофактора Лапласа по первым двум строкам следующим образом. Во-первых, обратите внимание, что есть 6 наборов двух разных чисел в ${1, 2, 3, 4},$ а именно пусть ${displaystyle S = left {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} ight}}$ быть вышеупомянутым набором.

Определив дополнительные кофакторы как

{displaystyle b _ {{j, k}} = {egin {vmatrix} a_ {1j} & a_ {1k} a_ {2j} & a_ {2k} end {vmatrix}},}

{displaystyle c _ {{p, q}} = {egin {vmatrix} a_ {3p} & a_ {3q} a_ {4p} & a_ {4q} end {vmatrix}},}

и знак их перестановки быть

{displaystyle varepsilon ^ {{j, k}, {p, q}} = {mbox {sgn}} {egin {bmatrix} 1 & 2 & 3 & 4 j & k & p & qend {bmatrix}}, {ext {where}} peq j, qeq k.}

Определитель А можно записать как

{displaystyle | A | = сумма _ {Hin S} varepsilon ^ {H, H ^ {prime}} b_ {H} c_ {H ^ {prime}},}

куда ${displaystyle H ^ {prime}}$ дополнительный набор к ${displaystyle H}$ .

В нашем явном примере это дает нам

{displaystyle {egin {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] & = {egin {vmatrix} 1 & 2 5 & 6end {vmatrix}} cdot {egin {vmatrix} 11 & 12 15 & 16end {vmatrix}} - {egin {vmatrix} 1 & 3 5 & 7end {vmatrix}} cdot {egin {vmatrix} 10 & 12 14 & 16end {vmatrix}} + {egin {vmatrix} 1 & 4 5 & 8end {vmatrix}} cdot {egin {vmatrix} 10 & 11 14 & 15end {vmatrix}} + {egin { vmatrix} 2 & 3 6 & 7end {vmatrix}} cdot {egin {vmatrix} 9 & 12 13 & 16end {vmatrix}} - {egin {vmatrix} 2 & 4 6 & 8end {vmatrix}} cdot {egin {vmatrix} 9 & 11 13 & 15end {vmatrix}} + egin {vmatrix} 3 & 4 7 & 8end {vmatrix}} cdot {egin {vmatrix} 9 & 10 13 & 14end {vmatrix}} [5pt] & = - 4cdot (-4) - (- 8) cdot (-8) + (- 12 ) cdot (-4) + (- 4) cdot (-12) - (- 8) cdot (-8) + (- 4) cdot (-4) [5pt] & = 16-64 + 48 + 48- 64 + 16 = 0. Конец {выровнено}}}

Как и выше, легко проверить правильность результата: матрица единственное число потому что сумма его первого и третьего столбца вдвое больше, чем второй столбец, и, следовательно, его определитель равен нулю.

Общее утверждение

Позволять ${displaystyle B = [b_ {ij}]}$ быть $п \times п$ матрица и ${displaystyle S}$ набор $k$ -элементные подмножества ${1, 2, ... , п}$ , ${displaystyle H}$ элемент в нем. Тогда определитель ${displaystyle B}$ может быть расширен по $k$ строки, идентифицированные ${displaystyle H}$ следующее:

{displaystyle | B | = сумма _ {Lin S} varepsilon ^ {H, L} b_ {H, L} c_ {H, L}}

куда ${displaystyle varepsilon ^ {H, L}}$ - знак перестановки, определяемый ${displaystyle H}$ и ${displaystyle L}$ , равно ${displaystyle (-1) ^ {left (sum _ {hin H} hight) + left (sum _ {ell in L} ell ight)}}$ , ${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}$ соответственно.

Это совпадает с теоремой выше, когда ${displaystyle k = 1}$ . То же самое верно для любых фиксированных $k$ столбцы.

Вычислительные затраты

Расширение Лапласа вычислительно неэффективно для матриц большой размерности с временная сложность в нотация большой O из ${displaystyle O (n!)}$ . В качестве альтернативы, используя разложение на треугольные матрицы как в LU разложение может дать детерминанты с временной сложностью ${displaystyle O (n ^ {3})}$ .^[1] Следующее Python код рекурсивно реализует расширение Лапласа^{[нужна цитата ]}:

def детерминант(M):    # Базовый случай рекурсивной функции: матрица 2x2 (такая, что det (M) = ad - cb)    если len(M) == 2:        возвращаться (M[0][0] * M[1][1]) - (M[0][1] * M[1][0])    еще:        общий = 0        за столбец, элемент в перечислять(M[0]):            # Исключить первую строку и текущий столбец.            K = [Икс[:столбец] + Икс[столбец + 1 :] за Икс в M[1:]]            # Учитывая, что элемент находится в строке 1, знак отрицательный, если индекс нечетный.            если столбец % 2 == 0:                общий += элемент * детерминант(K)            еще:                общий -= элемент * детерминант(K)        возвращаться общий