mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-06-07 22:55:00

행사다리꼴

가우스 소거법에서 넘어옴
선형대수학
Linear Algebra
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#006ab8> 기본 대상 일차함수 · 벡터 · 행렬 · 선형 변환
대수적 구조 가군(모듈) · 벡터 공간 · 내적 공간 · 노름 공간
선형 연산자 <colbgcolor=#006ab8> 기본 개념 연립방정식( 1차 · 2차) · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식( 라플라스 전개) · 주대각합
선형 시스템 기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법
주요 정리 선형대수학의 기본정리 · 차원 정리 · 가역행렬의 기본정리 · 스펙트럼 정리
기타 제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 · 노름(수학)
벡터공간의 분해 상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화( 대각행렬) · 삼각화 · 조르당 분해
벡터의 연산 노름 · 거리함수 · 내적 · 외적( 신발끈 공식) · 다중선형형식 · ∇ · 크로네커 델타
내적공간 그람-슈미트 과정 · 수반 연산자( 에르미트 내적)
다중선형대수 텐서 · 텐서곱 · 레비치비타 기호 }}}}}}}}}

1. 개요2. 정의3. 예시4. 연립방정식에서의 활용5. 기약행사다리꼴6. 가우스 소거법
6.1. 예시6.2. 가우스-조르당 소거법
7. 성질
7.1. 중요한 성질7.2. 별로 안 중요한 성질
8. 같이 보기

1. 개요

행사다리꼴행렬(row echelon form matrix, REF)이란 다음과 같이 성분이 계단 모양으로 배열된 행렬을 뜻한다.
[math(\begin{pmatrix}a_{11} & a_{12}& a_{13}& a_{14}&\cdots& a_{1n}\\0&a_{22}&a_{23}&a_{24}&\cdots&a_{2n}\\0&0&0&a_{34}&\cdots&a_{3n}\\0&0&0&0&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\\0&0&0&0&\cdots&0 \end{pmatrix})]
아래의 행렬처럼 배열된 행렬은 기약행사다리꼴(reduced row echelon form, RREF)이라 한다.
[math(\begin{pmatrix}1 & 0& a_{13}& 0&\cdots& a_{1n}\\0&1&a_{23}&0&\cdots&a_{2n}\\0&0&0&1&\cdots&a_{3n}\\0&0&0&0&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\\0&0&0&0&\cdots&0 \end{pmatrix})]
연립방정식의 계수행렬 또는 첨가행렬에 행동치인 행사다리꼴 행렬을 이용하여, 연립방정식의 해를 쉽게 구할수 있다. 또한 행렬의 계수(rank)와 퇴화차수(nullity)를 한 눈에 알 수 있다는 장점이 있다.

2. 정의

행사다리꼴 행렬을 정의하기에 앞서 용어 하나를 먼저 정의하겠다. 행사다리꼴 행렬은 다음의 성질을 만족하는 행렬을 뜻한다.

3. 예시

4. 연립방정식에서의 활용

연립방정식 [math(Y=AX)]에서 계수행렬 [math(A)]의 [math(i)] 열에 위치한 성분은 [math(x_{i})]의 계수를 나타낸다. 계수행렬이 행사다리꼴 행렬 [math(R)]인 연립방정식 [math(Y=RX)]에서 leading entry가 존재하는 열에 해당하는 변수는 종속변수가 되고, leading entry가 존재하지 않는 열에 해당하는 변수는 자유변수가 된다. 이를 이용해 아래에 위치한 행 부터 종속변수의 값을 결정해 나갈수있고, 해를 찾을수 있다. 이를 후진대입법이라 한다. 후진대입법을 통해 계수행렬이 행사다리꼴 행렬인 연립방정식을 풀어보자. 연립방정식
[math(\begin{pmatrix}2&3&2&0\\0&0&3&2\\0&0&0&1\\0&0&0&0\end{pmatrix}\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{pmatrix}=O)]
에 대하여, leading entry가 존재하는 열을 확인해보면, 자유변수는 [math(x_{2})]이고, 종속변수는 [math(x_{1})], [math(x_{3})], [math(x_{4})]임을 알수있다. 이게 맞다면, [math(x_{1})], [math(x_{3})], [math(x_{4})]를 [math(x_{2})]에 대한 함수로 나타낼수 있을것이다. 후진대입법을 통해, 3행으로부터 [math(x_{4}=0)]을 얻는다. 2행으로부터 [math(3x_{3}+2x_{4}=0)]를 얻고, 먼저 구한 [math(x_{4}=0)]을 대입하면, [math(x_{3}=0)]를 얻는다. 마찬가지로, 1행으로부터 [math(2x_{1}+3x_{2}+ 2x_{3}=0)]를 얻고, 미리 구한 [math(x_{3}=0)]를 대입하고 적절히 정리하면 [math(x_{1}=-\frac{3}{2}x_{2})]를 얻는다. 따라서 주어진 연립방정식의 해는
[math(X=x_{2}\begin{pmatrix}-\frac{3}{2}\\1\\0\\0\end{pmatrix})]
이라는것을 알수있다. 왜 굳이 후진대입법으로 아래의 행부터 종속변수의 값을 결정해야하느냐 하면, 같은 종속변수임에도 불구하고, 각 non-zero 행에서 leading entry에 해당하는 변수가 더 아래에 있는 행에 위치한 leading entry에 해당하는 변수의 영향을 받기 때문이다. 그러나, 연립방정식의 계수행렬이 후술할 기약행사다리꼴인 경우 굳이 후진대입법을 통해 해를 구할 필요는 없다.

