각자의 스타일 (반-바지)

게시일: 유닼님이 작성

반-바지님이 2018년 1월 공개하신 단편 만화 “각자의 스타일”. 기존에 존재하는 개념을 SF적 상상력이 가미된 관점으로 관찰해 다르게 풀어내는 것에 탁월하신 작가님이라 개인적으로 정말 좋아한다. 최근 작품들만 봐도, 팬그램에 등장하는 동물들을 소재로 한 “다람쥐 헌 쳇바퀴 타고파“, CPU가 있다면 둠을 돌릴 수 있다는 이야기를 치환한 “형이상학계의 D■■M“, 버그를 통해 롬의 데이터를 고쳐 엔딩을 띄우는 RTA를 논리 체계를 수정하는 ‘논리비행사’들의 작업과 병치하는 “기술발전 스피드런“, 갑자기 패턴이 달라지는 적분에 빗대어 패턴의 지레짐작을 하지 말라는 수학귀신의 이야기 “뙳띳 뙳띳 뙳띳 뙳띳” 등, 공상과학적 디테일과 여운 있는 서사와 수학적/물리학적 해석 등을 즐길 수 있는 한 편으로 이것이 무엇에 빗댄 것인지, 어느 레퍼런스인지 등을 깨닫고 나면 한 층 더 즐길 수 있는 테이스트의 작품들이 많다.

“각자의 스타일”은 수학을 공부하면서 느낄 수 있는 보편적인 경험이 어찌보면 다소 직설적으로 담겨진 작품이다. 수학에서는 같은 결론을 다른 맥락에서 다른 방법론으로 증명하는 경우가 많다. 가장 극단적인 경우는 귀류법 가정을 통해 모순임을 보이는 경우, 잘못된 가정을 통해서 잘못된 결론을 내리는 과정은 그야말로 다양하기 때문에 여러 가지 길이 있을 수 있다. 가장 간단한 예로는 소수의 무한성을 증명하기 위해 소수의 개수가 유한함을 가정하고 여러 가지 장치를 건설해 그 모순성을 보이는 것이 있기도 하다. (이에 대해서는 다음에 독립적인 글로 다루기로) 또한 개중에는, 전하고자 하는 바는 거의 대동소이한데 그것을 어떤 장치를, 어떤 언어를 통해 풀어가느냐에 따라 해석의 차이를 보여주는 증명들도 있다. 각자 어떤 분야에서 어떤 증명법을 쓰는 것에 더 익숙한지, 또한 어떤 것을 더 선호하는지에 따라 각자가 같은 문제를 바라보는 관점과 풀어내는 이야기는 조금씩 달라지고, 다른 분야를 전공하게 된 사람들과 한 문제에 대해 이야기하면서 그 차이를 알아내는 것 또한 연구 과정에서 느낄 수 있는 묘미이기도 하다.

구체적으로, 만화 속에 등장하는 수식과 그림이 무엇을 의미하는지를 개인적으로 아는 한도 내에서 이야기하고 싶다. 먼저 다소 잘 알려져있는 개념에서부터. 정사각행렬의 행렬값(determinant)은 선형대수학에서 자주 등장하는 중요한 오브젝트이다. 벡터들의 모임이 선형적으로 독립인지 아닌지를 따지게 하는 장치이기도 하고, 기하학적으로 그 행렬이 어떤 “크기”를 갖는지를 암시하는 기하학적인 요소이기도 하다. 이 행렬값은 몇 가지 방법으로 정의가 되는데 그 중 하나로는 아래와 같은 라이프니츠 공식(혹은 라플라스 공식)이 있다.

\displaystyle \text{det}(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}

즉 n \times n 행렬 A에 대해, 각 행과 열마다 하나씩 총 n개의 항을 뽑아 곱하고 이에 해당하는 행렬의 부호를 곱한 것들을 전부 합한 값으로 행렬값이 정의된다. 여기에서 부호에 해당하는 부분만 생략하면 permanent란 값이 정의된다.

