Solving Ax = b: row reduced form R

1. Complete solution of $A \mathbf{x} = b$

1.1 $A \mathbf{x} = b$의 해

■ $A \mathbf{x} = b$에서 해가 존재할 수도, 존재하지 않을 수도 있다. 해의 존재 여부는 소거법을 통해 확인해야 한다.

■ 그리고 해가 존재한다면, 유일한 해인지 아니면 여러 해가 존재하는지 확인해야 한다.

■ 예를 들어 방정식이 다음과 같을 때,

$\begin{aligned}     x_1 + 2x_2 + 2x_3 + 2x_4 &= b_1 \\     2x_1 + 4x_2 + 6x_3 + 8x_4 &= b_2 \\     3x_1 + 6x_2 + 8x_3 + 10x_4 &= b_3 \end{aligned}$

■ 이 방정식을 행렬로 바꿔 소거법을 풀기 위해서 계수 행렬에 미지수를 붙여 확대 행렬(augmented matrix)를 만들어 사용한다. $( A \mid b )$

- $A \mathbf{x} = 0$에서는 우변이 0이었기 때문에 좌변의 계수만 행렬로 만들어서 풀지만, 우변에 $b$가 존재하면 확대 행렬을 만들어서 소거를 진행한다.

■ $( A \mid b )$에서 소거를 진행하면,

■ 마지막 방정식은 $0 = b_3 - b_2 - b_1$이 된다. 이 조건을 해가 존재하기 위한 조건. 가해(solvability) 조건이라고 한다. 

■ 여기서 가해 조건은 $0 = b_3 - b_2 - b_1 \Leftrightarrow b_1 + b_2 = b_3$으로 표현할 수 있다. 이는 계수 행렬 $A$에서 row1 + row2 = row3이기 때문이다. 

■ $b = [ 1 5 6 ]^T$라고 가정하자. 그러면 $b_1 = 1$, $b_2 = 5 - 2 = 3$이 되고 $b_3 = 6 - 5 - 1 = 0$이 되므로 가해 조건을 만족한다. 가해 조건을 만족하므로 $b$는 해를 가질 수 있다.

■ 단, 이 예시의 가해 조건 $0 = b_3 - b_2 - b_1$는 일반적인 조건이 아니다. 이 가해 조건은 위의 선형 방정식에 해당되는 가해 조건이다. 

■ $A \mathbf{x} = b$가 풀리려면, $A \mathbf{x}$를 선형 결합으로 보았을 때, 선형 결합의 결과인 $b$는 $A$의 열공간에 속해야 한다.

■ 즉, ① 해가 존재하는 조건(가해 조건)은 $b$가 행렬 $A$의 열공간에 존재해야 한다는 것을 의미한다.

■ 위의 말을 행(row)의 관점에서 보면, ② 가해 조건은 행렬 $A$의 행들의 선형 결합으로 모든 원소가 0인 행을 만든다면, $b$의 항목들 역시 같은 선형 결합을 적용했을 때 $0$이 되어야 한다.

■ 행렬 $A$를 가우스 소거했을 때, 모든 원소가 0인 행이 생긴다는 것은 '서로 독립이 아닌 행(종속 관계를 갖는 행)'이 있음을 의미한다. 

■ 이때, 만약 $( A \mid b )$에 대해서도 같은 소거 과정을 적용했을 때 모든 원소가 0인 행 옆에 '0이 아닌 어떤 값'이 남아있다면 ( $[0 0 \cdots 0 \mid \neq 0]$ ) $0 = c \neq 0$이 되므로 모순이다. 

■ 그러므로 이런 '모순 행'이 생기지 않으려면 $A$에 대해 모든 원소가 0인 행을 만들었던 선형 결합이 $b$에도 똑같이 적용되어 0이 되어야 한다. 이는 가해 조건이 $\text{rank} (A) = \text{rank} (A \mid b)$임을 의미한다. 이것은 결국 $b$가 $\text{Col} (A)$에 속한다는 것과 동치이다.

