理論計算機科学を読むための数学・証明・アルゴリズム基礎

第12章 線形代数の最小限

章間ナビゲーション

この章で使う記号

記号 意味
x ∈ F^n 体 F 上の n 次元ベクトル
A ∈ F^{m×n} m × n 行列
Ax = b 連立一次方程式
rank(A) 行列 A のランク
I 単位行列
F_2 2元体
G / H 生成行列 / 検査行列として使われることが多い記号
d(x,y) Hamming距離などの距離

この章で解消する詰まりどころ

情報理論、符号理論、並行計算、機械学習に近い章では、行列やベクトルが道具として出てきます。

Ax = b
rank(A)
Gx
Hx = 0
x' = x + Cv

この章では、線形代数を網羅しません。理論計算機科学で式を読むために必要な、ベクトル、行列、線形写像、ランク、連立一次方程式、有限体上の計算を最小限扱います。

本体教科書で使う箇所

  • 情報理論: 線形符号、生成行列、検査行列、Hamming距離。
  • 並行計算: Petriネットの接続行列、状態方程式。
  • 確率・マルコフモデル: 遷移行列。
  • アルゴリズム: ガウス消去法、線形独立性、ランク。

1. ベクトル

ベクトルは、数を並べたものです。

x = (x_1, x_2, ..., x_n)

列ベクトルとして書くこともあります。

x = [x_1
     x_2
     ...
     x_n]

n 個の成分を持つ実ベクトル全体を R^n と書きます。F_2 上なら F_2^n と書きます。

2. ベクトル演算

同じ長さのベクトル同士は加算できます。

(1,2,3) + (4,5,6) = (5,7,9)

スカラー倍もできます。

3(1,2,3) = (3,6,9)

F_2 上では、計算は mod 2 で行います。

(1,0,1) + (1,1,0) = (0,1,1)   over F_2

なぜなら 1+1 ≡ 0 (mod 2) だからです。

3. 行列

行列は、数を長方形に並べたものです。

A = [1 2 3
     4 5 6]

この行列は2行3列なので、2×3 行列です。

一般に m×n 行列 A は、n 次元ベクトルを m 次元ベクトルへ写すものとして読めます。

A: R^n -> R^m

4. 行列とベクトルの積

m×n 行列 A と n 次元ベクトル x の積 Ax は、m 次元ベクトルです。

例:

A = [1 2
     3 4]

x = [5
     6]

Ax = [1・5 + 2・6
      3・5 + 4・6]
   = [17
      39]

列数とベクトルの次元が一致する必要があります。

5. 行列積

A が m×n、B が n×k のとき、AB は m×k 行列です。

行列積は一般に可換ではありません。

AB = BA

とは限りません。そもそも片方しか定義できない場合もあります。

6. 単位行列と逆行列

単位行列 I は、ベクトルを変えない行列です。

Ix = x

正方行列 A に対して、

AB = BA = I

を満たす行列 B が存在するとき、B を A の逆行列と呼びます。

B = A^{-1}

すべての正方行列が逆行列を持つわけではありません。

7. 線形結合

ベクトル v_1, ..., v_k とスカラー a_1, ..., a_k に対して、

a_1 v_1 + a_2 v_2 + ... + a_k v_k

を線形結合と呼びます。

例:

2(1,0) + 3(0,1) = (2,3)

8. span

ベクトル集合 S = {v_1, ..., v_k} の線形結合全体を、S の span と呼びます。

span(S) = { a_1v_1 + ... + a_kv_k | a_i はスカラー }

span は「そのベクトルたちで作れる範囲」です。

9. 線形独立

ベクトル v_1, ..., v_k が線形独立であるとは、

a_1v_1 + ... + a_kv_k = 0

を満たすのが、すべて a_i=0 の場合だけであることです。

そうでない場合、線形従属です。

直観的には、線形独立とは「どのベクトルも他のベクトルの組み合わせでは作れない」ことです。

10. 基底と次元

ベクトル空間 V の基底とは、次を満たすベクトル集合です。

  1. V 全体を span する。
  2. 線形独立である。

基底に含まれるベクトルの数を次元と呼びます。

例: R^2 の標準基底。

