Расширение Лапласа

Данная статья посвящена выражению детерминанты в отношении несовершеннолетних. Для приближения радиальных потенциалов см. Разложение Лапласа (потенциал) .

В линейной алгебре , Лапласа названное в честь Пьера-Симона Лапласа , также называемое кофакторным расширением , представляет собой выражение определителя n × расширение n - матрицы B как взвешенную сумму миноров , которые являются определителями некоторых ( n − 1) × ( n 1) — подматрицы B − . В частности, для каждого i разложение Лапласа по i -й строке представляет собой равенство $${\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j},\end{aligned}}$$ где $b_{i,j}$ - это запись i -й строки и j -го столбца B , и $m_{i,j}$ — определитель подматрицы, полученной удалением i -й строки и j -го столбца B. матрицы Аналогично, разложение Лапласа по j -му столбцу представляет собой равенство $${\begin{aligned}\det(B)&=\sum _{i=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j}.\end{aligned}}$$ (Каждое тождество подразумевает другое, поскольку определители матрицы и ее транспонирования одинаковы.)

Коэффициент $(-1)^{i+j}m_{i,j}$ из $b_{i,j}$ называется кофактором в приведенной выше сумме $b_{i,j}$ в Б. ​

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

некоторой перестановки τ ∈ Sn _с для $\tau (i)=j$и уникальная и очевидно связанная перестановка $\sigma \in S_{n-1}$ который выбирает те же второстепенные записи, что и τ . Аналогично, каждый выбор σ определяет соответствующее τ, т. е. соответствие $\sigma \leftrightarrow \tau$ является биекцией между $S_{n-1}$ и $\{\tau \in S_{n}\colon \tau (i)=j\}.$ Используя двухстрочную нотацию Коши , явная связь между $\tau$ и $\sigma$ можно записать как

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

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

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

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

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

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

где $(\leftarrow )_{i}$ это временное сокращение для $(n,n-1,\cdots ,i+1,i)$.

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

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

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

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

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

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

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

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

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

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

И поскольку карта $\sigma \leftrightarrow \tau$ является биективным,

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

откуда следует результат. Аналогично, результат верен, если индекс внешнего суммирования был заменен на $j$.

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

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

Пример

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

$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}, а именно пусть $S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}$ быть вышеупомянутым набором.

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

$b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},$

$c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},$

и знак их перестановки будет

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

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

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

где $H^{\prime }$ является дополнительным набором для $H$.

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

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

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

Общее заявление

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

$|B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}$

где $\varepsilon ^{H,L}$ - знак перестановки, определяемой $H$ и $L$, равный $(-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}$, $b_{H,L}$ квадратный минор $B$ полученное удалением из $B$ строки и столбцы с индексами в $H$ и $L$ соответственно, и $c_{H,L}$ (называемое дополнением $b_{H,L}$) определяется как $b_{H',L'}$ , $H'$ и $L'$ являющийся дополнением $H$ и $L$ соответственно.

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

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

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

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

См. также

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

Ссылки

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