行ランク = 列ランクの証明 (Strang 流)

第11章 行列のランク — 付録

このページの目標

本体 第11章 行列のランク §3 で述べた定理「任意の行列で行ランクと列ランクは等しい」を、ランク分解 $A = CB$ を使う Strang 流の議論で厳密に証明する。定義の言い換えで済ませず、A と $A^T$ に対する対称な構造から両方向の不等式を取り出して結合する。

前提知識

§1. 準備: 行空間・列空間・次元

証明で使う用語と基本等式をここで整理する。

用語: 行空間・列空間・次元

行空間と列空間: $A$ の行空間 $\mathrm{Row}(A)$ とは、$A$ の行ベクトル全体で張られる $\mathbb{R}^n$ の部分空間、列空間 $\mathrm{Col}(A)$ とは、$A$ の列ベクトル全体で張られる $\mathbb{R}^m$ の部分空間 (第1章 §4 部分空間・§5 基底と次元)。

次元: 部分空間 $V$ の次元 $\dim V$ は、$V$ の基底の個数として定義される (第1章 §5.3)。基底の個数が取り方によらず一定であること (= $\dim V$ の well-definedness) も第1章で述べた通り。線形独立性の扱いは 第2章。

本付録で補う事実: ベクトル空間 $V$ が有限個のベクトル $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_k$ で張られるとする (これらは線形独立でなくてもよく、互いに冗長であってもよい。たとえば一部が他の線形結合で書けていても構わない)。これらのうちから次の 2 条件を満たすように一部を選び出す (選んだ本数を $r$、$0 \leq r \leq k$ とおく):

  • (i) 選んだ $r$ 本は線形独立である;
  • (ii) 選ばれなかった (残りの $k - r$ 本の) どのベクトルを付け加えても、独立性は保てない。

このとき、選んだ $r$ 本は $V$ の基底になる。したがって $r = \dim V$。

証明 (要約): 条件 (ii) より、選ばれなかった任意のベクトル $\boldsymbol{v}$ を選ばれた $r$ 本に加えると従属になる。これは $\boldsymbol{v}$ が選ばれた $r$ 本の線形結合で書けることを意味する (でなければ独立が保たれてしまう)。ゆえに $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_k$ はすべて選ばれた $r$ 本の線形結合であり、これらが $V$ を張るという仮定と合わせて、選ばれた $r$ 本も $V$ を張る。条件 (i) と合わせて選ばれた $r$ 本は $V$ の基底である。$\blacksquare$

この事実から、$V$ を張る集合に含まれる線形独立な元の最大個数 = $\dim V$ が得られる (両者とも基底の個数に等しい)。$A$ の行空間を張るのは行ベクトル全体、列空間を張るのは列ベクトル全体なので:

$$\text{行ランク}(A) = \dim \mathrm{Row}(A), \qquad \text{列ランク}(A) = \dim \mathrm{Col}(A). \tag{1.1}$$

また転置の定義「$A^T$ の行 = $A$ の列」より、同じベクトル集合が張る空間は同一なので

$$\mathrm{Row}(A^T) = \mathrm{Col}(A), \qquad \mathrm{Col}(A^T) = \mathrm{Row}(A). \tag{1.2}$$

式 (1.1)(1.2) は次節 §2 の定理の証明で中心的に使う。

§2. 定理: 行ランク = 列ランク

定理: 行ランク = 列ランク

任意の行列について、行ランクと列ランクは等しい。したがって「行」か「列」かを区別せず、単にランクと呼ぶ。

