Kaidah Cramer

Dalam aljabar linear, kaidah Cramer adalah rumus yang dapat digunakan untuk menyelesaikan sistem persamaan linear dengan banyak persamaan sama dengan banyak variabel, dan berlaku ketika sistem tersebut memiliki solusi yang tunggal. Rumus ini menyatakan solusi dengan menggunakan determinan matriks koefisien (dari sistem persamaan) dan determinan matriks lain yang diperoleh dengan mengganti salah satu kolom matriks koefisien dengan vektor yang berada sebelah kanan persamaan. Metode ini dinamai dari matematikawan Swiss Gabriel Cramer (1704–1752), yang pada tahun 1750 menerbitkan kaidah ini untuk sebarang banyaknya variabel,^[1][2] walau Colin Maclaurin juga menerbitkan kasus khusus dari kaidah ini pada tahun 1748^[3] (dan mungkin ia sudah mengetahuinya sejak 1729).^[4][5][6]

Kaidah Cramer yang digunakan dengan naif (apa adanya) tidak efisien secara komputasi untuk sistem dengan lebih dari dua atau tiga persamaan.^[7] Untuk kasus dengan n persamaan dalam n variabel, rumus ini perlu menghitung n + 1 nilai determinan, sedangkan eliminasi Gauss menghasilkan solusi yang sama dengan kompleksitas komputasi yang setara dengan menghitung satu nilai determinan.^[8][9] Kaidah Cramer juga dapat tidak stabil secara numerik bahkan untuk sistem ukuran 2×2.^[10] Namun, belakangan ini berhasil dibuktikan bahwa kaidah Cramer dapat diterapkan dalam kompleksitas waktu O(n³).^[11] Hal ini membuatnya dapat disandingkan dengan metode-metode yang lebih umum untuk menyelesaikan sistem persamaan linear (seperti eliminasi Gauss), dan juga dapat disandingkan dalam hal kestabilan numerik pada kebanyakan kasus.

Kasus umum

Pertimbangkan sistem ${\displaystyle n}$ persamaan linear dengan ${\displaystyle n}$ variabel, yang direpresentasikan dalam bentuk perkalian matriks sebagai:

${\displaystyle A\mathbf {x} =\mathbf {b} }$

dengan matriks ${\displaystyle A}$ berukuran ${\displaystyle n\times n}$ memiliki determinan bukan nol, dan vektor ${\displaystyle x=(x_{1},\ldots ,x_{n})^{\mathsf {T}}}$ adalah vektor kolom dari variabel. Teorema menyatakan bahwa sistem memiliki solusi unik dalam keadaan ini, dengan nilai untuk setiap variabel diberikan oleh:

${\displaystyle x_{i}={\frac {\det(A_{i})}{\det(A)}}\qquad i=1,\ldots ,n}$

dimana ${\displaystyle A_{i}}$ adalah matriks yang dibentuk dengan mengganti kolom ke-${\displaystyle i}$ dari ${\displaystyle A}$ dengan vektor kolom ${\displaystyle b}$.

Versi yang lebih umum dari kaidah Cramer^[12] mempertimbangkan persamaan matriks

${\displaystyle AX=B}$

Dimana A adalah matriks ${\displaystyle n\times n}$ yang memiliki determinan bukan nol, sedangkan ${\displaystyle X}$ dan ${\displaystyle B}$ adalah matriks ${\displaystyle n\times m}$. Untuk sebuah barisan ${\displaystyle 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n}$ dan ${\displaystyle 1\leq j_{1}<j_{2}<\ldots <j_{k}\leq m}$, misalkan ${\displaystyle X_{I,J}}$ sebagai submatriks ukuran ${\displaystyle k\times k}$ yang berisi baris ${\displaystyle I:=(i_{1},\ldots ,i_{k})}$ dan kolom ${\displaystyle J:=(j_{1},\ldots ,j_{k})}$ dari matriks ${\displaystyle X}$. Misalkan pula ${\displaystyle A_{B}(I,J)}$ sebagai matriks ${\displaystyle n\times n}$ yang dibentuk dengan mengganti kolom ke-${\displaystyle i_{s}}$ matriks ${\displaystyle A}$ dengan kolom ke-${\displaystyle j_{s}}$ matriks ${\displaystyle B}$, untuk semua ${\displaystyle s=1,\ldots ,k}$. Kemudian

${\displaystyle \det X_{I,J}={\frac {\det(A_{B}(I,J))}{\det(A)}}.}$

Dalam kasus ${\displaystyle k=1}$, persamaan tersebut adalah kaidah Cramer yang normal.

