データサイエンスのための線形代数 第9回 ガウスの消去法

:::note info
本記事は数学講座[3.2 ガウスの消去法](https://www.matongxue.com/lessons/519/parts/4573)を勉強して投稿したメモです。詳細は元の素晴らしい講座のページをチェックしてください。
:::

# ガウスの消去法

高校時代では、線形方程式系を解くため、代入法を使っていました。しかし、プログラミングをする際に、代入法が難しくなりますので、こちらで紹介するガウスの消去法が必要になります。

以下のような繰り返しで、線形方程式系を解いて、最終的に$x,y,z$の値を求めます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3327130/bd15a95c-679b-eedd-59ab-67c7c9c5e351.png)

繰り返し計算の中で、係数で構成された行列は以下の通りで、**階段行列**$→$**対角行列**$→$**単位行列**$→$の変換になります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3327130/a527c978-9706-b494-6733-d1a89b07e9f5.png)

唯一解な線形方程式系と複数解な線形方程式系は、ガウスの消去法を使って計算する際に、係数で構成された行列の形も違ってきます。
複数解の場合には、対角行列がそんなしないです。以下の形で示した通り、対角行列になると、$x,y,z$それぞれ唯一解になります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3327130/580a1b94-ed0c-3b9c-f61c-9301b8f3e664.png)

# 階段行列 

ある行列がガウスの消去法の結果として得られる形状となっているとき、その行列は階段形であると言われる。
具体的に、行列が行階段形であるとは、次が成立するときを言う：
- ゼロでない成分を持つ行（少なくとも一つの成分がゼロでない行）が、ゼロしか成分に持たない行よりも上に位置している
    - 即ち、ゼロ成分だけからなる行が存在するならば、それらは行列の最下部に配置される
- 主成分（行の最も左にあるゼロでない成分）が、その行の上にある行の主成分よりも、真に右側に位置する。

```math
\left({\begin{array}{ccccc}1&a_{0}&a_{1}&a_{2}&a_{3}\\0&0&2&a_{4}&a_{5}\\0&0&0&1&a_{6}\end{array}}\right)
   or 
\left({\begin{array}{ccccc}1&a_{0}&a_{1}&a_{2}&a_{3}\\0&0&2&a_{4}&a_{5}\\0&0&0&0&0\end{array}}\right)
```
上の唯一解と複数解の計算の例を見てみると、

```math  
\begin{cases}
    x+2y+\ \ z=\quad\ 2\\
    \quad\ \ \ 2y-2z=\quad\ 6\\
    \qquad\qquad5z=-10\\
\end{cases},\qquad
\begin{cases}
    x+2y+\ \ z=2\\
    \quad\ \ \ 2y-2z=6\\
    \qquad\qquad\ \ 0=0\\
\end{cases}
```

係数で構成された行列が階段行列であり、以下の赤い文字の数字が主成分です。

```math  

\begin{pmatrix}
    \color{red}{1}&2&1\\
    0&\color{red}{2}&-2\\
    0&0&\color{red}{5}
\end{pmatrix},\qquad
\begin{pmatrix}
    \color{red}{1}&2&1\\
    0&\color{red}{2}&-2\\
    0&0&0
\end{pmatrix}

```

# 対角行列

**対角行列**とは、**正方行列**であって、その対角成分（$(i, i)$-要素）以外が零であるような行列のことである。

```math  
\Lambda_{n}=\begin{pmatrix}\lambda_1&0&...&0\\0&\lambda_2&...&0\\...&...&&...\\
0&0&...&\lambda_n\end{pmatrix}
```
以下のように表現できる：
```math  
\Lambda_{n}=diag(\lambda_1,\lambda_2,...,\lambda_n)
```

**単位行列** や **スカラー行列(単位行列をスカラー倍したも)** は対角行列の特殊例である。

## 対角行列の乗算

行数と列数が同じな二つ対角行列の乗算は、以下のお通りです。

```math  
\begin{pmatrix}a_{1}&&&\\&a_{2}&&\\&&\ddots &\\&&&a_{n}
\end{pmatrix}\begin{pmatrix}b_{1}&&&\\&b_{2}&&\\&&\ddots 
&\\&&&b_{n}\end{pmatrix}=\begin{pmatrix}a_{1}b_{1}&&&\\&a_{2}b_{2}&&\\&&\ddots &\\&&&a_{n}b_{n}\end{pmatrix}
```

# 単位行列

単位行列はその対角成分に $1$ が並び、他は全て $0$ となる。行列要素を $a_{ij}$ とすると次のように書ける。
```math  
a_{ij}=\left\{\begin{matrix} 1 & (i=j)\\ 0 & (i \ne j) \end{matrix}\right.
```
$n$次元の**対角行列**の対角成分が全部$1$、他は全て $0$ となる。
行列で表示すると：

```math  
I_n=\begin{pmatrix}1&0&...&0\\0&1&...&0\\...&...&&...\\
0&0&...&1\end{pmatrix}
```

単位行列の記法：$I_n = diag(1,1,1...1)$ 或いは $E_n$

## 単位元と単位1

