Формула Коши – Бине

В математике , особенно в линейной алгебре , формула Коши-Бине , названная в честь Огюстена-Луи Коши и Жака Филиппа Мари Бине двух прямоугольных матриц , представляет собой тождество определителя транспонированных произведения форм ( так что произведение четко определено и квадрат ). Он обобщает утверждение о том, что определитель произведения квадратных матриц равен произведению их определителей. Формула справедлива для матриц с элементами из любого коммутативного кольца .

Заявление

Пусть A — матрица размера m × n , а B — матрица размера n × m . Напишите [ n ] для набора {1, ..., n } и ${\tbinom {[n]}{m}}$ для множества m — комбинации [ n ] (т.е. подмножества [ n ] размера m ; существуют ${\tbinom {n}{m}}$ из них). Для $S\in {\tbinom {[n]}{m}}$, напишите A _{[ m ], S} для матрицы размера m × m , столбцы которой являются столбцами матрицы A по индексам из S , и B _{S ,[ m ]} для матрицы размера m × m , строки которой являются строками матрицы B по индексам из S. . Тогда формула Коши – Бине гласит:

$\det(AB)=\sum _{S\in {\tbinom {[n]}{m}}}\det(A_{[m],S})\det(B_{S,[m]}).$

Пример: беря m = 2 и n = 3, и матрицы $A={\begin{pmatrix}1&1&2\\3&1&-1\\\end{pmatrix}}$ и $B={\begin{pmatrix}1&1\\3&1\\0&2\end{pmatrix}}$, формула Коши–Бине дает определитель

$\det(AB)=\left|{\begin{matrix}1&1\\3&1\end{matrix}}\right|\cdot \left|{\begin{matrix}1&1\\3&1\end{matrix}}\right|+\left|{\begin{matrix}1&2\\1&-1\end{matrix}}\right|\cdot \left|{\begin{matrix}3&1\\0&2\end{matrix}}\right|+\left|{\begin{matrix}1&2\\3&-1\end{matrix}}\right|\cdot \left|{\begin{matrix}1&1\\0&2\end{matrix}}\right|.$

Действительно $AB={\begin{pmatrix}4&6\\6&2\end{pmatrix}}$, а его определитель $-28$ что равно $-2\times -2+-3\times 6+-7\times 2$ из правой части формулы.

Особые случаи

Если n < m, то ${\tbinom {[n]}{m}}$ — пустое множество, и формула говорит, что det( AB ) = 0 (ее правая часть — пустая сумма ); действительно, в этом случае ранг матрицы размером m × m , а это означает , AB не превосходит n что ее определитель равен нулю. Если n = m , случай, когда A и B являются квадратными матрицами, ${\tbinom {[n]}{m}}=\{[n]\}$ ( одноэлементный набор), поэтому в сумму входит только S = [ n ], и формула утверждает, что det( AB ) = det( A )det( B ).

При m = 0 A и B — пустые матрицы (но разной формы, если n > 0), как и их произведение AB ; суммирование включает один член S = Ø, а формула гласит 1 = 1, причем обе части задаются определителем матрицы 0×0. При m = 1 суммирование проводится по набору ${\tbinom {[n]}{1}}$ из n различных синглтонов, взятых из [ n ], и обе части формулы дают $\textstyle \sum _{j=1}^{n}A_{1,j}B_{j,1}$, скалярное произведение пары векторов, представленных матрицами. Наименьшее значение m , для которого формула устанавливает нетривиальное равенство, равно m = 2; это обсуждается в статье о тождестве Бине-Коши .

В случае n = 3

Позволять ${\boldsymbol {a}},{\boldsymbol {b}},{\boldsymbol {c}},{\boldsymbol {d}},{\boldsymbol {x}},{\boldsymbol {y}},{\boldsymbol {z}},{\boldsymbol {w}}$ быть трехмерными векторами.

