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
\)처럼 무수히 많은 해가 존재한다.