logo

過飽和系と未飽和系 📂行列代数

過飽和系と未飽和系

定義1

$m \times n$行列$A$について、以下の線形システムを考えよう。

$$ A \mathbf{x} = \mathbf{b} $$

もし$m \gt n$ならば、未知数より制約条件が多い場合であり、このような線形システムを過剰決定系overdetermined systemと呼ぶ。

もし$m \lt n$ならば、未知数より制約条件が少ない場合であり、このような線形システムを過小決定系underdetermined systemと呼ぶ。

定理 1

ランクが$r$である$m \times n$行列$A$についての線形システムを考えよう。

$$ A \mathbf{x} = \mathbf{b} $$

上記線形システムの一般解は$n-r$個のパラメーターを持つ。

証明

次元定理

$$ \rank(A) + \nullity(A) = \dim(A) $$

まず次元定理により、$\nullity(A) = n-r$である。それから次の定理より、パラメーターの数とヌル次数の数が同じであることがわかる。

$\mathbf{x}_{0}$が$A\mathbf{x} = \mathbf{b}$のある解だとしよう。$S= \left\{ \mathbf{v}_{1}, \mathbf{v}_{2}, \dots, \mathbf{v}_{k} \right\}$を$\mathcal{N}(A)$の基底としよう。その時、$A\mathbf{x} = \mathbf{b}$の全ての解は次のように表現できる。

$$ \mathbf{x} = \mathbf{x}_{0} + c_{1}\mathbf{v}_{1} + c_{2}\mathbf{v}_{2} + \cdots + c_{k}\mathbf{v}_{k} $$

つまり、パラメーターの数と$\nullity(A)$が同じである。

定理 2

$m \times n$行列$A$について、以下の線形システムを考えよう。

$$ A \mathbf{x} = \mathbf{b} $$

  • 過剰決定

    線形システムが過剰決定系の場合、すなわち$m \gt n$の場合、線形システムは$\mathbb{R}^{m}$にある少なくとも1つのベクトル$\mathbf{b}$に対して解を持たない。つまり、一般解を持たない。

  • 過小決定

    線形システムが過小決定系の場合、すなわち$m \lt n$の場合、線形システムは$\mathbb{R}^{m}$にある全てのベクトル$\mathbf{b}$に対して解を持たないか、または無限に多くの解を持つ。

証明

  • 過剰決定

    $m \gt n$とすると、$A$の列ベクトルは$n$個であるため、$\mathbb{R}^{m}$を生成することはできない(ベクトルの数が次元の数よりも少ないため)。したがって、$A$の列空間に属さない少なくとも1つのベクトル$\mathbf{b}$が存在する。

    補助定理

    線形システム$A \mathbf{x} = \mathbf{b}$が解を持つ必要十分条件は、$\mathbf{b}$が$A$の列空間の要素であることである。

    この補助定理によって、$A \mathbf{x} = \mathbf{b}$は解を持たない。

  • 過小決定

    $m \lt n$と仮定しよう。

    • 解を持たない場合

      この場合は証明が完了である。

    • 解を持つ場合

      解を持つならば、定理 1により、一般解は$n-r$個のパラメーターを持つ。$r = \rank (A)$は$m$と$n$のうちの小さい値以下であるので、次が成り立つ。

      $$ n-r \le n-m > 0 $$

      これは、線形システムの一般解が1つ以上のパラメーターを持つことを意味し、解が存在するならば、それは無数に多くのものである。


  1. Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p259 ↩︎