単位元の役割は単位$1$と似ています。例えば、
- 実数の乗算：$1\times a=a$
- 行列の乗算：$EA = A$ ($E$:単位元)
```math  

\begin{pmatrix}
    1&0\\
    0&1
\end{pmatrix}
\begin{pmatrix}
    1&2&3\\
    3&4&5
\end{pmatrix}
=
\begin{pmatrix}
    1&2&3\\
    3&4&5
\end{pmatrix}

```
その他の性質：
- 正方行列である
- 対角行列である
- 対称行列である
- 逆行列は自分自身である($I^{-1} = I$)

## 正方行列、対角行列、単位行列

この三者の関係は：
単位行列 $\displaystyle \subseteq$ 対角行列 $\displaystyle \subseteq$ 正方行列

# 行簡約階段形

行列が行簡約階段形（ 行標準形とも呼ばれる）であるとは、以下に述べる条件を満たすことを言う。
- ゼロでない成分を持つ行は全て、ゼロしか成分に持たない行の上に位置する。
- 主成分は常に、その上の行の主成分よりも真に右側に位置する。
- 全ての主成分は 1 であり、その主成分を含む列の中で唯一つのゼロでない成分である。

階段行列と比較して、階段行列の条件以外に、以下の条件も満たす必要があります。
- 全ての主成分は $1$ であり
- その主成分を含む列の中で、主成分以外は全て $0$ であり

例えば、以下のような：
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3327130/5f56607a-9738-bcf4-e4b6-9d3fa2fd3e1e.png)

この線形方程式系の係数行列も行簡約階段形:

```math  

\begin{cases}
    x+0+3z=-4\\
    \quad\ \ \ y-\ \ z=\ \ \ 3\\
    \qquad\qquad0=\ \ \ 0\\
\end{cases}

{  }の係数行列：

\begin{pmatrix}
    1&0&3\\
    0&1&-1\\
    0&0&0
\end{pmatrix}


```

# 基本行操作と基本行行列

次の三つを行基本変形 (elementary row transformations) または行基本操作 (elementary row operations) といいます。
- $i$行目に、$j$行目の$k$倍を加える($i$≠$j$,$k$≠0)
- ある行を$k$倍する
- $i$行目と$j$行目を入れ替える($i$≠$j$)

纏めると：

```math  

\begin{array}{c|c|c}
    \hline
    \quad 基本行操作\quad &\quad 操作\quad &\quad 基本行行列\quad\\
    \hline
    \\
    \quad \begin{aligned}\color{SkyBlue}{j行目のk倍を加える}\qquad\qquad\quad\\\text{row-addition transformations}\end{aligned}\quad &\quad \boldsymbol{r_1}'=\boldsymbol{r_1}+k\boldsymbol{r_2}\quad &\quad \begin{pmatrix}1&{\color{red}{k}}&0\\0&1&0\\0&0&1\end{pmatrix}\quad
    \\
    \\
    \hline
    \\
    \quad \begin{aligned}\color{Goldenrod}{ある行をk倍する}\qquad\qquad\quad\\\text{row-multiplying transformations}\end{aligned}\quad &\quad \boldsymbol{r_1}'=k\boldsymbol{r_1} (k\neq 0)\quad &
    \quad \begin{pmatrix}{\color{red}{k}}&0&0\\0&1&0\\0&0&1\end{pmatrix}\quad \\
    \\
    \hline
    \\
    \quad \begin{aligned}\color{orange}{入れ替える}\qquad\qquad\quad\\\text{row-switching transformations}\end{aligned}\quad &\quad \boldsymbol{r_1}\leftrightarrow \boldsymbol{r_2}\quad &
    \quad \begin{pmatrix}{\color{red}{0}}&{\color{red}{1}}&{\color{red}{0}}\\
    {\color{red}{1}}&{\color{red}{0}}&{\color{red}{0}}\\0&0&1\end{pmatrix}\quad \\
    \\
    \hline
\end{array}

```

# 参考情報

https://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95

https://www.krrk0.com/row-echelon-form/


https://ja.wikipedia.org/wiki/%E5%AF%BE%E8%A7%92%E8%A1%8C%E5%88%97

http://risalc.info/src/reduced-row-echelon-form.html

https://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E3%81%AE%E5%9F%BA%E6%9C%AC%E5%A4%89%E5%BD%A2



https://ja.wikipedia.org/wiki/%E8%A1%8C%E9%9A%8E%E6%AE%B5%E5%BD%A2#:~:text=%E8%A1%8C%E5%88%97%E3%81%8C%E8%A1%8C%E7%B0%A1%E7%B4%84%E9%9A%8E%E6%AE%B5%E5%BD%A2%EF%BC%88Reduced%20row,echelon%20form%C2%A0%3A%20%E8%A1%8C%E6%A8%99%E6%BA%96%E5%BD%A2%E3%81%A8%E3%82%82%E5%91%BC%E3%81%B0%E3%82%8C%E3%82%8B%EF%BC%89%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E3%81%AF%E3%80%81%E4%BB%A5%E4%B8%8B%E3%81%AB%E8%BF%B0%E3%81%B9%E3%82%8B%E6%9D%A1%E4%BB%B6%E3%82%92%E6%BA%80%E3%81%9F%E3%81%99%E3%81%93%E3%81%A8%E3%82%92%E8%A8%80%E3%81%86%E3%80%82

https://math.keicode.com/linear-algebra/elementary-operation.php