Kaidah Cramer berlaku untuk sistem persamaan dengan koefisien dan variabel di sebarang lapangan, tidak hanya di bilangan real.

Contoh

Berikut adalah sistem persamaan linear:

${\displaystyle \left\{{\begin{matrix}a_{1}x+b_{1}y&={\color {red}c_{1}}\\a_{2}x+b_{2}y&={\color {red}c_{2}}\end{matrix}}\right.}$

Matriks persamaan ini adalah:

${\displaystyle {\begin{bmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}{\color {red}c_{1}}\\{\color {red}c_{2}}\end{bmatrix}}.}$

Apabila a₁b₂ − b₁a₂ bukan nol, maka x dan y dapat dicari dengan menggunakan determinan matriks tersebut:

${\displaystyle {\begin{aligned}x&={\frac {\begin{vmatrix}{\color {red}{c_{1}}}&b_{1}\\{\color {red}{c_{2}}}&b_{2}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{vmatrix}}}={{\color {red}c_{1}}b_{2}-b_{1}{\color {red}c_{2}} \over a_{1}b_{2}-b_{1}a_{2}},\quad y={\frac {\begin{vmatrix}a_{1}&{\color {red}{c_{1}}}\\a_{2}&{\color {red}{c_{2}}}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{vmatrix}}}={a_{1}{\color {red}c_{2}}-{\color {red}c_{1}}a_{2} \over a_{1}b_{2}-b_{1}a_{2}}\end{aligned}}.}$

Untuk matriks 3 × 3, caranya sama:

${\displaystyle \left\{{\begin{matrix}a_{1}x+b_{1}y+c_{1}z&={\color {red}d_{1}}\\a_{2}x+b_{2}y+c_{2}z&={\color {red}d_{2}}\\a_{3}x+b_{3}y+c_{3}z&={\color {red}d_{3}}\end{matrix}}\right.}$

Persamaan ini dalam bentuk matriks adalah sebagai berikut:

${\displaystyle {\begin{bmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}{\color {red}d_{1}}\\{\color {red}d_{2}}\\{\color {red}d_{3}}\end{bmatrix}}.}$

Kemudian nilai x, y dan z dapat dicari dengan rumus berikut:

${\displaystyle x={\frac {\begin{vmatrix}{\color {red}d_{1}}&b_{1}&c_{1}\\{\color {red}d_{2}}&b_{2}&c_{2}\\{\color {red}d_{3}}&b_{3}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},\quad y={\frac {\begin{vmatrix}a_{1}&{\color {red}d_{1}}&c_{1}\\a_{2}&{\color {red}d_{2}}&c_{2}\\a_{3}&{\color {red}d_{3}}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},{\text{ dan }}z={\frac {\begin{vmatrix}a_{1}&b_{1}&{\color {red}d_{1}}\\a_{2}&b_{2}&{\color {red}d_{2}}\\a_{3}&b_{3}&{\color {red}d_{3}}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}}.}$

Bukti

Bukti untuk kaidah Cramer didasarkan pada sifat dari determinan: linearitas terhadap setiap kolom, dan fakta bahwa determinan bernilai nol jika terdapat dua kolom yang sama (tersirat dari sifat tanda determinan yang berubah ketika terjadi penukaran dua kolom matriks).

Pilih sebarang kolom ke-j dari sebuah matriks. Linearitas mengartikan jika kita menganggap hanya kolom ke-j sebagai variabel,^[13] fungsi ${\displaystyle \mathbb {R} ^{n}\to \mathbb {R} }$ yang dihasilkan (dengan asumsi elemen matriks adalah anggota ${\displaystyle \mathbb {R} }$) dapat ditulis sebagai perkalian sebuah matriks, dengan satu baris dan n kolom, dengan kolom ke-j. Faktanya, ini yang dilakukan oleh ekspansi Laplace, yang menyatakan ${\displaystyle \operatorname {det} (A)=C_{1}a_{1,j}+\dots +C_{n}a_{n,j}}$ dengan koefisien ${\displaystyle C_{1},\,\dots ,C_{n}}$^[14] bergantung pada kolom-kolom matriks ${\displaystyle A}$ selain kolom ke-j. Nilai ${\displaystyle \operatorname {det} (A)}$ juga dapat ditulis sebagai perkalian matriks satu-baris ${\displaystyle L_{(j)}=[C_{1}\ \ \dots \ \ C_{n}]}$ dengan kolom ke-j dari ${\displaystyle A}$. Jika ${\displaystyle L_{(j)}}$ dikalikan dengan kolom lain dari ${\displaystyle A}$, misal kolom ke-k, hal ini sama mengganti kolom ke-j dengan kolom ke-k. Pada kasus ini determinan akan bernilai 0 (sifat determinan jika terdapat dua kolom yang sama).

Selanjutnya perhatikan sistem n persamaan linear dengan n variabel, dengan ${\displaystyle A}$ sebagai matriks koefisien, dan ${\displaystyle \operatorname {det} (A)}$ diasumsikan tidak bernilai nol:

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}&=&b_{2}\\&\vdots &\\a_{n1}x_{1}+a_{n2}x_{2}+\cdots +a_{nn}x_{n}&=&b_{n}.\end{matrix}}}$

Lalu bentuk persamaan "gabungan" dari menjumlahkan persamaan pertama dikali ${\displaystyle C_{1}}$, dengan persamaan kedua dikali ${\displaystyle C_{2}}$, dan seterusnya, sampai persamaan terakhir dikali ${\displaystyle C_{n}}$. Koefisien untuk variabel ${\displaystyle x_{j}}$ pada persamaan ini adalah

${\displaystyle C_{1}a_{1,j}+\dots +C_{n}a_{n,j}=\operatorname {det} (A)}$

sedangkan koefisien untuk variabel lainnya akan bernilai 0; sehingga ekspresi di ruas kiri persamaan hanyalah ${\displaystyle \operatorname {det} (A)x_{j}}$. Sedangkan, ruas kanan memiliki bentuk ${\displaystyle C_{1}b_{1}+\dots +C_{n}b_{n}}$, yang sama dengan mengalikan ${\displaystyle L_{(j)}}$ dengan vektor kolom ${\displaystyle \mathbf {b} }$. Faktanya, proses yang kita lakukan sama dengan mengalikan persamaan ${\displaystyle A\mathbf {x} =\mathbf {b} }$ dengan ${\displaystyle L_{(j)}}$ dari kiri. Membagi kedua ruas dengan ${\displaystyle \operatorname {det} (A)}$ akan menghasilkan persamaan berikut:

${\displaystyle x_{j}={\frac {L_{(j)}\cdot \mathbf {b} }{\det(A)}}.}$

Bentuk pembilang pada persamaan tersebut sama dengan nilai determinan dari matriks ${\displaystyle A}$, dengan kolom ke-j yang diganti dengan vektor ${\displaystyle \mathbf {b} }$. Akhirnya, kita mendapatkan ekspresi kaidah Cramer yang juga merupakan syarat perlu untuk solusi. Proses yang sama dapat dilakukan untuk nilai-nilai j lain untuk mendapatkan nilai variabel ${\displaystyle x}$ lainnya.

Hal terakhir yang perlu dibuktikan adalah, apakah (satu-satunya) nilai yang didapatkan dari cara ini memang merupakan solusi dari sistem persamaan. Ketika matriks ${\displaystyle A}$ dapat diinvers dengan matriks invers ${\displaystyle A^{-1}}$, maka ${\displaystyle \mathbf {x} =A^{-1}\mathbf {b} }$ adalah solusi dari sistem (dan menunjukkan eksistensinya). Untuk menunjukkan ${\displaystyle A}$ dapat diinvers ketika ${\displaystyle \operatorname {det} (A)}$ tidak bernilai nol, pertimbangkan matriks ${\displaystyle M}$ ukuran ${\displaystyle n\times n}$ yang dibentuk dengan menumpuk matriks satu-baris ${\displaystyle L_{(j)}}$ secara berurutan untuk j = 1, ..., n (ini adalah matriks adjugat dari ${\displaystyle A}$). Dapat ditunjukkan bahwa ${\displaystyle L_{(j)}A=[0\ \ \dots 0\ \ \operatorname {det} (A)\ \ 0\ \ \dots 0]}$, dengan ${\displaystyle \operatorname {det} (A)}$ berada pada kolom ke-j; dari ini dapat simpulkan ${\displaystyle MA=\operatorname {det} (A)I_{n}}$. Sehingga didapatkan,

${\displaystyle {\frac {1}{\det(A)}}M=A^{-1},}$

yang melengkapi pembuktian.

Untuk bentuk-bentuk pembuktian yang lain, lihat dibawah.

Menemukan matriks invers

Misalkan ${\displaystyle A}$ adalah matriks ${\displaystyle n\times n}$ dengan entri-entrinya elemen suatu lapangan ${\displaystyle F}$. Selanjutnya

${\displaystyle A\,\operatorname {adj} (A)=\operatorname {adj} (A)\,A=\operatorname {det} (A)I}$

dengan ${\displaystyle \operatorname {adj} (A)}$ menunjukkan matriks adjugat dari ${\displaystyle A}$, ${\displaystyle \operatorname {det} (A)}$ adalah determinannya, dan ${\displaystyle I}$ adalah matriks identitas. Jika ${\displaystyle \operatorname {det} (A)}$ tidak bernilai nol, maka matriks invers dari ${\displaystyle A}$ adalah

${\displaystyle A^{-1}={\frac {1}{\operatorname {det} (A)}}\operatorname {adj} (A).}$

Terlebih lagi, rumus ini berlaku ketika ${\displaystyle F}$ merupakan gelanggang komutatif, asalkan ${\displaystyle \operatorname {det} (A)}$ adalah satuan. Jika ${\displaystyle \operatorname {det} (A)}$ bukan satuan, maka ${\displaystyle A}$ tidak memiliki invers atas gelanggang tersebut.

Interpretasi geometris

Kaidah Cramer memiliki interpretasi geometris yang juga dapat dianggap sebagai sebuah bukti atau setidaknya memberikan wawasan tentang sifat geometrisnya. Argumen geometris berikut disajikan untuk kasus dua persamaan dalam dua variabel, dan secara umum dapat diterapkan untuk kasus-kasus lain.

Misalkan kita memiliki sistem persamaan

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&=b_{1}\\a_{21}x_{1}+a_{22}x_{2}&=b_{2}\end{matrix}}}$