5. 기약행사다리꼴

행사다리꼴 행렬 중에서 다음과 같은 조건을 추가로 만족하는 것을 기약행사다리꼴 또는 행 간소 사다리꼴(reduced row echelon form, RREF)이라 한다.
기약행사다리꼴 행렬에 대해 다음의 세 성질을 만족한다. 범주론에서 위와 같은 세 성질(①[math(c(s)=c(c(s)))], ②[math(s_{1}\sim s_{2} \iff c(s_{1})=c(s_{2}))], ③[math(c(s)\sim s)])을 만족하는 수학적 오브젝트([math(c(s))])를 표준형(canonical form)이라고 하는데, 그러한 의미에서 기약행사다리꼴을 행 표준형(row canonical form) 이라고도 한다.

6. 가우스 소거법

가우스 소거법(Gaussian elimination)이란 주어진 행렬을 유한번의 기본행연산을 하여 행동치인 행사다리꼴로 만드는 방법이다. 그 방법은 다음과 같다. 행의 개수를 [math(n)], 열의 개수를 [math(m)]이라고 하자.
  1. [math(i=1)], [math(j=1)]이다.
  2. [math(i)]행부터 차례대로 [math(j)]열에 leading entry가 있는 행을 찾는다. (그런 행이 없으면 6으로 넘어간다.) 그 중 가장 먼저오는 행을 [math(k)]행 이라고 하자.
  3. [math(k)]행과 [math(i)]행을 서로 바꾼다.
  4. 바뀐 행렬에서 [math(i<i^{\prime}\leq n)]을 만족하는 모든 [math(i^{\prime})]에 대해 ([math(i^{\prime})]행)을 ([math(i^{\prime})]행)[math(-\displaystyle\frac{a_{i^{\prime}j}}{a_{ij}})]([math(i)]행)으로 바꾼다.
  5. [math(i)]를 [math(i+1)]로 바꾼다.
  6. [math(j=m)]이면 연산을 끝내고, [math(j<m)]이면 [math(j)]를 [math(j+1)]로 바꾸어 2로 돌아간다.

물론 위의 방법은 '적절한' 이라는 단어를 이해하지 못하는 컴퓨터를 위한 알고리즘이다. 직접 손으로 행동치인 행사다리꼴을 유도할 때에는 계산하기 편하도록 '적절하게' 행을 선택하여 유도해 나가면 된다. 물론 어떤 행을 선택했느냐에 따라 결과는 다르게 나올수도 있지만, 모두 행동치인 행사다리꼴이다.

6.1. 예시

