Формула Лейбница для определителей - Leibniz formula for determinants

В алгебре , то формула Лейбница , названная в честь Готфрида Лейбница , выражает определитель в виде квадратной матрицы в терминах перестановок матричных элементов. Если - матрица, где - запись в -й строке и -м столбце , формула имеет вид ${\ displaystyle A}$${\ Displaystyle п \ раз п}$${\ displaystyle a_ {ij}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A}$

${\ displaystyle \ det (A) = \ sum _ {\ tau \ in S_ {n}} \ operatorname {sgn} (\ tau) \ prod _ {i = 1} ^ {n} a_ {i, \, \ tau (i)} = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1} ^ {n} a _ {\ sigma (i), \, я},}$

где это функция знака из перестановок в группе перестановок , которая возвращает и для четных и нечетных перестановок , соответственно. ${\ displaystyle \ operatorname {sgn}}$ ${\ displaystyle S_ {n}}$${\ displaystyle +1}$${\ displaystyle -1}$

Другое распространенное обозначение, используемое для формулы, - это символ Леви-Чивиты и использует обозначение суммирования Эйнштейна , где оно становится

${\ displaystyle \ det (A) = \ epsilon _ {i_ {1} \ cdots i_ {n}} {a} _ {1i_ {1}} \ cdots {a} _ {ni_ {n}},}$

который может быть более знаком физикам.

Непосредственное вычисление формулы Лейбница из определения требует операций в целом, то есть ряда операций, асимптотически пропорциональных факториалу, поскольку это количество перестановок порядка . Это непрактично даже для относительно небольших устройств . Вместо этого определитель может быть вычислен в операциях путем формирования LU-разложения (обычно с помощью исключения Гаусса или аналогичных методов), и в этом случае определители треугольных матриц и являются просто произведениями их диагональных элементов. (Однако в практических приложениях числовой линейной алгебры явное вычисление определителя требуется редко.) См., Например, Trefethen & Bau (1997) . Определитель также можно вычислить за меньшее количество операций, сведя задачу к умножению матриц , но большинство таких алгоритмов непрактичны. ${\ Displaystyle \ Omega (п! \ CDOT п)}$${\ displaystyle n}$ ${\ displaystyle n!}$${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle О (п ^ {3})}$ ${\ displaystyle A = LU}$${\ Displaystyle \ Det A = \ Det L \ cdot \ Det U}$${\ displaystyle L}$${\ displaystyle U}$${\ Displaystyle О (п ^ {3})}$

Официальное заявление и доказательство

Теорема. Существует ровно одна функция, которая чередует полилинейные столбцы и такая, что . ${\ Displaystyle F: M_ {п} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$ ${\ Displaystyle F (I) = 1}$

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

Уникальность: Позвольте быть такой функцией, и пусть будет матрицей. Позвоните в -ю колонку , то есть , так что${\ displaystyle F}$${\ displaystyle A = (a_ {i} ^ {j}) _ {i = 1, \ dots, n} ^ {j = 1, \ dots, n}}$${\ Displaystyle п \ раз п}$${\ displaystyle A ^ {j}}$${\ displaystyle j}$${\ displaystyle A}$${\ displaystyle A ^ {j} = (a_ {i} ^ {j}) _ {i = 1, \ dots, n}}$${\ displaystyle A = \ left (A ^ {1}, \ dots, A ^ {n} \ right).}$

Кроме того, пусть обозначает -й вектор-столбец единичной матрицы. ${\ displaystyle E ^ {k}}$${\ displaystyle k}$

Теперь каждый записывает в терминах , т. Е. ${\ displaystyle A ^ {j}}$${\ displaystyle E ^ {k}}$

${\ displaystyle A ^ {j} = \ sum _ {k = 1} ^ {n} a_ {k} ^ {j} E ^ {k}}$.

Как полилинейно, ${\ displaystyle F}$

${\ Displaystyle {\ begin {align} F (A) & = F \ left (\ sum _ {k_ {1} = 1} ^ {n} a_ {k_ {1}} ^ {1} E ^ {k_ { 1}}, \ dots, \ sum _ {k_ {n} = 1} ^ {n} a_ {k_ {n}} ^ {n} E ^ {k_ {n}} \ right) = \ sum _ {k_ {1}, \ dots, k_ {n} = 1} ^ {n} \ left (\ prod _ {i = 1} ^ {n} a_ {k_ {i}} ^ {i} \ right) F \ left (E ^ {k_ {1}}, \ dots, E ^ {k_ {n}} \ right). \ End {align}}}$

Из чередования следует, что любой член с повторяющимися индексами равен нулю. Таким образом, сумма может быть ограничена кортежами с неповторяющимися индексами, то есть перестановками:

${\ Displaystyle F (A) = \ sum _ {\ sigma \ in S_ {n}} \ left (\ prod _ {i = 1} ^ {n} a _ {\ sigma (i)} ^ {i} \ right ) F (E ^ {\ sigma (1)}, \ dots, E ^ {\ sigma (n)}).}$

Поскольку F является чередующимся, столбцы можно менять местами, пока он не станет идентификатором. Функция знака определена для подсчета количества необходимых перестановок и учета результирующего изменения знака. В итоге получается: ${\ displaystyle E}$ ${\ displaystyle \ operatorname {sgn} (\ sigma)}$

${\ Displaystyle {\ begin {align} F (A) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1} ^ { n} a _ {\ sigma (i)} ^ {i} \ right) F (I) \\ & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1} ^ {n} a _ {\ sigma (i)} ^ {i} \ end {выровнено}}}$

как требуется, чтобы быть равным . ${\ Displaystyle F (I)}$${\ displaystyle 1}$

