Rumus Cauchy–Binet

Dalam matematika, khususnya aljabar linear, rumus Cauchy–Binet, dinamakan oleh Augustin-Louis Cauchy dan Jacques Philippe Marie Binet, adalah sebuah identitas determinan untuk hasil perkalian dua matriks yang dimensinya saling transpos (sehingga hasil kalinya terdefinisi dengan baik dan berupa matriks persegi). Identitas tersebut memperumum pernyataan bahwa determinan dari hasil perkalian matriks persegi, bernilai sama dengan hasil perkalian determinan-determinannya. Identitas ini berlaku untuk matriks yang setiap elemennya berasal sebarang gelanggang komutatif.

Pernyataan

Misalkan $A$ adalah sebuah matriks $m\!\times \!n$ dan $B$ adalah sebuah matriks $n\!\times \!m$. Misalkan pula $[n]$ menyatakan himpunan $\{1,\dots ,n\}$, dan ${\textstyle {\binom {[n]}{m}}}$ menyatakan himpunan kombinasi-$m$ dari $[n]$ (yaitu, himpunan bagian berukuran $m$ dari $[n]$; yang banyaknya ada ${\textstyle {\binom {n}{m}}}$). Untuk ${\textstyle S\in {\binom {[n]}{m}}}$, tulis $A_{[m],S}$ sebagai matriks $m\times m$ yang kolomnya merupakan kolom matriks $A$ pada indeks dari $S$, dan $B_{S,[m]}$ untuk matriks $m\times m$ yang barisnya merupakan baris matriks $B$ pada indeks dari $S$. Rumus Cauchy–Binet kemudian menyatakan

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

Sebagai contoh, anggap $m=2$ dan $n=3$, dan matriks $A={\begin{pmatrix}1&1&2\\3&1&-1\end{pmatrix}}$ dan matriks :$B={\begin{pmatrix}1&1\\3&1\\0&2\end{pmatrix}}$. Ruas kanan dari rumus Cauchy–Binet memberikan determinan

${\begin{aligned}\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|\\&=-2\times (-2)+(-3)\times 6+(-7)\times 2\\&=-28\end{aligned}}$

Hasilnya sama dengan nilai determinan dari $AB={\begin{pmatrix}4&6\\6&2\end{pmatrix}}$, yakni $-28$ .

Kasus khusus

Jika $n<m$ maka ${\textstyle {\binom {[n]}{m}}}$ adalah himpunan kosong, dan rumus tersebut mengatakan bahwa $\det(AB)=0$ (karena ruas kanannya adalah sebuah jumlah kosong). Hal tersebut benar, karena pada kasus ini, rank dari matriks $AB$ berukuran $m\!\times \!m$ maksimum bernilai $n$, yang menyiratkan bahwa determinannya bernilai nol.

Jika $n=m$, yakni kasus ketika $A$ dan $B$ merupakan matriks persegi, ${\textstyle {\binom {[n]}{m}}=\{[n]\}}$ (sebuah himpunan singleton). Jadi penjumlahan di ruas kanan hanya melibatkan $S=[n]$, sehingga rumusnya menyatakan bahwa $\det(AB)=\det(A)\det(B)$.

Untuk kasus $m=0$, $A$ dan $B$ adalah matriks kosong (tetapi dengan bentuk yang berbeda jika $n>0$), begitu pula dengan hasil kalinya, $AB$. Dalam kasus ini, penjumlahan di ruas kanan hanya melibatkan sebuah suku $S=\varnothing$. Rumus tersebut menyatakan $1=1$, karena determinan dari matriks $0\!\times \!0$ adalah $1$. Untuk $m=1$, ${\textstyle {\binom {[n]}{1}}}$ berisi $n$ singleton yang berbeda dari $[n]$, sehingga kedua ruas dari rumus tersebut memiliki bentuk $\sum _{j=1}^{n}A_{1,j}B_{j,1}$; yakni produk dot dari pasangan vektor pada matriks. Nilai $m$ terkecil sehingga rumus Cauchy–Binet menghasilkan sebuah persamaan yang tidak sederhana adalah $m=2$; hal ini dibahas dalam artikel pada identitas Binet–Cauchy.

Kasus n=3

Berikut adalah bentuk dari rumus Cauchy–Binet untuk $n=3$. Misalkan ${\boldsymbol {a,b,c,d,x,y,z,w}}$ adalah vektor tiga dimensi,