${\begin{aligned}&1=1&(m=0)\\[10pt]&{\boldsymbol {a}}\cdot {\boldsymbol {x}}=a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}&(m=1)\\[10pt]&{\begin{vmatrix}{\boldsymbol {a}}\cdot {\boldsymbol {x}}&{\boldsymbol {a}}\cdot {\boldsymbol {y}}\\{\boldsymbol {b}}\cdot {\boldsymbol {x}}&{\boldsymbol {b}}\cdot {\boldsymbol {y}}\end{vmatrix}}\\[4pt]={}&{\begin{vmatrix}a_{2}&a_{3}\\b_{2}&b_{3}\end{vmatrix}}{\begin{vmatrix}x_{2}&y_{2}\\x_{3}&y_{3}\end{vmatrix}}+{\begin{vmatrix}a_{3}&a_{1}\\b_{3}&b_{1}\end{vmatrix}}{\begin{vmatrix}x_{3}&y_{3}\\x_{1}&y_{1}\end{vmatrix}}+{\begin{vmatrix}a_{1}&a_{2}\\b_{1}&b_{2}\end{vmatrix}}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}\\[4pt]={}&({\boldsymbol {a}}\times {\boldsymbol {b}})\cdot ({\boldsymbol {x}}\times {\boldsymbol {y}})&(m=2)\\[10pt]&{\begin{vmatrix}{\boldsymbol {a}}\cdot {\boldsymbol {x}}&{\boldsymbol {a}}\cdot {\boldsymbol {y}}&{\boldsymbol {a}}\cdot {\boldsymbol {z}}\\{\boldsymbol {b}}\cdot {\boldsymbol {x}}&{\boldsymbol {b}}\cdot {\boldsymbol {y}}&{\boldsymbol {b}}\cdot {\boldsymbol {z}}\\{\boldsymbol {c}}\cdot {\boldsymbol {x}}&{\boldsymbol {c}}\cdot {\boldsymbol {y}}&{\boldsymbol {c}}\cdot {\boldsymbol {z}}\end{vmatrix}}={\begin{vmatrix}a_{1}&a_{2}&a_{3}\\b_{1}&b_{2}&b_{3}\\c_{1}&c_{2}&c_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\\x_{3}&y_{3}&z_{3}\end{vmatrix}}\\[4pt]={}&[{\boldsymbol {a}}\cdot ({\boldsymbol {b}}\times {\boldsymbol {c}})][{\boldsymbol {x}}\cdot ({\boldsymbol {y}}\times {\boldsymbol {z}})]&(m=3)\\[10pt]&{\begin{vmatrix}{\boldsymbol {a}}\cdot {\boldsymbol {x}}&{\boldsymbol {a}}\cdot {\boldsymbol {y}}&{\boldsymbol {a}}\cdot {\boldsymbol {z}}&{\boldsymbol {a}}\cdot {\boldsymbol {w}}\\{\boldsymbol {b}}\cdot {\boldsymbol {x}}&{\boldsymbol {b}}\cdot {\boldsymbol {y}}&{\boldsymbol {b}}\cdot {\boldsymbol {z}}&{\boldsymbol {b}}\cdot {\boldsymbol {w}}\\{\boldsymbol {c}}\cdot {\boldsymbol {x}}&{\boldsymbol {c}}\cdot {\boldsymbol {y}}&{\boldsymbol {c}}\cdot {\boldsymbol {z}}&{\boldsymbol {c}}\cdot {\boldsymbol {w}}\\{\boldsymbol {d}}\cdot {\boldsymbol {x}}&{\boldsymbol {d}}\cdot {\boldsymbol {y}}&{\boldsymbol {d}}\cdot {\boldsymbol {z}}&{\boldsymbol {d}}\cdot {\boldsymbol {w}}\end{vmatrix}}=0&(m=4)\end{aligned}}$

В случае m > 3 правая часть всегда равна 0.

Простое доказательство

Следующее простое доказательство опирается на два факта, которые можно доказать несколькими различными способами:

1. Для любого $1\leq k\leq n$ коэффициент $z^{n-k}$ в полиноме $\det(zI_{n}+X)$ представляет собой сумму $k\times k$ основные несовершеннолетние $X$.
2. Если $m\leq n$ и $A$ это $m\times n$ матрица и $B$ а $n\times m$ матрица, тогда

$\det(zI_{n}+BA)=z^{n-m}\det(zI_{m}+AB)$.

Теперь, если сравнить коэффициент $z^{n-m}$ в уравнении $\det(zI_{n}+BA)=z^{n-m}\det(zI_{m}+AB)$, левая часть даст сумму главных миноров $BA$ а правая часть даст постоянный член $\det(zI_{m}+AB)$, что просто $\det(AB)$, что и утверждает формула Коши – Бине, т.е.