\displaystyle \text{per}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i,\sigma(i)}

한 편, 모든 항들이 0 또는 1인 \{0,1\}-행렬의 permanent는 대수적 표현에서 그치지 않고 조합론에서도 그 의미를 찾을 수 있다.

Source: https://en.wikipedia.org/wiki/Bregman%E2%80%93Minc_inequality

이분그래프(bipartite graph)는 점집합이 두 집합 V,W로 분할되며 모든 변이 V 중의 한 점과 W 중의 한 점을 연결해야만 하는 그래프를 뜻한다. 여기서 V=\{v_1,\ldots,v_n\},W=\{w_1,\ldots,w_n\}의 크기가 같을 때, v_i, w_j를 연결하는 변이 존재할 때 (i,j)-항이 1이 되고 그 외의 경우 0이 되는 행렬을 생각한다. (이를 biadjacency matrix라 한다) 그러면 이 행렬의 permanent는 곧 각 행과 열마다 한 개씩의 1을 뽑도록 n개의 1을 뽑는 경우의 수가 되는데, 이를 다시 원래 그래프에서 생각하면 v_i들과 w_i들을 하나씩 짝짓는 경우의 수와 같아진다. 이렇게 V,W 사이의 일대일대응을 주어진 변들 내에서 찾는 것을 perfect matching이라 한다. 결론적으로 \{0,1\}-행렬의 permanent는 그에 해당하는 이분그래프의 perfect matching 개수로 볼 수 있다.

1963년 Henryk Minc는 이 $\{0,1\}$-행렬의 permanent에 대해 다음과 같은 conjecture를 세웠다. i번째 행에 등장하는 1의 개수를 r_i라 할 때

\displaystyle \text{per}(A) \leq \prod_{i=1}^n (r_i!)^{1/r_i}

가 성립한다는 것. 이 문제는 1973년 Lev Bregman이 증명해 그의 이름을 딴 Bregman’s theorem, 혹은 Bregman-Minc inequality 등으로 불린다. 그는 convex programming의 duality theorem 등을 이용해 문제를 증명했고, 그 이후로도 여러 사람들이 서로 다른 증명들을 남겼다. Schrijver는 가중치 산술-기하평균 부등식과 수학적 귀납법을 이용해 짧고 간결한 증명을 남겼으며[1] Radhakrishnan은 확률 분포의 엔트로피를 이용해 매우 깔끔한 증명을 남기기도 했다.[2] 이 증명들 역시 앞서 이야기한 다른 관점에서 찾아내는 같은 논리적 결론의 한 예시가 되기도 한다.

앞에서 본 바에 의하면 이분그래프 G 입장에서 perfect matching의 개수를 M(G)라 하고 A를 그 biadjecency matrix라 하면 M(G)=\text{per}(A)가 되고, r_i, 즉 i번째 행의 1의 개수는 곧 v_i의 차수(degree: 연결된 변의 개수)가 되므로 Bregman’s theorem은

M(G) \leq \prod_{i=1}^n(d(v_i)!)^{1/d(v_i)}

가 성립함을 의미한다. 한 편, 마찬가지로 M(G) \leq \prod_{i=1}^n(d(w_i)!)^{1/d(w_i)}도 되므로, 둘을 곱해 기하평균을 취하면

\displaystyle M(G) \leq \prod_v (d(v)!)^{\frac{1}{2d(v)}}

가 성립하는데, Alon과 Friedland는 이것이 (크기가 같은 두 점집합에 대한) 이분그래프뿐만이 아니라 일반적인 (점의 개수가 짝수인) 그래프에 대해서도 성립함을 보였다.[3] 그 일반화의 증명이 조합적으로 간단해 이를 소개하고자 한다.