■ 왜냐하면, $\text{Col} (A)$란 행렬 $A$의 선형 독립인 열벡터들이 만들어내는 선형적인 '모든 조합'을 모아놓은 공간이다. 그리고 $\text{rank} (A)$는 행렬 $A$의 선형 독립인 열벡터(또는 행벡터)의 개수이다.

■ 즉, $\text{rank} (A)$는 $A$의 열공간 $\text{Col} (A)$의 차원(= $A$의 열벡터들 중 서로 독립인 벡터의 개수)과 같다.

■ $( A \mid b )$는 행렬 $A$에 $b$를 하나 더 붙인 확장된 행렬이다. 만약, $b$가 $A$의 선형 결합으로 만들어질 수 없다면(독립 이라면), 다음과 같이 $( A \mid b )$에서 $b$의 랭크가 1만큼 증가한다.

반대로 $A$의 선형 결합으로 $b$를 만들 수 있다면, 소거 과정을 통해 $\text{rank} (A) = \text{rank} (A \mid b)$가 성립한다.

■ 여기서 $\text{rank} (A) = \text{rank} (A \mid b)$. 즉, $A$의 선형 결합으로 $b$를 만들 수 있다는 것은 $A$의 선형 결합 결과인 $b$가 $A$의 열공간에 존재한다는 것이므로, 가해 조건 ①과 ②가 동치라는 것을 알 수 있다.

■ 이 개념을 동일하게 생각하면, $\text{rank} (A) < \text{rank} (A \mid b)$라는 것은 $A$의 선형 결합으로 $b$를 만들 수 없는 것이므로 해가 존재하지 않는다고 할 수 있다.

■ 정리하면 $A \mathbf{x} = b$에서 $\text{rank} (A) < \text{rank} (A \mid b) \Leftrightarrow b \in \text{Col} (A)$라면 '해가 존재한다', $\text{rank} (A) < \text{rank} (A \mid b)$이면 '해가 존재하지 않는다.'

1.2 $A \mathbf{x} = b$의 완전해(complete solution)를 찾는 방법

■ 이 예에서 $( A \mid b )$의 마지막 방정식이 0 = 0 이므로, 방정식이 해를 가질 것이라 기대할 수 있다.

- 실제로 두 개의 방정식과 네 개의 미지수가 존재하므로, 여러 해가 존재할 것으로 예상할 수 있다.

■ $A \mathbf{x} = b$의 완전해를 찾기 위해 먼저 특수 해(particular solution)인 $\mathbf{x}_{\text{particular}}$, $\mathbf{x}_p$를 찾아야 한다.

■ 이 예에서는 여러 개의 해가 존재하므로, 특수 해인 $\mathbf{x}_p$를 찾는 방법은 다양할 수 있다.

■ 이런 경우, 가장 간단한 방법은 모든 자유 변수(free variable)을 0으로 설정하는 것이다.

- free variable은 어떤 값도 될 수 있으므로 가장 간단한 설정은 모두 0으로 설정하는 것이다.

■ 그다음, 피벗 변수(pivot variable)에 대해 $A \mathbf{x} = b$를 푼다.

■ 이 예에서 $x_2, x_4$가 free variable이므로 $x_2 = x_4 = 0$으로 설정하면, 첫 번째 방정식은 다음과 같이 $x_1$과 $2x_3$만 남으며, 이는 $b_1 = 1$과 같아야 한다. 그리고 두 번째 방정식은 $2x_3$만 남고, $2x_3$은 $b_2 = 3$과 같아야 한다.

■ $x_3 = \dfrac{3}{2}$이고 $x_1 = -2$이므로 특수 해 $\mathbf{x}_p$는 벡터 $[-2, 0, \dfrac{3}{2}, 0]^T$가 된다.

