クラメルの公式
線型代数学におけるクラメルの法則あるいはクラメルの公式(クラメルのこうしき、Cramer's rule; クラメルの規則)は、未知数の数と方程式の本数が一致し、かつ一意的に解ける線型方程式系の解を明示的に書き表す行列式公式である。これは、方程式の解を正方係数行列とその各列ベクトルを一つずつ方程式の右辺のベクトルで置き換えて得られる行列の行列式で表すものになっている。名称はガブリエル・クラーメル (1704–1752) に因むもので、クラーメルは任意個の未知数に関する法則を1750年に記している。なお特別の場合に限れば、コリン・マクローリンが1748年に公表している(また、恐らくはそれを1729年ごろにはすでに知っていたと思われる)。
与えられた線型方程式が n 個の変数を持ち、同数 n 本の一次方程式からなる形:\begin{cases}
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,\\
\qquad\qquad \vdots\\
a_{n1} x_1 +  a_{n2} x_2 + \cdots + a_{nn} x_n = b_n
\end{cases} で与えられているとする。あるいはこれを
A := \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nn}
\end{bmatrix}, \quad
x := \begin{bmatrix} x_1\\ x_2 \\ \vdots \\ x_n\end{bmatrix},\quad
b := \begin{bmatrix} b_1\\ b_2 \\ \vdots \\ b_n\end{bmatrix}
と置いて Ax = b と行列の記法で書いていてもよい。この時さらに、係数行列 A が正則(可逆)であるものと仮定する。これは det(A) ≠ 0 であることと同値。
これらの仮定の下、この方程式系は一意的に解くことができて、一意的な解 x の各成分 xi は x_i = \frac{\det(A_i)}{\det(A)} で与えられる。ただし、ここで用いた行列 Ai は行列 A の第 i-列 (i = 1, 2, …, n) を系の右辺である b で置き換えて得られる行列 A_i := \begin{bmatrix}
a_{1,1}   & \cdots & a_{1,i-1}   & b_1     & a_{1,i+1}   & \cdots & a_{1,n} \\
a_{2,1}   & \cdots & a_{2,i-1}   & b_2     & a_{2,i+1}   & \cdots & a_{2,n} \\
\vdots    &        & \vdots      & \vdots  & \vdots      &        & \vdots \\
a_{n,1}   & \cdots & a_{n,i-1}   & b_n     & a_{n,i+1}   & \cdots & a_{n,n}
\end{bmatrix}
とする。
例えば、次の線型方程式系 \begin{cases}
{\color{blue}1}\,x_1+{\color{blue}2}\,x_2={\color{OliveGreen}3}\\
{\color{blue}4}\,x_1+{\color{blue}5}\,x_2={\color{OliveGreen}6}
\end{cases} を考える。この方程式系の拡大係数行列は
({\color{blue}A} \mid {\color{OliveGreen}b}) =
\left[ \begin{array}{cc|c}
{\color{blue}1} & {\color{blue}2} & {\color{OliveGreen}3} \\
{\color{blue}4} & {\color{blue}5} & {\color{OliveGreen}6}
\end{array}\right]
である。クラメルの法則により、系の解は \begin{align}
x_1 &= \frac{\det(A_1)}{\det(A)} = \frac{\begin{vmatrix}
\color{OliveGreen}{3}&\color{blue}{2}\\
\color{OliveGreen}{6}&\color{blue}{5}
\end{vmatrix}{\begin{vmatrix}
{\color{blue}1}&{\color{blue}2}\\
{\color{blue}4}&{\color{blue}5}
\end{vmatrix} = \frac{3}{-3} = -1,\\[10pt]
x_2 &= \frac{\det(A_2)}{\det(A)} = \frac{\begin{vmatrix}
{\color{blue}1}&{\color{OliveGreen}3}\\
{\color{blue}4}&{\color{OliveGreen}6}
\end{vmatrix}{\begin{vmatrix}
{\color{blue}1}&{\color{blue}2}\\
{\color{blue}4}&{\color{blue}5}
\end{vmatrix} = \frac{-6}{-3} = 2
\end{align}
と求められる。ここで、縦棒は行列式を表す標準的な記号法に従ったものである。
別な例として次の線型方程式系 \begin{cases}
{\color{blue}82}\,x_1+{\color{blue}45}\,x_2+{\color{blue}9}\,x_3={\color{OliveGreen}1}\\
{\color{blue}27}\,x_1+{\color{blue}16}\,x_2+{\color{blue}3}\,x_3={\color{OliveGreen}1}\\
{\color{blue}9}\, x_1+{\color{blue}5}\, x_2+{\color{blue}1}\,x_3={\color{OliveGreen}0}\\
\end{cases} をとる。拡大係数行列は
({\color{blue}A} \mid {\color{OliveGreen}b}) =
\left[ \begin{array}{ccc|c}
{\color{blue}82} & {\color{blue}45} & {\color{blue}9} & {\color{OliveGreen}1} \\
{\color{blue}27} & {\color{blue}16} & {\color{blue}3} & {\color{OliveGreen}1} \\
{\color{blue}9}  & {\color{blue}5}  & {\color{blue}1} & {\color{OliveGreen}0}
\end{array}\right]
である。解をクラメルの法則に従って求めれば、\begin{align}
x_1 &= \frac{\det(A_1)}{\det(A)} =
\tfrac{
\begin{vmatrix}
\color{OliveGreen}{1} & \color{blue}{45} & \color{blue}{9}\\
\color{OliveGreen}{1} & \color{blue}{16} & \color{blue}{3}\\
\color{OliveGreen}{0} & \color{blue}{5}  & \color{blue}{1}
\end{vmatrix}
}{
\begin{vmatrix}
\color{blue}{82} & \color{blue}{45} & \color{blue}{9}\\
\color{blue}{27} & \color{blue}{16} & \color{blue}{3}\\
\color{blue}{9}  & \color{blue}{5}  & \color{blue}{1}
\end{vmatrix} = \frac{1}{1} = 1,\\[10pt]
x_2 &= \frac{\det(A_2)}{\det(A)} =
\tfrac{
\begin{vmatrix}
\color{blue}{82} & \color{OliveGreen}{1} & \color{blue}{9}\\
\color{blue}{27} & \color{OliveGreen}{1} & \color{blue}{3}\\
\color{blue}{9}  & \color{OliveGreen}{0} & \color{blue}{1}
\end{vmatrix}
}{
\begin{vmatrix}
\color{blue}{82} & \color{blue}{45} & \color{blue}{9}\\
\color{blue}{27} & \color{blue}{16} & \color{blue}{3}\\
\color{blue}{9}  & \color{blue}{5}  & \color{blue}{1}
\end{vmatrix}
} = \frac{1}{1} = 1,\\[10pt]
x_3 &= \frac{\det(A_3)}{\det(A)} =
\tfrac{
\begin{vmatrix}
\color{blue}{82} & \color{blue}{45} & \color{OliveGreen}{1}\\
\color{blue}{27} & \color{blue}{16} & \color{OliveGreen}{1}\\
\color{blue}{9}  & \color{blue}{5}  & \color{OliveGreen}{0}
\end{vmatrix}
}{
\begin{vmatrix}
\color{blue}{82} & \color{blue}{45} & \color{blue}{9}\\
\color{blue}{27} & \color{blue}{16} & \color{blue}{3}\\
\color{blue}{9}  & \color{blue}{5}  & \color{blue}{1}
\end{vmatrix}
} = \frac{-14}{1} = -14
\end{align}となる。
クラメルの法則は、ガブリエル・クラメルが1750年に出版した著書 «Introduction à l′analyse des lignes courbes algébriques»  の付録 1 に収録されている。クラメルは、より多くの本数の方程式を持つ系を解くための公式の作り方を述べるために、三本の方程式を持つ線型方程式系に対する明示公式を与えている。この頃にはまだ行列式の概念は存在していないので、クラメルは分母と分子が多項式であるような分数を用いて記述していた。以下はクラメルのオリジナルの論文からの抜粋である(これらは行列式に関するライプニッツの公式と同じものである)この例においてクラメルが現代的なものとは違う記法を用いていることが見て取れる。これは現代的な記法で言えばx_1 = \frac{b_1a_{22}a_{33} - b_1a_{32}a_{23} - b_2a_{12}a_{33} + b_2a_{32}a_{13} + b_3a_{12}a_{23} - b_3a_{22}a_{13}{a_{11}a_{22}a_{33} - a_{11}a_{32}a_{23} - a_{21}a_{12}a_{33} + a_{21}a_{32}a_{13} + a_{31}a_{12}a_{23} - a_{31}a_{22}a_{13}なることを示すものである。クラメル自身は一意的に解くことができない線型方程式系が存在することを知っていた。ベズーは1764年に、一意的に解くことができない線型方程式系では、この式の分母が 0 になることを示す。クラメルもまた、この法則の証明を与えてはおらず、それが成されるのは1815年、コーシーの手によってである(今日用いられるクラメルの法則の記法を導入したのもコーシーである)。ライプニッツは1678年の手書きの論文において既にクラメルの法則を用いているが、しかしこれは後々まで発見されず、線型方程式系の解法の発展に影響を与えはしなかった。マクローリンは1748年の著書“Treatise on Algebra"において、方程式が二本または三本であるような場合の線型方程式に対する、クラメルの法則の特別の場合を述べている。マクローリンも、これらの公式をより方程式の本数が多い一般の場合へ拡張するアイデアを持っていたが、クラメルと違って多項式の符号を正しく定める方法が分からなかった。20世紀になって、数学史家カール・ベンジャミン・ボイヤーは、クラメルとマクローリンのどちらがこの公式を発見したのかという疑義を提示し、名称はマクローリン・クラメルの法則とすべしとした。
クラメルの法則を利用して n 元線型方程式系を解こうとすれば、n + 1 個の行列式を計算しなければならない。このアルゴリズムにおいて算術演算の数は専ら行列式の計算から生じる。
クラメルの法則に現れる行列式をライプニッツの公式に従って計算すれば、(n − 1)·n! 回の掛け算と n − 1 回の足し算をすることになる。これは4本の方程式を持つ系の場合でも、360回の掛け算、4回の割り算、115回の足し算をすることを意味する。これは他の方法に比べて極めて多くの計算を要する。行列式の計算により効率的なアルゴリズムを用いたとしても、線型方程式をクラメルの法則で解こうとすれば、ガウス消去法などよりもずっと大きな計算量が必要になる。
n 元一次連立方程式に対して、毎秒 108 回浮動小数点演算可能 (100 Mflops) な性能の計算機で計算すると、計算時間は次の表のようになる:
証明のために、単位行列の第 i-列を方程式 Ax = b の変数ベクトル x に置き換えて得られる行列 Xi を考える。例えば n = 4 のときの X2 は X_2 = \begin{bmatrix}1 & x_1 & 0 & 0 \\ 0 & x_2 & 0 & 0 \\ 0 & x_3 & 1 & 0 \\ 0 & x_4 & 0 & 1\end{bmatrix} で与えられる。このとき、AXi = Ai および det(Xi) = xi となることが示せる。実際、いま挙げた例では \begin{align}
A \cdot X_2
&= \begin{bmatrix}
a_{11} & a_{12} & a_{13} & a_{14} \\
a_{21} & a_{22} & a_{23} & a_{24} \\
a_{31} & a_{32} & a_{33} & a_{34} \\
a_{41} & a_{42} & a_{43} & a_{44}
\end{bmatrix} \cdot \begin{bmatrix}
1 & x_1 & 0 & 0 \\
0 & x_2 & 0 & 0 \\
0 & x_3 & 1 & 0 \\
0 & x_4 & 0 & 1
\end{bmatrix}\\[10pt]
&= \begin{bmatrix}
a_{11} & a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 & a_{13} & a_{14} \\
a_{21} & a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 & a_{23} & a_{24} \\
a_{31} & a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 & a_{33} & a_{34} \\
a_{41} & a_{41}x_1 + a_{42}x_2 + a_{43}x_3 + a_{44}x_4 & a_{43} & a_{44}
\end{bmatrix}\\[10pt]
&= \begin{bmatrix}
a_{11} & b_1 & a_{13} & a_{14} \\
a_{21} & b_2 & a_{23} & a_{24} \\
a_{31} & b_3 & a_{33} & a_{34} \\
a_{41} & b_4 & a_{43} & a_{44}
\end{bmatrix}\\[10pt]
&= A_2
\end{align} が成り立っている。また行列式の乗法性により \begin{align}
\det(A)\cdot\det(X_i) &=\det(A_i)\\
\det(A)\cdot x_i      &=\det(A_i)\\
x_i &= \det(A_i)\cdot\det(A)^{-1}
\end{align} となる。仮定により det(A) ≠ 0 ゆえ det(A)−1 が存在することに注意。
証明の内容を省みれば、クラメルの法則の成立は以下の定理
正方線型方程式系 Ax = b が与えられたとき、x = (x1, x2, …, xn) がこの方程式系の解であるならば、各 i について det(A)xi = det(Ai) が成り立つ。
に集約されることがわかる。もちろん行列 Ai は行列 A の第 i-列を系の右辺である b で置き換えて得られる行列である。方程式の解が一意であるという仮定を外せば、割り算を実行することができないことも起こり得るが、いま述べた形の定理であれば、方程式系の係数が可換環に値をとる場合も含めて常に成立するが、これはもはやクラメルの法則と呼ばれることはない。
行列 A の逆行列は単位行列の各列ベクトル ej に対して、線型方程式系 Axj = ej の解を求めれば求まる。これらの解をクラメルの法則によって求めれば、余因子行列 adj(A) を用いて公式 A^{-1} = \frac 1{\det(A)} \operatorname{adj} (A) を得る。この公式は行列の成分が(実数体 R のような)体とは限らない可換環 R に値をとるとしても成り立つ。従って、行列 A が可逆となることと det(A) が(R において)可逆(単元)となることとが同値であることもわかる。R が体であるときは、この条件は det(A) ≠ 0 と同じである。
クラメルの法則を使えば、det(A) ≠ 0 のとき斉次方程式系が自明な解 x1 = x2 = ⋯ = xn = 0 を唯一の解として持つことは容易に示せる。各 i について A の第 i-列を零ベクトルで置き換えて得られる行列 Ai は、列ベクトルの全体がもはや線型独立ではなく、従って det(Ai) = 0 が成り立つ。これにより xi = 0 が結論付けられる。
上記性質により、線型方程式系 Ax = b (det(A) ≠ 0) の核が零ベクトルのみからなることが従い、従ってそれが唯一の解である。
線型方程式系 \begin{cases} ax+by ={\color{red}e}\\ cx + dy = {\color{red}f}\end{cases} あるいは行列記法で
\begin{bmatrix} a & b \\ c & d \end{bmatrix}\ \begin{bmatrix} x \\ y \end{bmatrix}
=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix} を考え、ad − bc ≠ 0 と仮定すると、x および y はクラメルの法則で計算できて \begin{align}
x = \tfrac { \begin{vmatrix} \color{red}{e} & b \\ \color{red}{f} & d \end{vmatrix}\ } { \begin{vmatrix} a & b \\ c & d \end{vmatrix} } = { {\color{red}e}d - b{\color{red}f} \over ad - bc},\\[8pt]
y = \tfrac { \begin{vmatrix} a & \color{red}{e} \\ c & \color{red}{f} \end{vmatrix}\ } { \begin{vmatrix} a & b \\ c & d \end{vmatrix} } = { a{\color{red}f} - {\color{red}e}c \over ad - bc}
\end{align}  を得る。三次の場合も同様で、線型方程式系 \begin{cases}
ax + by + cz = {\color{red}j}\\
dx + ey + fz = {\color{red}k}\\
gx + hy + iz = {\color{red}l}
\end{cases} あるいは
\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\ \begin{bmatrix} x \\ y \\ z \end{bmatrix}
=\begin{bmatrix} {\color{red}j} \\ {\color{red}k} \\ {\color{red}l}\end{bmatrix}
に対して、 x, y, z は
x = \tfrac { \begin{vmatrix} {\color{red}j} & b & c \\ {\color{red}k} & e & f \\ {\color{red}l} & h & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }, \quad
y = \tfrac { \begin{vmatrix} a & {\color{red}j} & c \\ d & {\color{red}k} & f \\ g & {\color{red}l} & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} },\quad
z = \tfrac { \begin{vmatrix} a & b & {\color{red}j} \\ d & e & {\color{red}k} \\ g & h & {\color{red}l} \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }
で求められる。
クラメルの法則は微分幾何学における問題を解くのにもきわめて有効である。二つの方程式 F(x, y, u, v) = 0 および G(x, y, u, v) = 0 を考える。u と v とが独立変数のとき、x = X(u, v) と y = Y(u, v) が陰伏的に定まる。
∂x に対する方程式を求めることは、クラメルの法則の自明な応用である。
まず F, G, x, y それぞれの一階微分を計算する: \begin{align}
\mathrm{d}F &= \frac{\partial F}{\partial x} \mathrm{d}x + \frac{\partial F}{\partial y} \mathrm{d}y +\frac{\partial F}{\partial u} \mathrm{d}u +\frac{\partial F}{\partial v} \mathrm{d}v = 0,\\
\mathrm{d}G &= \frac{\partial G}{\partial x} \mathrm{d}x + \frac{\partial G}{\partial y} \mathrm{d}y +\frac{\partial G}{\partial u} \mathrm{d}u +\frac{\partial G}{\partial v} \mathrm{d}v = 0,\\
\mathrm{d}x &= \frac{\partial X}{\partial u} \mathrm{d}u + \frac{\partial X}{\partial v} \mathrm{d}v,\\
\mathrm{d}y &= \frac{\partial Y}{\partial u} \mathrm{d}u + \frac{\partial Y}{\partial v} \mathrm{d}v.
\end{align} dx, dy を dF, dG に代入して \begin{align}
\mathrm{d}F & = \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial F}{\partial u} \right) \mathrm{d}u + \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial F}{\partial v} \right) \mathrm{d}v = 0,\\[5pt]
\mathrm{d}G &= \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial G}{\partial u} \right) \mathrm{d}u + \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial G}{\partial v} \right) \mathrm{d}v = 0
\end{align} を得る。u, v は独立変数だから du, dv の係数は 0 でなければならない。故に係数に関する方程式を立てれば、\begin{cases}
\dfrac{\partial F}{\partial x} \dfrac{\partial x}{\partial u} +\dfrac{\partial F}{\partial y} \dfrac{\partial y}{\partial u} = -\dfrac{\partial F}{\partial u}\\[10pt]