Nilai $m$	Rumus Cauchy–Binet
$m=0$	$1=1$
$m=1$	${\boldsymbol {a}}\cdot {\boldsymbol {x}}=a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}$
$m=2$	${\begin{aligned}{\begin{vmatrix}{\boldsymbol {a}}\cdot {\boldsymbol {x}}&{\boldsymbol {a}}\cdot {\boldsymbol {y}}\\{\boldsymbol {b}}\cdot {\boldsymbol {x}}&{\boldsymbol {b}}\cdot {\boldsymbol {y}}\end{vmatrix}}&={\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}}\\&=({\boldsymbol {a}}\times {\boldsymbol {b}})\cdot ({\boldsymbol {x}}\times {\boldsymbol {y}})\end{aligned}}$
$m=3$	${\begin{aligned}{\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}}\\&=[{\boldsymbol {a}}\cdot ({\boldsymbol {b}}\times {\boldsymbol {c}})][{\boldsymbol {x}}\cdot ({\boldsymbol {y}}\times {\boldsymbol {z}})]\end{aligned}}$
$m=4$	${\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$

Dalam kasus $m>3$, ruas kanan selalu sama dengan 0.

Bukti sederhana

Bukti sederhana berikut bergantung pada dua fakta yang dapat dibuktikan dalam beberapa cara yang berbeda:

1. Untuk setiap $1\leq k\leq n$, koefisien dari $z^{n-k}$ dalam polinomial $\det(zI_{n}+X)$ adalah jumlah dari minor utama berukuran $k\!\times \!k$ dari $X$.
2. Jika $m\leq n$ dan $A$ adalah sebuah matriks $m\!\times \!n$ dan $B$ adalah sebuah matriks $n\!\times \!m$, maka $\det(zI_{n}+BA)=z^{n-m}\det(zI_{m}+AB)$

Sekarang, jika kita membandingkan koefisien $z^{n-m}$ dalam persamaan $\det(zI_{n}+BA)=z^{n-m}\det(zI_{m}+AB)$, ruas kiri akan memberikan jumlah dari minor utama $BA$ sedangkan ruas kanan akan memberikan suku tetap dari $\det(zI_{m}+AB)$. Suku tetap ini tidak lain adalah $\det(AB)$, yang rumus Cauchy–Binet nyatakan; dengan kata lain:

${\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})\\&=\sum _{S\in {\tbinom {[n]}{m}}}\det(A_{[m],S})\det(B_{S,[m]})\end{aligned}}$

Bukti

Terdapat beragam jenis bukti yang dapat diberikan untuk rumus Cauchy–Binet. Bukti berikut didasarkan hanya pada manipulasi formal, dan menghindari menggunakan interpretasi tertentu dari determinan, selain yang didefinisikan oleh rumus Leibniz. Bukti ini hanya menggunakan sifat multilinearitas pada baris dan kolom, dan sifat alternating mereka (bernilai nol jika ada baris atau kolom yang sama). Sifat perkalian determinan untuk matriks persegi tidak digunakan, namun dianggap sudah dibuktikan (untuk kasus $n=m$). Bukti ini sah untuk sebarang gelanggang koefisien komutatif.

Rumus Cauchy–Binet dapat dibuktikan dalam dua langkah:

1. Menggunakan fakta bahwa kedua ruas adalah multilinear (lebih tepatnya linear $2m$) dalam baris $A$ dan kolom $B$, untuk mengurangi kasus tersebut bahwa setiap baris $A$ dan setiap kolom $B$ hanya memiliki satu entri tak nol, yaitu 1.
2. Tangani kasus itu menggunakan fungsi $[m]\to [n]$ bahwa memetakan masing-masing bilangan baris $A$ ke bilangan kolom entri tak nolnya, dan bilangan kolom $B$ ke bilangan baris entri tak nolnya.

