선형대수 note 7: Solving Ax = 0 pivot variables, special solutions

m \times n 행렬 A 의 Null space 인 A\mathbf{x} = \mathbf{0} 의 해를 Elimination 을 이용해 계산하는1 알고리즘을 알아보자.

    \[A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10  \end{bmatrix} \rightarrow \begin{bmatrix} \fbox{1} & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4  \end{bmatrix} \rightarrow \begin{bmatrix} \fbox{1} & 2 & 2 & 2 \\ 0 & 0 & \fbox{2} & 4 \\ 0 & 0 & 0 & 0  \end{bmatrix} = U \text{(Echelon Matrix)}\]

Gauss elimination 에서는 두번째 열에서 Pivot 이 0 이 나오면 유일해를 구할 수 없었으므로 실패로 간주했지만, 여기서는 해집합을 구하는 과정이므로 다른 열로 계속 이어간다. 정사각 행렬에서는 Elimination 결과 Upper triangular Matrix 이었다면 직사각 행렬에서는 계단 형태의 Echelon Matrix 가 된다.2

Elimination 결과 Pivot 이 존재하는 열의 개수는 2 개, Pivot 이 없는 (0 인) 열의 개수도 2 개가 나왔다. 여기서 Pivot 열의 개수를 rank 라고 부른다.3 Pivot 있는 열을 Pivot 열, Pivot 이 없는 열을 Free 열 이라 부른다. Free 의 의미는 U\mathbf{x} = \mathbf{0} 에서 연립 방정식의 미지수의 계수가 0 이므로 미지수 (x_2, x_4) 를 아무값이나 자유롭게 선택할 수 있다는 뜻이다. U\mathbf{x} = \mathbf{0} 에서 첫번째와 세번째 열이 Pivot 변수를, 두번째와 네번째 열이 Free 변수를 나타낸다.

    \[\begin{aligned} x_1 + 2x_2 + 2x_3 + 2x_4 &= 0 \\ 2x_3 + 4x_4 &= 0 \end{aligned}\]

Free 변수들 (x_2, x_4) 의 값을 결정해야 해를 구할 수 있는데, 아무값이나 올 수 있지만 특별히 1 이나 0 을 대입하여 Free vector 들이 선형 독립적인 벡터 형태가 되게 한다.

이 과정이 직관적으로 이해가 안갈 수도 있는데.. 이렇게 생각해보자. 두개의 Pivot 변수를 갖고, 두개의 Free 변수를 갖는 해들은 4차원 공간안에서 2차원 벡터 공간을 이룬다. Free 변수들은 아무값이나 가질 수 있으므로 무작위로 값을 넣어도 상관없지만 빠짐없는 전체적인 해를 구하려면 이들을 선형적으로 분리해서 결합하는 형태로 만들어야 한다. 물론 Free 변수가 1 이나 0 이 아니어도 선형독립인 벡터 형태를 만들면 상관이 없지만 가장 자연스럽고 계산이 편한 형태는 1 또는 0 인 것이다.

이렇게 결정한 Free 변수를 가지고 해를 구하면 이것을 특수해 (Special solution) 이라고 부르는데, 일반해 (General solution) 는 이 특수해들의 선형결합이 된다.

    \[\mathbf{x} = c_1  \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}\]

pivot 변수의 개수는 rank r 이고, free 변수의 개수는 n - r 이다. 이제 여기서 한단계 더 들어가 보자.

Echelon form 으로 만든 후에도 지난번에 Gauss-Jordan elimination 에서 했던 것처럼 대각성분을 1 로 만들고 Backward elimination 을 할 수 있다. 정사각 행렬에서는 결과 행렬이 단위 행렬인 I 가 되었지만 직사각 행렬에서는 이것을 포함하는 일반적인 형태가 되는데, 이것을 RREF (Reduced Row Echelon Form) 이라고 부른다.4 RREF 로 변환된 행렬은 전형적으로 아래와 같은 모양새가 된다.5

    \[R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}\]

해를 나타내면

    \[RX = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} \begin{bmatrix} -F \\ I \end{bmatrix} = \vec{0}\]

결국 해는 행렬 X 의 열과 같다.


선형대수 note 목록

  1. Elimination 은 행에 대한 선형 결합 연산이고, 이것은 null space 를 변하게 하지 않는다.
  2. 넓은 의미에서 Upper triangular Matrix 는 Echelon Matrix 이다.
  3. rank 는 행렬에서 중요한 속성인데 나중에 차차 배운다.
  4. Backward elimination 과정 없이 대각성분만 1 로 만든 형태를 REF (Row Echelon Form) 이라고 한다.
  5. I 와 F 는 열이 섞여 있을 수 있다.

Leave a Reply

Your email address will not be published. Required fields are marked *