쌍대성(Duality)

서로 다른 두 점을 지나는 직선은 하나뿐이고, 서로 다른 두 직선이 만나는 점은 (평행하지 않다면) 하나뿐입니다. 앞 문장에서 '점'과 '직선', '지나는'과 '만나는'을 맞바꾸면 뒤 문장이 됩니다. 평행이라는 예외는 아래의 사영기하⁠(projective geometry)⁠가 없앱니다. 이렇게 한 세계의 대상과 관계를 다른 세계의 대상과 관계로 뒤집어 옮겨도 참이 참으로 남는 짝을 쌍대성이라 부릅니다. 쌍대성에는 알아보기 쉬운 표시가 있습니다. 두 번 뒤집으면 제자리로 돌아오고, 한쪽에서 어렵던 질문이 다른 쪽에서는 쉬워지며, 최적화⁠(optimization)⁠ 문제에서는 한쪽의 최댓값이 다른 쪽의 최솟값을 넘지 못하고, 좋은 경우에는 둘이 정확히 만납니다. 그러면 정리 하나를 증명할 때마다 정리 두 개를 얻고, 둘이 만나는 경우에는 답 하나를 찾을 때마다 그 답이 최선이라는 증명서도 함께 얻습니다.

기하⁠(geometry)⁠: 점과 직선을 맞바꾸기. 1640년 열여섯 살의 파스칼은 원이나 타원⁠(ellipse)⁠, 포물선⁠(parabola)⁠처럼 원뿔을 평면으로 잘라 생기는 곡선(원뿔곡선⁠(conic section)⁠) 위의 여섯 점으로 만든 육각형에서 마주 보는 변을 늘인 교점 셋이 한 직선 위에 놓인다는 정리를 발표했습니다. 1806년 에콜 폴리테크니크의 학생 샤를 브리앙숑은 원뿔 곡선에 접하는 여섯 직선으로 만든 육각형에서 마주 보는 꼭짓점을 이은 대각선 셋이 한 점에서 만난다는 정리를 얻었습니다. 파스칼의 정리⁠(Pascal's theorem)⁠에서 점과 직선을 맞바꾼 것입니다. 1820년대 프랑스의 기하학자 장빅토르 퐁슬레와 조제프 제르곤은, 평행선도 무한히 먼 한 점에서 만난다고 보는 사영기하에서는 모든 정리에 이렇게 쌍대 정리⁠(duality theorem)⁠가 따라붙는다는 원리를 내세웠습니다. 좌표로 적으면 간단합니다. 점 (a, b)에 직선 $y = ax - b$를 짝지으면 됩니다. 아래 왼쪽의 세 점을 끌어 보세요. 오른쪽에 짝이 되는 세 직선이 있습니다.

이 짝짓기에서는 세로 거리까지 보존됩니다. 점이 직선 위에 있다는 것과 직선이 점을 지난다는 것이 같은 식이기 때문입니다. P₁과 P₂를 세로로 나란히 놓으면 L₁과 L₂가 평행해져 교점이 사라지는데, 사영기하는 평행선이 '무한히 먼 점'에서 만난다고 보아 이 예외를 없앱니다. 같은 짝짓기는 자료에서 규칙을 배우는 기계 학습⁠(machine learning)⁠에도 숨어 있습니다. 퍼셉트론⁠(perceptron)⁠은 가중치 (w₁, w₂)로 점들을 두 무리로 가르는데, 가중치들을 좌표로 삼은 평면(가중치 공간)에서 보면 데이터 점 하나는 직선(고차원에서는 초평면⁠(hyperplane)⁠) 하나가 되고, 모든 점을 옳게 가르는 가중치들은 그 직선들이 잘라 낸 영역에 모입니다. 정다면체⁠(regular polyhedron)⁠에도 쌍대가 있습니다. 정육면체의 면 한가운데마다 점을 찍어 이으면 정팔면체가 되고, 정십이면체와 정이십면체도 서로의 쌍대이며, 정사면체는 자기 자신의 쌍대입니다. 꼭짓점 수와 면 수가 자리를 바꾸고 모서리 수는 그대로이니, 오일러의 $V - E + F$는 쌍대를 취해도 변하지 않습니다.

그래프와 지도: 나라와 꼭짓점을 맞바꾸기. 평면 지도의 나라마다 수도를 하나씩 찍고, 국경을 사이에 둔 수도끼리 선을 이으면 쌍대 그래프⁠(dual graph)⁠가 생깁니다. 나라는 꼭짓점이, 꼭짓점은 면이 되고, 국경 하나는 그것을 가로지르는 선 하나와 짝을 이룹니다. 이웃한 나라를 다른 색으로 칠하는 문제가 이웃한 꼭짓점을 다른 색으로 칠하는 문제로 바뀌어, 1879년 영국의 변호사이자 아마추어 수학자 앨프리드 켐프의 잘못된 증명 이래 4색 정리⁠(four color theorem)⁠의 모든 증명은 그래프의 말로 이루어졌습니다. 평면 위의 점들에도 같은 짝이 있습니다. 가장 가까운 점별로 평면을 나눈 보로노이 다이어그램⁠(Voronoi diagram)⁠에서 이웃한 영역의 점끼리 이으면(네 점이 한 원 위에 놓이지 않는 보통의 경우), 1934년 소련의 수학자 보리스 들로네가 연구한 들로네 삼각분할⁠(Delaunay triangulation)⁠이 됩니다. 점을 끌어 보세요. 보기: .

존 스노가 콜레라 지도에서 집마다 가장 가까운 펌프를 따진 것이 보로노이 쪽의 질문이고, 새 점에 가장 가까운 예를 찾는 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠도 그렇습니다. 반면 점들을 가장 짧게 잇는 최소 신장 트리⁠(minimum spanning tree)⁠는 들로네 삼각분할의 변 가운데에서만 고르면 되니, 후보가 크게 줄어듭니다. 흐름 문제에서도 평면이면 쌍대가 계산을 바꿉니다. 평면 네트워크의 최소 절단은 쌍대 그래프에서 최단 경로⁠(shortest path)⁠ 하나를 찾는 문제가 됩니다.

최적화: 최댓값과 최솟값이 만나는 곳. 관 네트워크로 보낼 수 있는 최대 흐름⁠(maximum flow)⁠은 출발점과 도착점을 가르는 가장 좁은 절단의 용량⁠(capacity)⁠과 같습니다(최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠). 1956년 RAND 연구소의 레스터 포드와 델버트 풀커슨, 그리고 MIT의 피터 일라이어스, 에이미얼 파인스타인, 섀넌이 따로 증명했습니다. 어떤 흐름도 어떤 절단보다 클 수 없다는 쪽은 당연하고, 둘이 정확히 만난다는 쪽이 깊은 내용입니다. 1931년 부다페스트의 쾨니그 데네시와 에게르바리 예뇌는 이분 그래프(점들이 두 무리로 나뉘고 변은 서로 다른 무리의 점만 잇는 그래프)에서, 끝점을 공유하지 않는 변을 가장 많이 고른 수(최대 매칭⁠, maximum matching⁠)가 모든 변의 한쪽 끝을 덮는 가장 적은 꼭짓점 수와 같다는 것을 보였고, 에게르바리는 이것을 변마다 가중치가 붙은 경우로 넓혔습니다(홀의 정리⁠(Hall's theorem)⁠, 부다페스트의 수학자들). 1955년 해럴드 쿤은 그 헝가리어 논문을 스스로 번역해, 일꾼 n명과 일 n개를 짝지어 비용의 합을 가장 작게 하는 배정 문제⁠(assignment problem)⁠를 행과 열에 '가격'을 매겨 푸는 헝가리안 방법⁠(Hungarian method)⁠을 만들었습니다. 가격표는 '이보다 더 잘할 수는 없다'는 증명서입니다. 1928년, 두 사람이 겨루는 게임에서 각자 최악을 대비해 고른 값이 서로 같아진다는 미니맥스 정리⁠(minimax theorem)⁠를 증명했던 폰 노이만은, 1947년 조지 댄치그가 선형 계획법⁠(linear programming)⁠을 설명하자 곧바로 쌍대 정리를 짐작했다고 전합니다(최적화, 프린스턴 고등연구소). 선형 계획법은 일차식으로 된 제약들을 지키며 일차식 목표를 최대로 만드는 문제입니다. 빵집이 밀가루와 설탕의 재고 안에서 빵과 과자를 얼마씩 구워 이윤을 최대로 할지 묻는 것이 원래 문제라면, 쌍대 문제⁠(dual problem)⁠는 재료마다 값을 매겨 '빵 하나, 과자 하나에 드는 재료의 값이 그 이윤 이상'이 되게 하면서 재고 전체의 값을 최소로 하는 문제입니다. 쌍대 정리는 두 답이 정확히 같다는 것입니다. 레닌그라드의 레오니트 칸토로비치는 1939년 이미 이런 가격에 경제적인 뜻을 주었고(최적 수송⁠, optimal transport⁠), 제약 조건 하나마다 붙는 라그랑주 승수⁠(Lagrange multiplier)⁠가 그 제약을 조금 풀어 줄 때 목표가 얼마나 좋아지는지를 알려 주는 '그림자 가격⁠(shadow price)⁠'인 것도 같은 이야기입니다.

선형대수⁠(linear algebra)⁠와 확률⁠(probability)⁠: 행과 열, 분포와 함수⁠(function)⁠. 연립일차방정식⁠(system of linear equations)⁠ Ax = b는 행마다 직선 하나씩을 그려 교점을 찾는 문제(행 그림)이면서, 열들을 몇 개씩 더해 b를 만드는 문제(열 그림)입니다. 행이 만드는 공간과 열이 만드는 공간의 차원이 늘 같다는 정리(행 계수 = 열 계수)가 두 그림을 짝으로 묶어 줍니다. 행 하나는 벡터⁠(vector)⁠를 받아 수 하나를 내놓는 측정 장치이고, 그 측정이 내적⁠(dot product)⁠입니다. 최소제곱⁠(least squares)⁠의 답은 남은 오차가 모든 열과 수직이라는 조건, 곧 $A^{\mathsf T}(b - Ax) = 0$으로 정해지는데(정사영⁠(orthogonal projection)⁠, 열공간⁠(column space)⁠), 행과 열을 맞바꾼 전치 행렬⁠(transpose)⁠ $A^{\mathsf T}$가 행의 세계와 열의 세계를 오가는 다리입니다. 마르코프 연쇄⁠(Markov chain)⁠의 전이 행렬⁠(transition matrix)⁠ P도 양쪽에서 읽힙니다. 확률 분포를 왼쪽에서 곱하면 사람들이 어디에 있는지가 한 걸음 나아가고, 정상 분포⁠(stationary distribution)⁠ $\pi P = \pi$가 페이지랭크⁠(PageRank)⁠입니다. 함수를 오른쪽에서 곱하면 '한 걸음 뒤에 기대할 값'이 되고, $Ph = h$를 만족하는 함수가 도박꾼의 파산⁠(gambler's ruin)⁠에서 본 '목표에 먼저 닿을 확률'입니다. 같은 행렬⁠(matrix)⁠의 왼쪽 고유벡터⁠(eigenvector)⁠와 오른쪽 고유벡터가 서로 쌍대인 두 질문에 답합니다.

푸리에: 시간과 진동수. 신호는 시간에 따라 적을 수도 있고 푸리에 급수⁠(Fourier series)⁠처럼 진동수에 따라 적을 수도 있습니다. 한쪽에서 좁은 것은 다른 쪽에서 넓습니다. 짧게 끊긴 소리는 넓은 진동수를 품고, 순수한 음 하나는 끝없이 이어져야 합니다. 이 맞바꿈의 한계가 불확정성 원리⁠(uncertainty principle)⁠의 수학이고, 종 모양 곡선 $e^{-x^2/2}$은 변환해도 모양이 그대로인 자기 쌍대입니다(가우스 적분⁠(Gaussian integral)⁠, 정규분포⁠(normal distribution)⁠). 연산도 짝을 이룹니다. 시간 쪽에서 고르게 뽑는 것은 진동수 쪽에서 스펙트럼을 되풀이해 겹쳐 놓는 것이라, 너무 드물게 뽑으면 겹친 스펙트럼이 뒤섞여, 영화 속 마차 바퀴가 거꾸로 도는 것처럼 빠른 진동이 느린 진동으로 둔갑하는 에일리어싱⁠(aliasing)⁠이 생깁니다(표본화 정리⁠(sampling theorem)⁠, 나이퀴스트). 열로 온도 분포를 매끄럽게 하는 것은 진동수 쪽에서 높은 성분을 $e^{-k^2 t}$로 누르는 것이고(열방정식⁠, heat equation⁠), 시간 쪽에서 번거로운 합성곱⁠(convolution)⁠은 진동수 쪽에서 곱셈 한 번입니다. 합성곱은 두 수열의 한쪽을 뒤집어 밀어 가며 겹치는 칸끼리 곱해 더하는 연산인데, 큰 수 두 개를 곱할 때 자릿수끼리 곱해 같은 자리에 모으는 계산이 바로 합성곱입니다. 그래서 큰 수의 곱셈이 고속 푸리에 변환⁠(fast Fourier transform)⁠으로 빨라집니다. 푸리에 변환을 두 번 하면 원래 함수가 좌우로 뒤집혀 나오고, 네 번 해야 제자리로 돌아옵니다.

논리, 부호, 복소수⁠(complex number)⁠. 불 대수⁠(Boolean algebra)⁠의 식에서 AND와 OR, 0과 1을 모두 맞바꾸면 참인 법칙은 참인 법칙으로 바뀝니다. 불과 같은 해인 1847년 런던의 오거스터스 드모르간이 정리한 드모르간 법칙⁠(De Morgan's laws)⁠ '(A 또는 B)가 아니다 = A가 아니고 B도 아니다'가 그 대표이고, 집합의 연산⁠(set operations)⁠에서는 합집합⁠(union)⁠과 교집합⁠(intersection)⁠이 여집합⁠(complement)⁠을 사이에 두고 짝을 이룹니다. 1937년 섀넌이 보인 대로 스위치를 직렬로 이으면 AND, 병렬로 이으면 OR이니, 회로에서는 직렬과 병렬을 맞바꾸는 것이 같은 쌍대입니다. 섀넌의 정보 이론에도 짝이 있습니다. 압축(원천 부호화 정리⁠(source coding theorem)⁠)은 쓸모없는 여분을 없애고, 오류 정정 부호(통로 부호화 정리⁠, noisy-channel coding theorem⁠)는 쓸모 있는 여분을 되돌려 놓습니다. 그는 1959년 율–왜곡 이론⁠(rate–distortion theory)⁠ 논문 끝에서, 왜곡을 허용하는 원천과 잡음이 있는 통로 사이에 기묘하고도 흥미를 돋우는 쌍대성이 있다고 적었습니다. 복소평면⁠(complex plane)⁠에서는 $z \mapsto 1/z$가 0과 무한대를 맞바꾸고, 함수의 영점과 극⁠(zeros and poles)⁠을 서로 바꿔 놓습니다.

어긋남과 놀라움. 모든 짝이 완벽하지는 않습니다. 최소 절단은 증가 경로⁠(augmenting path)⁠로 빨리 찾지만, 건너는 변이 가장 많은 최대 절단을 찾는 문제는 NP-난해⁠(NP-hard)⁠하다는 것, 곧 빠른(다항식 시간⁠, polynomial time⁠) 알고리즘⁠(algorithm)⁠이 있다면 P = NP가 되어 버리는 부류에 든다는 것이 알려져 있습니다. 정수⁠(integer)⁠만 허용하거나 목표가 볼록하지 않은 최적화에서는 최댓값과 최솟값 사이에 틈(쌍대 간극⁠, duality gap⁠)이 남고, 그 틈을 얼마나 좁힐 수 있느냐가 근사 알고리즘 연구의 한 줄기입니다. 램지 이론⁠(Ramsey theory)⁠에서는 관계망을 여그래프⁠(complement graph)⁠, 곧 이어진 쌍과 끊긴 쌍을 맞바꾼 그래프로 뒤집으면 '서로 다 아는 무리'와 '서로 다 모르는 무리'가 자리를 바꾸니, 램지 수⁠(Ramsey number)⁠는 두 수를 맞바꿔도 같습니다. 쌍대성은 때로 역사를 가로질러 숨어 있었습니다. 2000년대에 19세기 독일의 수학자 카를 야코비가 남긴 유고에서 헝가리안 방법과 거의 같은 절차가 발견되었고, 쿤은 말년에 이 발견을 직접 소개했습니다. 좋은 짝이 한 세기 동안 잠들어 있었던 것입니다.

이어지는 곳. 점과 직선을 맞바꿔도 참이 남는다는 것은 이론 전체가 가진 대칭이라 대칭과 불변량⁠(invariant)⁠과 한 뿌리입니다. 쌍대 문제가 최적성의 증명서가 되는 이야기는 가장 좋은 것 고르기에서, 시간 대신 진동수로 적는 것처럼 같은 대상을 다른 좌표로 보는 일은 표현 바꾸기에서 이어집니다. 평행선이 만나는 무한원점⁠(point at infinity)⁠은 무한을 다루는 법의 한 수법이고, 작은 영역의 성질을 전체로 이어 붙이는 국소에서 전체로의 이야기에서도 쌍대 그래프와 오일러 지표가 다시 나옵니다. 'LX에서 Y로 가는 화살표'와 'X에서 RY로 가는 화살표'가 하나씩 짝지어지는 짝 관계를 범주론⁠(category theory)⁠에서는 수반이라 하는데, 올림과 내림, 논리의 ∃와 ∀가 그 예입니다. 순서에서의 수반인 갈루아 연결⁠(Galois connection)⁠은 체와 군 사이에서 포함 관계를 뒤집는 갈루아 대응을 낳았고, 부정을 두 번 하면 제자리이며($A^{\perp\perp} = A$) 드모르간 법칙이 두 '그리고'와 두 '또는'을 맞바꾸는 선형 논리⁠(linear logic)⁠는 쌍대성을 논리 안에 통째로 들인 예입니다. 최대공약수⁠(greatest common divisor)⁠와 최소공배수⁠(least common multiple)⁠, 교집합과 합집합, '그리고'와 '또는'이 화살표를 뒤집은 한 쌍이라는 것을 직접 뒤집어 보는 그림은 「화살표만으로 본 수학」 1절에 있습니다.