過飽和系と未飽和系
定義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つ以上のパラメーターを持つことを意味し、解が存在するならば、それは無数に多くのものである。
■
Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p259 ↩︎