math.luma.dev

行列の積(matrix multiplication)

行列(matrix) $\underset{n \times m}{A}$ と $\underset{m \times l}{B}$ の行列の積 $A \cdot B$ を行列 $\underset{n \times l}{C}$ として定義する。ただし、

\underset{n \times m}{(a_{i, j})_{i, j}} \cdot \underset{m \times l}{(b_{j, k})_{j, k}} \overset{def}{=} \underset{n \times l}{{(\sum_{1 \leq j \leq m} a_{i, j} \times b_{j, k})}_{i, k}}

とする。

ところで、行列の行(row)と列(column)に関する定義は基本的には対称的で、どちらが横向きでもいいのだが、そうでない定義（片方で定義したものが特に意味を持つ定義）というのが今後登場する。この章にもそうした定義が登場する。その非対称性は、この行列の積の定義の、行と列の非対称性に由来する。

$A \cdot B$ は省略して $A B$ とも書く。

行列の積の計算方法

TODO

行列の積の意味

TODO

多変数(multiple variable)線形方程式(system of linear equations)を行列の積で表す

{\begin{cases} 3 x + y + 2 z = 3 \\ x + (- 1) y + z = 4 \end{cases}

を

(\begin{array}{ccc} 3 & 1 & 2 \\ 1 & - 1 & 1 \end{array}) (\begin{array}{c} x \\ y \\ z \end{array}) = (\begin{array}{c} 3 \\ 4 \end{array})

と表すことができる。

より一般に、 $n$ 変数(variable)、 $m$ 個の方程式(equation)が連立しているとき、係数(coefficient)を表す行列 $\underset{n \times m}{A}$ 、変数を表すベクトル(vector) $x = (x_{0}, x_{1}, \dots, x_{n - 1})$ 、そして定数部を表すベクトル $b = (b_{0}, b_{1}, \dots, b_{m - 1})$ を用いて、

A x = b

と表せる。これを線型方程式と呼ぶ。また、 $b = 0$ であるとき、線形方程式は斉次(homogeneous)（さいじ）であるといい、斉次方程式(homogeneous system)（さいじほうていしき）と呼ぶ。

行列の積の性質

1. 結合律: $(A B) C = A (B C)$

証明

TODO

■

2. 行列の和(matrix addition)との分配則(distributivity): $A (B + C) = A B + A C$

証明略。

3. スカラー倍(scaling)との結合律: $(k A) B = k (A B)$

証明略。

4. $^{t} (A B) =^{t} B^{t} A$

証明

$X ≔ (左辺)$ とする。 $^{t} X = A B$ となる。

\begin{aligned} ^{t} x_{i, k} & = & \sum_{1 \leq j \leq m} a_{i, j} \times b_{j, k} & () \end{aligned}

上記の $i$ と $k$ を入れ替えることで転置(transpose)となる。

\begin{aligned} x_{i, k} & = & \sum_{1 \leq j \leq m} a_{k, j} \times b_{j, i} \end{aligned}

$Y ≔ (右辺)$ とする。

\begin{aligned} y_{i, j} & = & \sum_{1 \leq j \leq m}^{t} b_{i, j} \times^{t} a_{j, k} & () \\ = & \sum_{1 \leq j \leq m} b_{j, i} \times a_{k, j} & (の定義より、それぞれの添字を入れ替える) \\ = & \sum_{1 \leq j \leq m} a_{k, j} \times b_{j, i} & (の に関する) \end{aligned}

以上より $\forall i, j [x_{i, j} = y_{i, j}]$ であることがわかった。つまり、 $X = Y$ となる。

■

逆行列(inverse)

行列 $A$ に対して、 $A B = I$ かつ $B A = I$ となる行列 $B$ を逆行列と呼ぶ。

注意: このような $A$ は正方行列(square matrix)しかありえないが、証明するまでは循環論法を避けるためにこれらの性質は使わない。

正則行列(invertible)

正則行列とは、逆行列が存在する行列のことである。

定理: 正則行列 $A$ の逆行列は一意である

正則行列 $A$ の逆行列を $A^{- 1}$ と書く。

証明

$B$ と $C$ を正則行列 $A$ の逆行列とする。

\begin{aligned} A B = I & ⟹ & C A B = C & (左から C を乗じた) \\ ⟺ & (C A) B = C & (の) \\ ⟺ & I B = C & (の定義より C A = I) \\ ⟺ & B = C & (の性質より) \end{aligned}

■

正則行列の性質

正則行列に $0$ のみの行や列は含まれない。

$0$ のみの行や列のことを零(zero)行や零列と呼ぶことにする。

証明

$A B = I$

行列同士の積の定義を見てもらうとわかるように、 $A$ の行 $i$ が $0$ のみのなら、 $I$ の行 $i$ も $0$ のみと言うことになるが、 $I$ には零行はないので矛盾。
$B A = I$ に対して同様の議論を行うことで、零列も含まれない。

■

主成分(leading entry)

主成分とは、行列内の要素(element)であって、 $0$ を除いたもののうち、各行ごとに、最も左にある要素のこと。
各行ごとに、高々 $1$ 個の主成分が存在する。

なお、この主成分が行に関して定義されていることがまさに、上記で述べた行と列の非対称性の一つになる。

行階段形(row echelon form)

行階段形とは、以下の条件をすべて満たす行列のこと。

✔主成分が右肩下がりである。

✔

0

だけの行より、そうでない行がすべて上にくる

行簡約階段形(reduce row echelon form)

行簡約階段形とは、以下の条件をすべて満たす行列のこと。

行標準形とも。

✔行階段形である

✔すべての主成分は

1

✔主成分のある列は、主成分以外は

0

解(solution)を求めた多変数線形方程式を行列で表現すると行簡約階段形

詳しい求め方は、後述する(TODO)で説明する。

\begin{aligned} {\begin{cases} x + 2 y + 3 z = 4 \\ x + y + 2 z = 3 \end{cases} \\ ⟺ & {\begin{cases} x + 2 y + 3 z = 4 \\ - 1 y + 2 z = - 1 \end{cases} & (下の式から上の式を引く) \\ ⟺ & {\begin{cases} x + 2 y + 3 z = 4 \\ y + (- 2) z = 1 \end{cases} & (下の式を両辺 - 1 倍する) \\ ⟺ & {\begin{cases} x + 7 z = - 2 \\ y + (- 2) z = 3 \end{cases} & (上の式から下の式を 2 倍して引く) \end{aligned}

より解をパラメータ表示(parametrization)する。
$a \in R$ をパラメータ(parameter)として、 $z = a$ とすれば、

{\begin{cases} x = - 2 - 7 a \\ y = 3 + 2 a \\ z = a \end{cases}

となる。

ここで、最後の式変形後の方程式を行列で表現すると、

(\begin{array}{ccc} 1 & 0 & 7 \\ 0 & 1 & - 2 \end{array}) (\begin{array}{c} x \\ y \\ z \end{array}) = (\begin{array}{c} - 2 \\ 3 \end{array})

ここで左辺の行列を見ると、これは行簡約階段形だ。

行基本変形(elementary row operation)

ここで、上記のような多変数一次線形方程式に対して行えた操作をまとめて行基本変形と呼ぶ。

行基本変形とは、以下の3つの行列に対する操作である。

1. 行 $i$ と行 $j$ を入れ替える。

例えば、 $i = 2$ , $j = 3$ を選択して、

(\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 21 & 22 & 23 & 24 \\ 31 & 32 & 33 & 34 \\ 41 & 42 & 43 & 44 \end{array}) \to (\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 31 & 32 & 33 & 34 \\ 21 & 22 & 23 & 24 \\ 41 & 42 & 43 & 44 \end{array})

これは一般に、行列 $\underset{n \times m}{A}$ に対して、以下の行列を左から掛けることと同義である。

\begin{array}{rcl} \underset{n \times n}{P_{i, j}} \overset{def}{=} & (\begin{array}{ccccccccccc} 1 \\ ⋱ \\ 1 \\ 0 & — & — & — & 1 & — & — & — \\ | & 1 & | \\ | & ⋱ & | \\ | & 1 & | \\ 1 & — & — & — & 0 & — & — & — \\ | & | & 1 \\ | & | & ⋱ \\ | & | & 1 \end{array}) & \begin{array}{c} \leftarrow i \\ \leftarrow j \end{array} \\ \begin{array}{ccccccccccccc} ↑ & ↑ \end{array} \\ \begin{array}{ccccccccccccc} i & j \end{array} \end{array}

2. 行 $i$ を $λ$ 倍する。( $λ \in R, λ \neq 0$ )

例えば、 $i = 2$ , $λ = 10$ を選択して、

(\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 21 & 22 & 23 & 24 \\ 31 & 32 & 33 & 34 \\ 41 & 42 & 43 & 44 \end{array}) \to (\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 210 & 220 & 230 & 240 \\ 31 & 32 & 33 & 34 \\ 41 & 42 & 43 & 44 \end{array})

これは一般に、 $\underset{n \times m}{A}$ に対して、以下の行列を左から掛けることと同義である。

\begin{array}{rcl} \underset{n \times n}{P_{i}(λ)} \overset{def}{=} & (\begin{array}{ccccccc} 1 \\ ⋱ \\ 1 \\ λ & — & — & — \\ | & 1 \\ | & ⋱ \\ | & 1 \end{array}) & \begin{array}{c} \leftarrow i \end{array} \\ \begin{array}{cccccccc} ↑ \end{array} \\ \begin{array}{cccccccc} i \end{array} \end{array}

3. 行 $i$ に行 $j$ を $λ$ 倍したものを加える。( $λ \in R, λ \neq 0$ )

例えば、 $i = 3$ , $j = 2$ , $λ = 100$ を選択して、

(\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 21 & 22 & 23 & 24 \\ 31 & 32 & 33 & 34 \\ 41 & 42 & 43 & 44 \end{array}) \to (\begin{array}{cccc} 11 & 12 & 13 & 14 \\ 21 & 22 & 23 & 24 \\ 2131 & 2232 & 2333 & 2434 \\ 41 & 42 & 43 & 44 \end{array})

これは一般に、行列 $\underset{n \times m}{A}$ に対して、以下の行列を左から掛けることと同義である。

\begin{array}{rcl} \underset{n \times n}{P_{i, j}(λ)} \overset{def}{=} & (\begin{array}{ccccccc} 1 \\ ⋱ & λ & — & — \\ 1 & | \\ 1 & | \\ 1 \\ | & ⋱ \\ | & 1 \end{array}) & \begin{array}{c} \leftarrow i \end{array} \\ \begin{array}{cccccccc} ↑ \end{array} \\ \begin{array}{cccccccc} j \end{array} \end{array}

基本行列(elementary matrix)

基本行列とは、上記で定義した $P_{i, j}$ と $P_{i} (λ)$ 、そして $P_{i, j} (λ)$ のこと。
行基本行列と呼ばないのは、仮に列基本行列を同様に定義したとしてもまったく同様の行列になるからだ。

系: 線形方程式を解くことは、行列を行基本変形を任意の回数行って行簡約階段形に変形することである

線形方程式の行列での表現を行うと、各列がそれぞれ一つの変数 $x_{j}$ に対応することになる。ここで、主成分の存在しない列をパラメータとすれば解が求まる。

基本行列の逆行列

基本行列 $P$ に対して、 $P^{- 1}$ が次のように存在する。

P_{i} (λ)^{- 1} \overset{def}{=} P_{i} (λ^{- 1}) P_{i, j}^{- 1} \overset{def}{=} P_{i, j} P_{i, j} (λ)^{- 1} \overset{def}{=} P_{i, j} (- λ)

これらはすべて、行基本変形をもとに戻す行基本変形に対応する。そのことから、以下のような性質を持つことがすぐにわかる。

$P P^{- 1} = I$
$P^{- 1} P = I$
$(P^{- 1})^{- 1} = P$

行基本変形による同値関係(equivalence relation)の定義

行列 $A$ に行基本変形を何回か行って $B$ が得られるとき、 $A \sim B$ という二項関係(binary relation)を定義すると、これは同値関係になる。

言い換えると、基本行列のSEQ $(P_{0}, P_{1}, \dots, P_{n - 1})$ であって、 $B = P_{0} P_{1} \dots P_{n - 1} A$ であるものが存在するとき、かつそのときに限り $A \sim B$ であると定義する。

証明

a. 反射律(reflexivity): $A \sim A$

空列(null sequence)が対応する。 $A = A$ であるため、 $A \sim A$

b. 対称律(symmetricity): $A \sim B ⟺ B \sim A$
$A$ から $B$ にする際の行基本変形の列を、反転(reverse)させてから、各操作を逆操作(基本行列の逆行列)に換えると、 $B$ から $A$ への行基本変形の列になる。

基本行列で言い換えると、

$B = P_{0} P_{1} \dots P_{p - 1} A$

としたとき、

$A = P_{p - 1}^{- 1} \dots P_{1}^{- 1} P_{0}^{- 1} B$

なので、 $B \sim A$ となる。

c. 推移律(transitivity): $A \sim B \land B \sim C ⟹ A \sim C$
$A$ から $B$ 、 $B$ から $C$ への操作列をそのまま連結すると $A$ から $C$ への操作列になる。

基本行列で言い換えると、

$B = P_{0} P_{1} \dots P_{p - 1} A$
$C = Q_{0} Q_{1} \dots Q_{q - 1} B$

としたとき、

\begin{aligned} C & = & Q_{0} Q_{1} \dots Q_{q - 1} (P_{0} P_{1} \dots P_{p - 1} A) \\ = & (Q_{0} Q_{1} \dots Q_{q - 1} P_{0} P_{1} \dots P_{p - 1}) A & (の) \end{aligned}

$(Q_{0}, Q_{1}, \dots, Q_{q - 1}, P_{0}, P_{1}, \dots, P_{p - 1})$ は基本行列の列であるから、 $A \sim C$

■

簡約化(matrix reduction)

簡約化とは、行列を行基本変形によって行簡約階段形に変形することだ。もう少し形式的に言うなら、与えられた行列 $A$ に対して、 $B = P_{0} P_{1} \dots P_{p - 1} A$ であるような基本行列の列 $P$ と行簡約階段形 $B$ の組(tuple)を提示すること、ということ。

「 $A$ を簡約化する」というのを、「基本行列の列 $P_{0}, P_{1}, \dots P_{p - 1}$ であって、 $P ≔ P_{0} P_{1} \dots P_{p - 1}$ と定義して、 $P A = X$ なるものを選ぶ」を意味するものとする。変数 $P, p$ は $Q, q$ であったりする場合もある。また、 $P_{p - 1}^{- 1} \dots P_{1} P_{0} \dots$ を考えると、これは $P^{- 1}$ である。

$P_{i}^{- 1}$ はTODOより常に存在する。

また、同様の用語として、上三角行列(upper triangular matrix)を目指すことを上三角化(upper triangularization)と呼ぶことにする。

ガウスの消去法(Gaussian elimination)

ガウスの消去法は、任意の行列を簡約化するアルゴリズム(algorithm)だ。

前進消去(forward elimination)と後退代入(back substitution)の2つのパートからなる。

ここではそれぞれの概要を説明する。厳密なアルゴリズムに関しては、以下のアニメーションを、数値を変えながら試してほしい。

前進消去

前進消去では、上三角行列かつ、主成分が $1$ であることを目指す。同時に、枢軸選択(pivotting)（すうじくせんたく）という、見ている要素が $0$ であった場合に別の行と交換する ( $P_{i, j}$ に対応する) をすることによって、零行が自動的に下に行く。

前進消去の終了時点で得られた主成分は、最終的に得られる行簡約階段形の主成分となる。

後退代入

後退代入では、前進消去で決定した主成分をすべてを、上向きに探索する。そして、それぞれについて、前進消去と同じように、打ち消すように $P_{i, j} (λ)$ を行う。やっていることはほぼ同じである。

後退代入を行う理由について

後退代入を行う理由、もしくは、前進消去と上三角行列を分ける理由について。単に行簡約階段形を得るだけなら、前進消去の時点で、後ろ向きにも削除を行えば、アルゴリズムはシンプルになる。ガウス・ジョルダンの消去法(Gauss-Jordan elimination)は、そのような実装のバリエーションを指すことがある。

しかし、わざわざ後退代入として分けるのは、計算回数を抑えるためだ。実際、アニメーションを見てもらうと、後退代入の際には、これまで調べた主成分に関しては $0$ だとわかっているので、処理をしなくてすむ。

ガウスの消去法の計算量(computation complexitiy)

加算(addition)・乗算(multiplication)の回数がどれくらい起こるか、という計算量を考える。 $n \times m$ の行列に対してガウスの消去法を行うとする。それぞれの $n, m$ について最悪でどれくらいになるかを考える。
これは最悪 $Θ (\min {n, m} n m) = Θ ((n + m) n m)$ になる。

例

A = (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 2 & 3 & 1 & 5 \\ 2 & 0 & - 5 & 8 \end{array})

上記の行列に対してガウスの消去法を行う、以下の例を見る。

\begin{aligned} (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 2 & 3 & 1 & 5 \\ 2 & 0 & - 5 & 8 \end{array}) \\ \sim & (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 0 & - 1 & - 3 & - 3 \\ 2 & 0 & - 5 & 8 \end{array}) & (P_{1, 2} (- 2)) \\ \sim & (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 0 & - 1 & - 3 & - 3 \\ 0 & - 4 & - 9 & 0 \end{array}) & (P_{1, 3} (- 2)) \\ \sim & (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 0 & 1 & 3 & 3 \\ 0 & - 4 & - 9 & 0 \end{array}) & (P_{2} (- 1)) \\ \sim & (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 3 & 12 \end{array}) & (P_{2, 3} (4)) \\ \sim & (\begin{array}{cccc} 1 & 2 & 2 & 4 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 1 & 4 \end{array}) & (P_{3} (\frac{1}{3})) \\ \sim & (\begin{array}{cccc} 1 & 2 & 0 & - 4 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 1 & 4 \end{array}) & (P_{3, 1} (- 2)) \\ \sim & (\begin{array}{cccc} 1 & 2 & 0 & - 4 \\ 0 & 1 & 0 & - 9 \\ 0 & 0 & 1 & 4 \end{array}) & (P_{3, 2} (- 3)) \\ \sim & (\begin{array}{cccc} 1 & 0 & 0 & 14 \\ 0 & 1 & 0 & - 9 \\ 0 & 0 & 1 & 4 \end{array}) & (P_{2, 1} (- 2)) \end{aligned}

以上より、

P_{2, 1} (- 2) P_{3, 2} (- 3) P_{3, 1} (- 2) P_{3} (\frac{1}{3}) P_{2, 3} (4) P_{2} (- 1) P_{1, 3} (- 2) P_{1, 2} (- 2) A = (\begin{array}{cccc} 1 & 0 & 0 & 14 \\ 0 & 1 & 0 & - 9 \\ 0 & 0 & 1 & 4 \end{array})

左辺の基本行列の列の行列の積を計算すると、

(\begin{array}{ccc} 5 & - \frac{10}{3} & \frac{4}{3} \\ - 4 & 3 & - 1 \\ 2 & - \frac{4}{3} & \frac{1}{3} \end{array})

定理: 任意の行列は、行基本変形によって行簡約階段形に変形することが可能。

ガウスの消去法がそのまま構築による証明となる。

ガウス・ジョルダンの消去法

ガウスの消去法の中でも少しだけ触れたが、ガウス・ジョルダンの消去法の定義はいくつかの文献でゆらぎがある。ただ、かんたんにまとめると、ガウス・ジョルダンの消去法はガウスの消去法のアルゴリズムの方針を利用して、行基本変形や列基本変形(elementary column operation)によって行簡約階段形や上三角行列に変形すること、もしくはそのアイデアのことを指す。

そのアイデアというのはつまり、左上から順に主成分を決定していくことである。

定理: 任意の行列について、行基本変形によって得られる行簡約階段形は一意である。

この定理に明確に言及しているのを見かける機会は少ないかもしれないが、今後の各種定義がwell-defined(well-defined)であるかどうかはこの定理による部分が多い。

証明

行列 $A$ が異なる基本行列の列によって簡約化されたとする。

$P_{0} P_{1} \dots P_{p - 1} A = K$
$Q_{0} Q_{1} \dots Q_{q - 1} A = K^{'}$

ということになる。 $K = K^{'}$ を示せばよい。

まず、

$A = P_{p - 1}^{- 1} \dots P_{1}^{- 1} P_{0}^{- 1} K$
$A = Q_{q - 1}^{- 1} \dots Q_{1}^{- 1} Q_{0}^{- 1} K^{'}$

と変形できる。つまり、 $P_{p - 1}^{- 1} \dots P_{1}^{- 1} P_{0}^{- 1} K = Q_{q - 1}^{- 1} \dots Q_{1}^{- 1} Q_{0}^{- 1} K^{'}$ となるが、更に変形して、

K = P_{0} P_{1} \dots P_{p - 1} Q_{q - 1}^{- 1} \dots Q_{1}^{- 1} Q_{0}^{- 1} K^{'}

となる。 $F = P_{0} P_{1} \dots P_{p - 1} Q_{q - 1}^{- 1} \dots Q_{1}^{- 1} Q_{0}^{- 1}$ と置く。 $K = F K^{'}$

$F (Q_{0} Q_{1} \dots Q_{q - 1} P_{p - 1}^{- 1} \dots P_{1}^{- 1} P_{0}^{- 1}) = I$ であるから、 $F$ は正則行列だ。つまり、零行がない。この性質をこのあと用いる。

さて、ここからは、行列同士の積の定義と同様の表記法をして、 $K^{'}$ のみから $F$ と $K$ が決定できることを示す。

$K^{'} = F K$ の掛け算を以下のように表す。

\begin{array}{cc} K^{'} \\ F & K \end{array}

決定されていない場所を $?$ 、任意の値がありうる場所を $*$ で表記したのが以下だ。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} ? & ? & ? & ? & ? & ? & ? \\ ? & ? & ? & ? & ? & ? & ? \\ ? & ? & ? & ? & ? & ? & ? \\ ? & ? & ? & ? & ? & ? & ? \end{array}) = K \end{array}

$3$ 個の主成分である場合を例示している。なお、 $K^{'}$ の左側と下側の零行・列は $0$ 個以上の任意の数がそれぞれあり得る。また、 $*$ （アスタリスク）のある列も同様に $0$ 個以上の任意の数だ。

$K$ を左の列から決定していく。

1ブロック目 (最初に0列以上続く零列)

まずは零列なので、 $K$ の1列目も $0$ のみである。 $F$ については何も決定しない。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & ? & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \end{array}) = K \end{array}

2ブロック目 (最初の主成分を含む列)

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & ! & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \\ 0 & ? & ? & ? & ? & ? & ? \end{array}) = K \end{array}

$!$ で表した要素について、この値は $1$ のみがありうる。
まず、 $0$ だとしたら、 $F$ の1行目がすべて $0$ となってしまう。
そして、行簡約階段形の条件より $1$ と決定できる。行簡約階段形であるため、その下も $0$ だと決定できる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} ! & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \\ ? & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \end{array}) = K \end{array}

$!$ で表した $F$ の要素について、 $1 \times! + 0 \times ? + 0 \times ? + 0 \times ? = 1$ を満たす必要がある。
よって、この値は $1$ のみがありうる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & ? & ? & ? \\ ! & ? & ? & ? \\ ! & ? & ? & ? \\ ! & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \end{array}) = K \end{array}

$!$ で表した $F$ のすべての要素について、 $1 \times! + 0 \times ? + 0 \times ? + 0 \times ? = 0$ を満たす必要がある。
よって、この値は $0$ のみがありうる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \\ 0 & 0 & ? & ? & ? & ? & ? \end{array}) = K \end{array}

3ブロック目 (0列以上続く、1行目まで任意の値を含む列)

このブロックは、一般化すると、1ブロック目と同一だと捉えらる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & * & ? & ? & ? & ? \\ 0 & 0 & 0 & ? & ? & ? & ? \\ 0 & 0 & 0 & ? & ? & ? & ? \\ 0 & 0 & 0 & ? & ? & ? & ? \end{array}) = K \end{array}

$F$ の1列目が決定しているため、 $K^{'}$ と同一の列であると決定する。
$K$ 側の $*$ は、 $K^{'}$ と同様の値であるとする。

4ブロック目 (2個目の主成分を含む列)

このブロックは、一般化すると、2ブロック目と同一だと捉えらる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \\ 0 & ? & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & * & 0 & ? & ? & ? \\ 0 & 0 & 0 & 1 & ? & ? & ? \\ 0 & 0 & 0 & 0 & ? & ? & ? \\ 0 & 0 & 0 & 0 & ? & ? & ? \end{array}) = K \end{array}

2ブロック目と同様に、 $F$ の2行目がすべて $0$ になってはいけないこと、行列の積による等式から $1$ であることが決定し、行簡約階段形であることから、他の要素が $0$ であることが決定する。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & 0 & ? & ? \\ 0 & 1 & ? & ? \\ 0 & 0 & ? & ? \\ 0 & 0 & ? & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & * & 0 & ? & ? & ? \\ 0 & 0 & 0 & 1 & ? & ? & ? \\ 0 & 0 & 0 & 0 & ? & ? & ? \\ 0 & 0 & 0 & 0 & ? & ? & ? \end{array}) = K \end{array}

$F$ についても、同様に2行目とそれ以外でそれぞれ立式すると、 $1$ と $0$ に決定する。

終了時

のこりは同様に、ということになる。

\begin{array}{cc} (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K^{'} \\ F = (\begin{array}{cccc} 1 & 0 & 0 & ? \\ 0 & 1 & 0 & ? \\ 0 & 0 & 1 & ? \\ 0 & 0 & 0 & ? \end{array}) & (\begin{array}{ccccccc} 0 & 1 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) = K \end{array}

これにより、 $F = F^{'}$ が示された。

■

上記は具体的なものしか取り扱っていないが、形式的な議論が見える範囲で記述するように心がけた。

なお、 $F$ は上記のように決定しないこともある。行数より主成分が少ない場合がそうだ。これは、下の零行に関して行基本変形を追加でいくらやっても良い、その自由度(degree of freedom)から来ている。なお、この決定されない行数はそのまま自由度の定義として使える。

定理: 正則行列ならば正方行列である。

証明

\underset{n \times m}{A} \cdot \underset{m \times n}{B} = I_{n} \underset{m \times n}{B} \cdot \underset{n \times m}{A} = I_{m}

としておく。

$A$ を簡約化して $\underset{n \times n}{P} \cdot \underset{n \times m}{A} = \underset{n \times m}{X}$ 、両辺に右から $B$ を乗じて $P A B = X B$ 、 $P A B = P (A B) = P I = P$ より、 $P = X B$ となる。
$P P^{- 1} = I$ であるので、 $P$ は零行を含まない。
ここで、もし $X$ が零行を含むと、 $P$ も零行を持つことになるが、上記に矛盾するので、 $X$ は零行を含まない。
零行を含まない行簡約階段形は対角成分(main diagonal)が $1$ で、それ以外が $0$ のもので、 $\underset{n \times m}{X}$ は横長か正方行列( $n \leq m$ )である。

また、 $B$ を簡約化して $\underset{m \times m}{Q} \cdot \underset{m \times n}{B} = \underset{m \times n}{Y}$ とする。
$Q B = Y$ 、両辺に右から $A$ を乗じて $Q = Y A$ となる。 $Q$ も同様の議論で零行を含まないので、 $\underset{m \times n}{Y}$ も含まない。よって、 $Y$ は横長か正方行列( $m \leq n$ )である。

よって $n = m$ 。

■

系: 正則行列を基本行列すると単位行列(identity matrix)となる。

正方行列かつ行簡約階段形であって、零行を含まないものは単位行列のみであるから。

系: 任意の正則行列は基本行列の行列の積で表わせる。

$A$ を正則行列とする。

証明

$B A = I$ なる $B$ が存在する。 $B$ を簡約化して $P B = I$ となる。両辺に右から $A$ をかけると、 $P (B A) = A$ 、よって $P = A$ 。 $A = P_{0} P_{1} \dots P_{p - 1}$ となる。

■

行列と実数(real)の性質の相違

一般に $A B \neq B A$ 。 $A B = B A$ なら $A$ と $B$ は可換(commutative)である、という。
例えば対称行列(symmetrix matrix)同士は常に可換である。
$A \neq O, B \neq O$ であっても $A B = O$ となりうる。このとき、 $A$ と $B$ を零因子(zero divisor)という。例:

(\begin{array}{cc} 1 & 1 \\ 2 & 2 \end{array}) (\begin{array}{cc} 1 & 1 \\ - 1 & - 1 \end{array}) = (\begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array})

$A \neq O$ であっても $A^{- 1}$ が存在する(正則行列である)とは限らない。

行列のランク

任意の行列 $A$ に関する行列のランクを、 $A$ を簡約化して $P A = X$ になるとして、 $X$ の主成分の数として定義する。

この定義はTODOによってwell-definedである。( $P$ のとり方によらない)

行列のランクを $rank A$ と書く。

定理: $P$ が基本行列なら、 $rank P B = rank B$

証明

$P B$ の簡約化 $Q P B = X$ を考えると、 $Q P$ がそのまま $B$ の簡約化になっている。
よって、 $P B$ と $B$ の行列のランクはどちらも $X$ の零でない行の個数として一致する。

■

系: $A$ が正則行列なら、 $rank A B = rank B$

証明

TODOより $A = P_{0} P_{1} \dots P_{p - 1}$ と表せるから、
$rank A B = rank P_{0} P_{1} \dots P_{p - 1} B$ 、TODOを $p$ 回適用して、 $rank A B = rank B$

■

定理: $A \in R^{n \times n}$ について。 $A$ が正則行列 $⟺ rank A = n$

証明

$⟹$ はTODOによりすぐ。

$⟸$ について。
$rank A = n$ なので $A$ を簡約化すると $P A = I$ となる。 $P$ が $A^{- 1}$ である。

■

定理: $k$ 個の零行を含む行列 $\underset{n \times m}{A}$ について、 $rank A \leq n - k$

証明

ガウスの消去法を考えると、零行はそのまま簡約化しても残ることになる。
よって、行簡約階段形には、 $k$ 個は少なくとも零行が含まれることになる。

■

定理: $A$ が正則行列でなければ、 $A B$ も正則行列ではない。

今後に議論するより多くの行列のランクの性質からすぐにわかることなのだが、ここでは一応別の方法で示す。

証明

$A$ を簡約化して $P A = X$ とする。 $A = P^{- 1} X$ となる。

\begin{aligned} rank A B \\ = & rank P^{- 1} X B & (A = P^{- 1} X を代入) \\ = & rank X B & (TODOより) \end{aligned}

ここで、 $A$ は正則行列でないから、 $X$ は零行を含む。 $X B$ も同様に含む。TODOより、 $rank X B < n$ 。よって、 $rank A B < n$ であるが、TODOより $A B$ は正則行列ではない。

■

線形方程式の求め方

線形方程式とは一次の連立方程式(system of equations)のこと。 $n$ 変数で $m$ 連立であるとすると、変数を $x = (\begin{array}{cccc} x_{0} & x_{1} & \dots & x_{n - 1} \end{array})$ として、 $\underset{n \times m}{A} x = b$ と書ける。

$b = 0$ の場合、その線形方程式は斉次である、という。

線形方程式をガウスの消去法を使って解くことが可能。

まず、 $(\begin{array}{cc} A & b \end{array})$ という行列を考える。これを上記の線形方程式に対する拡大行列(augmented matrix)と呼ぶ。

$(\begin{array}{cc} A & b \end{array})$ に対する行基本変形は、もとの連立方程式への同値変形と同一視(identify)できる。

そこで、 $(\begin{array}{cc} A & b \end{array})$ をガウスの消去法する。それを、 $(\begin{array}{cc} A & b \end{array}) \sim (\begin{array}{cc} A^{'} & b^{'} \end{array})$ とする。たとえば以下のような形をしている。

(\begin{array}{ccccc} 1 & * & 0 & * & * \\ 0 & 0 & 1 & * & * \\ 0 & 0 & 0 & 0 & * \\ 0 & 0 & 0 & 0 & * \end{array})

ここで、もし最右だけ $0$ でない行、つまり、上の例で言う最後の行のアスタリスクが $0$ でない場合は、解がない。

$rank A < rank (\begin{array}{cc} A & b \end{array})$ なら解なし、ということだ。
ここから、線形方程式の解の存在の必要十分条件は、 $rank A = rank (\begin{array}{cc} A & b \end{array})$ であることがわかる。

逆にそうでない場合は解が必ず存在する。

各列が一つの変数に対応している。
主成分がない列をそれぞれ自由変数を割り当てて、主成分がある行について、主成分以外の項(term)を移すと一般解が得られる。

また、斉次線形方程式の場合は、常に解が存在する。斉次なら常に $rank A = rank (\begin{array}{cc} A & b \end{array}) = rank (\begin{array}{cc} A & 0 \end{array})$ であるからだ。

自由度

解が存在する線形方程式 $\underset{n \times m}{A} x = b$ の自由度を、これを解いた際の、一般解の自由変数の(最小)数として定義する。

イメージとしては、自由度 $0$ なら点、 $1$ なら線、 $2$ なら平面のようになる。TODO

自由度は、 $A$ を簡約化した際の零でない行の数、つまり $m - rank A$ と等しくなる。

行列同士の積の定義

行列の積(matrix multiplication)

行列の積の計算方法

行列の積の意味

多変数(multiple variable)線形方程式(system of linear equations)を行列の積で表す

行列の積の性質

1. 結合律: (AB)C=A(BC)(AB)C=A(BC)

証明

2. 行列の和(matrix addition)との分配則(distributivity): A(B+C)=AB+ACA(B+C)=AB+AC

3. スカラー倍(scaling)との結合律: (kA)B=k(AB)(kA)B=k(AB)

4. t(AB)=tBtAt(AB)=tBtA

証明

逆行列(inverse)

正則行列(invertible)

定理: 正則行列AAの逆行列は一意である

証明

正則行列の性質

正則行列に00のみの行や列は含まれない。

証明

主成分(leading entry)

行階段形(row echelon form)

行簡約階段形(reduce row echelon form)

解(solution)を求めた多変数線形方程式を行列で表現すると行簡約階段形

行基本変形(elementary row operation)

1. 行iiと行jjを入れ替える。

2. 行iiをλλ倍する。(λ∈R,λ≠0λ∈R,λ=0)

3. 行iiに行jjをλλ倍したものを加える。(λ∈R,λ≠0λ∈R,λ=0)

基本行列(elementary matrix)

系: 線形方程式を解くことは、行列を行基本変形を任意の回数行って行簡約階段形に変形することである

基本行列の逆行列

行基本変形による同値関係(equivalence relation)の定義

証明

簡約化(matrix reduction)

ガウスの消去法(Gaussian elimination)

前進消去

後退代入

後退代入を行う理由について

ガウスの消去法の計算量(computation complexitiy)

例

定理: 任意の行列は、行基本変形によって行簡約階段形に変形することが可能。

ガウス・ジョルダンの消去法

定理: 任意の行列について、行基本変形によって得られる行簡約階段形は一意である。

証明

1ブロック目 (最初に0列以上続く零列)

2ブロック目 (最初の主成分を含む列)

3ブロック目 (0列以上続く、1行目まで任意の値を含む列)

4ブロック目 (2個目の主成分を含む列)

終了時

定理: 正則行列ならば正方行列である。

証明

系: 正則行列を基本行列すると単位行列(identity matrix)となる。

系: 任意の正則行列は基本行列の行列の積で表わせる。

証明

行列と実数(real)の性質の相違

行列のランク

定理: PPが基本行列なら、rank⁡PB=rank⁡BrankPB=rankB

証明

系: AAが正則行列なら、rank⁡AB=rank⁡BrankAB=rankB

証明

定理: A∈Rn×nA∈Rn×nについて。AAが正則行列 ⟺ rank⁡A=n⟺rankA=n

証明

定理: kk個の零行を含む行列An×mn×mA​について、rank⁡A≤n−krankA≤n−k

証明

定理: AAが正則行列でなければ、ABABも正則行列ではない。

証明

線形方程式の求め方

自由度

1. 結合律: $(A B) C = A (B C)$

2. 行列の和(matrix addition)との分配則(distributivity): $A (B + C) = A B + A C$

3. スカラー倍(scaling)との結合律: $(k A) B = k (A B)$

4. $^{t} (A B) =^{t} B^{t} A$

定理: 正則行列 $A$ の逆行列は一意である

正則行列に $0$ のみの行や列は含まれない。

1. 行 $i$ と行 $j$ を入れ替える。

2. 行 $i$ を $λ$ 倍する。( $λ \in R, λ \neq 0$ )

3. 行 $i$ に行 $j$ を $λ$ 倍したものを加える。( $λ \in R, λ \neq 0$ )

定理: $P$ が基本行列なら、 $rank P B = rank B$

系: $A$ が正則行列なら、 $rank A B = rank B$

定理: $A \in R^{n \times n}$ について。 $A$ が正則行列 $⟺ rank A = n$

定理: $k$ 個の零行を含む行列 $\underset{n \times m}{A}$ について、 $rank A \leq n - k$

定理: $A$ が正則行列でなければ、 $A B$ も正則行列ではない。