Untuk langkah 1, amati bahwa untuk setiap baris $A$ atau kolom $B$, dan untuk setiap kombinasi-$m$ dari $S$, nilai $\det(AB)$ dan $\det(A_{[m],S})\det(B_{S,[m]})$ memang tergantung secara linear pada baris atau kolom. Untuk yang terakhir, ini langsung dari sifat multinlinear dari determinan, untuk yang pertama salah satunya harus dalam penjumlahan diperiksa bahwa mengambil sebuah kombinasi linear untuk baris $A$ atau kolom $B$ sementara meninggalkan sisanya hanya tidak berubah hanya mempengaruhi baris dan kolom yang sesuai dan dengan kombinasi lienar yang sama. Jadi salah satu dapat bekerja pada kedua ruas dari rumus Cauchy–Binet dengan secara ilnear untuk setiap baris $A$ atau kolom $B$, menulis setiap baris dan kolom sebagai sebuah kombinasi linear vektor basis standar. Hasil banyak penjumlahan sangatlah besar , tetapi mereka memiliki bentuk yang sama untuk kedua ruas; istilah yang sesuai melibatkan faktor skalar yang sama (setiap tersebut adalah sebuah hasil kali entri-entri $A$ dan $B$), dan istilah-istilah ini hanya berbeda dengan melibatkan dua ekspresi yang berbeda dalam istilah matriks konstanta dari jenis yang digambarkan di atas, yang ekspresi-ekspresi tersebut harus sama menurut rumus Cauchy–Binet. Ini mencapai pengurangan dari langkah pertama

Secara konkret, banyak penjumlahan dapat dikelompokkan menjadi dua penjumlahan, salah satunya dari semua fungsi $f:[m]\to [n]$ yang untuk setiap indeks baris $A$ memberikan sebuah indeks kolom yang sesuai, dan salah satunya dari fungsi $g:[m]\to [n]$ yang untuk semua indeks kolom $B$ memberikan sebuah indeks baris yang sesuai. matriks tersebut yang terkait dengan $f$ dan $g$ adalah

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

dimana "$\delta$" adalah delta Kronecker, dan rumus Cauchy–Binet untuk dibuktikan telah ditulis ulang sebagai

$\sum _{f:[m]\to [n]}\sum _{g:[m]\to [n]}p(f,g)\det(L_{f}R_{g})=\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]})$

dimana $p(f,g)$ melambangkan faktor skalar

$\prod _{i=1}^{m}A_{i,f(i)})(\prod _{k=1}^{m}B_{g(k),k})$

Ini masih harus dibuktikan rumus Cauchy–Binet untuk $A=L_{f}$ dan $B=R_{g}$, untuk semua $f,g:[m]\to [n]$.

Untuk langkah 2, jika $f$ gagal injektif maka $L_{f}$ dan $L_{f}R_{g}$ keduanya memiliki dua baris identik, dan jika $g$ gagal injektif maka $R_{g}$ dan $L_{f}R_{g}$ keduanya memiliki dua kolom identik, dalam kedua kasus tersebut kedua ruas dari identitasnya adalah nol. Seandainya sekarang bahwa $f$ dan $g$ merupakan injekif memetakan $[m]\to [n]$, faktor $\det((L_{f})_{[m],S})$ pada ruas kanan adalah nol kecuali $S=f([m])$, sedangkan faktor $\det((R_{g})_{S,[m]})$ adalah nol kecuali $S=g([m])$. Jadi jika gambar $f$ dan $g$ berbeda, ruas kanan hanya memiliki istilah kosong, dan ruas kiri adalah nol juga karena $L_{f}R_{g}$ memiliki sebuah baris nol (untuk $i$ dengan $f(i)\notin g([m])$). Dalam kasus selanjutnya dimana gambar-gambar $f$ dan $g$ adalah sama, katakan $f([m])=S=g([m])$, kita harus buktikan bahwa

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

Misalkan $h$ adalah tunggal yang meningkatkan bijeksi $[m]\to S$, dan $\pi ,\sigma$ adalah permutasi $[m]$ seperti $f=h\circ \pi ^{-1}$ dan $g=h\circ \sigma$, maka $(L_{f})_{[m],S}$ adalah matriks permutasi untuk $\pi$, $(R_{g})_{S,[m]}$ adalah matriks permutasi untuk $\sigma$, dan $L_{f}R_{g}$ adalah matriks permutasi untuk $\pi \circ \sigma$, dan karena determinannya dari sebuahmatriks permutasi sama dengan tanda tangan dari permutasinya, identitas tersebut mengikuti dari fakta bahwa tanda tangan adalah perkalian.

