Linear System

Linear system(선형 시스템)이란 linear eqautions의 유한 집합이다. m개의 선형 방정식과 n개의 unknowns(미지수)를 가진 일반적인 선형 시스템을 아래와 같이 표기한다.

 

$a_{11}x_{1} + a_{12}x_{2} + \cdots + a_{1n}x_{n} = b_{1}$

$a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} = b_{2}$

$\vdots$

$a_{m1}x_{1} + a_{m2}x_{2} + \cdots + a_{mn}x_{n} = b_{m}$

 

중학교에서 배우는 내용이지만, n개의 미지수를 가진 선형 시스템의 유일해(unique solution) 존재하기 위해서는 반드시 n개의 선형 방정식이 필요하다. 하지만 미지수와 선형방정식의 수가 같더라도, 유일해가 아닌 무수히 많은 해(infinite many solution)이 존재하거나, 해가 존재하지 않을 수도 있다. 즉, 모든 선형 시스템의 해가 존재하는 경우는 아래와 같다.

 

● 유일해가 존재한다(unique solution)

● 해가 존재하지 않는다(no solution)

● 무수히 많은 해가 존재한다(infinite many solution)

 

아래는 유일해가 존재하는 경우이다.

 

$x - y = 1$

$2x+y = 6$

 

선형 시스템을 풀어서 해를 구하면 $x = \frac{7}{3}, y = \frac{4}{3}$이 나온다.

 

다음은 솔루션이 존재하지 않는 경우이다. 

 

$x + y = 4$

$3x+3y = 6$

 

계산하면 $x+y = 4$와 $0 = -6$ 이라는 두 개의 식이 등장한다. 따라서 선형 시스템의 해가 존재하지 않는다.

 

다음은 무수히 많은 해가 존재하는 경우이다.

 

$x + y = 4$

$2x+ 2y = 8$

 

두 번째 방정식은 소거되어 $0 = 0$이 되고, $x + y = 4$만 남는다. 따라서 $(1,3), (2,2), (0.5,3.5)$ 등 $x + y = 4$를 만족하는 모든 pair가 solution이 된다.

 

그럼 어떤 경우에 각각의 해의 개수를 가지는 선형시스템이 될까? 좌표평면 관점에서 보자면, 두 직선이 한 점에서 만나면 유일해, 두 직선이 평행하면 해 없음, 두 직선이 겹치면 무수히 많은 해를 가지게 된다.

 

이를 행렬 관점에서 살펴보자. 선형 시스템을 행렬로 표현한 것을 증강행렬(Augmented Matrix)라고 한다. 즉, 아래의 선형 시스템

 

$a_{11}x_{1} + a_{12}x_{2} + \cdots + a_{1n}x_{n} = b_{1}$

$a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} = b_{2}$

$\vdots$

$a_{m1}x_{1} + a_{m2}x_{2} + \cdots + a_{mn}x_{n} = b_{m}$

 

을 아래와 같은 $m \times (n+1)$ 행렬로 표현할 수 있다.

 

\begin{bmatrix}
a_{11} & a_{12} &\cdots & a_{1n} & b_1 \\
a_{21} & a_{22} &\cdots & a_{2n} & b_2 \\
 &  & \vdots &  &  \\
a_{m1} & a_{m2} &\cdots & a_{mn} & b_m \\
\end{bmatrix}

 

선형 시스템을 증강행렬로 표현했을 때 보다시피 미지수 $x_{i}$는 사라지고, 계수들만 남은 것을 확인할 수 있다. 이제 증강행렬에 적절한 연산을 이용해서 선형 시스템의 해를 구할 수 있게 된 것이다. 그 방법에 대해선 다음 포스팅에서 다룰 것이다.

 

References

1. Elementary linear algebra 12th editon, Howard Anton, Anton Kaul