[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) 이라고 합니다.

$$\left[\begin{array}{ccccc}0& a& b& c& \cdots \\ 0& 0& d& e& \cdots \\ 0& 0& 0& f& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right]$$

(식 1)

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

$$\begin{array}{rl}x+y& =2\\ 2x+4y& =-3\\ 3x+6y& =5\end{array}\Rightarrow \left[\begin{array}{cc}1& 1\\ 2& 4\\ 3& 6\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}2\\ -3\\ 5\end{array}\right]$$

(식 2)

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

$$\begin{array}{rl}\left[\begin{array}{ccc}1& 1& :2\\ 2& 4& :-3\\ 3& 6& :5\end{array}\right]& \Rightarrow \left[\begin{array}{ccc}1& 0& :a\\ 0& 1& :b\\ 0& 0& :0\end{array}\right]\\ \left[\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]& =\left[\begin{array}{c}a\\ b\\ c\end{array}\right]\\ \therefore x=a& y=b\end{array}$$

(식 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와 같이 나타낼 수 있습니다.

$$\left[\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}5\\ -3\\ 1\end{array}\right]\Rightarrow \begin{array}{rl}x& =5\\ y& =-3\\ 0x+0y& =1\end{array}$$

(식 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과 같이 표현되는 기약행사다리꼴은 행렬의 다양한 정보를 포함하고 있습니다.

$$\left[\begin{array}{ccccc}1& 0& 0& 0& \cdots \\ 0& 1& 0& 0& \cdots \\ 0& 0& 1& 0& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right]$$

(식 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{array}{rl}& \left[\begin{array}{cccc}1& 0& 0& -2\\ 0& 1& 0& \frac{5}{3}\\ 0& 0& 1& \frac{-10}{3}\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\\ & \Rightarrow \begin{array}{rl}a-d=0& \to a=d\\ b+\frac{5}{3}d=0& \to a=-\frac{5}{3}\\ c-\frac{10}{3}d=0& \to c=\frac{10}{3}d\end{array}\end{array}$$

(식 7)

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