■ 이제 나머지 해들을 찾아야 한다. 이 나머지 해들은 영공간에서 찾는다. 이 해를 nullspace solution $\mathbf{x}_{\text{nullspace}}$, $\mathbf{x}_n$이라고 한다. 

■ 즉, $A \mathbf{x} = b$의 완전해 $\mathbf{x}$는  $\mathbf{x} = \mathbf{x}_p + \mathbf{x}_n$이며, 이는 $A \mathbf{x} = b$의 완전(전체) 해가 특수 해와 영공간에 속하는 모든 벡터의 선형 결합으로 정의할 수 있음을 의미한다.

■ 완전해를 구하기 위해 이와 같은 조합을 사용하는 이유는 $A \mathbf{x} = b$에서 $b$가 $A$의 열공간에 존재한다면, 선형 방정식은 해가 존재하는데, 

■ 이때 이 해에 영공간에 존재하는 어떠한 벡터를 추가해도 그 결과는 해가 된다. 이는 다음과 같은 식이 성립하기 때문이다.

- 특수 해의 경우 $A \mathbf{x}_p = b$이고, 영공간의 해는 항상 $A \mathbf{x}_n = 0$. 즉 우변 $b$가 0이된다.

- 그러므로 두 방정식을 더하면 우변은 $b$가 그대로 오기 때문에 식이 성립한다.

■ 이 예의 완전해를 찾으면 다음과 같이 특수 해와 영공간의 해를 더한 형태가 된다.

- 여기서 특수해에 상수를 곱할 수 없는 이유는 $A \mathbf{x}_p = b$를 만족해야 하기 때문이다. 

- 즉, $A \mathbf{x}_p$는 특정 값을 가지는 $b$를 만족해야 하기 때문에 상수를 곱하는 것은 허용되지 않는다.

- 반면, $A \mathbf{x}_n = 0$에서 영공간의 해는 유일한 해가 아니기 때문에 영공간 전체를 표현하기 위해 상수를 곱한 것이다.

 

2. Rank와 $A \mathbf{x} = b$의 해

2.1 Full column rank $r = n$

행렬 $A$가 $m \times n$이고 $\text{rank} (A) = r$일 때,

■ 행렬애 $m$개의 행이 있고 $r$개의 피벗이 있다면(= 행렬의 rank가 $r$), $r$과 $m$의 관계는 $r \leq m$이다.

- 행의 개수가 $m$개이므로 피벗의 개수 $r$은 $m$을 초과할 수 없다. 즉, 피벗의 개수는 $m$개 이하이다.

■ 행렬의 열이 $n$개라면, $r$과 $n$의 관계도 $r \leq n$이다. 하나의 열에는 하나의 피벗만 있을 수 있기 때문이다. 즉, 피벗의 개수는 열의 개수 $n$을 초과할 수 없다.

■ 이때 $r = n$이면, 모든 열이 피벗을 가지고 있는 것으로 free variable이 존재하지 않는다. 이를 풀 컬럼 랭크(full column rank)라고 한다. 이는 해의 존재여부와 관련이 있다.

■ $r = n$이라는 것은  free variable이 존재하지 않으므로, 행렬 $A$의 영공간에는 오직 영벡터(zero vector)만 존재함을 의미한다. 

■ 그러므로 완전해 $\mathbf{x} = \mathbf{x}_p + \mathbf{x}_n$에서 $\mathbf{x}_n = 0$이므로 $\mathbf{x} = \mathbf{x}_p$가 된다.

■ 만약, 특수 해 $\mathbf{x}_p$가 존재한다면, 유일한 해로 특수 해를 가질 것이며, 특수 해가 존재하지 않는다면 해가 없는 상황이 된다.

- 해가 존재하지 않는 상황은 앞서 설명한 $A$의 열벡터의 선형 결합으로 $b$를 만들 수 없는 상황이다.

■ 정리하면, $r = n$인 경우 해가 없거나 단 하나의 해만 존재한다.

