エレファントな線形代数(4) - エレファント・コンピューティング調査報告

順序に依存する掃き出し法

ここで再び順序に依存する場合を考えます。

$E = [ e_{1}, e_{2}, \cdots, e_{n} ]$ とし、以下のように $R = [ r_{1}, r_{2}, \cdots, r_{n} ]$ を決めます(順序に依存する列をこのように書くことにします)。
$\left\{ \begin{matrix} E_1 = E & = & [ e_{11}, e_{12}, \cdots, e_{1n} ] \\ E_2 & = & [ e_{22}, e_{23}, \cdots, e_{2n} ] \\ & \vdots \\ E_n & = & [ e_{nn} ] \\ \end{matrix} \right.$
とします。

$d(e, r, v_i)$ を $e \stackrel{i}{-} r$ をと書くことにします。

$e, r \notin \mathcal{R}^*_i$ ならば $e \stackrel{i}{-} r$ が存在する
$e \stackrel{i}{-} r \in \mathcal{R}^*_i \cup \mathcal{O}$ ( $\mathcal{O}$ は $e \stackrel{i}{-} r$ が存在しないことを表す)
$e, r \in \mathcal{R}^*_j$ ならば $e \stackrel{i}{-} r \in \mathcal{R}^*_j$

とします。

$\left\{ \begin{matrix} e_{22} & = & e_{12} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ e_{23} & = & e_{13} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ & \vdots \\ e_{2n} & = & e_{1n} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ \end{matrix} \right.$

$\left\{ \begin{matrix} e_{33} & = & e_{23} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ e_{34} & = & e_{24} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ & \vdots \\ e_{3n} & = & e_{2n} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ \end{matrix} \right.$

$\begin{matrix} & \vdots & \\ e_{nn} & = & e_{n-1,n} \stackrel{n-1}{-} e_{n-1,n-1} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \cup \mathcal{O} \end{matrix}$

$\begin{array} {ccl} r_n & = & e_{nn} & \in & \mathcal{R}_n \cup \mathcal{O} = \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \\ r_{n-1} & = & e_{n-1,n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-1} \cup \mathcal{O} \cup \mathcal{O} \\ r_{n-2} & = & e_{n-2,n-2} \stackrel{n-1}{-} r_{n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-2} \cup \mathcal{O} \\ & \vdots & \\ r_{1} & = & e_{11} \stackrel{2}{-} r_{2} \stackrel{3}{-} r_{3} \stackrel{4}{-} \cdots \stackrel{n}{-} r_n & \in & \mathcal{R}_{1} \cup \mathcal{O} \end{array}$

掃き出し法の順序の置換

上記の数式を以下のように書くことにします。

$\begin{cases} [ e_{i+1,i+1}, e_{i+1,i+2}, \cdots, e_{i+1,n} ] = [ e_{i,i+1}, e_{i,i+2}, \cdots, e_{i,n} ] \stackrel{i}{-} e_{ii} \\ r_{i} = e_{ii} \stackrel{i+1}{-} r_{i+1} \stackrel{i+2}{-} r_{i+2} \stackrel{i+3}{-} \cdots \stackrel{n}{-} r_n \end{cases}$

ここで $\sigma$ 、 $\tau$ を $\{1, 2, \cdots, n\}$ の置換( $\sigma$ は行の置換、 $\tau$ は列の置換を表す)とします。

$E^\sigma = [ e^\sigma_{1}, e^\sigma_{2}, \cdots, e^\sigma_{n} ]$ とし、 $R^{\sigma\tau} = [ r^{\sigma\tau}_{1}, r^{\sigma\tau}_{2}, \cdots, r^{\sigma\tau}_{n} ]$ 、 $E^{\sigma\tau}_i = [ e^{\sigma\tau}_{i1}, e^{\sigma\tau}_{i2}, \cdots, e^{\sigma\tau}_{in} ]$ を以下のように決めます。
$\begin{cases} E^{\sigma\tau}_1 = E^{\sigma} \\ [ e^{\sigma\tau}_{\sigma(i+1)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i+1)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i+1)\tau(n)} ] \\ = [ e^{\sigma\tau}_{\sigma(i)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i)\tau(n)} ] \stackrel{\tau(i)}{-} e^{\sigma\tau}_{\sigma(i)\tau(i)} \\ r^{\sigma\tau}_{\sigma\tau(i)} = e^{\sigma\tau}_{\sigma(i)\tau(i)} \stackrel{\tau(i+1)}{-} r^{\sigma\tau}_{\sigma\tau(i+1)} \stackrel{\tau(i+2)}{-} r^{\sigma\tau}_{\sigma\tau(i+2)} \stackrel{\tau(i+3)}{-} \cdots \stackrel{\tau(n)}{-} r^{\sigma\tau}_{\sigma\tau(n)} \end{cases}$

$\sigma, \tau$ に対して $e^{\sigma\tau}_{\sigma(t)\tau(t)}$ が存在する最大の $t$ を $\mathrm{rank}^{\sigma\tau}(E)$ とします。すべての $\sigma, \tau$ に関して最大の $\mathrm{rank}^{\sigma\tau}(E)$ を $\mathrm{rank}(E)$ とします。

$\mathrm{rank}^{\sigma\tau}(E) = n$ のとき $[E^{\exists\sigma} \to\to R^{\exists\tau}]$ と書くことにします。この計算から以下のことが導けるかどうか調べます。以下では $[E^{\exists\sigma} \to\to R^{\exists\tau}]$ の中の $E$ 、 $R$ は順序があるリストを表し、それ以外は順序のない通常の集合を表すとします。

$[E^{\exists\sigma} \to\to R^{\exists\tau}] \iff E \twoheadrightarrow R$
$\mathrm{rank}(E) = n \iff E \twoheadrightarrow_\exists R$
$E \twoheadrightarrow R_1, E \twoheadrightarrow R_2 \implies R_1 = R_2$