M(G)^2, 즉 perfect matching 개수를 제곱한 값은 두 개의 perfect matching의 순서쌍의 개수로 볼 수 있다. 두 perfect matching에 해당되는 변들은 G의 2-regular(모든 점의 차수가 2) subgraph H를 이룬다. H는 2-regular임에서 겹치지 않는 싸이클들로 분할되어야 하며, 더 나아가 그 싸이클들은 모두 짝수 싸이클이어야 한다. 또한 H의 싸이클 개수를 s라 하면 H는 총 2^s번 등장한다. 이는 두 perfect matching을 각각 빨간색과 파란색으로 칠했다고 할 때, 각각의 싸이클은 빨간 변과 파란 변이 교대로 나타나야 하며, 그렇게 칠하는 경우의 수가 2가지이므로 모든 싸이클들에 대해 따지면 2^s가지이기 때문이다. (참고로 두 perfect matching이 같은 변을 포함한다면 2-싸이클이 생기게 되는데 그런 경우도 짝수 싸이클이라 생각한다)

한 편, G의 adjacency matrix B를 잡는다. 이 행렬은 앞에서 잡은 biadjacency matrix와는 약간 다른데, 이분그래프일 필요 없이 일반적인 (단순)그래프에 대해 두 점 v_i, v_j가 변으로 연결되면 (i,j)-항을 1, 그 외의 경우는 0으로 정의한 행렬을 뜻한다. (그래서 변에 방향성이 없는 undirected graph라면 이 행렬은 반드시 대칭행렬이어야 한다) 그러면 B의 permanent는 B_{i,w(i)}가 모두 1인 순열 w의 개수가 되고 이는 곧 변 v_i v_{w(i)}들로 이루어진 그래프 H^{\prime}을 잡는 경우의 수가 된다. 이 H^{\prime}은 G의 2-regular subgraph이므로 s개의 겹치지 않는 싸이클들로 분할되며, 이번에도 또 2^s번 등장하게 된다. (각각의 싸이클에 대해 어떤 방향을 택하는지에 따라 w가 결정된다) 단 앞에서와는 다르게 이 H^{\prime}에서는 홀수 싸이클이 나타나는 것도 가능하다.

따라서

\displaystyle \text{per}(A)^2 = M(G)^2 \leq \text{per}(B)

가 성립하는데 B의 i번째 행의 1의 개수는 곧 G에서 점 v_i의 차수 d(v_i)가 되므로, Bregman’s theorem에 의해 \text{per}(B) \leq \prod_{i=1}^n (d(v_i)!)^{1/d(v_i)}가 성립해 증명이 끝난다.

일반적인 그래프에서의 counting 문제가 어떻게 대수적으로 정의된 행렬의 특정 값에 대한 이야기로 바뀌는지, 또한 그 증명에 어떻게 엔트로피 이론이 적용될 수 있는지 등에서 그 관점의 전이가 엿보이는 흥미로운 주제이다. 다만 이 글은 개인적으로 아는 한에서 주제와 관련된 증명들을 다룬 것에 가까우며, 반-바지님이 상정한 것은 permanent와 Bregman’s theorem의 다른 응용일 수도 있어 이 글이 반-바지님이 이야기하고 싶은 것을 제대로 다루지 못했을 가능성도 있다는 점을 마지막으로 짚고 싶다.

트윗 타래를 정리. (2018/01/10)

References

[1] A. Schrijver, “A Short Proof of Minc’s Conjecture” J. Combin. Theory Ser. A, 25, 80-83 (1978). DOI: 10.1016/0097-3165(78)90036-5

[2] J. Radhakrishnan, “An Entropy Proof of Bregman’s Theorem” J. Combin. Theory Ser. A, 77, 161-164 (1997). DOI: 10.1006/jcta.1996.2727

[3] N. Alon and S. Friedland, “The maximum number of perfect matchings in graphswith a given degree sequence” The Electronic Journal of Combinatorics 15 (2008), #N13. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1n13/pdf

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

Gravatar
WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

취소

%s에 연결하는 중