■ 예를 들어 다음과 같은 행렬 $A$가 존재할 때,

$\begin{bmatrix} 1 & 3 \\ 2 & 1 \\ 6 & 1 \\ 5 & 7 \end{bmatrix}$

■ 소거법을 적용하면 2개의 열에 2개의 피벗이 존재하게 된다. ( 두 열벡터는 독립 관계를 가지므로 = 두 열벡터는 서로 다른 방향을 가리키므로)

■ 행렬 $A$를 기약행사다리꼴행렬 $R$로 만들면 다음과 같다.

$\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}$

■ $R$의 형태를 보면 $2 \times 2$ 단위행렬이 있으며, 그 아래는 모두 0이다. 즉, 이 행렬에는 두 개의 독립적인 행이 있으며, 첫 번째와 두 번째 행은 서로 독립이다. 그러므로 이 두 행은 동일한 방향을 가리키지 않는다고 할 수 있다.

■ 그리고 나머지 행인 3행과 4행은 모두 0이므로 첫 번째와 두 번째 행의 선형 결합으로 나머지 두 행을 표현할 수 있다는 것을 알 수 있다.

■ 결국 $A$에서 독립인 행은 첫 번째 행과 두 번째 행뿐이다. 그렇다면, 행렬 $A$에 대해 $A \mathbf{x} = b$는 항상 해를 가질 수 있을까

■ 이 예의 행렬 $A$는 full column rank이다. 두 열벡터를 이용해서 어떤 선형 결합을 해도 zero column을 만들 수 없다.  이는 영공간에 영벡터를 제외하면, 영공간에는 어떠한 비영벡터도 존재하지 않음을 의미한다. 

■ $A \mathbf{x} = b$의 완전해는 특수해와 영공간의 해로 표현된다는 점에서 영공간에 어떠한 비영벡터도 존재하지 않는다는 것은 특수해가 존재하면 유일한 해를 가지며, 특수해도 존재하지 않으면 해가 아예 존재하지 않는다는 것을 알 수 있다.

■ 이는 full column rank인 행렬에는 free variable이 없기 때문에 발생하는 일이라고 볼 수 있다.

■ 정리하면, 행렬 $A$가 풀 컬럼 랭크(full column rank)이면 $A \mathbf{x} = b$의 해는 아예 존재하지 않거나, 유일해를 가질 수 있다.

2.2 Full row rank $r = m$

■ 이번에는 행렬 $A$가 $r = m$으로 full row rank를 가지는 경우이다.

■ $r = m$이 의미하는 것은 모든 행이 pivot을 가지는 경우이므로 소거법을 수행하면 모든 행에 총 $m$개의 pivot이 존재한다. 

■ 즉, 소거법을 수행해도 모든 원소가 0인 행이 존재하지 않는다. 즉, 모두 독립 관계를 가지며 $A \mathbf{x}$라는 선형 결합으로 우변에 있는 어떠한 $b$를 생성할 수 있다고 볼 수 있다. 

■ 그러므로  $r = m$인 경우 모든 $b$에 대해 특별한 조건이 없어도  $A \mathbf{x} = b$의 해가 항상 존재한다.

■ free variable의 개수는 $n - r$개이다. $r = m$이라면 free variable의 수를 $n - m$으로 나타낼 수 있다.

■ 예를 들어 다음과 같은 행렬 $A$가 있을 때

$A = \begin{bmatrix} 1 & 2 & 6 & 5 \\ 3 & 1 & 1 & 1 \end{bmatrix}$

■ 이 행렬은 두 개의 행을 가지며, 소거법을 진행하면 행렬의 rank = 2임을 알 수 있다.

■ 기약행사다리꼴행렬 $R$을 보면, 첫 번째와 두 번째 컬럼은 pivot column으로 두 열은 행렬 $R$에서 단위행렬이 된다. 그리고 나머지 두 행은 free column으로 $F$ 행렬이다.

