📂행렬대수

과도결정계와 과소결정계

정의¹

$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}$에 있는 적어도 하나의 어떤 벡터 $\mathbf{b}$에 대해서는 해를 갖지 않는다. 즉 일반해를 갖지 않는다.

• 과소결정

  선형시스템이 과소결정계인 경우, 즉 $m \lt n$인 경우에 선형시스템은 $\mathbb{R}^{m}$에 있는 모든 벡터 $\mathbf{b}$에 대해서 해를 갖지 않거나 또는 무수히 많은 해를 갖는다.

증명

• 과도결정

  $m \gt n$이라고 하면, $A$의 열벡터들은 $n$개 이므로 $\mathbb{R}^{m}$을 생성할 수 없다.(차원의 수보다 벡터의 수가 작으므로) 따라서 $A$의 열공간에 속하지 않는 적어도 하나의 벡터 $\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$$

    이는 선형시스템의 일반해가 하나 이상의 매개변수를 갖는다는 것을 의미한다. 따라서 해가 존재하면 무수히 많다.

■