行列式の計算（4）

数学

掃き出し法で行列式を求める。これならO(n3)で求められる。その前に、定義を再掲。

|A| = \sum_{\sigma \in S_n}{\mbox{sgn}(\sigma)\prod_{k=1}^n{a_{k\sigma(k)}}}

まず、

\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ ca_{k1} & \cdots & ca_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} = c\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix}

は定義より明らか。

\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} + b_{k1} & \cdots & a_{kn} + b_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} = \begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} + \begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ b_{k1} & \cdots & b_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix}

も明らか。

\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} = 0
（k行とl行が同じ）

これは、σとτ=σ(k l)がペアになっていて、符合が逆でキャンセルする。
これらより、

\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ c_1a_{l1} + c_2a{k1} & \cdots & c_1a_{ln} + c_2a_{kn} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} = c_1\begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kn} \\ \vdots & & \vdots \\ a_{l1} & \cdots & a_{ln} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix}

これにより掃き出し法が可能になる。

\begin{vmatrix} 5 & 1 & 2 \\ 3 & 4 & 5 \\ 2 & 1 & 3 \end{vmatrix} = \frac{1}{5}\begin{vmatrix} 5 & 1 & 2 \\ 15 & 20 & 25 \\ 2 & 1 & 3 \end{vmatrix} = \begin{vmatrix} 5 & 1 & 2 \\ 0 & 17 & 19 \\ 2 & 1 & 3 \end{vmatrix}

1行目で2行目の頭を0にしている。

= \frac{1}{25}\begin{vmatrix} 5 & 1 & 2 \\ 0 & 17 & 19 \\ 10 & 5 & 15 \end{vmatrix} = \frac{1}{25}\begin{vmatrix} 5 & 1 & 2 \\ 0 & 17 & 19 \\ 0 & 3 & 11 \end{vmatrix}

3行目も同様に。

= \frac{1}{25 \cdot 17}\begin{vmatrix} 5 & 1 & 2 \\ 0 & 17 & 19 \\ 0 & 51 & 187 \end{vmatrix} = \frac{1}{25 \cdot 17}\begin{vmatrix} 5 & 1 & 2 \\ 0 & 17 & 19 \\ 0 & 0 & 130 \end{vmatrix}

2行目で3行目の2列目を0にし、上三角が完成。この形なら対角成分だけ考えればいいから、

= \frac{5 \cdot 17 \cdot 130}{25 \cdot 17} = 26