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

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

$${\ displaystyle {\ begin {align} \ det (B) & = \ sum _ {j = 1} ^ {n} (- 1) ^ {i + j} B_ {i, j} M_ {i, j} , \ end {выровнено}}}$$

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

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

Термин называется кофактором из в B .${\ Displaystyle (-1) ^ {я + j} M_ {я, j}}$${\ displaystyle B_ {i, j}}$

Разложение Лапласа часто используется в доказательствах, например, при разрешении рекурсии по размеру матриц. Он также представляет дидактический интерес своей простотой и как один из нескольких способов просмотра и вычисления определителя. Для больших матриц вычисления быстро становятся неэффективными по сравнению с методом исключения Гаусса .

Примеры [ править ]

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

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

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

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

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

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

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

Доказательство [ править ]

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

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

Рассмотрим условия расширения, которые имеют как фактор. Каждый имеет форму${\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)}}$

для некоторой перестановки τ ∈ S _n с , и единственной и очевидно связанной перестановкой, которая выбирает те же второстепенные элементы, что и τ . Точно так же каждый выбор σ определяет соответствующее τ, т. Е. Соответствие является взаимно однозначным соответствием между и . Явное соотношение между и может быть записано как${\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\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &\tau (i+1)(\leftarrow )_{j}&\cdots &\tau (n)(\leftarrow )_{j}\end{pmatrix}}}$

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

Перестановка τ может быть получена из σ следующим образом. Определите как для и . Тогда выражается как ${\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\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &\tau (i+1)(\leftarrow )_{j}&\cdots &\tau (n)(\leftarrow )_{j}&n\end{pmatrix}}}$

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

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

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

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

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

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

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

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

где является обратным который .${\displaystyle (\rightarrow )_{j}}$${\displaystyle (\leftarrow )_{j}}$${\displaystyle (j,j+1,\cdots ,n)}$

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

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

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

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

А поскольку карта биективна,${\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}}}$

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

Разложение определителя по Лапласу дополнительными минорами [ править ]

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

Пример [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Общее заявление [ править ]

Пусть - матрица размера n × n и набор k -элементных подмножеств {1, 2, ..., n } , элемент в ней. Тогда определитель можно разложить по k строкам, обозначенным следующим образом:${\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}}$

где есть знак перестановки , определенная и , равный , квадратный минор , полученный удаление из строк и столбцов с номерами в и соответственно, и ( так называемом дополнением ) определяется как , и является дополнением и соответственно.${\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}$

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

Вычислительные расходы [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

• Дэвид Пул: Линейная алгебра. Современное введение . 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 (на португальском языке)