Следовательно, никакая функция, кроме функции, определенной формулой Лейбница, не может быть полилинейной функцией с чередованием . ${\ Displaystyle F \ влево (I \ вправо) = 1}$

Существование: теперь мы покажем, что F, где F - функция, определенная формулой Лейбница, обладает этими тремя свойствами.

Мультилинейный :

${\ displaystyle {\ begin {align} F (A ^ {1}, \ dots, cA ^ {j}, \ dots) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} ( \ sigma) ca _ {\ sigma (j)} ^ {j} \ prod _ {i = 1, i \ neq j} ^ {n} a _ {\ sigma (i)} ^ {i} \\ & = c \ сумма _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) a _ {\ sigma (j)} ^ {j} \ prod _ {i = 1, i \ neq j} ^ {n} a _ {\ sigma (i)} ^ {i} \\ & = cF (A ^ {1}, \ dots, A ^ {j}, \ dots) \\\\ F (A ^ {1}, \ dots , b + A ^ {j}, \ dots) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ left (b _ {\ sigma (j)} + a_ { \ sigma (j)} ^ {j} \ right) \ prod _ {i = 1, i \ neq j} ^ {n} a _ {\ sigma (i)} ^ {i} \\ & = \ sum _ { \ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ left (\ left (b _ {\ sigma (j)} \ prod _ {i = 1, i \ neq j} ^ {n} a_ {\ sigma (i)} ^ {i} \ right) + \ left (a _ {\ sigma (j)} ^ {j} \ prod _ {i = 1, i \ neq j} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) \ right) \\ & = \ left (\ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) b _ {\ sigma (j )} \ prod _ {i = 1, i \ neq j} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) + \ left (\ sum _ {\ sigma \ in S_ {n} } \ operatorname {sgn} (\ sigma) \ prod _ {i = 1} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) \\ & = F (A ^ {1}, \ точки, b, \ точки) + F (A ^ {1}, \ dots, A ^ {j}, \ dots) \\\\\ конец {выровнен}}}$

Чередование :

${\ displaystyle {\ begin {align} F (\ dots, A ^ {j_ {1}}, \ dots, A ^ {j_ {2}}, \ dots) & = \ sum _ {\ sigma \ in S_ { n}} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma (i) } ^ {i} \ right) a _ {\ sigma (j_ {1})} ^ {j_ {1}} a _ {\ sigma (j_ {2})} ^ {j_ {2}} \\\ end {выровнено }}}$

Для любого пусть будет кортеж, равный с переключенными индексами и . ${\ Displaystyle \ sigma \ в S_ {п}}$${\ displaystyle \ sigma '}$${\ displaystyle \ sigma}$${\ displaystyle j_ {1}}$${\ displaystyle j_ {2}}$

${\ Displaystyle {\ begin {align} F (A) & = \ sum _ {\ sigma \ in S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ left [\ имя оператора {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma (i)} ^ {i } \ right) a _ {\ sigma (j_ {1})} ^ {j_ {1}} a _ {\ sigma (j_ {2})} ^ {j_ {2}} + \ operatorname {sgn} (\ sigma ' ) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma '(i)} ^ {i} \ right) a_ { \ sigma '(j_ {1})} ^ {j_ {1}} a _ {\ sigma' (j_ {2})} ^ {j_ {2}} \ right] \\ & = \ sum _ {\ sigma \ в S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ left [\ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) a _ {\ sigma (j_ {1})} ^ {j_ {1}} a _ {\ sigma (j_ {2})} ^ {j_ {2}} - \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) a _ {\ sigma (j_ {2})} ^ {j_ {1}} a _ {\ sigma (j_ {1 })} ^ {j_ {2}} \ right] \\ & = \ sum _ {\ sigma \ in S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}} ^ {n} a _ {\ sigma (i)} ^ {i} \ right) \ underbrace {\ left (a _ {\ sigma (j_ {1})} ^ {j_ {1}} a _ {\ sigma (j_ {2})} ^ {j_ {2}} - a _ {\ sigma (j_ {1})} ^ {j_ {2}} a _ {\ sigma (j_ {2})} ^ {j _ {_ {1} }} \ right)} _ {= 0 {\ text {, if}} j_ {1} = j_ {2}} \\\\\ конец {выровнено}}}$

Таким образом, если то . ${\ displaystyle A ^ {j_ {1}} = A ^ {j_ {2}}}$${\ Displaystyle F (\ точки, A ^ {j_ {1}}, \ точки, A ^ {j_ {2}}, \ точки) = 0}$

И, наконец, : ${\ Displaystyle F (I) = 1}$

${\ Displaystyle {\ begin {align} F (I) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1} ^ {n} I_ {\ sigma (i)} ^ {i} = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1} ^ {n} \ operatorname {\ delta} _ {i, \ sigma (i)} \\ & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ operatorname {\ delta} _ {\ sigma, \ operatorname {id} _ {\ {1 \ ldots n \}}} = \ operatorname {sgn} (\ operatorname {id} _ {\ {1 \ ldots n \}}) = 1 \ end {выровнено}}}$

Таким образом, единственные чередующиеся полилинейные функции с ограничены функцией, определенной формулой Лейбница, и фактически она также обладает этими тремя свойствами. Следовательно, определитель можно определить как единственную функцию с этими тремя свойствами. ${\ Displaystyle F (I) = 1}$${\ Displaystyle \ Det: M_ {п} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$

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

• Матрица
• Разложение Лапласа
• Правило Крамера

использованная литература

• "Определитель" , Энциклопедия математики , EMS Press , 2001 [1994]
• Trefethen, Lloyd N .; Бау, Дэвид (1 июня 1997 г.). Числовая линейная алгебра . СИАМ . ISBN 978-0898713619.