主張 与えられた線型方程式 が n 個の変数を持ち、同数 n 本の一次方程式からなる形:
{ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 , a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 , ⋮ a n 1 x 1 + a n 2 x 2 + ⋯ + a n n x n = b n {\displaystyle {\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 := [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] , x := [ x 1 x 2 ⋮ x n ] , b := [ b 1 b 2 ⋮ b n ] {\displaystyle 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 = det ( A i ) det ( A ) {\displaystyle x_{i}={\frac {\det(A_{i})}{\det(A)}}} で与えられる。ただし、ここで用いた行列 Ai は行列 A の第 i -列 (i = 1, 2, …, n ) を系の右辺である b で置き換えて得られる行列 A i := [ a 1 , 1 ⋯ a 1 , i − 1 b 1 a 1 , i + 1 ⋯ a 1 , n a 2 , 1 ⋯ a 2 , i − 1 b 2 a 2 , i + 1 ⋯ a 2 , n ⋮ ⋮ ⋮ ⋮ ⋮ a n , 1 ⋯ a n , i − 1 b n a n , i + 1 ⋯ a n , n ] {\displaystyle 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}}} とする。
例
二階線型方程式系 例えば、次の線型方程式系
{ 1 x 1 + 2 x 2 = 3 4 x 1 + 5 x 2 = 6 {\displaystyle {\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}}} を考える。この方程式系の拡大係数行列は ( A ∣ b ) = [ 1 2 3 4 5 6 ] {\displaystyle ({\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]} である。クラメルの法則により、系の解は x 1 = det ( A 1 ) det ( A ) = | 3 2 6 5 | | 1 2 4 5 | = 3 − 3 = − 1 , x 2 = det ( A 2 ) det ( A ) = | 1 3 4 6 | | 1 2 4 5 | = − 6 − 3 = 2 {\displaystyle {\begin{aligned}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{aligned}}} と求められる。ここで、縦棒は行列式 を表す標準的な記号法に従ったものである。
三階線型方程式系 別な例として次の線型方程式系
{ 82 x 1 + 45 x 2 + 9 x 3 = 1 27 x 1 + 16 x 2 + 3 x 3 = 1 9 x 1 + 5 x 2 + 1 x 3 = 0 {\displaystyle {\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}}} をとる。拡大係数行列 は ( A ∣ b ) = [ 82 45 9 1 27 16 3 1 9 5 1 0 ] {\displaystyle ({\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]} である。解をクラメルの法則に従って求めれば、 x 1 = det ( A 1 ) det ( A ) = | 1 45 9 1 16 3 0 5 1 | | 82 45 9 27 16 3 9 5 1 | = 1 1 = 1 , x 2 = det ( A 2 ) det ( A ) = | 82 1 9 27 1 3 9 0 1 | | 82 45 9 27 16 3 9 5 1 | = 1 1 = 1 , x 3 = det ( A 3 ) det ( A ) = | 82 45 1 27 16 1 9 5 0 | | 82 45 9 27 16 3 9 5 1 | = − 14 1 = − 14 {\displaystyle {\begin{aligned}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{aligned}}} となる。
歴史
計算量 クラメルの法則を利用して n 元線型方程式系を解こうとすれば、n + 1 個の行列式を計算しなければならない。このアルゴリズムにおいて算術演算の数は専ら行列式の計算から生じる。
クラメルの法則に現れる行列式をライプニッツの公式に従って計算すれば、(n − 1)·n ! 回の掛け算と n − 1 回の足し算をすることになる。これは4本の方程式を持つ系の場合でも、360回の掛け算、4回の割り算、115回の足し算をすることを意味する。これは他の方法に比べて極めて多くの計算を要する。行列式の計算により効率的なアルゴリズムを用いたとしても、線型方程式をクラメルの法則で解こうとすれば、ガウス消去法 などよりもずっと大きな計算量が必要になる。
n 元一次連立方程式に対して、毎秒 108 回浮動小数点演算可能 (100 Mflops) な性能の計算機で計算すると、計算時間は次の表のようになる[9] :
n 10 12 14 16 18 20 計算時間 0.4秒 1分 3.6時間 41日 38年 16,000年
証明の概略と一般化について
応用
逆行列の計算 行列 A の逆行列 は単位行列の各列ベクトル ej に対して、線型方程式系 Axj = ej の解を求めれば求まる。これらの解をクラメルの法則によって求めれば、余因子行列 adj(A ) を用いて公式
A − 1 = 1 det ( A ) adj ( A ) {\displaystyle A^{-1}={\frac {1}{\det(A)}}\operatorname {adj} (A)} を得る。この公式は行列の成分が(実数体 R のような)体 とは限らない可換環 R に値をとるとしても成り立つ。従って、行列 A が可逆となることと det(A ) が(R において)可逆 (単元 )となることとが同値であることもわかる。R が体であるときは、この条件は det(A ) ≠ 0 と同じである。
斉次方程式系の解法 クラメルの法則を使えば、det(A ) ≠ 0 のとき斉次方程式系が自明な解 x 1 = x 2 = ⋯ = xn = 0 を唯一の解として持つことは容易に示せる。各 i について A の第 i -列を零ベクトルで置き換えて得られる行列 Ai は、列ベクトルの全体がもはや線型独立 ではなく、従って det(Ai ) = 0 が成り立つ。これにより xi = 0 が結論付けられる。
上記性質により、線型方程式系 Ax = b (det(A ) ≠ 0) の核が零ベクトルのみからなることが従い、従ってそれが唯一の解である。
低次線型方程式系に対する行列式公式 線型方程式系
{ a x + b y = e c x + d y = f {\displaystyle {\begin{cases}ax+by={\color {red}e}\\cx+dy={\color {red}f}\end{cases}}} あるいは行列記法で [ a b c d ] [ x y ] = [ e f ] {\displaystyle {\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 はクラメルの法則で計算できて x = | e b f d | | a b c d | = e d − b f a d − b c , y = | a e c f | | a b c d | = a f − e c a d − b c {\displaystyle {\begin{aligned}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{aligned}}} を得る。三次の場合も同様で、線型方程式系 { a x + b y + c z = j d x + e y + f z = k g x + h y + i z = l {\displaystyle {\begin{cases}ax+by+cz={\color {red}j}\\dx+ey+fz={\color {red}k}\\gx+hy+iz={\color {red}l}\end{cases}}} あるいは [ a b c d e f g h i ] [ x y z ] = [ j k l ] {\displaystyle {\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 = | j b c k e f l h i | | a b c d e f g h i | , y = | a j c d k f g l i | | a b c d e f g h i | , z = | a b j d e k g h l | | a b c d e f g h i | {\displaystyle 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 ⁄∂u に対する方程式を求めることは、クラメルの法則の自明な応用である。
まず F , G , x , y それぞれの一階微分を計算する:
d F = ∂ F ∂ x d x + ∂ F ∂ y d y + ∂ F ∂ u d u + ∂ F ∂ v d v = 0 , d G = ∂ G ∂ x d x + ∂ G ∂ y d y + ∂ G ∂ u d u + ∂ G ∂ v d v = 0 , d x = ∂ X ∂ u d u + ∂ X ∂ v d v , d y = ∂ Y ∂ u d u + ∂ Y ∂ v d v . {\displaystyle {\begin{aligned}\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{aligned}}} dx , dy を dF , dG に代入して d F = ( ∂ F ∂ x ∂ x ∂ u + ∂ F ∂ y ∂ y ∂ u + ∂ F ∂ u ) d u + ( ∂ F ∂ x ∂ x ∂ v + ∂ F ∂ y ∂ y ∂ v + ∂ F ∂ v ) d v = 0 , d G = ( ∂ G ∂ x ∂ x ∂ u + ∂ G ∂ y ∂ y ∂ u + ∂ G ∂ u ) d u + ( ∂ G ∂ x ∂ x ∂ v + ∂ G ∂ y ∂ y ∂ v + ∂ G ∂ v ) d v = 0 {\displaystyle {\begin{aligned}\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{aligned}}} を得る。u, v は独立変数だから du , dv の係数は 0 でなければならない。故に係数に関する方程式を立てれば、 { ∂ F ∂ x ∂ x ∂ u + ∂ F ∂ y ∂ y ∂ u = − ∂ F ∂ u ∂ G ∂ x ∂ x ∂ u + ∂ G ∂ y ∂ y ∂ u = − ∂ G ∂ u ∂ F ∂ x ∂ x ∂ v + ∂ F ∂ y ∂ y ∂ v = − ∂ F ∂ v ∂ G ∂ x ∂ x ∂ v + ∂ G ∂ y ∂ y ∂ v = − ∂ G ∂ v {\displaystyle {\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]{\dfrac {\partial G}{\partial x}}{\dfrac {\partial x}{\partial u}}+{\dfrac {\partial G}{\partial y}}{\dfrac {\partial y}{\partial u}}=-{\dfrac {\partial G}{\partial u}}\\[10pt]{\dfrac {\partial F}{\partial x}}{\dfrac {\partial x}{\partial v}}+{\dfrac {\partial F}{\partial y}}{\dfrac {\partial y}{\partial v}}=-{\dfrac {\partial F}{\partial v}}\\[10pt]{\dfrac {\partial G}{\partial x}}{\dfrac {\partial x}{\partial v}}+{\dfrac {\partial G}{\partial y}}{\dfrac {\partial y}{\partial v}}=-{\dfrac {\partial G}{\partial v}}\end{cases}}} を得る。ここでクラメルの法則を使えば、 ∂ x ∂ u = | − ∂ F ∂ u ∂ F ∂ y − ∂ G ∂ u ∂ G ∂ y | | ∂ F ∂ x ∂ F ∂ y ∂ G ∂ x ∂ G ∂ y | {\displaystyle {\frac {\partial x}{\partial u}}={\frac {\begin{vmatrix}-{\frac {\partial F}{\partial u}}&{\frac {\partial F}{\partial y}}\\-{\frac {\partial G}{\partial u}}&{\frac {\partial G}{\partial y}}\end{vmatrix}}{\begin{vmatrix}{\frac {\partial F}{\partial x}}&{\frac {\partial F}{\partial y}}\\{\frac {\partial G}{\partial x}}&{\frac {\partial G}{\partial y}}\end{vmatrix}}}} が得られる。これは二つの函数行列式 ∂ x ∂ u = − ( ∂ ( F , G ) ∂ ( u , y ) ) ( ∂ ( F , G ) ∂ ( x , y ) ) {\displaystyle {\frac {\partial x}{\partial u}}=-{\frac {\left({\frac {\partial (F,G)}{\partial (u,y)}}\right)}{\left({\frac {\partial (F,G)}{\partial (x,y)}}\right)}}} を使って書き表される公式である。同様の公式が ∂x ⁄∂v , ∂y ⁄∂u , ∂y ⁄∂v からもそれぞれ導かれる。
整数計画法 クラメルの法則は、制約行列が完全単模 (totally unimodular) で、右辺値が整数、基本解も整数であるような整数計画 問題を解くのにも利用できる。これにより整数問題を解くことが大幅に容易になる。
常微分方程式 クラメルの法則は非斉次の線型微分方程式の一般解を定数変化法 で導く場合にも利用できる。
幾何学的解釈
不能や不定の場合 方程式系が、不能 (incompatible) であるとは解が存在しないことを言う。また不定 (indeterminate) であるとは、二つ以上の解を持つことを言う。線型方程式の場合(基礎体が無限体であるとすると)、それが不定な系ならば一つ以上の変数が任意の値を取り得るから、解は無数に存在する。
クラメルの法則は係数行列の行列式が 0 でない場合にしか適用できないから、2 × 2 の系で行列式の値に基づく不能や不定の場合とは相容れない。
3 × 3 あるいはより高次の系に対して、係数行列の行列式が 0 のときに言えるのは
(クラメルの公式の)分子になっている行列式のどれか一つでも 0 でないならば、系は不能である。 ということだけである。逆は正しくなく、系が不能であっても全ての行列式が 0 になる場合がある。例えば x + y + z = 1, x + y + z = 2, x + y + z = 3 がそのような系である。
脚注
関連文献
関連項目
外部リンク