克萊姆法則

克萊姆法則或克拉瑪公式（Cramer's rule / formula）是一個線性代數中的定理，用行列式來計算出線性等式組中的所有解。這個定理因加百列·克萊姆（1704年 - 1752年）的卓越使用而命名。在計算上，並非最有效率之法，因而在很多條等式的情況中沒有廣泛應用。不過，這一定理在理論性方面十分有效。

## 基本方程

一個線性方程組可以用矩陣與向量的方程來表示：

$Ax = c\, \qquad \qquad \qquad \qquad \qquad \qquad (1)$

其中的$A$是一個$n \times n$的方塊矩陣，而向量 $x=( x_1, x_2, \cdots x_n )^T$ 是一個長度為n的行向量。$c=( c_1, c_2, \cdots c_n )^T$ 也一樣。

克萊姆法則說明：如果$A$是一個可逆矩陣（$\det{A} \neq 0$），那麼方程(1)有解 $x=( x_1, x_2, \cdots x_n )^T$，其中

$x_i = { \det(A_i) \over \det(A)}$ (1)

當中$x_i$是列向量$x$的第i行（行向量與列向量不一樣，解釋默認列向量）

當中$A_i$是列向量$c$取代了$A$的第i列後得到的矩陣。為了方便，我們通常使用$\Delta$來表示$\det(A)$，用$\Delta_i$來表示$\det(A_i)$。所以等式(1)可以寫成為：

$x_i = { \Delta_i \over \Delta }\,$。

## 抽象方程

設$R$為一個環，$A$就是一個包含$R$的系數的$n\times n$矩陣。所以：

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

當中$\det (A)$就是$A$的行列式，以及$I$就是單位矩陣。

## 證明概要

對於$n$元線性方程組$$A x = c$$

把係數矩陣 表示成行向量的形式

$$A = \left( u_1, u_2, \cdots, u_n\right)$$

由於係數矩陣可逆，故方程組一定有解$x^* = A^{-1} c$.

設$x^* = (x_1, x_2, \cdots, x_n)^T$，即

$$A x^* = \sum_{k=1}^n x_k u_k = c$$

考慮$\Delta_i$的值，利用行列式的線性和交替性質，有

$$\begin{align} \Delta_i &= det\left(\cdots, u_{i-1}, c, u_{i+1}, \cdots\right) \\ & = det\left(\cdots, u_{i-1}, \sum_{k=1}^n x_k u_k, u_{i+1}, \cdots\right) \\ & = \sum_{k=1}^n x_k \cdot det\left(\cdots, u_{i-1}, u_k, u_{i+1}, \cdots\right) \\ & = x_i \cdot det\left(\cdots, u_{i-1}, u_i, u_{i+1}, \cdots\right) \\ & = x_i \Delta \end{align}$$

於是

$$x_i = \frac{\Delta_i}{\Delta}$$

## 例子

運用克萊姆法則可以很有效地解決以下方程組。

已知：

$$ax + by = {\color{red}e}\,$$

$$cx + dy = {\color{red}f}\,$$

使用矩陣來表示時就是：

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix}$$

當矩陣可逆時，x和y可以從克萊姆法則中得出：

$$x = \frac { \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}$$

以及

$$y = \frac { \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}$$

用3×3矩陣的情況亦差不多。

已知：

$$ax + by + cz = {\color{red}j}\,$$

$$dx + ey + fz = {\color{red}k}\,$$

$$gx + hy + iz = {\color{red}l}\,$$

當中的矩陣表示為：

$$\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 = \frac { \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} }$、 $y = \frac { \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} }$ 以及 $z = \frac { \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)\,$。

找出一條等式適合$\partial x/\partial u$是克萊姆法則的簡單應用。

首先，我們要計算$F$、$G$、$x$和$y$的導數：

$$dF = \frac{\partial F}{\partial x} dx + \frac{\partial F}{\partial y} dy +\frac{\partial F}{\partial u} du +\frac{\partial F}{\partial v} dv = 0$$

$$dG = \frac{\partial G}{\partial x} dx + \frac{\partial G}{\partial y} dy +\frac{\partial G}{\partial u} du +\frac{\partial G}{\partial v} dv = 0$$

$$dx = \frac{\partial X}{\partial u} du + \frac{\partial X}{\partial v} dv$$

$$dy = \frac{\partial Y}{\partial u} du + \frac{\partial Y}{\partial v} dv$$

將$dx$和$dy$代入$dF$和$dG$，可得出：

$$dF = \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) du + \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) dv = 0$$

$$dG = \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) du + \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) dv = 0$$

因為$u$和$v$互不相關，所以$du$和$dv$的系數都要等於0。所以等式中的系數可以被寫成：

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

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

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

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

現在用克萊姆法則就可得到：

$$\cfrac{\partial x}{\partial u} = \cfrac{\begin{vmatrix} -\cfrac{\partial F}{\partial u} & \cfrac{\partial F}{\partial y} \\ -\cfrac{\partial G}{\partial u} & \cfrac{\partial G}{\partial y}\end{vmatrix}}{\begin{vmatrix}\cfrac{\partial F}{\partial x} & \cfrac{\partial F}{\partial y} \\ \cfrac{\partial G}{\partial x} & \cfrac{\partial G}{\partial y}\end{vmatrix}}$$

用兩個雅可比矩陣來表示的方程：

$$\cfrac{\partial x}{\partial u} = - \cfrac{\left(\cfrac{\partial\left(F, G\right)}{\partial\left(u, y\right)}\right)}{\left(\cfrac{\partial\left(F, G\right)}{\partial\left(x, y\right)}\right)}$$

用類似的方法就可以找到$\frac{\partial x}{\partial v}$，$\frac{\partial y}{\partial u}$，$\frac{\partial y}{\partial v}$。

### 基本代數上的應用

克萊姆法則可以用來證明一些線性代數中的定理，當中的定理對環理論十分有用。

### 線性規劃上的應用

克萊姆法則可以用來證明一個線性規劃問題有一個基本整數的解。這樣使得線性規劃的問題更容易被解決。

## 缺點

克萊姆法則在電子計算機出現後，被認為是難以實際用於計算的。當使用克萊姆法則計算一個$n$階線性方程組時，所需乘法次數為$(n+1)!$ 次。例如求解25階線性方程組時，總計乘法次數需要$26!$（即4.03×1026）次，若電腦每秒能計算100億次，所需時間約12.79億年。相比之下，高斯消元法只需3060次乘法，對電腦而言易如反掌。

## 外部連結

- Online calculator to solve a system of ecuations using the Cramer's Rule
- Systems Solver