証明 (Strang 流): $A$ を $m \times n$ 行列、行ランクを $r$ とする。

  1. 定義により、$A$ の行空間には $r$ 個の基底 $\boldsymbol{b}_1, \ldots, \boldsymbol{b}_r \in \mathbb{R}^n$ が存在する。
  2. $A$ の各行 $\boldsymbol{a}_i$ はこの基底で一意に表せる: $$\boldsymbol{a}_i = c_{i1}\boldsymbol{b}_1 + c_{i2}\boldsymbol{b}_2 + \cdots + c_{ir}\boldsymbol{b}_r \quad (i = 1, \ldots, m).$$
  3. $\boldsymbol{a}_i, \boldsymbol{b}_j$ を列ベクトル ($\mathbb{R}^n$) と見なし、それぞれの転置 $\boldsymbol{a}_i^\top, \boldsymbol{b}_j^\top$ を行ベクトルとして縦に並べ、係数 $c_{ij}$ を $m \times r$ 行列にまとめると、(2) は次の 1 本の行列等式と同値になる: $$ \underbrace{\begin{pmatrix} \boldsymbol{a}_1^\top \\ \boldsymbol{a}_2^\top \\ \vdots \\ \boldsymbol{a}_m^\top \end{pmatrix}}_{A\ (m \times n)} = \underbrace{\begin{pmatrix} c_{11} & c_{12} & \cdots & c_{1r} \\ c_{21} & c_{22} & \cdots & c_{2r} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mr} \end{pmatrix}}_{C\ (m \times r)} \underbrace{\begin{pmatrix} \boldsymbol{b}_1^\top \\ \boldsymbol{b}_2^\top \\ \vdots \\ \boldsymbol{b}_r^\top \end{pmatrix}}_{B\ (r \times n)} $$ すなわち $$A = CB.$$ この分解はランク分解と呼ばれ、後に SVD や低ランク近似の基礎となる。
  4. 両辺の第 $k$ 列を比較すると $$A_{*k} = C\, B_{*k}$$ つまり $A$ の各列は $C$ の $r$ 本の列の線形結合。ゆえに $A$ の列空間の次元 (= 列ランク) は $r$ 以下: $$\text{列ランク}(A) \leq r = \text{行ランク}(A). \tag{2.1}$$
  5. 次に、同じ議論をそのまま $A^T$ に対して適用する ($A^T$ は $n \times m$ 行列)。記号が重ならないよう、以下では $A^T$ 用に $r', \boldsymbol{d}_j, e_{ij}$ を用いる。
    証明ステップ 1-4 と 5 の抽出構造 (対称) (a) A の第 i 行 → aᵢ (証明ステップ 1-4) ····· ····· ····· ····· i行 A (m × n) 転置 ····· aᵢ (n × 1, 列) aᵢ ∈ ℝⁿ (b) Aᵀ の第 i 行 → a′ᵢ (証明ステップ 5) ···· ···· ···· ···· ···· i行 Aᵀ (n × m) 転置 ···· a′ᵢ (m × 1, 列) a′ᵢ ∈ ℝᵐ (= A の第 i 列)
    図1: 証明の2種類のベクトル抽出 (対称構造)。(a) 前半 (ステップ 1-4) では $A$ ($m \times n$) の第 $i$ 行を取り出し、転置して列ベクトル $\boldsymbol{a}_i \in \mathbb{R}^n$ を得る。(b) 後半 (ステップ 5) では $A^T$ ($n \times m$) の第 $i$ 行を取り出し、転置して列ベクトル $\boldsymbol{a}'_i \in \mathbb{R}^m$ を得る。$\boldsymbol{a}'_i$ は $A$ の第 $i$ 列にも等しい。両者は「転置を噛ませて行 → 列ベクトル」という同じ抽出パターンであり、これによりステップ 1-4 の議論がそのまま $A^T$ に適用できる。

    5-1. $A^T$ の行ランクを $r'$ とする。定義により、$A^T$ の行空間には $r'$ 個の基底 $\boldsymbol{d}_1, \ldots, \boldsymbol{d}_{r'} \in \mathbb{R}^m$ が存在する (注: $A^T$ の行は $A$ の列なので、これは $A$ の列空間の基底でもある)。

    5-2. $A^T$ の第 $i$ 行を $\boldsymbol{a}'_i$ (列ベクトルとみる, $\boldsymbol{a}'_i \in \mathbb{R}^m$) とおくと、この基底で一意に表せる: $$\boldsymbol{a}'_i = e_{i1}\boldsymbol{d}_1 + e_{i2}\boldsymbol{d}_2 + \cdots + e_{i r'}\boldsymbol{d}_{r'} \quad (i = 1, \ldots, n).$$

    5-3. これを行列形にまとめると: $$ \underbrace{\begin{pmatrix} (\boldsymbol{a}'_1)^\top \\ (\boldsymbol{a}'_2)^\top \\ \vdots \\ (\boldsymbol{a}'_n)^\top \end{pmatrix}}_{A^T\ (n \times m)} = \underbrace{\begin{pmatrix} e_{11} & e_{12} & \cdots & e_{1 r'} \\ e_{21} & e_{22} & \cdots & e_{2 r'} \\ \vdots & \vdots & \ddots & \vdots \\ e_{n1} & e_{n2} & \cdots & e_{n r'} \end{pmatrix}}_{E\ (n \times r')} \underbrace{\begin{pmatrix} \boldsymbol{d}_1^\top \\ \boldsymbol{d}_2^\top \\ \vdots \\ \boldsymbol{d}_{r'}^\top \end{pmatrix}}_{D\ (r' \times m)} $$ すなわち $$A^T = ED.$$

    5-4. 両辺の第 $k$ 列を比較すると $$(A^T)_{*k} = E\, D_{*k}$$ つまり $A^T$ の各列は $E$ の $r'$ 本の列の線形結合。ゆえに $$\text{列ランク}(A^T) \leq r' = \text{行ランク}(A^T). \tag{2.2}$$

    5-5. §1 の基本等式 (1.1), (1.2) を $A^T$ に適用すると、次の 2 つの等式が導かれる:

    • $\text{行ランク}(A^T) = \dim \mathrm{Row}(A^T) = \dim \mathrm{Col}(A) = \text{列ランク}(A)$
      （第 1 等号は (1.1) を $A^T$ に適用、第 2 等号は (1.2) の $\mathrm{Row}(A^T) = \mathrm{Col}(A)$、第 3 等号は再度 (1.1)）
    • $\text{列ランク}(A^T) = \dim \mathrm{Col}(A^T) = \dim \mathrm{Row}(A) = \text{行ランク}(A)$
      （第 1 等号は (1.1) を $A^T$ に適用、第 2 等号は (1.2) の $\mathrm{Col}(A^T) = \mathrm{Row}(A)$、第 3 等号は再度 (1.1)）

    各等号の根拠を注釈として併記している。

    5-6. これを (2.2) に代入すると

    $$\text{行ランク}(A) \leq \text{列ランク}(A). \tag{2.3}$$
  6. ステップ 4 で得た不等式 (2.1) と、ステップ 5-6 で得た不等式 (2.3): $$\text{列ランク}(A) \leq \text{行ランク}(A) \quad (2.1), \qquad \text{行ランク}(A) \leq \text{列ランク}(A) \quad (2.3)$$ を合わせると $\text{行ランク}(A) = \text{列ランク}(A).$ $\blacksquare$

§3. 参考文献

  • Strang, G. (2016). Introduction to Linear Algebra (5th ed.). Wellesley-Cambridge Press. — ランク分解 $A = CB$ の簡明な扱い。
  • Axler, S. (2015). Linear Algebra Done Right (3rd ed.). Springer.