어떤 선형계가 주어졌을 때, 그 선형계의 해집합을 구하기 전에 확인해 봐야 할 것은 해가 존재하지는 여부이다. 주어진 선형계가 해를 가지고 있는지, 그 해가 유일한 것인지 따위를 결정하기 위해서는 행축소 알고리즘(The Row Reduction Algorithm)을 사용하여 행렬을 사다리꼴 모양(echelon form) 행렬로 변환해봐야 한다. 만약 어떤 직사각형 행렬이 다음 세 가지 성질을 갖고 있다면 이것을 사다리꼴 모양 행렬이라 하며, 행축소 알고리즘은 행렬이 첨가행렬(argument matrix)이든, 그렇지 않든 모든 행렬에 적용할 수 있다.
1. 0이 아닌 모든 행은 항상 성분이 모두 0인 행보다 위에 놓여 있다.
2. 행의 주성분은 그 행보다 위에 있는 행의 주성분보다 항상 오른쪽에 위치한다. 여기서 주성분(leading entry)은 맨 왼쪽의, 0이 아닌 성분을 의미한다.
3. 주성분보다 밑에 있는 열의 성분은 모두 0이다.
사다리꼴 모양 행렬이 다음의 조건을 만족하면 그 행렬을 기약 사다리꼴 모양(reduced echelon form) 행렬이라 한다. (또는, 간단히 기약 가우스 행렬(reduced Gauss matrix)이라고 한다. 다음 4, 5를 만족하지 않는 행렬은 행 사다리꼴(row echeleon from), 또는 가우스 행렬(Gauss matrix)라고 한다. 기약 사다리꼴 모양 행렬은 반드시 행 사다리꼴 모양이지만, 역은 성립하지 않는다)
4. 0이 아닌 행의 주성분은 1이다.
5. 각각의 주성분 1은 그 열에서 하나 밖에 없는 0이 아닌 성분이다.
행렬은, 오직 하나의 기약 사다리꼴 모양 행렬과 행동치이다. 만일 행렬 A가 사다리꼴 모양 행렬 U와 행동치이면 U를 A의 사다리꼴 모양 행렬이라 한다. 또한 U가 기약 사다리꼴 모양 행렬이면 U를 A의 기약 사다리꼴 모양 행렬이라 한다.
행렬에 행연산을 수행하여 사다리꼴 모양 행렬을 얻은 다음, 기약 사다리꼴 모양 행렬을 얻기 위해 사다리꼴 모양 행렬에 행연산을 다시 수행해도 이들 행연산은 주성분의 위치를 변화시키지 않는다. 기약 사다리꼴 모양 행렬이 유일하기 때문에, 주성분의 위치는 주어진 행렬로부터 얻어지는 어떠한 사다리꼴 모양 행렬의 주성분 위치와도 동일하다. 즉, 행렬 A의 피벗 위치(a pivot position)는 행렬 A의 사다리꼴 모양 행렬의 주성분 위치와 같다. 피벗열(a pivot column)은 피벗 위치를 포함하고 있는 행렬 A의 열이다. 또, 모든 행렬은 유일한 기약행 사다리꼴 모양 행렬(기약 가우스 행렬)로 변형될 수 있다. 즉, 주어진 행렬에 행연산의 순서를 달리 하더라도 결국 같은 기약 가우스 행렬을 얻게 된다. 그러나, 주어진 행렬의 가우스 행렬은 유일하지 않다. 행연산의 순서가 다르다면 각각의 다른 가우스 행렬을 얻게 된다.
이제, 어떤 행렬이든 사다리꼴 모양 행렬로 변환할 수 있다면 이 선형계가 해를 갖는지 판단할 수 있을 것이다. 즉, 사다리꼴 모양 행렬을 얻었다면 단순히 주성분의 1 / n 스칼라를 곱해서 기약 사다리꼴 모양 행렬로 변환할 수 있으며, 이것이 첨가 행렬이었다면 이 선형계의 해는 이것으로부터 간단히 알아 볼 수 있다. 예를 들어, 선형계의 첨가행렬이 그것과 동치인 기약 사다리꼴 모양의 행렬로 변형되었다고 하자.
1 0 -5 1
0 1 1 4
0 0 0 0
첨가행렬이 네 개의 열을 갖고 있으므로, 변수의 세 개이다. 첨가행렬에 관한 선형방정식은 다음과 같다.
x1 -5 * x3 = 1
x2 + x3 = 4
0 = 0
행렬의 피벗열에 있는 변수 x1과 x2를 기본변수(basic variable)라 하고, 나머지 변수 x3을 자유변수(free variable, 자유변수에 지정된 값을 간혹 매개변수(parameter)라 하기도 한다)라 한다. x3이 자유변수라는 것은 x3가 임의의 값을 선택할 수 있음을 뜻한다. x3의 값이 결정되면 x1과 x2 역시 값이 결정된다. 이 대수적 표현은 실질적으로 이 선형계의 모든 해집합을 표현할 수 있는데, 이렇게 해집합을 표현한 것을 해집합의 매개변수식 표현이라 한다. 단, 선형계가 해집합을 갖지 않을 때는 선형계가 자유변수를 가지더라도 해집합은 공집합이다. 이런 경우에는 해집합을 매개변수식 표현으로 표현할 수 없다.
결론적으로, 선형계가 해를 갖기 위한 필요충분 조건은 첨가행렬의 가장 오른쪽 열이 피벗열이 아닌 것이다. 즉 필요충분 조건은 첨가행렬의 사다리꼴 모양 행렬이 다음과 같은 형태의 행을 갖지 않는 것이다.
[ 0, 0, ... b ], b≠ 0 (즉, 0 = b라는 형태는 있을 수 없다)
선형계가 해를 갖는다면 해집합은 유일하거나, 무한히 많은 해를 갖는다.
Reference
David C. Lay, Linear Algebra and Its Application 3rd edition, Pearson Education, 2003