[math(\begin{pmatrix}0 & 1 & 2 & 1 & 0 & 3 \\3 & 0 & 1 & 4 & 3 & 2 \\1 & 2 & 2 & 0 & 5 & 1 \\2 & 0 & 0 & 3 & 1 & 0 \end{pmatrix})]
위의 행렬의 1열에는 2행,3행,4행의 leading entry가 있다. 그중 가장 빠른 행은 2행이지만, 2행으로 3행,4행을 빼려면 분수 계산을 해야하므로 leading entry가 [math(1)]인 3행을 택하여 1행과 바꾸자.
[math(\begin{pmatrix}1 & 2 & 2 & 0 & 5 & 1 \\3 & 0 & 1 & 4 & 3 & 2 \\0 & 1 & 2 & 1 & 0 & 3 \\2 & 0 & 0 & 3 & 1 & 0 \end{pmatrix})]
그 다음 2행, 3행, 4행을 1행에 적절히 상수배를 하여 1열에 0이 오도록 빼준다.
[math(\begin{pmatrix}1 & 2 & 2 & 0 & 5 & 1 \\0 & -6 & -5 & 4 & -12 & -1 \\0 & 1 & 2 & 1 & 0 & 3 \\0 & -4 & -4 & 3 & -9 & -2 \end{pmatrix})]
마찬가지로 위의 행렬에 2열에 leading entry가 있는 행 중 3행의 leading entry가 [math(1)]이므로 3행과 2행을 바꾸자.
[math(\begin{pmatrix}1 & 2 & 2 & 0 & 5 & 1 \\0 & 1 & 2 & 1 & 0 & 3\\0 & -6 & -5 & 4 & -12 & -1 \\0 & -4 & -4 & 3 & -9 & -2 \end{pmatrix})]
그 다음, 3행, 4행을 2행에 적절히 상수배를 하여 2열에 0이 오도록 빼준다.
[math(\begin{pmatrix}1 & 2 & 2 & 0 & 5 & 1 \\0 & 1 & 2 & 1 & 0 & 3\\0 & 0 & 7 & 10 & -12 & 17 \\0 & 0 & 4 & 7 & -9 & 10 \end{pmatrix})]
그 다음 3행을 선택하든 4행을 선택하든 분수계산은 피할수 없으므로 아무거나 선택하자. 3행을 택하겠다. 그 후 4행을 3행에 적절히 상수배를 해줘서 빼주면
[math(\begin{pmatrix}1 & 2 & 2 & 0 & 5 & 1 \\0 & 1 & 2 & 1 & 0 & 3\\0 & 0 & 7 & 10 & -12 & 17 \\0 & 0 & 0 & \displaystyle\frac{9}{7} & -\displaystyle\frac{15}{7} & \displaystyle\frac{2}{7} \end{pmatrix})]
가 된다. 위의 행렬은 행사다리꼴 행렬이므로 끝난 것이다. Wolfram Alpha 유료 앱을 핸드폰에 깔아서 수식 입력창에 'row echelon form of {{0,1,2,1,0,3},{3,0,1,4,3,2},{1,2,2,0,5,1},{2,0,0,3,1,0}}'을 입력하고 'Step-by-step solution'을 클릭하면 저 과정을 그대로 보여주며 마지막에는 행사다리꼴을 넘어서 아예 기약행사다리꼴(reduced row echelon form)로 정리해준다.

6.2. 가우스-조르당 소거법

가우스 소거법이 행렬을 단순한 행사다리꼴행렬로 만든다면 가우스-조르당 소거법은 (가능하면 단위행렬인) 기약행사다리꼴행렬로 만드는 소거법이다.

예시로
[math(\left[ \begin{array}{ccc|c} 4 & 1 & 5 & 53 \\ 0 & 2 & 4 & 0 \\ 6 & 11 & 23 & 69 \end{array} \right])]
이 첨가 행렬을 가우스-조르당 소거법으로 소거하면

우선 1열에 1을 차지할 행은 1행이니, 3행 1열의 값을 0으로 만들어준다 (즉 이번에는 1행의 3/2값을 뺀다)
[math(\left[ \begin{array}{ccc|c} 4 & 1 & 5 & 53 \\ 0 & 2 & 4 & 0 \\ 0 & 9.5 & 15.5 & -10.5 \end{array} \right])]

그리고 2행의 1열은 1행에 1을 차지할 자리는 1열이니, 2열에 1을 차지할 행은 2행이라 2행을 그렇게 정리한다 (즉 2행을 2로 나눈다)
[math(\left[ \begin{array}{ccc|c} 4 & 1 & 5 & 53 \\ 0 & 1 & 2 & 0 \\ 0 & 9.5 & 15.5 & -10.5 \end{array} \right])]

가우스 소거법에서는 1행을 둬도 괜찮으나, 가우스-조르당 소거법은 기약행사다리꼴행렬로 만들기 때문에 1행의 2열과 3열을 0으로 만들어야 한다. 즉 1행에서 2행을 빼 2열을 0으로 만든다.
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 3 & 53 \\ 0 & 1 & 2 & 0 \\ 0 & 9.5 & 15.5 & -10.5 \end{array} \right])]

