Lecture 8. Ax = b 풀기 : 완전해와 랭크 Solving Ax = b — 서술
L6에서 A x = b A\vv{x} = \vv{b} A x = b x p + N ( A ) \vv{x}_p + N(A) x p + N ( A ) x p \vv{x}_p x p
이번 강의에서는 그 절차를 마무리하고, 그다음 랭크에 따라 해의 개수가 어떻게 달라지는지 를
정리한다. 결론부터 말하면 해의 개수를 정하는 것은 행렬의 크기가 아니라 랭크이다.
식이 미지수보다 많아도 해가 무한할 수 있고, 적어도 해가 없을 수 있다.
L7에서 쓴 행렬을 그대로 이어서 쓴다.
A = [ 1 2 2 2 2 4 6 8 3 6 8 10 ] , r = 2 A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix},
\qquad r = 2 A = ⎣ ⎡ 1 2 3 2 4 6 2 6 8 2 8 10 ⎦ ⎤ , r = 2 1. 해가 존재할 조건 ¶ 우변이 0일 때는 소거를 해도 우변이 계속 0이라 신경 쓸 것이 없었다. 이제는 우변도 함께
소거해야 하므로 L2에서처럼 증강행렬 [ A ∣ b ] [A \mid \vv{b}] [ A ∣ b ]
b = ( 1 , 5 , 6 ) \vv{b} = (1, 5, 6) b = ( 1 , 5 , 6 )
b 2 ← 5 − 2 ⋅ 1 = 3 b 3 ← 6 − 3 ⋅ 1 = 3 그다음 b 3 ← 3 − 1 ⋅ 3 = 0 \begin{aligned}
b_2 &\leftarrow 5 - 2 \cdot 1 = 3 \\
b_3 &\leftarrow 6 - 3 \cdot 1 = 3
\end{aligned}
\qquad\text{그다음}\qquad
b_3 \leftarrow 3 - 1 \cdot 3 = 0 b 2 b 3 ← 5 − 2 ⋅ 1 = 3 ← 6 − 3 ⋅ 1 = 3 그다음 b 3 ← 3 − 1 ⋅ 3 = 0 [ A ∣ b ] ⟶ [ 1 2 2 2 1 0 0 2 4 3 0 0 0 0 0 ] [\,A \mid \vv{b}\,] \longrightarrow
\left[\begin{array}{cccc|c}
1 & 2 & 2 & 2 & 1 \\
0 & 0 & 2 & 4 & 3 \\
0 & 0 & 0 & 0 & 0
\end{array}\right] [ A ∣ b ] ⟶ ⎣ ⎡ 1 0 0 2 0 0 2 2 0 2 4 0 1 3 0 ⎦ ⎤ 마지막 행은 0 = 0 0 = 0 0 = 0
이번에는 b = ( 1 , 5 , 7 ) \vv{b} = (1, 5, 7) b = ( 1 , 5 , 7 ) 7 − 3 − 3 = 1 7 - 3 - 3 = 1 7 − 3 − 3 = 1 0 = 1 0 = 1 0 = 1 x \vv{x} x x \vv{x} x
Figure 1: 증강행렬을 소거하고 마지막 행을 읽으면 해의 존재 여부가 바로 나온다.
왜 b 3 = b 1 + b 2 b_3 = b_1 + b_2 b 3 = b 1 + b 2 ¶ 위의 두 경우를 가른 것은 무엇인가. 소거에서 마지막 행이 0이 된 것은 세 행 사이에
관계가 있었기 때문이다. 그 관계를 계수로 적어 보자.
− ( 1행 ) − ( 2행 ) + ( 3행 ) = 0 -(\text{1행}) - (\text{2행}) + (\text{3행}) = \vv{0} − ( 1 행 ) − ( 2 행 ) + ( 3 행 ) = 0 실제로 계산하면 − ( 1 , 2 , 2 , 2 ) − ( 2 , 4 , 6 , 8 ) + ( 3 , 6 , 8 , 10 ) = ( 0 , 0 , 0 , 0 ) -(1,2,2,2) - (2,4,6,8) + (3,6,8,10) = (0,0,0,0) − ( 1 , 2 , 2 , 2 ) − ( 2 , 4 , 6 , 8 ) + ( 3 , 6 , 8 , 10 ) = ( 0 , 0 , 0 , 0 ) y = ( − 1 , − 1 , 1 ) \vv{y} = (-1, -1, 1) y = ( − 1 , − 1 , 1 )
y T A = 0 \vv{y}^{\mathsf{T}} A = \vv{0} y T A = 0 로 쓸 수 있다. 그런데 소거는 좌변과 우변에 똑같이 적용된다. 따라서 A x = b A\vv{x} = \vv{b} A x = b y T \vv{y}^{\mathsf{T}} y T
y T A x = y T b ⟹ 0 ⋅ x = y T b ⟹ y T b = 0 \vv{y}^{\mathsf{T}} A \vv{x} = \vv{y}^{\mathsf{T}} \vv{b}
\;\Longrightarrow\;
\vv{0} \cdot \vv{x} = \vv{y}^{\mathsf{T}} \vv{b}
\;\Longrightarrow\;
\vv{y}^{\mathsf{T}} \vv{b} = 0 y T A x = y T b ⟹ 0 ⋅ x = y T b ⟹ y T b = 0 이 되어야 한다. 좌변이 어떤 x \vv{x} x
− b 1 − b 2 + b 3 = 0 즉 b 3 = b 1 + b 2 -b_1 - b_2 + b_3 = 0
\qquad\text{즉}\qquad
b_3 = b_1 + b_2 − b 1 − b 2 + b 3 = 0 즉 b 3 = b 1 + b 2 이다. b = ( 1 , 5 , 6 ) \vv{b} = (1,5,6) b = ( 1 , 5 , 6 ) 1 + 5 = 6 1 + 5 = 6 1 + 5 = 6 ( 1 , 5 , 7 ) (1,5,7) ( 1 , 5 , 7 )
L6의 언어로 말하면 이것은 b ∈ C ( A ) \vv{b} \in C(A) b ∈ C ( A ) y \vv{y} y
2. 특수해 구하기 ¶ 해가 있다는 것을 확인했으니 하나를 구해 보자. 자유 변수는 L7에서 본 대로 x 2 x_2 x 2 x 4 x_4 x 4 자유 변수를 전부 0으로 두고 후진 대입하면 된다.
(3) x 2 = x 4 = 0 x_2 = x_4 = 0 x 2 = x 4 = 0
2 x 3 + 4 ⋅ 0 = 3 ⟹ x 3 = 3 2 2x_3 + 4 \cdot 0 = 3 \;\Longrightarrow\; x_3 = \tfrac{3}{2} 2 x 3 + 4 ⋅ 0 = 3 ⟹ x 3 = 2 3 x 1 + 2 ⋅ 0 + 2 ⋅ 3 2 + 2 ⋅ 0 = 1 ⟹ x 1 + 3 = 1 ⟹ x 1 = − 2 x_1 + 2 \cdot 0 + 2 \cdot \tfrac{3}{2} + 2 \cdot 0 = 1
\;\Longrightarrow\; x_1 + 3 = 1
\;\Longrightarrow\; x_1 = -2 x 1 + 2 ⋅ 0 + 2 ⋅ 2 3 + 2 ⋅ 0 = 1 ⟹ x 1 + 3 = 1 ⟹ x 1 = − 2 x p = [ − 2 0 3 / 2 0 ] \vv{x}_p = \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix} x p = ⎣ ⎡ − 2 0 3/2 0 ⎦ ⎤ 검산해 보자. 자유 변수가 0이므로 2열과 4열은 쓰이지 않는다.
− 2 [ 1 2 3 ] + 3 2 [ 2 6 8 ] = [ − 2 + 3 − 4 + 9 − 6 + 12 ] = [ 1 5 6 ] -2\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}
+ \tfrac{3}{2}\begin{bmatrix} 2 \\ 6 \\ 8 \end{bmatrix}
= \begin{bmatrix} -2 + 3 \\ -4 + 9 \\ -6 + 12 \end{bmatrix}
= \begin{bmatrix} 1 \\ 5 \\ 6 \end{bmatrix} − 2 ⎣ ⎡ 1 2 3 ⎦ ⎤ + 2 3 ⎣ ⎡ 2 6 8 ⎦ ⎤ = ⎣ ⎡ − 2 + 3 − 4 + 9 − 6 + 12 ⎦ ⎤ = ⎣ ⎡ 1 5 6 ⎦ ⎤ 자유 변수를 0으로 둔 것은 계산이 편해서일 뿐 이다. 다른 값을 넣어도 해가 나온다.
그렇게 얻은 것도 똑같이 특수해이다.
3. 완전해 ¶ 이제 해를 전부 모은다. L6에서 유도한 것을 다시 확인해 보자.
x 1 \vv{x}_1 x 1 x 2 \vv{x}_2 x 2 A x 1 = b A\vv{x}_1 = \vv{b} A x 1 = b A x 2 = b A\vv{x}_2 = \vv{b} A x 2 = b
A ( x 1 − x 2 ) = b − b = 0 A(\vv{x}_1 - \vv{x}_2) = \vv{b} - \vv{b} = \vv{0} A ( x 1 − x 2 ) = b − b = 0 이다. 두 해의 차이는 반드시 영공간에 있다. 거꾸로 해 하나에 영공간 원소를 더하면
A ( x p + x n ) = A x p + A x n = b + 0 = b A(\vv{x}_p + \vv{x}_n) = A\vv{x}_p + A\vv{x}_n = \vv{b} + \vv{0} = \vv{b} A ( x p + x n ) = A x p + A x n = b + 0 = b 이므로 그것도 해이다. 두 방향을 합치면 해집합이 정확히 결정된다.
L7에서 구한 영공간의 특수해를 넣으면 이 예제의 완전해가 나온다.
x = [ − 2 0 3 / 2 0 ] + c 1 [ − 2 1 0 0 ] + c 2 [ 2 0 − 2 1 ] ( c 1 , c 2 ∈ R ) \vv{x} = \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix}
+ c_1 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}
+ c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}
\qquad (c_1, c_2 \in \R) x = ⎣ ⎡ − 2 0 3/2 0 ⎦ ⎤ + c 1 ⎣ ⎡ − 2 1 0 0 ⎦ ⎤ + c 2 ⎣ ⎡ 2 0 − 2 1 ⎦ ⎤ ( c 1 , c 2 ∈ R ) c 1 c_1 c 1 c 2 c_2 c 2 2차원만큼 자유롭다.
특수해를 바꾸면 해집합이 달라지는가 ¶ 달라지지 않는다. x p ′ \vv{x}_p' x p ′ (12) x p ′ − x p ∈ N ( A ) \vv{x}_p' - \vv{x}_p \in N(A) x p ′ − x p ∈ N ( A ) x p ′ + N ( A ) \vv{x}_p' + N(A) x p ′ + N ( A )
x p ′ + n = x p + ( x p ′ − x p + n ) ⏟ ∈ N ( A ) \vv{x}_p' + \vv{n}
= \vv{x}_p + \underbrace{(\vv{x}_p' - \vv{x}_p + \vv{n})}_{\in\, N(A)} x p ′ + n = x p + ∈ N ( A ) ( x p ′ − x p + n ) 이 되어 x p + N ( A ) \vv{x}_p + N(A) x p + N ( A )
x p ′ + N ( A ) = x p + N ( A ) \vv{x}_p' + N(A) = \vv{x}_p + N(A) x p ′ + N ( A ) = x p + N ( A ) 특수해는 여러 개이지만 해집합은 하나이다.
기하적으로 보면 ¶ 해집합은 영공간을 x p \vv{x}_p x p
Figure 2: 랭크가 1인 3 × 3 3 \times 3 3 × 3 x p \vv{x}_p x p
원점은 주황색 평면 위에 있지 않다. A 0 = 0 ≠ b A\vv{0} = \vv{0} \neq \vv{b} A 0 = 0 = b
4. 랭크에 따른 네 경우 ¶ 지금까지 나온 것을 정리하면 두 가지가 해의 개수를 결정한다.
그런데 두 가지 모두 랭크로 결정된다. 피벗이 행마다 하나씩 들어가므로 0인 행이 생기지 않는 것은
r = m r = m r = m r = n r = n r = n r r r m m m n n n
Figure 3: 기약 사다리꼴의 모양은 네 가지뿐이다. I I I F F F
r = m = n r = m = n r = m = n r = n < m r = n < m r = n < m r = m < n r = m < n r = m < n r < m , r < n r < m,\; r < n r < m , r < n RREF I I I [ I 0 ] \begin{bmatrix} I \\ 0 \end{bmatrix} [ I 0 ] [ I F ] [\,I \;\; F\,] [ I F ] [ I F 0 0 ] \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} [ I 0 F 0 ] 0인 행 없음 있음 없음 있음 자유 변수 없음 없음 있음 있음 해의 개수 언제나 1개 0개 또는 1개 무수히 많음 0개 또는 무수히 많음
각 경우를 하나씩 확인해 보자.
r = m = n r = m = n r = m = n ¶ 피벗이 모든 행과 모든 열에 있으므로 RREF가 I I I b \vv{b} b (6) N ( A ) = { 0 } N(A) = \{\vv{0}\} N ( A ) = { 0 } (14)
A = [ 1 2 3 4 ] A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} A = [ 1 3 2 4 ] 이 경우가 L3에서 다룬 가역행렬이다.
r = n < m r = n < m r = n < m ¶ 열마다 피벗이 있으므로 자유 변수가 없고, 따라서 N ( A ) = { 0 } N(A) = \{\vv{0}\} N ( A ) = { 0 } m − r m - r m − r
A = [ 1 0 0 1 1 1 ] A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} A = ⎣ ⎡ 1 0 1 0 1 1 ⎦ ⎤ 세 번째 행이 앞의 두 행의 합이므로, 해가 있으려면 b 3 = b 1 + b 2 b_3 = b_1 + b_2 b 3 = b 1 + b 2 b = ( 1 , 2 , 3 ) \vv{b} = (1, 2, 3) b = ( 1 , 2 , 3 ) ( 1 , 2 , 4 ) (1, 2, 4) ( 1 , 2 , 4 )
r = m < n r = m < n r = m < n ¶ 행마다 피벗이 있으므로 0인 행이 없다. 어떤 b \vv{b} b n − r n - r n − r
A = [ 1 0 1 0 1 1 ] A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} A = [ 1 0 0 1 1 1 ] 랭크가 2이고 미지수가 셋이므로 자유 변수가 하나이다. 해집합은 직선이 된다.
r < m r < m r < m r < n r < n r < n ¶ 0인 행도 있고 자유 변수도 있다. 우변이 조건을 만족하지 않으면 해가 없고, 만족하면 무수히 많다.
A = [ 1 2 3 2 4 6 ] A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix} A = [ 1 2 2 4 3 6 ] 두 번째 행이 첫 번째 행의 2배이므로 b 2 = 2 b 1 b_2 = 2b_1 b 2 = 2 b 1 A A A r = 2 < 3 r = 2 < 3 r = 2 < 3 r = 2 < 4 r = 2 < 4 r = 2 < 4
5. 랭크가 말해 주는 두 문장 ¶ 위의 표는 사실 두 문장으로 압축된다.
첫 번째 문장은 열공간의 언어로 다시 쓸 수 있다. 피벗이 모든 행에 있다는 것은 소거해도 0인 행이
생기지 않는다는 뜻이고, 그러면 (5) y \vv{y} y b \vv{b} b
r = m ⟺ C ( A ) = R m r = m \;\Longleftrightarrow\; C(A) = \R^m r = m ⟺ C ( A ) = R m 이다. 두 번째 문장은 영공간의 언어이다. L7에서 dim N ( A ) = n − r \dim N(A) = n - r dim N ( A ) = n − r
r = n ⟺ dim N ( A ) = 0 ⟺ N ( A ) = { 0 } r = n \;\Longleftrightarrow\; \dim N(A) = 0 \;\Longleftrightarrow\; N(A) = \{\vv{0}\} r = n ⟺ dim N ( A ) = 0 ⟺ N ( A ) = { 0 } 이고, (14)
두 조건이 모두 성립하면, 즉 r = m = n r = m = n r = m = n b \vv{b} b
마치며... ¶ 이번 강의에서 다룬 것을 정리하면 다음과 같다.
대상 내용 해의 존재 조건 소거 후 0 = ( 0이 아닌 수 ) 0 = (\text{0이 아닌 수}) 0 = ( 0 이 아닌 수 ) 같은 조건, 다른 표현 y T A = 0 \vv{y}^{\mathsf{T}}A = \vv{0} y T A = 0 y \vv{y} y y T b = 0 \vv{y}^{\mathsf{T}}\vv{b} = 0 y T b = 0 특수해 x p \vv{x}_p x p 자유 변수를 전부 0으로 두고 후진 대입 완전해 x = x p + x n \vv{x} = \vv{x}_p + \vv{x}_n x = x p + x n r = m r = m r = m 모든 b \vv{b} b r = n r = n r = n 해가 있다면 유일
L1에서 시작한 A x = b A\vv{x} = \vv{b} A x = b
그런데 지금까지 랭크, 차원, 자유 변수 같은 말을 계속 써 오면서 정확히 정의한 적이 없다.
랭크는 피벗의 개수라고 했을 뿐이고, 차원은 L7에서 기저의 개수라고 하면서 기저가 무엇인지는
설명하지 않았다. 소거 방법을 바꾸면 피벗이 달라질 수도 있는데, 그러면 랭크도 달라지는가.
다음 강의에서는 독립 , 기저 , 차원 을 정확히 정의하고 그 물음에 답한다.
이번 강의의 내용을 파이썬으로 확인해 보려면 L8 실습 노트북 으로 넘어가면 된다.
완전해를 구하는 함수를 짜고, 특수해를 바꿔도 해집합이 같은지 확인하며,
네 경우의 예제를 각각 만들어 해의 개수를 세어 볼 수 있다.