sistem ini dapat dianggap sebagai persamaan antar vektor

${\displaystyle x_{1}{\binom {a_{11}}{a_{21}}}+x_{2}{\binom {a_{12}}{a_{22}}}={\binom {b_{1}}{b_{2}}}.}$

Luas jajar genjang dibentuk oleh ${\displaystyle {\binom {a_{11}}{a_{21}}}}$ dan ${\displaystyle {\binom {a_{12}}{a_{22}}}}$ diberikan oleh determinan:

${\displaystyle {\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}}.}$

Secara umum, untuk kasus jumlah persamaan dan variabel yang lebih banyak, determinan dari n vektor dengan panjang n akan memberikan volume dari parallelepiped, yang dibentuk oleh vektor-vektor tersebut dalam dimensi ke- n ruang Euklides.

Oleh karena itu, luas jajar genjang ditentukan oleh ${\displaystyle x_{1}{\binom {a_{11}}{a_{21}}}}$ dan ${\displaystyle {\binom {a_{12}}{a_{22}}}}$ akan memiliki ${\displaystyle x_{1}}$ kali luas dari jajar genjang asalnya, karena salah satu sisinya telah dikalikan dengan faktor ini. Sekarang, jajar genjang terakhir ini, dengan menggunakan prinsip Cavalieri, memiliki luas yang sama dengan jajar genjang yang dibentuk oleh ${\displaystyle {\binom {b_{1}}{b_{2}}}=x_{1}{\binom {a_{11}}{a_{21}}}+x_{2}{\binom {a_{12}}{a_{22}}}}$ dan ${\displaystyle {\binom {a_{12}}{a_{22}}}.}$

