Разложение Лапласа - 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{aligned}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{aligned}}}$

куда ${displaystyle det(M_{ij})}$ минор элемента ${displaystyle B_{ij}}$, т.е. определитель подматрицы ${displaystyle M_{ij}}$ сформированный путем удаления ${displaystyle i^{th}}$ ряд и ${displaystyle j^{th}}$ столбец матрицы ${displaystyle B}$.

Примеры

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

${displaystyle B={egin{bmatrix}1&2&34&5&67&8&9end{bmatrix}}.}$

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

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

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

${displaystyle {egin{aligned}|B|&=-2cdot {egin{vmatrix}4&67&9end{vmatrix}}+5cdot {egin{vmatrix}1&37&9end{vmatrix}}-8cdot {egin{vmatrix}1&34&6end{vmatrix}}[5pt]&=-2cdot (-6)+5cdot (-12)-8cdot (-6)=0.end{aligned}}}$

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

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

Предполагать ${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)}=operatorname {sgn} au ,b_{ij}a_{1,sigma (1)}cdots a_{n-1,sigma (n-1)}}$

для некоторых перестановка τ ∈ S_п с ${displaystyle au (i)=j}$, и уникальная и очевидно связанная перестановка ${displaystyle sigma in S_{n-1}}$ который выбирает те же второстепенные записи, что и τ. Подобным образом каждый выбор σ определяет соответствующий τ то есть соответствие ${displaystyle sigma leftrightarrow au }$ это биекция между ${displaystyle S_{n-1}}$ и ${displaystyle { au in S_{n}colon 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)(leftarrow )_{j}end{pmatrix}}}$

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

Перестановка τ может быть получено из σ следующим образом. ${displaystyle sigma 'in 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)(leftarrow )_{j}& au (2)(leftarrow )_{j}&cdots & au (i+1)(leftarrow )_{j}&cdots & au (n)(leftarrow )_{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)(leftarrow )_{j}&cdots & au (n)(leftarrow )_{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)(leftarrow )_{j}& au (n)(leftarrow )_{j}end{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{aligned}sum _{ au in S_{n}: au (i)=j}operatorname {sgn} au ,b_{1, au (1)}cdots b_{n, au (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}}}$

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

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

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

Пример

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

${displaystyle A={egin{bmatrix}1&2&3&45&6&7&89&10&11&1213&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&4j&k&p&qend{bmatrix}},{ ext{ where }}peq j,qeq k.}$

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

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

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

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

${displaystyle {egin{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]&={egin{vmatrix}1&25&6end{vmatrix}}cdot {egin{vmatrix}11&1215&16end{vmatrix}}-{egin{vmatrix}1&35&7end{vmatrix}}cdot {egin{vmatrix}10&1214&16end{vmatrix}}+{egin{vmatrix}1&45&8end{vmatrix}}cdot {egin{vmatrix}10&1114&15end{vmatrix}}+{egin{vmatrix}2&36&7end{vmatrix}}cdot {egin{vmatrix}9&1213&16end{vmatrix}}-{egin{vmatrix}2&46&8end{vmatrix}}cdot {egin{vmatrix}9&1113&15end{vmatrix}}+{egin{vmatrix}3&47&8end{vmatrix}}cdot {egin{vmatrix}9&1013&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.end{aligned}}}$

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

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

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

${displaystyle |B|=sum _{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)        возвращаться общий

Смотрите также

• Математический портал

• Формула Лейбница для определителей
• Правило Сарруса за ${displaystyle 3 imes 3}$ детерминанты

Рекомендации

1. Стоер Булирш: Введение в вычислительную математику

• Дэвид Пул: Линейная алгебра. Современное введение. Cengage Learning 2005 г., ISBN  0-534-99845-3, стр. 265–267 (ограниченная онлайн-копия, п. 265, в Google Книги )
• Харви Э. Роуз: Линейная алгебра. Чистый математический подход. Springer 2002, ISBN  3-7643-6905-1, стр. 57–60 (ограниченная онлайн-копия, п. 57, в Google Книги )

внешняя ссылка

• Разложение Лапласа в C (на португальском)
• Расширение Лапласа в Java (на португальском)