[Linear Algebra] 기약행 사다리꼴 형태 (Reduced row echelon form, rref)

기약행 사다리꼴 형태 (Reduced row echelon form, rref)

관련된 내용

• 역행렬(Inverse matrix)
• 행렬식(Determinant)

행사다리 꼴(row echelon form, ref)은 식 1과 같이 상삼각행렬 형태를 보입니다. 각 행에서 0이외의 첫번 째 요소가 1인 경우를 기약행사다리꼴(reduced row echelon form, rref) 이라고 합니다.

$$\begin{bmatrix}0& a& b & c & \cdots\\0& 0& d & e & \cdots\\0& 0& 0 & f & \cdots\\ \vdots& \vdots& \vdots& \vdots& \ddots\end{bmatrix}$$

(식 1)

식 2는 연립방정식을 행렬 방정식으로 나타낸 것입니다.

$$\begin{aligned}x+y& =2\\ 2x+4y &=-3\\ 3x+6y & =5 \end{aligned}\Rightarrow \begin{bmatrix} 1& 1\\2& 4\\3& 6\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix}2\\ -3\\5\end{bmatrix}$$

(식 2)

식 2에서는 나타낸 것과 같이 표준행렬은 정방행렬이 아니므로 역행렬에 의한 해를 결정할 수 없습니다. 이 경우 식 3에서 나타낸 것과 같이 표준행렬과 상수행렬을 결합한 형태에서 각 행간의 연산에 의해 표준행렬을 항등행렬의 형태로 전환할 수 있다면 해를 결정 할 수 있습니다.

\begin{align}\begin{bmatrix} 1& 1& :2 \\2& 4& :-3\\3& 6 & :5\end{bmatrix} &\Rightarrow \begin{bmatrix} 1& 0& :a \\0& 1& :b\\0& 0 & :0\end{bmatrix}\\ \begin{bmatrix} 1& 0 \\0& 1\\0& 0\end{bmatrix} \begin{bmatrix} x \\y\end{bmatrix}&= \begin{bmatrix} a \\b\\c\end{bmatrix}\\ \therefore x=a &\quad y=b\end{align}

(식 3)

식 3의 첫 행렬과 같이 표준행렬과 상수행렬을 결합한 형태를 확대 행렬(augment matrix)이라고 합니다. 식 4와 같이 확대행렬에서 두 행간의 연산을 반복하여 최종적으로 표준행렬을 항등행렬과 유사한 형태인 기약행 사다리꼴 형태(rref)로 수정하는 것으로 각 미지수의 해를 결정할 수 있습니다. 이 방법을 가우스조르당 소거법이라고 합니다.

1행 × 2 − 2행 = 2행	(식 4)
⋮

식 2.2.7에서 나타낸 것과 같이 확대 행렬에서 표준행렬과 상수행렬을 구분하기 위해 콜론을 사용했습니다. 다음은 콜론의 오른쪽에 나타낸 표준행렬을 rref로 변환하기 위한 연산 과정을 코드화한 것입니다.

au=np.array([[1,1,2], [2,4,-3], [3,6,5]])
print(au)

[[ 1  1  2]
 [ 2  4 -3]
 [ 3  6  5]]

au[1,:]=au[1,:]-2*au[0,:]
print(au)

[[ 1  1  2]
 [ 0  2 -7]
 [ 3  6  5]]

au[2,:]=au[2,:]-3*au[0,:] 
au[1,:]=au[1,:]/2 
au[0,:]=au[0,:]-au[1,:] 
au[2,:]=au[2,:]-3*au[1,:] 
au[2,:]=au[2,:]/8
print(au)

[[ 1  0  5]
 [ 0  1 -3]
 [ 0  0  1]]

위 결과와 같이 상수행렬의 각 요소는 표준행렬에 표시되는 각 변수에 대한 해가 됩니다. 위 결과는 식 5와 같이 나타낼 수 있습니다.

$$\begin{bmatrix} 1& 0 \\0& 1\\0& 0\end{bmatrix} \begin{bmatrix} x \\y\end{bmatrix}= \begin{bmatrix} 5\\-3\\1\end{bmatrix} \Rightarrow \begin{aligned}x&=5\\y&=-3\\0x+0y&=1 \end{aligned}$$

(식 5)

식 5의 3번째 행(식)의 경우는 계수가 모두 0인데 상수 1과 같음을 의미하는 것으로 성립될 수 없는 식입니다. 그러므로 이 선형시스템(연립방정식)의 해는 존재할 수 없습니다. 이와 같이 해를 결정할 수 없는 연립방정식(선형시스템)을 모순된 시스템(inconsistemt system)이라 합니다. 그림 1은 위 연립방정식(식 2)을 나타낸 것으로 세개의 직선의 교차점은 존재할 수 없습니다.