Menyamakan dua cara menghitung luas dari jajar genjang terakhir akan menghasilkan persamaan

${\displaystyle {\begin{vmatrix}b_{1}&a_{12}\\b_{2}&a_{22}\end{vmatrix}}={\begin{vmatrix}a_{11}x_{1}&a_{12}\\a_{21}x_{1}&a_{22}\end{vmatrix}}=x_{1}{\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}}}$

yang tidak lain adalah bentuk dari kaidah Cramer.

Aplikasi

Geometri diferensial

Kalkulus Ricci

Kaidah Cramer digunakan dalam kalkulus Ricci dalam berbagai perhitungan yang melibatkan simbol Christoffel jenis pertama dan kedua.^[15]

Secara khusus, aturan Cramer dapat digunakan untuk membuktikan bahwa operator divergensi pada manifold Riemannian invarian (tidak bergantung) pada perubahan koordinat. Berikut disajikan bukti langsung pernyataan tersebut, sambil mengurangi pemakaian simbol Christoffel. Misal ${\displaystyle (M,g)}$ adalah manifold Riemannian yang dilengkapi dengan koordinat lokal ${\displaystyle (x^{1},x^{2},\dots ,x^{n})}$. Misalkan pula ${\displaystyle A=A^{i}{\frac {\partial }{\partial x^{i}}}}$ sebagai bidang vektor. Bukti ini menggunakan konvensi penjumlahan Einstein.

Teorema.

Divergensi dari ${\displaystyle A}$,

