선형대수 03 - RREF, 동차연립방정식, Rank of Matrix

행 간소 사다리꼴 (Reduced Row Echelon Form, RREF)

RREF는 REF를 조금 더 단순화시킨 형태입니다. 다음과 같은 특성을 만족하는 경우 RREF라고 합니다.

  • all-zero-row는 항상 가장 아래에 배치한다.
  • leading-entry (leading-1)은 1이여야 한다.
  • Upper Triangle의 구조가 되어야 한다.
  • leading-1을 가지고 있는 칼럼에서는 leading-1을 제외한 나머지 성분이 모두 0이여야 한다.

위 세가지는 REF가 가지고 있던 특성입니다. RREF에서는 맨 아래 줄의 특성이 추가된 것이라고 보면 되는데, 열(칼럼)을 기준으로 leading-1이 있는 열에서는 ERO를 통해서 leading-1을 제외한 나머지 성분을 0으로 바꾸어 주어야 합니다. 그렇게 해서 완성된 Form을 우리는 RREF라고 부릅니다.

{x1+x2+2x3=92x27x3=1712x3=32  or  [112902717001232]  {x1+x2+2x3=9x272x3=172x3=3  or  [112901721720013]  {x1+x2+2x3=9x2=2x3=3  or  [112901020013]  {x1=1x2=2x3=3  or  [100101020013]\begin{cases} x_1 + x_2 + 2x_3 = 9 \\ 2x_2 -7x_3 = -17 \\ -\frac{1}{2}x_3 = -\frac{3}{2} \\ \end{cases} \;or\; \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 2 & -7 & -17 \\ 0 & 0 & -\frac{1}{2} & -\frac{3}{2} \\ \end{bmatrix} \\ \rightarrow \; \begin{cases} x_1 + x_2 + 2x_3 = 9 \\ x_2 - \frac{7}{2}x_3 = -\frac{17}{2} \\ x_3 = 3 \end{cases} \;or\; \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 1 & -\frac{-7}{2} & -\frac{17}{2} \\ 0 & 0 & 1 & 3 \end{bmatrix} \\ \rightarrow \; \begin{cases} x_1 + x_2 + 2x_3 = 9 \\ x_2 = 2 \\ x_3 = 3 \end{cases} \;or\; \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{bmatrix} \\ \rightarrow \; \begin{cases} x_1 = 1 \\ x_2 = 2 \\ x_3 = 3 \end{cases} \;or\; \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{bmatrix} \\

마지막에 정확히 열(column)마다 leading-1을 제외하고는 모두 0이 되었음을 알 수 있습니다.

RREF는 Identity Matrix(단위 행렬)와 비슷한 형태라고 볼 수 있습니다. 굳이 RREF가 아니고 REF 정도만 만들더라도 문제를 푸는데 지장은 없지만, RREF를 만들면 해를 구하기 훨씬 쉬워집니다.

하지만 방정식의 개수와 미지변수의 개수가 일치하지 않을 수 있습니다. 특히 미지변수가 더 많은 경우, 모든 칼럼에 leading-1이 존재하는 것이 불가능하게 됩니다. 그런 경우, leading-1이 존재하지 않는 칼럼이 생기게 됩니다.

여기서 미지변수에 대응하는 leading-1이 존재할 때, (즉 미지변수에 해당하는 칼럼에 leading-1이 있을 때) 해당 미지변수를 leading-variable이라고 합니다.

반대로, 미지변수에 대응하는 leading-1이 없을 때(즉 미지변수에 해당하는 칼럼에 leading-1이 존재하지 않을 때) 해당 미지변수는 free-variable이라고 합니다.

{x1x2+x4=2x3x4=10=0    [110120011100000]\begin{cases} x_1 - x_2 + x_4 = 2 \\ x_3 - x_4 = 1 \\ 0 = 0 \end{cases} \; \rightarrow \; \begin{bmatrix} 1 & -1 & 0 & 1 & 2 \\ 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \\

여기서 x1x_1x3x_3은 각각 1열과 3열에 leading-variable을 가지고 있으므로 leading-variable입니다.
반대로 x2x_2x4x_4는 각각 2열과 4열에 leading-varibable을 가지고 있지 않으므로 free-variable입니다.

저는 미지변수가 방정식의 개수보다 많으면 무한대로 많은 솔루션을 가지게 되므로, free-variable이 발생하는 것이라고 이해했습니다.

어떤 연립방정식(SOLE)이 무한대로 많은 솔루션을 가지고 있을 때, 각각의 free-variable에 parameter를 할당해줌으로써 전체적인 솔루션을 구성할 수 있습니다.

Example. RREF에서 free-variable에 대해서 parameter 할당하기

{x1x2+x4=2x3x4=1\begin{cases} x_1 - x_2 + x_4 = 2 \\ x_3 - x_4 = 1 \end{cases}

위 연립방정식에서 우리는 x1x_1x3x_3이 leading-variable임을 알 수 있다.x2x_2x4x_4가 free-variable임으로,

{x1=x2x4+2x3=x4+1\begin{cases} x_1 = x_2 - x_4 + 2 \\ x_3 = x_4 + 1 \end{cases}

위와 같이 나타낼 수 있다. free variable에 각각 다음과 같이 parameter를 할당해주는 방식으로 문제를 푸는 것이 편리합니다.
결국 해의 개수가 매우 많으므로, parameter를 기준으로 해를 구하는 것이라고 보시면 됩니다.

x2=s,  x4=tx_2 = s, \; x_4 = t {x1=st+2x3=t+1  or  [x1x2x3x4]=[2010]+s[1100]+t[1011]\begin{cases} x_1 = s - t + 2 \\ x_3 = t + 1 \end{cases} \;or\; \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 1 \\ 0 \end{bmatrix} + s \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + t \begin{bmatrix} -1 \\ 0 \\ 1 \\ 1 \end{bmatrix}

이와 같이 표현할 수 있습니다. 연립선형방정식이 무한대개의 솔루션을 가지고 있을 때, 가장 일반적인 표현 방법입니다.

REF와 RREF

REF의 모든 행은 다음의 2가지 타입 중 하나입니다.

  • All Zero Row
  • 0이 아닌 첫 성분이 1, 즉 leading-1을 가지고 있는 행

REF와 RREF의 관계

  • REF가 일련의 ERO를 거치면 RREF가 된다.
  • REF와 RREF는 행동치(row equivalant)이다.
  • REF와 RREF의 leading-variable은 같다.
  • RREF는 leading-1을 가지고 있는 칼럼의 나머지 성분을 제거해주는 것 뿐이다.
  • REF와 RREF의 Solution의 결과는 항상 같다.

동차연립방정식 (Homogeneous linear Systems)

동차연립방정식: 우변의 데이터 값이 0인 연립방정식입니다. Ax=0Ax = 0

  • Homogeneous System은 Consistant(해를 갖는)다.
  • Homogeneous System은 자명해를 갖는다.
  • Homogeneous System은 자명해 외에 무한히 많은 솔루션을 가질 수 있다.
  • Homogeneous System에서 특히 under-determinned 상황에서는 무한대로 많은 개수의 Solution을 가지고 있다고 예측할 수 있다.

Rank of Matrix

rank는 REF 형태에서의 non-zero row의 개수를 말합니다.

만약 A가 SOLE이고 n개의 미지변수를 갖고, 이 방정식이 해를 갖는다면,

Number  of  free  variables=nrank(A)Number\;of\;free\;variables = n - rank(A)이다.

Free variable의 개수는 항상 0보다 크거나 같습니다. nrank(A)0n - rank(A) \ge 0이기 때문.

© 2020 leshleekor