우리는 소거법을 사용하여 연립일차방정식을 대수적으로 풀 것입니다. 다시 말해, 방정식들을 여러 방식으로 결합하여 각 방정식에서 가능한 한 많은 변수를 소거하려고 합니다. 연립방정식에 수행할 수 있는 유효한 연산은 세 가지입니다.

• 스케일링: 방정식의 양변에 0이 아닌 수를 곱할 수 있습니다.
  
• 치환: 한 방정식의 배수를 다른 방정식에 더하고, 그 결과로 두 번째 방정식을 대체할 수 있습니다.
  
• 교환: 두 방정식의 위치를 바꿀 수 있습니다.
  

첨가행렬과 행 연산

소거법으로 방정식을 풀려면 단지 자리 표시를 위해 변수 와 등호 를 계속해서 반복하여 써야 합니다. 방정식에서 실제로 바뀌는 것은 계수인 수뿐입니다. 숫자만 뽑아내어 상자에 넣으면, 즉 첨가행렬로 나타내면 일이 훨씬 수월해집니다:

이것을 첨가행렬이라고 합니다. “첨가”라는 말은 등호가 어디에 있는지 상기하기 위해 그리는 세로선을 가리킵니다. 행렬은 세로선이 없는 수의 격자입니다. 이 표기법에서 방정식을 다루는 세 가지 유효한 방법은 행 연산이 됩니다.

• 스케일링: 한 행의 모든 성분에 0이 아닌 수를 곱합니다.
  
  여기서 행 연산에 쓰인 이라는 표기는 단순히 “첫 번째 행”을 뜻하며, 등도 마찬가지입니다.
• 대체: 한 행에 다른 행의 상수배를 더하고, 두 번째 행을 그 결과로 대체하는 행 연산입니다.
  
• 교환: 두 행을 서로 맞바꾸는 행 연산입니다.
  

참고

위에서 행 연산을 적을 때 우리는 와 같은 표현을 사용했습니다. 물론 이것은 두 번째 행이 두 번째 행에서 첫 번째 행의 두 배를 뺀 것과 같다는 뜻이 아닙니다. 그 대신 두 번째 행을 두 번째 행에서 첫 번째 행의 두 배를 뺀 것으로 대체한다는 뜻입니다. 이런 종류의 구문은 컴퓨터 프로그래밍에서 변수의 값을 바꾸고 싶을 때 자주 사용됩니다.

예제

행렬에 행 연산을 하는 과정은 대응하는 일차방정식들의 해집합을 바꾸지 않습니다!

사실 이러한 연산을 하는 목적은 바로 소거법을 사용하여 방정식을 푸는 데 있습니다.

정의

두 행렬 중 하나에 행 연산을 몇 번 하여 다른 하나를 얻을 수 있으면 두 행렬을 행 동치라고 합니다.

따라서 행 동치인 행렬들의 일차방정식은 같은 해집합을 가집니다.

예제(불능인 연립방정식)

앞 소절에서 연립일차방정식을 첨가행렬로 옮기는 방법을 살펴보았습니다. 이제 그러한 첨가행렬을 “푸는” 알고리즘을 찾고자 합니다. 먼저 첨가행렬이 “풀렸다”는 것이 무엇을 뜻하는지 정해야 합니다.

다음은 행 사다리꼴 행렬을 그림으로 나타낸 것입니다:

행 사다리꼴 행렬은 일반적으로 후진 대입을 사용하여 쉽게 풀 수 있습니다. 예를 들어,

바로 임을 알 수 있으며, 이로부터 이고 임을 얻습니다. 이 예제을 참고하십시오.

다음은 기약 행 사다리꼴 행렬을 그림으로 나타낸 것입니다:

기약 행 사다리꼴 행렬은 어떤 의미에서 완전히 풀린 상태입니다. 예를 들어,

첨가행렬이 기약 행 사다리꼴이면, 대응하는 연립일차방정식은 풀린 것으로 간주합니다. 왜 그런지는 아래에서 살펴볼 것이며, 어떤 행렬이든 행 연산만으로 기약 행 사다리꼴로 만들 수 있음을 보일 것입니다.

다음 연립방정식을 생각해 봅시다:

이 연립방정식은 에서 점 에서 만나는 두 직선(아래 그림에서 각각 빨간색과 파란색)으로 시각화할 수 있습니다. 두 번째 방정식에서 첫 번째 방정식을 빼면 방정식 즉 을 얻습니다. 그 결과 다음 연립방정식을 얻습니다:

이를 행렬에 대한 행 연산으로 나타내면 다음과 같습니다:

기하학적으로 보면, 원래의 파란 직선이 새로운 파란 직선 로 바뀐 것입니다. 파란 직선이 해 를 중심으로 회전한다, 즉 피벗한다고 생각할 수 있습니다. 파란 직선을 이와 같이 피벗시키기 위해 행렬의 피벗 위치를 사용했습니다. 이것이 “피벗”이라는 용어에 대한 한 가지 설명이 될 수 있습니다.

모든 행렬이 적어도 하나의 기약 행 사다리꼴 행렬과 행 동치임을 보여 주는 알고리즘을 제시할 것이며, 이를 행 축약 또는 가우스 소거법이라고 합니다.

물론 이는 허용된 세 가지 행 연산만 수행하고 계산 실수를 하지’ 않는다는 것을 전제로 합니다.

유일성을 증명하지는 않겠지만, 여러분은 증명할 수 있을지도 모릅니다!

다음은 행렬의 행 축약 알고리즘을 그림으로 요약한 것입니다.

행 축약 후 행렬의 피벗이 어디에 있는지 아는 것은 매우 중요합니다. 이것이 다음 용어를 도입하는 이유입니다.

위 예제에서 불능인 연립방정식의 기약 행 사다리꼴을 알아보는 방법을 보았습니다.

다시 말해, 불능인 연립방정식의 행 축약된 행렬은 다음과 같은 모양입니다:

지금까지 두 부류의 행렬을 다루었습니다.

1. 행렬의 기약 행 사다리꼴이 첨가되지 않은 모든 열에 피벗을 가지면, 그 행렬은 유일한 해를 갖는 연립방정식에 대응합니다:
   
2. 행렬의 기약 행 사다리꼴이 마지막(첨가된) 열에 피벗을 가지면, 그 행렬은 해가 없는 연립방정식에 대응합니다:
   

첨가되지 않은 열 중 하나에 피벗이 없으면 어떻게 됩니까? 이것이 절 1.3의 주제입니다.