${\begin{aligned}&\det(AB)=\sum _{S\in {\tbinom {[n]}{m}}}\det((BA)_{S,S})=\sum _{S\in {\tbinom {[n]}{m}}}\det(B_{S,[m]})\det(A_{[m],S})\\[5pt]={}&\sum _{S\in {\tbinom {[n]}{m}}}\det(A_{[m],S})\det(B_{S,[m]}).\end{aligned}}$

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

Существуют различные виды доказательств формулы Коши-Бине. Приведенное ниже доказательство основано только на формальных манипуляциях и избегает использования какой-либо конкретной интерпретации определителей, которые можно считать определяемыми формулой Лейбница . Используются только их полилинейность по строкам и столбцам и свойство знакочередности (исчезающее при наличии равных строк или столбцов); в частности, мультипликативное свойство определителей квадратных матриц не используется, а скорее устанавливается (случай n = m ). Доказательство справедливо для произвольных коммутативных колец коэффициентов.

Формулу можно доказать в два этапа:

1. используйте тот факт, что обе стороны полилинейны (точнее, 2 и столбцах B , m -линейны) в строках A чтобы свести к случаю , когда каждая строка A и каждый столбец B имеют только одну ненулевую запись, что равно 1.
2. обработайте этот случай, используя функции [ m ] → [ n ], которые сопоставляют соответственно номера строк A с номером столбца их ненулевой записи, а номера столбцов B с номерами строк их ненулевой записи.

На этапе 1 обратите внимание, что для каждой строки A или столбца B и для каждой m -комбинации S значения det( AB ) и det( A _{[ m ], S} )det( BS _{, [ m ]} ) действительно зависят линейно от строки или столбца. Для последнего это непосредственно следует из свойства полилинейности определителя; для первого необходимо дополнительно проверить, что взятие линейной комбинации для строки A или столбца B, оставляя все остальное неизменным, влияет только на соответствующую строку или столбец произведения AB , причем на ту же линейную комбинацию. Таким образом, можно вычислить обе части формулы Коши-Бине линейно для каждой строки A , а затем также для каждого столбца B , записывая каждую из строк и столбцов как линейную комбинацию стандартных базисных векторов. Получающиеся в результате множественные суммирования огромны, но они имеют одинаковую форму для обеих сторон: соответствующие члены включают в себя один и тот же скалярный коэффициент (каждый является продуктом записей A и B ), и эти члены отличаются только тем, что включают в себя два разных выражения в терминах константных матриц описанного выше вида, выражения которых должны быть равны согласно формуле Коши-Бине. Этим достигается сокращение первой ступени.

Конкретно, множественные суммирования можно сгруппировать в два суммирования: одно по всем функциям f :[ m ] → [ n ], которое для каждого индекса строки A дает соответствующий индекс столбца, и одно по всем функциям g :[ m ] → [ n ], который для каждого индекса столбца B дает соответствующий индекс строки. Матрицы, связанные с f и g, равны

$L_{f}={\bigl (}(\delta _{f(i),j})_{i\in [m],j\in [n]}{\bigr )}\quad {\text{and}}\quad R_{g}={\bigl (}(\delta _{j,g(k)})_{j\in [n],k\in [m]}{\bigr )}$

где " $\delta$" — это дельта Кронекера , а формула Коши-Бине, которую нужно доказать, была переписана как

${\begin{aligned}&\sum _{f:[m]\to [n]}\sum _{g:[m]\to [n]}p(f,g)\det(L_{f}R_{g})\\[5pt]={}&\sum _{f:[m]\to [n]}\sum _{g:[m]\to [n]}p(f,g)\sum _{S\in {\tbinom {[n]}{m}}}\det((L_{f})_{[m],S})\det((R_{g})_{S,[m]}),\end{aligned}}$

где p ( f , g ) обозначает скалярный коэффициент $\textstyle (\prod _{i=1}^{m}A_{i,f(i)})(\prod _{k=1}^{m}B_{g(k),k})$. Осталось доказать формулу Коши-Бине для = Lf и _для B = Rg , _g всех f , m :[ A ] → [ n ].