다음 3행 2열의 값이 0이 아니므로 3행 2열의 값을 0으로 만들어준다 (3행에서 2행의 9.5배를 뺀다)
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 3 & 53 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & -3.5 & -10.5 \end{array} \right])]

3행은 1열과 2열이 0이며 3열을 1로 만들면 3행에 대한 작업은 끝난다. (3행을 -3.5로 나눈다)
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 3 & 53 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & 3 \end{array} \right])]

이제 1행과 2행의 3열을 0으로 바꾼다. 2행부터 시작한다. (2행에서 3행의 2배를 뺀다)
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 3 & 53 \\ 0 & 1 & 0 & -6 \\ 0 & 0 & 1 & 3 \end{array} \right])]

그리고 1행도 역시 3열을 0으로 바꾼다.
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 0 & 44 \\ 0 & 1 & 0 & -6 \\ 0 & 0 & 1 & 3 \end{array} \right])]

1행을 4로 나누어 1행 1열을 0으로 바꾼다.
[math(\left[ \begin{array}{ccc|c} 1 & 0 & 0 & 11 \\ 0 & 1 & 0 & -6 \\ 0 & 0 & 1 & 3 \end{array} \right])]

그리고 이는 기약행사다리꼴행렬이 된다.

허나 이 방식으로 한 행이 모두 0으로 되거나 한 행에 부득이하게 여러 열에 값이 있을 수 있다. 전자의 경우 다른 행들의 결합으로 나타낼 수 있다는 뜻이며, 후자의 경우 선형방정식이라는 가정하에 해가 줄이라서 한 값은 그 어떠한 값을 허용하며 다른 행 중 최소 하나는 그 값에 따라 바뀌는 것이다.

예시
[math(4x_{1}+2x_{2}+6x_{3} = 48, 4x_{2}+4x_{3} = 16)]를 보자면
[math(\left[ \begin{array}{ccc|c} 4 & 2 & 6 & 48 \\ 0 & 4 & 4 & 16 \end{array} \right])]

이므로 우선 2행을 4로 나눈다.
[math(\left[ \begin{array}{ccc|c} 4 & 2 & 6 & 48 \\ 0 & 1 & 1 & 4 \end{array} \right])]

그 후 1행에서 2행의 2배를 빼고
[math(\left[ \begin{array}{ccc|c} 4 & 0 & 4 & 40 \\ 0 & 1 & 1 & 4 \end{array} \right])]

1행을 4로 나눈다.
[math(\left[ \begin{array}{ccc|c} 1 & 0 & 1 & 10 \\ 0 & 1 & 1 & 4 \end{array} \right])]
여기서 추가 작업으로 1열과 2열을 건드리지 않고 3열을 없앨 수 없다. 이러할 경우 [math(x_{3})]는 [math(S_1)]로 취급되어 어느 실수라도 허용되며, [math(x_{1})]과 [math(x_{2})]는 이에 따라 각자 [math(10-S_1)]과 [math(4-S_1)]가 된다.

7. 성질

7.1. 중요한 성질

7.2. 별로 안 중요한 성질

8. 같이 보기

[1] 존재성은 가우스-조르당 소거법에 의해 보장된다. 유일성에 관해서는, 두 기약행사다리꼴이 행동치일 경우 서로 같다는것을 수학적 귀납법으로 보일수 있는데, 어떤 행렬에 행동치인 기약행사다리꼴이 두 개 존재한다면, 행동치는 동치관계이기때문에, 두 기약행사다리꼴은 행동치가 돼서 모순이 발생한다. [2] 기본행연산 과정을 기본행렬와의 곱들로 나타낼 수 있으므로 이 사실이 성립한다는 것을 알 수 있다. [3] 가역행렬의 기본정리 중 일부이다. [4] =leading entry의 개수 [5] 엄밀히 말하여, 행렬A와 행동치인 행사다리꼴의 0이 아닌 행의 개수는 A의 행 계수(row rank, 1차 독립인 행의 최대 개수)를 의미하는데, 차원 정리에 의하여, 열 계수(column rank, 1차 독립인 열의 최대 개수)는 열의 개수에서 퇴화 차수를 뺀 값과 같다는것을 알 수 있고, 간단한 사칙연산을 통해, 행 계수와 열 계수가 같을 수 밖에 없다는것을 유도할수 있다. 그래서 행계수든 열계수든 계수로 퉁쳐서 이야기 할수 있는것.

분류