a*x + b*y + M = 0
c*x + d*y + N = 0
이라는 두 개의 이원(x, y) 일차방정식이 있다고 치자. 흔히 연립방정식이라고도 불린다.
이 방정식을 풀려면 x, y 중 하나의 계수를 a나 c, 아니면 b나 d로 맞춰 줘서 한 변수를 소거해야 한다. 그래서 일원 일차방정식으로 바꿔서 반대편 변수의 근을 구한 뒤, 그 값을 대입하여 원래 변수의 근까지 구하면 된다.
이를 일반화하여 위의 방정식의 '근의 공식'을 구하면 다음과 같다. 뭔가 규칙성이 있는 것 같으면서도 미묘하게 잘 안 외워진다.
x = (N*b-M*d) / (a*d-b*c)
y = (N*a-M*c) / (a*d-b*c)
분모를 보니 생각나는 게 없는가?
그렇다. 이것은
[ a b ]
[ c d ]
라는 원소로 구성된 2*2 정방행렬의 행렬식을 구하는 공식이다.
이 행렬식의 값이 0이라는 건 a:b와 c:d의 비율이 동일하다는 뜻이다. 따라서 이 행렬을 구성하는 벡터들은 서로 일차(선형) 독립을 이루지 못하며, 상수항이 어떻냐에 따라서 이 방정식은 근이 무수히 많거나 근이 존재하지 않게 된다.
이런 행렬을 거친 일차변환은 2차원 평면을 1차원 선이나 점으로 찌그러뜨린다. 이런 행렬은 영벡터(모든 원소의 값이 0)가 아닌 벡터 중에서도 자신과의 곱을 영벡터로 만드는 물건이 무수히 존재하게 된다(Ax=O).
예를 들어 연립방정식 x+2*y = 0 과 3*x+5*y = 0의 근은 x와 y가 모두 0인 trivial solution 단 하나밖에 없으나, x+2*y = 0과 3*x+6*y = 0은 두 식이 동치나 마찬가지이기 때문에 x = -2*y이기만 하면(가령 2와 -1) 식이 성립한다. non-trivial solution들이 존재한다는 뜻이다. 결국, 근이 무수히 많을 수 있다는 말과 본질적으로 동일하다.
이들은 모두 필요충분조건 관계에 있으며, 이외에도 이런 행렬의 엄밀한 특성에 대해서는 선형대수학 시간에 많이 배우게 된다.
말이 길어졌는데, 그럼 변수가 세 개 이상이 되면 근을 구하는 양상이 어떻게 바뀔까?
그야말로 폭발적으로 복잡해진다.
변수가 2개일 때는 x, y 근에 최대 두 변수의 곱(최대 2차)으로 이뤄진 항이 분자와 분모에 2개씩 있었다.
그러나 3개일 때는 세 변수의 곱으로 이뤄진 항이 분자와 분모에 6개씩 들어간다.
그리고 이를 일반화하면, n원 1차 연립방정식의 근은 n개의 변수의 곱으로 이뤄진 항이 분자와 분모에 무려 n! (팩토리얼)개씩 들어간다!
이것이 '폭발적'이라는 단어의 의미이다. 예를 들어,
[ a b c ]
[ d e f ]
[ g h i ]
라는 3*3 정방행렬의 행렬식은 다음과 같다. 어떤 규칙성이 있는지, 어떻게 하면 잘 외울 수 있겠는지 한번 생각해 보시라.;;
a*e*i - a*f*h - b*d*i + b*f*g + c*d*h - c*e*g
a가 속한 행과 열을 제낀 2*2 행렬(e f / h i)의 행렬식에다가 a를 곱해서 더하고,
다음으로 b가 속한 행과 열을 제낀 2*2 행렬(d f / g i)의 행렬식에다가 b를 곱해서 빼고,
끝으로 c가 속한 행과 열을 제낀 2*2 행렬(d e / g h)의 행렬식에다가 c를 곱해서 더하면.. 이 행렬 전체의 행렬식이 나오긴 한다. 2*2 행렬식이 2개의 항으로 구성돼 있는데 그런 식이 3개가 늘어나니 총 6개가 되는 게 맞다.
이런 방식으로 행렬을 쪼개면 그 어떤 크기의 행렬의 행렬식도 구할 수는 있다. 하지만 크기가 3을 넘어가는 행렬에 대해 행렬식 내지 방정식을 푸는 일반적인 공식을 구하려는 생각은 포기하는 게 좋다. 머리 터진다..;;
참고로 1변수 n차 방정식의 경우를 생각해 보자. 2차 방정식은 잘 알다시피 비교적 외우기 쉬운 근의 공식이 존재하는 반면 3차와 4차는 근의 공식이 있기는 하나 인간의 머리로 도저히 외울 수 없을 수 없을 정도로 미치도록 복잡한 형태이다. 게다가 서로 인접한 차수끼리 규칙성 같은 것도 아예 존재하지 않는다. 5차 이상부터는 대수적인 방법만으론 깔끔하게 풀 수조차 없다.
그에 반해 n변수 1차 연립방정식은 비록 그 정도로 카오틱하게 복잡한 건 아니지만, 그래도 좀 다른 양상으로 복잡해진다는 게 오묘한 점이다.
그리고, 이건 일반적인 공식을 구하려 할 때 딸려 나오는 식이 지수함수 급으로 복잡해진다는 소리다. 일반적인 경우가 아니라 그때 그때 특정 숫자가 주어진 행렬의 행렬식을 구하는 알고리즘의 시간 복잡도가 지수함수라거나 NP 완전 문제 급이라는 뜻은 아니다. 둘은 서로 다른 개념이다.
변수가 3개를 넘어가는 방정식은 어떻게 풀어야 할까?
가령, 변수가 x, y, z라고 치면 일단 모든 방정식의 x의 계수를 1이든, 맨 위의 식의 계수로든 어쨌든 하나로 일치시켜야 한다. “등식에서 같은 수를 더하거나 빼도 등식은 성립한다.” / “등식에서 같은 수를 곱해도 등식은 성립한다” 라고.. 초등학교 산수 시간에 배우는 지극히 당연하고 기본적인 원리를 이용해서 방정식을 푸는 것이다.
그렇게 해서 x 변수를 없는 놈 취급할 수 있게 만든 뒤, 다음 방정식에 대해서 y 변수의 계수를 일치시킨다.
이런 절차를 반복하여 변수를 z만 남겨서 z 값을 구하고, 다음으로 y, x의 순으로 재귀적으로 근을 구하면 된다.
행렬이라는 물건 자체가 이런 연립방정식을 푸는 동작을 간략하게 모델링하는 과정에서 고안되었다.
앞서 말한 절차를 행렬 용어로 표현하자면, 가우스-조던 소거법으로 행렬을 대각화하는 것과 같다.
행렬이 대각화가 되고 나면 방정식을 다 푼 것이나 다름없을 뿐만 아니라, 행렬식의 값은 그 행렬의 대각선 원소들의 곱으로 쉽게 구할 수 있게 된다.
행렬을 대각화하는 데 드는 시간 복잡도는 일반적으로 O(n^3)으로, 행렬 곱셈의 비용과 같다.
이 작업을 숫자를 대상으로 곧장 곧장 업데이트하는 게 아니라, 기호를 이용해서 일반적인 경우를 다 고려하여 표현하려다 보면 항 개수가 아까 같은 팩토리얼 급으로 증가하게 되는 것일 뿐이다.
연립방정식 하니까 응용수학 내지 산업/경영공학 같은 데서 다루는 그 이름도 유명한 선형 계획법(LP)이 생각난다.
이런 데서 다루는 문제는 대체로 변수의 개수가 식의 개수보다 더 많고, 식도 등식이 아니라 부등식이다. 애초에 해 자체는 무한히 많을 수밖에 없는데 그래프의 능선을 따라다니면서 주어진 조건을 최대한 만족하는 영역을 찾는 게 목적이다. 이런 문제는 실용적인 가치도 무진장 높다.
이런 걸 푸는 제일 간단한 알고리즘으로는 simplex method가 있는데, 그 이상의 디테일은 본인도 비전공자인 관계로 잘 모른다. 변수의 차원이 최대 2차원 정도일 때나 그래프를 그려서 생각할 수 있지, 이 역시 3차원 이상으로 가면 머리에 쥐 난다. 고등학교에서 행렬을 2*2까지밖에 다루지 않는 것, 그리고 전산학에서 간단한 bool 대수 연산을 다룰 때 변수를 3개까지밖에 넣지 않는 게 다 이유가 있어서 그런 것이다.
Posted by 사무엘