этом шаге 2, если f не может быть инъективным, то и _и LfRg имеют _На Rg _не две одинаковые строки, а если g может быть инъективным, то имеют _​​LfRg два одинаковых _по Lf _{столбца} ; в любом случае обе части тождества равны нулю. Предположим теперь, что и f, и g являются инъективными отображениями [ m ] → [ n ], фактор $\det((L_{f})_{[m],S})$ справа равно нулю, если только S = f ([ m ]), а множитель $\det((R_{g})_{S,[m]})$ равен нулю, если только S = g ([ m ]). Так если изображения f и g различны, правая часть имеет только нулевые члены, а левая часть также равна нулю, поскольку L _f R _g имеет нулевую строку (для i с $f(i)\notin g([m])$). В оставшемся случае, когда образы f и g совпадают, скажем, f ([ m ]) = S = g ([ m ]), нам нужно доказать, что

$\det(L_{f}R_{g})=\det((L_{f})_{[m],S})\det((R_{g})_{S,[m]}).\,$

Пусть h — единственная возрастающая биекция [ m ] → S , а π , σ — перестановки [ m ] такие, что $f=h\circ \pi ^{-1}$ и $g=h\circ \sigma$; затем $(L_{f})_{[m],S}$ - матрица перестановок для π , $(R_{g})_{S,[m]}$ — матрица перестановок для σ , а L _f R _g — матрица перестановок для $\pi \circ \sigma$, и поскольку определитель матрицы перестановки равен сигнатуре перестановки, тождество следует из того факта, что сигнатуры мультипликативны.

Использование полилинейности как по отношению к строкам A , так и по столбцам B в доказательстве не является необходимым; можно использовать только один из них, скажем первый, и использовать то, что матричное произведение L _f B либо состоит из перестановки строк B _{f ([ m ]), [ m ]} (если f инъективно), либо имеет не менее двух равных рядов.

Связь с обобщенной дельтой Кронекера

Как мы видели, формула Коши–Бине эквивалентна следующему:

$\det(L_{f}R_{g})=\sum _{S\in {\tbinom {[n]}{m}}}\det((L_{f})_{[m],S})\det((R_{g})_{S,[m]}),$

где

$L_{f}={\bigl (}(\delta _{f(i),j})_{i\in [m],j\in [n]}{\bigr )}\quad {\text{and}}\quad R_{g}={\bigl (}(\delta _{j,g(k)})_{j\in [n],k\in [m]}{\bigr )}.$

Используя обобщенную дельту Кронекера , мы можем вывести формулу, эквивалентную формуле Коши – Бине:

$\delta _{g(1)\dots g(m)}^{f(1)\dots f(m)}=\sum _{k:[m]\to [n] \atop k(1)<\dots <k(m)}\delta _{k(1)\dots k(m)}^{f(1)\dots f(m)}\delta _{g(1)\dots g(m)}^{k(1)\dots k(m)}.$

Геометрические интерпретации

Если A — действительная матрица размера m × n , то det( A   A ^Т ) равен квадрату m -мерного объема параллелоэдра, натянутого в R ^н по m строк А. ​Формула Бине утверждает, что она равна сумме квадратов объемов, возникающих, если параллелепипед ортогонально спроецировать на m -мерные координатные плоскости (из которых имеются ${\tbinom {n}{m}}$).

В случае m = 1 параллелоэдр сводится к одному вектору, а его объем равен его длине. Затем в приведенном выше утверждении говорится, что квадрат длины вектора представляет собой сумму квадратов его координат; это действительно так по определению этой длины, основанному на теореме Пифагора .

В тензорной алгебре , учитывая пространство внутреннего произведения $V$ размерности n формула Коши–Бине определяет индуцированное скалярное произведение на внешней алгебре $\wedge ^{m}V$, а именно:

$\langle v_{1}\wedge \cdots \wedge v_{m},w_{1}\wedge \cdots \wedge w_{m}\rangle =\det \left(\langle v_{i},w_{j}\rangle \right)_{i,j=1}^{m}.$

Обобщение

Формулу Коши-Бине можно напрямую расширить до общей формулы для миноров произведения двух матриц. Контекст формулы дан в статье о минорах , но идея состоит в том, что и формула обычного умножения матриц , и формула Коши – Бине для определителя произведения двух матриц являются частными случаями следующего общего утверждения о минорах. произведения двух матриц. Предположим, что A — матрица размера m × n , B — матрица размера n × p , I — подмножество {1,..., m } с k элементами, а J — подмножество {1,..., p }. с k элементами. Затем

$[\mathbf {AB} ]_{I,J}=\sum _{K}[\mathbf {A} ]_{I,K}[\mathbf {B} ]_{K,J}\,$

