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

В линейной алгебре , Лапласа названное в честь Пьера-Симона Лапласа , также называемое кофакторным расширением , представляет собой выражение определителя n × $расширение n -$ матрицы B $как$ взвешенную сумму миноров , которые являются определителями некоторых $(n - 1) \times (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)}

некоторой перестановки $τ \in 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$ . ^{[ 1 ]}

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

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

Пример

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

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 \times 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 3)$ . ^{[ 2 ]} Следующий код 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$ детерминанты

Ссылки

^ Уолтер, Дэн; Тайтун, Алекс (1949). «Элементарная задача 834». Американский математический ежемесячник . 56 (6). Американское математическое общество: 409.
^ Стер Булирш: Введение в числовую математику

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

[1] Уолтер, Дэн; Тайтун, Алекс (1949). «Элементарная задача 834». Американский математический ежемесячник . 56 (6). Американское математическое общество: 409.

[2] Стер Булирш: Введение в числовую математику

[ 1 ]

[ 2 ]