e_1 = (1,0)
e_2 = (0,1)

任意の (x,y) は、

(x,y) = x e_1 + y e_2

と一意に書けます。

11. 線形写像

関数 T: V -> W が線形写像であるとは、次を満たすことです。

T(u+v) = T(u) + T(v)
T(cv) = cT(v)

行列による写像 x -> Ax は線形写像です。

理論計算機科学では、符号化、状態遷移、制約条件、連立方程式を線形写像として扱うことがあります。

12. ランク

行列 A のランク rank(A) は、列ベクトルが張る空間の次元です。行空間の次元として定義しても同じ値になります。

直観的には、行列の中に含まれる独立な情報の数です。

例:

A = [1 2
     2 4]

2行目は1行目の2倍なので、独立な行は1本だけです。

rank(A) = 1

13. 連立一次方程式

連立一次方程式は、行列を使って

Ax = b

と書けます。

例:

x + 2y = 5
3x + 4y = 11

は、

[1 2] [x] = [5]
[3 4] [y]   [11]

です。

14. ガウス消去法

ガウス消去法は、行基本変形によって連立一次方程式を解く方法です。

許される操作:

  1. 2つの行を入れ替える。
  2. 行を0でないスカラー倍する。
  3. ある行に別の行のスカラー倍を加える。

これらの操作は、解集合を変えません。

15. 核と像

線形写像 T: V -> W に対して、核と像を定義します。

ker(T) = { v∈V | T(v)=0 }
im(T)  = { T(v) | v∈V }

行列 A に対しては、

ker(A) = { x | Ax=0 }
im(A)  = { Ax | x はベクトル }

です。

核は「0に潰れる入力」、像は「到達できる出力」です。

16. F_2 上の線形代数

符号理論では、ビット列を F_2 上のベクトルとして扱います。

F_2 = {0,1}

加算と乗算は mod 2 です。

演算 結果
0+0 0
0+1 1
1+0 1
1+1 0
1・1 1

F_2 上では、加算は XOR と同じです。

17. 線形符号の入口

線形符号では、メッセージ u を行列 G で符号語 c に写します。

c = uG

G を生成行列と呼びます。

符号語であるかを検査する行列 H を検査行列と呼びます。

Hc^T = 0

この式は「c が符号空間に属している」という線形制約を表します。

18. Hamming距離

同じ長さの2つのビット列が異なる位置の数を Hamming 距離と呼びます。

例:

x = 10110
y = 10011

異なる位置は3番目と5番目なので、

d(x,y) = 2

符号理論では、符号語同士の最小 Hamming 距離が、誤り検出・訂正能力に関係します。

19. Petriネットと接続行列への入口

並行計算で Petriネットを扱うと、状態をベクトル、遷移を行列で表すことがあります。

m' = m + Cx

ここで、

  • m: 現在のマーキング、つまり各場所のトークン数ベクトル。
  • C: 接続行列。
  • x: 発火回数ベクトル。
  • m': 遷移後のマーキング。

この式を読むには、行列とベクトルの積、ベクトル加算、成分ごとの非負制約が分かれば十分です。

20. よくある誤り

誤り1: 行列積を成分ごとの積と考える

行列積は、行と列の内積で定義されます。成分ごとの積ではありません。

誤り2: AB=BA と考える

行列積は一般に可換ではありません。

誤り3: 実数上の直観を F_2 にそのまま持ち込む

F_2 では 1+1=0 です。符号理論ではこの違いが本質的です。

誤り4: ランクを行数や列数そのものと考える

ランクは独立な行または列の数です。行数・列数の最大値以下ですが、常に一致するわけではありません。

21. 章末確認

次を説明できれば、この章の目的は達成です。

  1. m×n 行列と n 次元ベクトルの積の意味を説明できる。
  2. 線形結合、span、線形独立を説明できる。
  3. ランクを「独立な情報の数」として説明できる。
  4. Ax=b を連立一次方程式として読める。
  5. F_2 上で 1+1=0 と計算できる。
  6. 生成行列、検査行列の役割を説明できる。
  7. Petriネットの状態方程式を行列式として読める。

次に読む章

Edit this page on GitHub