[include(틀:선형대수학)] [목차] == 개요 == 행사다리꼴행렬('''R'''ow '''E'''chelon '''F'''orm 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)이라 한다. [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)를 한 눈에 알 수 있다는 장점이 있다. == 정의 == 행사다리꼴 행렬을 정의하기에 앞서 용어 하나를 먼저 정의하겠다. * leading entry: 각 행을 왼쪽에서부터 읽었을 때, 처음으로 0이 아닌 성분을 뜻한다. 예를들어 행렬 [math(A)]가 [math(A=\begin{pmatrix}9&3&2\\0&0&1\\0&0&0\\0&2&3\end{pmatrix})] 일 때, 1행, 2행 4행의 leading entry는 각각 9, 1, 2이고, 3행의 leading entry는 존재하지 않는다. 책에 따라서는 피봇(pivot)이라고도 한다. '''선도 성분'''이라고 번역하기도 한다. 행사다리꼴 행렬은 다음의 성질을 만족하는 행렬을 뜻한다. * 모든 성분이 0인 행은 모두 최하단에 위치한다. (모든 성분이 0인 행이 없어도 좋고, 많아도 상관없다.) * 임의의 두 leading entry의 위치를 비교했을 때, 행이 빠를수록 열도 빠르다. (같은 열에 위치하는 것은 허용하지 않는다.) == 예시 == * [math(\begin{pmatrix}1&3&2&1&4\\0&0&0&7&2\\0&1&3&2&1\\0&0&0&0&0\end{pmatrix})] 위 행렬은 행사다리꼴 행렬이 아니다. 왜냐하면 2행의 leading entry인 7의 열이 4열인데, 3행의 leading entry는 2열에 위치하기 때문이다. * [math(\begin{pmatrix}1&3&2\\0&0&2\\0&0&0\\0&6&3\end{pmatrix})] 위 행렬은 모든 성분이 0인 행이 최하단에 위치하지 않았기 때문에 행사다리꼴이 아니다. * [math(\begin{pmatrix}1&3&2&0\\0&0&3&2\\0&0&0&1\\0&0&0&0\end{pmatrix})] 위 행렬은 행사다리꼴 행렬의 모든 조건을 만족하기 때문에 행사다리꼴 행렬이다. == [[연립방정식]]에서의 활용 == 연립방정식 [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에 해당하는 변수의 영향을 받기 때문이다. 그러나, 연립방정식의 계수행렬이 후술할 기약행사다리꼴인 경우 굳이 후진대입법을 통해 해를 구할 필요는 없다. == 기약행사다리꼴 == 행사다리꼴 행렬 중에서 다음과 같은 조건을 추가로 만족하는 것을 기약행사다리꼴 또는 행 간소 사다리꼴('''R'''educed '''R'''ow '''E'''chelon '''F'''orm, '''RREF''')이라 한다. * leading entry는 1이다. 기약행사다리꼴의 leading entry를 leading one이라고 한다. * leading one과 같은 열에 위치한 성분은 모두 0이다. 기약행사다리꼴 행렬에 대해 다음의 세 성질을 만족한다. * 기약행사다리꼴의 행동치인 기약행사다리꼴은 자기 자신이다. * 두 행렬이 행동치일 필요충분조건은 두 행렬의 행동치인 기약행사다리꼴이 서로 같다는 것이다. * 임의의 행렬에 대해 행동치인 기약행사다리꼴이 유일하게 존재한다.[* 존재성은 가우스-조르당 소거법에 의해 보장된다. 유일성에 관해서는, 두 기약행사다리꼴이 행동치일 경우 서로 같다는것을 수학적 귀납법으로 보일수 있는데, 어떤 행렬에 행동치인 기약행사다리꼴이 두 개 존재한다면, 행동치는 동치관계이기때문에, 두 기약행사다리꼴은 행동치가 돼서 모순이 발생한다.] [[범주론]]에서 위와 같은 세 성질(①[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) 이라고도 한다. == 가우스 소거법 == 가우스 소거법(Gaussian Elimination)이란 주어진 행렬을 유한번의 [[기본행연산]]을 하여 [[행동치]]인 행사다리꼴로 만드는 방법이다. 그 방법은 다음과 같다. 행의 개수를 [math(n)], 열의 개수를 [math(m)]이라고 하자. 1. [math(i=1)], [math(j=1)]이다. 1. [math(i)]행부터 차례대로 [math(j)]열에 leading entry가 있는 행을 찾는다. (그런 행이 없으면 6으로 넘어간다.) 그 중 가장 먼저오는 행을 [math(k)]행 이라고 하자. 1. [math(k)]행과 [math(i)]행을 서로 바꾼다. 1. 바뀐 행렬에서 [math(i