где сумма распространяется на все подмножества K из {1,..., n } с k элементами.

Непрерывная версия

Непрерывная версия формулы Коши – Бине, известная как Андреефа – Гейне . тождество или тождество Андрефа обычно появляется в теории случайных матриц. Утверждается так: пусть $\left\{f_{j}(x)\right\}_{j=1}^{N}$ и $\left\{g_{j}(x)\right\}_{j=1}^{N}$ — две последовательности интегрируемых функций, поддерживаемые на $I$. Затем

$\int _{I}\cdots \int _{I}\det \left[f_{j}(x_{k})\right]_{j,k=1}^{N}\det \left[g_{j}(x_{k})\right]_{j,k=1}^{N}dx_{1}\cdots dx_{N}=N!\,\det \left[\int _{I}f_{j}(x)g_{k}(x)dx\right]_{j,k=1}^{N}.$

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

Позволять $S_{N}$ группа перестановок порядка N, $|s|$ быть знаком перестановки, $\langle f,g\rangle =\int _{I}f(x)g(x)dx$ быть «внутренним продуктом». $${\begin{aligned}{\text{left side}}&=\sum _{s,s'\in S_{N}}(-1)^{|s|+|s'|}\int _{I^{N}}\prod _{j}f_{s(j)}(x_{j})\prod _{k}g_{s'(k)}(x_{k})\\&=\sum _{s,s'\in S_{N}}(-1)^{|s|+|s'|}\int _{I^{N}}\prod _{j}f_{s(j)}(x_{j})g_{s'(j)}(x_{j})\\&=\sum _{s,s'\in S_{N}}(-1)^{|s|+|s'|}\prod _{j}\int _{I}f_{s(j)}(x_{j})g_{s'(j)}(x_{j})dx_{j}\\&=\sum _{s,s'\in S_{N}}(-1)^{|s|+|s'|}\prod _{j}\langle f_{s(j)},g_{s'(j)}\rangle \\&=\sum _{s'\in S_{N}}(-1)^{|s'|+|s'|}\sum _{s\in S_{N}}(-1)^{|s|+|s'^{-1}|}\prod _{j}\langle f_{(s\circ s'^{-1})(j)},g_{j}\rangle \\&=\sum _{s'\in S_{N}}\sum _{s\in S_{N}}(-1)^{|s\circ s'^{-1}|}\prod _{j}\langle f_{(s\circ s'^{-1})(j)},g_{j}\rangle \\&={\text{right side}}\\\end{aligned}}$$

Форрестер описывает, как восстановить обычную формулу Коши – Бине как дискретизацию приведенного выше тождества.

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

Выбирать $t_{1}<\cdots <t_{m}$ в $[0,1]$, выбирать $f_{1},\ldots ,g_{n}$, такой, что $f_{j}(t_{k})=A_{j,k}$ и то же самое справедливо для $g$ и $B$. Сейчас подключаюсь $f_{j}(x_{k})\sum _{l}\delta (x_{k}-t_{l})$ и $g_{j}(x_{k})$ в тождество Андреева и упростив обе части, получим: $$\sum _{l_{1},\ldots ,l_{n}\in [1:m]}\det[f_{j}(t_{l_{k}})]\det[g_{j}(t_{l_{k}})]=n!\det \left[\sum _{l}f_{j}(t_{l})g_{k}(t_{l})\right]$$ Правая сторона $n!\det(AB)$, а левая сторона $n!\sum _{S\subset [1:m],|S|=n}\det(A_{[1:m],S})\det(B_{S,[1:m]})$.

Ссылки

• Джоэл Г. Бройда и С. Гилл Уильямсон (1989) Всестороннее введение в линейную алгебру , §4.6 Теорема Коши-Бине, стр. 208–14, Аддисон-Уэсли ISBN   0-201-50065-5 .
• Джин Хо Квак и Сунгпё Хонг (2004) Линейная алгебра, 2-е издание, пример 2.15, формула Бине-Коши, стр. 66,7, Birkhäuser ISBN   0-8176-4294-3 .
• И.Р. Шафаревич и А.О. Ремизов (2012) Линейная алгебра и геометрия , §2.9 (стр. 68) и §10.5 (стр. 377), Springer ISBN   978-3-642-30993-9 .
• М. Л. Мехта (2004) Случайные матрицы , 3-е изд., Elsevier ISBN   9780120884094 .