Menggunakan multi-linearitas berkenaan dengan baris $A$ dan kolom $B$ dalam bukti tidak diperlukan, salah satunya dapat menggunakan hanya salah satu dari mereka, katakan yang pertama, dan menggunakan sebuah hasil kali matriks $L_{f}B$ terdiri dari sebuah pemrutasi dari baris $B_{f([m]),[m]}$ (jika $f$ injektif), atau memiliki setidaknya dua baris yang sama.

Relasi ke delta Kronecker yang digeneralisasi

Seperti yang telah kita lihat, rumus Cauchy–Binet setara dengan berikut ini:

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

dimana

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

Dalam istilah delta Kronecker yang digeneralisasi, kita dapat turunkan rumus tersebut setara dengan rumus Cauchy–Binet:

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

Interpretasi geometrik

Jika $A$ adalah sebuah matriks $m\!\times \!n$ riil, maka $\det(AA^{\mathbf {T} })$ sama dengan persegi dari volume $m$-dimensi dari paralelotop rentang di $\mathbf {R} ^{n}$ oleh baris $m$ dari $A$. Rumus Binet menyatakan bahwa ini sama dengan jumlah persegi-persegi dari volume-volume yang muncul jika paraleliped secara ortogonal diproyeksikan ke bidang koordinat $m$-dimensi (yang ada ${\textstyle {\binom {n}{m}}}$).

Dalam kasus $m=1$, paralelotop berkurang menjadi sebuah vektor tunggal dan volumenya adalah panjangnya. Pernyataan di atas kemudian menyatakan bahwa persegi dari panjang sebuah vektor adalah jumlah dari persegi koordinatnya; ini memang kasus oleh definisi dari panjangnya, yang berdasarkan pada teorema Pythagoras.

Generalisasi

Rumus Cauchy–Binet dapat diperpanjang dalam sebuah cara yang terus terang pada sebuah rumus yang umum untuk minor dari hasil kali dua matriks. Konteks untuk rumus diberikan dalam artikel pada minor, tetapi idenya adalah bahwa kedua rumus tersebut untuk perkalian matriks biasa dan rumus Cauchy–Binet untuk determinan dari hasil kali dua matriks merupakan kasus yang khusus pada pernyataan umum berikut mengenai minor dari sebuah hasi kali dua matriks. Andaikan bahwa $\mathbf {A}$ adalah sebuah matriks $m\!\times \!n$, $\mathbf {B}$ adalah sebuah matriks $n\!\times \!p$, $I$ adalah himpunan bagian $\{1,\dots ,m\}$ dengan elemen $k$ dan $J$ adalah sebuah himpunan bagian $\{1,\dots ,p\}$ dengan elemen $k$. Maka

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

dimana jumlah tersebut memperpanjang dari semua himpunan bagian $K$ dari $\{1,\dots ,n\}$ dengan

Versi kontinu

Sebuah versi kontinu rumus Cauchy–Binet, dikenal sebagai identitas Andréief–Heine atau identitas Andréief muncul secara umum dalam teori matriks acak. Ini dinyatakan sebagai berikut: misal $\{f_{j}(x)\}_{j=0}^{N-1}$ dan $\{g_{j}(x)\}_{j=0}^{N-1}$ adalah dua barisan fungsi terintegralkan, disokong pada $I$. Maka

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

Forrester menggambarkan bagaimana memulihkan rumus Cauchy–Binet biasa sebagai sebuah diskretisasi dari identitas di atas.

Referensi

• Joel G. Broida & S. Gill Williamson (1989) A Comprehensive Introduction to Linear Algebra, §4.6 Cauchy-Binet theorem, pp 208–14, Addison-Wesley ISBN 0-201-50065-5.
• Jin Ho Kwak & Sungpyo Hong (2004) Linear Algebra 2nd edition, Example 2.15 Binet-Cauchy formula, pp 66,7, Birkhäuser ISBN 0-8176-4294-3.
• I. R. Shafarevich & A. O. Remizov (2012) Linear Algebra and Geometry, §2.9 (hal. 68) & §10.5 (hal. 377), Springer ISBN 978-3-642-30993-9.
• M.L. Mehta (2004) Random matrices, 3erd ed., Elsevier ISBN 9780120884094

Pranala luar

• Aaron Lauve (2004) A short combinatoric proof of Cauchy–Binet formula Diarsipkan 2019-03-04 di Wayback Machine. from Université du Québec à Montréal.
• Peter J. Forrester (2018) Meet Andréief, Bordeaux 1886, and Andreev, Kharkov 1882–83