■ 그러므로, free variable이 존재하기 때문에 항상 해가 존재한다고 할 수 있다.

2.3 Full row and column rank $r = m = n$

■ 마지막 경우는 $r = m = n$으로 행렬의 rank와 행렬의 행 개수 그리고 열 개수가 모두 동일한 경우이다. 즉, 행렬이 정방행렬이면서 full rank를 가지는 경우이다.

■ 예를 들어 행렬 $A$가 다음과 같이 정방행렬이며 $r = m = n$이라면

$A = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$

■ 다음과 같이 free column이 존재하지 않기 때문에 영공간에는 오직 영벡터만 존재한다. 

■ 그리고 $R$이 단위행렬의 형태가 되므로 행렬 $A$가 가역행렬임을 알 수 있다. 

■ 그러므로 $r = m = n$인 경우 모든 $b$에 대해 $A \mathbf{x} = b$의 해가 존재한다. 단, 이 해는 $b$에 대한 유일해이다.

- $\mathbf{x} = A^{-1}b$

■ 위의 $r = m$과 $r = n$인 경우에 해를 갖는 조건으로 생각하면, $r = m$이므로 모든 $b$에 대해 $A \mathbf{x} = b$의 해가 존재하며, $r = n$이므로 해는 유일하다고 할 수 있다.

■ 그리고 위의 예시처럼, $r = m = n$인 경우 행렬 $A$를 $R$로 만들면 단위행렬이 되는 것을 확인하였다. 그러므로 $r = m = n$인 행렬은 가역행렬의 완벽한 조건을 만족한다고 볼 수 있다.

 

■ 행렬 $A$가 $m \times n$이고 $\text{rank} (A) = r$일 때, $A \mathbf{x} = b$의 해를 가지는 조건을 정리하면,

- ① $r = m = n$이면 (정방)행렬 $A$는 기약행사다리꼴은 단위행렬이며, $A \mathbf{x} = b$에 대해 유일해를 갖는다.

- ② $r = n < m$이면 행렬 $A$의 기약행사다리꼴행렬 $R$은 단위행렬과 0으로 구성되며, 해가 아예 없거나 유일해를 가질 수 있다.

- ③ $r = m < n$이면 행렬 $A$의 기약행사다리꼴행렬 $R$은 pivot column으로 구성된 단위행렬과 free column으로 구성되므로, 항상 해가 존재한다. (무수히 많은 해를 갖는다.)

- ④ $r < m , r < n$이면 행렬 $A$의 기약행사다리꼴행렬 $R$은 $[ I F 0 0 ]^T$ 형태가 되며, 해가 아예 없거나 무수히 많은 해를 가질 수 있다.

■ 이러한 해를 가지는 조건을 확대행렬로 옮기면

- ① $\text{rank} (A) = \text{rank} (A \mid b) = m$이면 해가 존재한다.

- $r = m$이면 모든 $b \in \mathbb{R}^m$에 대해 방정식 $A \mathbf{x} = b$는 해를 갖는다.

- $m$은 행의 개수 = 선형 방정식의 식의 개수 = rank A의 최댓값이다. 

- 그런데 $\text{rank} (A) = r = m$이라는 것은, 풀랭크를 의미하며 이는 자동적으로 $m = \text{rank} (A) = \text{rank} (A \mid b)$을 의미한다.

- ② $\text{rank} (A) < \text{rank} (A \mid b)$이면 해가 존재하지 않는다. 

- 우변 $b$ 계수행렬 $A$의 열공간에 속하지 않기 때문이다.

- ③ $\text{rank} (A) = \text{rank} (A \mid b) = n$이면 유일해를 가진다. 

- ④ 단, $\text{rank} (A) = \text{rank} (A \mid b) < n$라면  free variable이 존재하기 때문에 $\mathbf{x} = \text{scalar} \cdot [\,\text{vector1},\ \text{vector2},\ \dots\,]^\top$처럼 무수히 많은 해가 존재한다.