${\displaystyle \operatorname {div} A={\frac {1}{\sqrt {\det g}}}{\frac {\partial }{\partial x^{i}}}\left(A^{i}{\sqrt {\det g}}\right),}$

bersifat invarian pada perubahan koordinat.

Menghitung turunan secara implisit

Pertimbangkan dua persamaan ${\displaystyle F(x,y,u,v)=0}$ dan ${\displaystyle G(x,y,u,v)=0}$. Jika ${\displaystyle u}$ dan ${\displaystyle v}$ adalah variabel bebas pada sistem, kita dapat mendefinisikan ${\displaystyle x=X(u,v)}$ dan ${\displaystyle y=Y(u,v).}$ Persamaan untuk ${\displaystyle {\dfrac {\partial x}{\partial u}}}$ dapat ditemukan dengan menerapkan aturan Cramer.

Pemrograman bilangan bulat

Kaidah Cramer dapat digunakan untuk membuktikan bahwa masalah integer programming, yang matriks pembatasnya bersifat totally unimodular dan yang ruas kanannya berupa bilangan bulat, memiliki solusi bilangan bulat. Hal ini membuat integer program jauh lebih mudah untuk diselesaikan.

Persamaan diferensial biasa

Kaidah Cramer digunakan untuk menurunkan solusi umum ke persamaan diferensial linear yang tidak homogen dengan metode variasi parameter.

Bukti lainnya

Bukti dengan aljabar linier abstrak

Bukti kaidah Cramer dapat dinyataan dalam bahasa yang lebih abstrak.

Pertimbangkan peta ${\displaystyle {\vec {x}}=(x_{1},\ldots ,x_{n})\mapsto {\frac {1}{\det A}}(\det(A_{1}),\ldots ,\det(A_{n})),}$ dengan ${\displaystyle A_{i}}$ adalah matriks ${\displaystyle A}$ yang kolom ke-${\displaystyle i}$-nya diganti dengan vektor ${\displaystyle {\vec {x}}}$, seperti pada kaidah Cramer. Peta ini bersifat linear karena sifat linearitas determinan pada setiap kolom. Selain itu, karena determinan matriks dengan dua kolom yang sama akan bernilai 0, kolom ke-${\displaystyle i}$ dari matriks ${\displaystyle A}$ akan dipetakan basis vektor standar ke-${\displaystyle i}$ ${\displaystyle {\vec {e}}_{i}=(0,\ldots ,1,\ldots ,0)}$ (dengan nilai 1 di tempat ke-${\displaystyle i}$). Jadi kita memiliki sebuah peta linier yang sama dengan invers dari ${\displaystyle A}$ pada ruang kolom; karenanya peta ini sama dengan ${\displaystyle A^{-1}}$ pada span dari ruang kolom. Karena ${\displaystyle A}$ dapat diinvers, span dari vektor-vektor kolom adalah ${\displaystyle \mathbb {R} ^{n}}$, jadi peta kita benar-benar invers dari ${\displaystyle A}$. Kaidah Cramer mengikuti.

Bukti singkat

Sebuah bukti singkat kaidah Cramer^[16] dapat ditunjukkan dengan memperhatikan bahwa ${\displaystyle x_{1}}$ adalah determinan dari matriks

${\displaystyle X_{1}={\begin{bmatrix}x_{1}&0&0&\dots &0\\x_{2}&1&0&\dots &0\\x_{3}&0&1&\dots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\x_{n}&0&0&\dots &1\end{bmatrix}}}$

Di sisi lain, dengan mengasumsikan matriks ${\displaystyle A}$ dapat diinvers, matriks ${\displaystyle X_{1}}$ ini memiliki kolom-kolom ${\displaystyle A^{-1}b,\,A^{-1}v_{2},\,\ldots ,\,A^{-1}v_{n}}$, dengan ${\displaystyle v_{n}}$ adalah kolom ke-n matriks ${\displaystyle A}$. Ingat pula bahwa matriks ${\displaystyle A_{1}}$ memiliki kolom-kolom ${\displaystyle b,v_{2},\ldots ,v_{n}}$, sehingga kita memiliki hubungan ${\displaystyle X_{1}=A^{-1}A_{1}}$. Selanjutnya, dengan menggunakan sifat determinan dari hasil kali matriks sama dengan hasil kali determinan setiap matriks, kita dapatkan

${\displaystyle x_{1}=\det(X_{1})=\det(A^{-1})\det(A_{1})={\frac {\det(A_{1})}{\det(A)}}.}$

Bukti yang serupa juga dapat ditulis untuk nilai ${\displaystyle x_{j}}$ lainnya.

Catatan kaki

Pranala luar