Данная статья посвящена выражению определителя в отношении несовершеннолетних. Для приближения радиальных потенциалов см.
Разложение Лапласа (потенциал) .
Expression of a determinant in terms of minors
В линейной алгебре расширение Лапласа , названное в честь -Симона Лапласа , также называемое кофакторным расширением , представляет собой выражение определителя n × Пьера n - матрицы B как взвешенную сумму миноров , которые являются определителями некоторых ( n − 1) × ( n 1) — подматрицы B − . В частности, для каждого i разложение Лапласа по i-й строке представляет собой равенство
![{\displaystyle {\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j} ,\end{выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26d1eb5c3abdac6ae65566270d6ea639378f6e96)
где
![{\displaystyle b_{i,j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c01bc815e19e0446968a07c762eb225c3738a65b)
- это запись
i-й строки и
j- го столбца
B , и
![{\displaystyle m_{i,j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd5b8059baa5be84593d0400fa3a5b133286494c)
— определитель подматрицы, полученной удалением
- й строки и
j- го столбца матрицы
B. i Аналогично,
разложение Лапласа по j -му столбцу представляет собой равенство
![{\displaystyle {\begin{aligned}\det(B)&=\sum _{i=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j} .\end{выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61471c189c4ccd5d4f6248bc0a933c84edd6f132)
(Каждое
тождество подразумевает другое, поскольку определители матрицы и ее
транспонирования одинаковы.)
Коэффициент
из
называется кофактором в приведенной выше сумме
в Б.
Расширение Лапласа часто бывает полезно в доказательствах, например, позволяя рекурсию размера матриц. Он также представляет дидактический интерес из-за своей простоты и как один из нескольких способов просмотра и вычисления определителя. Для больших матриц вычисления быстро становятся неэффективными по сравнению с методом исключения Гаусса .
Рассмотрим матрицу
![{\displaystyle B={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66d75e650da2d1c082ea06c60d2dc734f8b09eae)
Определитель этой матрицы можно вычислить, используя разложение Лапласа по любой из ее строк или столбцов. Например, разложение по первой строке дает:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43a17127798eae0e148044adf5b9255929aefb41)
Разложение Лапласа по второму столбцу дает тот же результат:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0c63a3d7cafc0f04b7bd6e0db0a054a12bf9053)
В правильности результата легко убедиться: матрица сингулярна, поскольку сумма ее первого и третьего столбцов в два раза больше второго столбца, а значит, ее определитель равен нулю.
Доказательство [ править ]
Предполагать
представляет собой матрицу размера n × n и
Для ясности мы также помечаем записи
которые составляют его
второстепенная матрица
как
для
Рассмотрим условия разложения
которые имеют
как фактор. Каждый имеет форму
![{\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)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c95cc2f22d35682c376818bc15748c64c369f23)
для перестановки τ ∈ Sn с некоторой
и уникальная и очевидно связанная перестановка
который выбирает те же второстепенные записи, что и τ . Аналогично, каждый выбор σ определяет соответствующее τ , т. е. соответствие
является биекцией между
и
Используя двухстрочную нотацию Коши , явная связь между
и
можно записать как
![{\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}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/43b3873be8bdb279b6fe3118cde663ee7f11d1ce)
где
это временное сокращенное обозначение цикла
.
Эта операция уменьшает все индексы, большие, чем j, так что каждый индекс помещается в набор {1,2,...,n-1}.
Перестановку τ можно получить из σ следующим образом.
Определять
к
для
и
.
Затем
выражается как
![{\displaystyle \sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\ тау (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e66028b0bd3e9f546f00e95dac7ca26ab2b78d2)
Теперь операция, которая применяется
сначала, а потом применять
(Обратите внимание, что применение A перед B эквивалентно
к применению обратного A к верхней строке B в двухстрочной записи)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4dae629f3733d0a4a040c822771c09adf85e76ec)
где
это временное сокращение для
.
операция, которая применяется
сначала, а потом применяется
является
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67966028a24e8d656fc913c5389439aab80dd3d5)
вышеуказанные два равны, таким образом,
![{\displaystyle (\leftarrow)_{j}\tau =\sigma '(\leftarrow)_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d656b103ffcc935ca4ad8091a980d8fcc750e311)
![{\displaystyle \tau =(\rightarrow)_{j}\sigma '(\leftarrow)_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/576fa81d5a54c15de47fd05e5af51c198354aeeb)
где
является обратным
который
.
Таким образом
![{\displaystyle \tau \,=(j,j+1,\ldots,n)\sigma '(n,n-1,\ldots,i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9660512364d06e0e4a15cb2561ba3c36b5efa04a)
Поскольку два цикла можно записать соответственно как
и
транспозиции ,
![{\displaystyle \operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {знак} \ сигма .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcf97ed0b9179780d93d1bcdddac553dce8d1f41)
И поскольку карта
является биективным,
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/131acd2c0adb6fecea2e5754797ac92d9b0df0c6)
откуда следует результат. Аналогично, результат верен, если индекс внешнего суммирования был заменен на
.
Разложение определителя по минорами Лапласу дополнительными
Кофакторное разложение Лапласа можно обобщить следующим образом.
Рассмотрим матрицу
![{\displaystyle A={\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8aafc1b3cc5ef887243f78fbc5f434ff7f75796b)
Определитель этой матрицы можно вычислить, используя разложение кофактора Лапласа по первым двум строкам следующим образом. Во-первых, обратите внимание, что существует 6 наборов двух различных чисел в {1, 2, 3, 4}, а именно пусть
быть вышеупомянутым набором.
Определив дополнительные кофакторы, которые будут
![{\displaystyle b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3380d30a694444cb64836c6bdb95d29740642e2f)
![{\displaystyle c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a3d5e3a55b79b99d74740053c3690064807daff)
и знак их перестановки будет
![{\displaystyle \itempsilon ^{\{j,k\},\{p,q\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ где }}p\neq j,q\neq k.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38dc53407e46f7c5777cee723cffca064313785f)
Определитель A можно записать в виде
![{\displaystyle |A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f06e7c48ec9427c8841ab3baab0107606bc86680)
где
является дополнительным набором для
.
В нашем явном примере это дает нам
![{\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 }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31cf78d4760eec74fbfac158630611c41bb45726)
Как и выше, легко проверить правильность результата: матрица сингулярна, поскольку сумма ее первого и третьего столбцов в два раза больше второго столбца, и, следовательно, ее определитель равен нулю.
Общее заявление [ править ]
Позволять
быть матрицей размера n × n и
набор k -элементных подмножеств {1, 2, ..., n } ,
элемент в нем. Тогда определитель
может быть расширено вдоль k строк, обозначенных
следующее:
![{\displaystyle |B|=\sum _{L\in S} \varepsilon ^{H,L}b_{H,L}c_{H,L}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97086f8788420d6663b1b62e07955b8dc57125b9)
где
- знак перестановки, определяемой
и
, равно
,
квадратный минор
полученное удалением из
строки и столбцы с индексами в
и
соответственно, и
(называемое дополнением
) определяется как
,
и
являющийся дополнением
и
соответственно.
Это совпадает с теоремой выше, когда
. То же самое справедливо для любых фиксированных k столбцов.
Вычислительные затраты [ править ]
Расширение Лапласа вычислительно неэффективно для матриц большой размерности, поскольку временная сложность выражается в большом значении O, равном O ( n ! ) . Альтернативно, использование разложения на треугольные матрицы , как при разложении LU, может дать определители с временной сложностью O ( n 3 ) . [1] Следующий код Python реализует расширение Лапласа:
def определитель ( M ):
# Базовый случай рекурсивной функции: матрица 1x1
if len ( M ) == 1 :
возвращает M [ 0 ][ 0 ]
total = 0
для столбца , элемента в перечислении ( M [ 0 ]):
# Исключить первая строка и текущий столбец.
K = [ x [: столбец ] + x [ столбец + 1 :] для x в M [ 1 :]]
s = 1 если столбец % 2 == 0 иначе - 1
итого += s * элемент * определитель ( K )
return общий
- ^ Стер Булирш: Введение в числовую математику