그림 1. 교차점을 가지지 않는 세 직선.

메서드 sympy객체.rref()를 사용하여 rref를 확인할 수 있습니다. 이 메서드를 적용하는 sympy 객체는 모듈 sympy의 여러 함수들로 생성된 객체이며 파이썬의 기본 자료형인 리스트 형식으로 생성됩니다. 이것은 numpy의 배열(array)과 같은 형식이므로 두 모듈에서 생성된 객체의 상호변환이 가능합니다. 그러므로 다음 코드와 같이 numpy의 배열 객체는 sympy 모듈의 행렬을 생성하는 함수 Matrix()을 사용하여 변환하여 메서드 rref()에 적용할 수 있습니다. 이 메서드는 객체의 rref와 선도변수의 위치를 튜플 형태로 반환합니다. 선도변수의 위치는 각 행에서 첫 1의 값이 나오는 위치에 해당하는 열 번호를 나타냅니다.

A=np.array([[1,1],[2,4],[3,6]])
print(A)

[[1 1]
 [2 4]
 [3 6]]

print(Matrix(A).rref())

(Matrix([
[1, 0],
[0, 1],
[0, 0]]), (0, 1))

식6과 같이 표현되는 기약행사다리꼴은 행렬의 다양한 정보를 포함하고 있습니다.

$$\begin{bmatrix}{\color{red}{1}}&0&0&0 & \cdots\\0& {\color{red}{1}}& 0 & 0 & \cdots\\0& 0& {\color{red}{1}} & 0 & \cdots\\ \vdots& \vdots& \vdots& \vdots& \ddots\end{bmatrix}$$

(식 6)

[기약행사다리꼴 형태의 특성]

1. 선도 1(leading 1): 각 행에서 0이후에 나타나는 첫 번째 요소로서 그 값이 1인 경우를 의미
   • 선도 1이 나타난 위치를 피봇 위치(pivot position)이라 합니다.
2. 피봇열(pivot column): 피봇 위치를 포함하는 열 (column)
   • 선도변수(leading variable): 피봇 열에 해당하는 변수
   • 자유변수(free variable): 피봇 열이 아닌 열에 대응하는 변수
   • 자유변수가 존재하면 다수의 해들이 존재합니다.
3. k 행이 모두 0으로 구성되지 않는 경우 선도 1 이전의 0수는 k+1 행보다 k행이 더 많습니다.
4. 어떤 행의 요소들이 모두 0인 경우 그 직전 행의 모든 요소들이 0은 아닙니다.
5. 선도 1을 포함하는 행의 나머지 요소들은 모두 0입니다.

위 특성들 중 1, 2, 3, 4를 만족하면 행사다리꼴 형태(row echelon form, ref)이며 위의 모든 특성을 충족하는 경우 기약 행 사다리꼴 형태(rref)이 됩니다.

예 1)

다음 연립 방정식의 해를 기약행사리꼴 형태를 사용하여 계산해봅니다.

a + b - c + 3d = 0

3a + b - c - d = 0

2a - b - 2c + d = 0

위 연립방정식의 확대행렬 aug는 다음과 같습니다.

aug=np.array([[1,1,-1,3, 0], [3,1,-1, -1, 0], [2,-1,-2, 1, 0]])
print(aug)

[[ 1  1 -1  3  0]
 [ 3  1 -1 -1  0]
 [ 2 -1 -2  1  0]]

re=Matrix(aug).rref()
re

(Matrix([
 [1, 0, 0,    -2, 0],
 [0, 1, 0,   5/3, 0],
 [0, 0, 1, -10/3, 0]]),
 (0, 1, 2))

위 결과는 1, 2, 그리고 3열이 피봇열로 3개의 선도변수와 1개의 자유변수가 존재함을 나타냅니다. 이 결과는 식 7과 같이 나타낼 수 있습니다.

\begin{align}&\begin{bmatrix} 1&0&0&-2\\ 0& 1& 0 & \frac{5}{3} \\ 0& 0&1 &\frac{-10}{3}\end{bmatrix} \begin{bmatrix} a\\b\\c\\d\end{bmatrix}= \begin{bmatrix} 0\\0\\0\end{bmatrix}\\ &\Rightarrow \begin{aligned}a-d =0 & \rightarrow a=d\\ b+\frac{5}{3}d=0& \rightarrow a=-\frac{5}{3}\\ c-\frac{10}{3}d=0 &\rightarrow c=\frac{10}{3}d\end{aligned}\end{align}

(식 7)

식 7에서 나타낸 것과 같이 선도변수인 a, b, c는 자유변수인 d에 의존합니다. 즉, 자유변수가 존재하면 다수의 해가 존재합니다.