선형대수학 조별프로젝트활동 - Lindström–Gessel–Viennot lemma and applications

선형대수학 조별탐구 활동으로 격자에서의 LGV의 응용에 대해 탐구했습니다. 생각보다 LGV가 개쩌는 정리이기에 여기도 올려보려 합니다.

개요

• Lindström–Gessel–Viennot lemma, 줄여서 LGV 보조정리는, 유향 그래프에서 서로 교차하지 않는 경로쌍의 개수를 구할 때 사용할 수 있는 정리입니다.
• 어떠한 가중치 있는 DAG $G$의 정점 부분집합 $A={a_1,…,a_n}$, $B={b_1,…,b_n}$, (즉 $a_i$와 $b_i$는 $G$의 정점입니다. $A \cap B = \emptyset$일 필요는 없습니다)를 정의합시다. 또, $G$ 위의 경로 $P$에 대해 $w(P)$를 $P$에 포함된 간선의 가중치 곱으로 정의하고, $e(a,b) = \sum_{P:a \rightarrow b}w(P)$라고 합시다. (참고로, $G$의 모든 간선의 가중치가 1이면 $e(a,b)$는 $a$에서 $b$로 가는 경로의 수를 나타내게 됩니다)
• 다음으로, $G$ 위의 $A$와 $B$에 대해 행렬 $M_{n \times n}$을 제시합시다. $M_{i,j}=e(a_i,b_j)$입니다.
• 이제, 다음을 고려합니다:
  • $A$의 $n$개의 정점에서 $B$의 정점으로 가는 교차하지 않는 $n$개의 경로쌍이 있다고 합시다.
  • 이러한 경로쌍이 ${P_1, P_2, …, P_n}$라고 두고, $P_i$는 $a_i$에서 $b_{\sigma(i)}$로 가는 경로라고 하면, 이를 만족하는 $\sigma(i)$는 ${1,2,…,n}$의 순열입니다. 이 순열을 $\sigma(P)$라 합시다.
  • 또한, $i \neq j$에 대해 $P_i$와 $P_j$는 공유하는 정점이 없습니다.
• 이때, LGV lemma의 claim은 다음과 같습니다.
  • $A$에서 $B$로 가는 서로 교차하지 않는 모든 경로쌍 $P$에 대해, (아래의 공식에서 $\sum_P$는 이러한 모든 $P$를 나타냅니다,)
  • \(det(M) = \sum_P (sign(\sigma(P))\Pi_{i=1}^{n}w(P_i))\).
    • 단, 어떤 수열 $P$에 대해 $sign(P)$, 혹은 $signum(P)$는, $P$의 inversion의 수가 홀수면 $-1$, 짝수면 $+1$입니다. 순열의 inversion이란, $i<j$이고 $P_i>P_j$인 $(i,j)$의 개수입니다.
    • 즉, $P$의 inversion의 수가 $N(P)$이면 $sign(P)=(-1)^{N(P)}$입니다.

증명

• 최대한 엄밀히 쓰려고 하기는 했는데 솔직히 LGV를 아예 모르는 사람이 쭉 읽을 수 있을 만큼 충분히 잘 썼는지 모르겠습니다. 영문 위키피디아의 서술이 가장 엄밀한 것 같고, ibm2006님의 블로그에도 좋은 설명이 있으므로 아래가 이해가 안 된다면 두 곳을 참고하시면 되겠습니다.
• 아래에 증명의 요약을 작성했으니 참고하세요.
• 어떤 순열 $\sigma$에 대해, ${a_1,a_2,…,a_N}$에서 ${b_{\sigma(1)}, b_{\sigma(2)}, …,b_{\sigma(N)}}$으로 제시된 순서대로 대응되는 경로쌍(경로가 교차해도 됨을 주의)의 집합을 ‘$\sigma$에 대해 $A$에서 $B$로 가는 $N$-경로’, 임의의 순열 $\sigma$에 대한 ‘$\sigma$에 대해 $A$에서 $B$로 가는 $N$-경로’를 ‘$A$에서 $B$로 가는 섞인 $N$-경로’라고 부릅시다. 이러한 $N$-경로가 서로 교차하지 않을 경우 ‘비교차 $N$-경로’, 교차할 경우 ‘교차 $N$-경로’라고 합시다.
  • 섞인 경로는 $\sigma$가 정해지지 않은 경로쌍, 경로는 $\sigma$가 정해진 경로쌍이라고 생각하시면 됩니다.
• 행렬식의 정의에 의해, $detM = \sum_\sigma sign(\sigma) \Pi_{i=1}^n e(a_i,b_{\sigma(i)})$ 입니다. 이를 정리하면, $detM$

$= \sum_\sigma sign(\sigma) \Pi_{i=1}^n e(a_i,b_{\sigma(i)})$

$= \sum_\sigma sign(\sigma) \Pi_{i=1}^n \sum_{Pi: a_i \rightarrow b_\sigma(i)} w(P_i)$

$= \sum_\sigma sign(\sigma) \sum(: \sigma$에 대해 $A$에서 $B$로 가는 $N$-경로의 모든 경로 $P)w(P)$

$= \sum(:A$에서 $B$로 가는 섞인 $N$-경로의 모든 경로 $P)sign(\sigma(P))w(P)$

$= \sum(: A$에서 $B$로 가는 섞인 비교차 $N$-경로의 모든 경로 $P$)$sign(\sigma(P))w(P)$

$+\sum(: A$에서 $B$로 가는 섞인 교차 $N$-경로의 모든 경로 $P)sign(\sigma(P))w(P)$

• 여기서, $\sum(: A$에서 $B$로 가는 섞인 비교차 $N$-경로의 모든 경로 $P)sign(\sigma(P))w(P)$는 LGV lemma 공식의 우변 $\sum_P (sign(\sigma(P))\Pi_{i=1}^{N}w(P_i))$과 같습니다. 따라서, LGV lemma를 증명하기 위해서는 $\sum(: A$에서 $B$로 가는 섞인 교차 $N$-경로의 모든 경로 $P) sign(\sigma(P))w(P) = 0$임을 증명하면 됩니다.
  • 조금 풀어서 쓰자면, $detM$을 식정리하여 교차 경로에 대한 항과 비교차 경로에 대한 항으로 나누었습니다. 각 항은 LGV 공식의 우항과 비슷한 구조를 가지며, 특히 비교차 경로에 대한 항은 LGV 공식의 우항입니다. 즉 교차 경로에 대한 LGV 공식의 우항이 0임을 증명하면 됩니다.
• $A$에서 $B$로 가는 섞인 교차 $N$-경로의 모든 경로의 집합 $\epsilon$에 대해, $\sum(:A$에서 $B$로 가는 섞인 교차 $N$-경로의 모든 경로 $P) sign(\sigma(P))w(P) = \sum_{P \in \epsilon} sign(\sigma(P))w(P)$입니다. 이때, 어떤 대합(involution) $f:\epsilon \to \epsilon$이 존재하여 $w(f(P))=w(P)$이고 $sign(\sigma(f(P)))=-sign(\sigma(P))$이면 $\sum_{P \in \epsilon} sign(\sigma(P))w(P) = 0$이 됩니다.
  • 대합이란, 쉽게 설명하면 정의역에서 정의역으로 가는 일대일대응입니다.
  • 마찬가지로 조금 풀어서 쓰면, 모든 교차 $N$-경로들을 어떠한 방식으로 두 개가 한 쌍이 되도록 묶었을 때, 각 쌍의 $sign(\sigma(P))w(P)$의 합이 $0$임을 보일 것입니다. 그렇게 하면 모든 교차 경로에 대한 LGV 공식의 우항(즉 합)이 $0$임을 알 수 있습니다.
• 이 사실을 증명해봅시다. 섞인 교차 $N$-경로 $P=(P_1,P_2,…,P_N)$에 대해, $G$의 어떤 정점 $V$가 $P$의 경로 중 두 개 이상에 포함되면 이러한 정점 $V$를 ‘넘친다’고 합시다. $P$가 교차 경로이므로 넘치는 정점이 무조건 하나 이상 있음이 자명합니다. $P_i$가 넘치는 정점을 포함하는 최소의 자연수 를 $i$라고 하고, 그러한 $P_i$의 경로상 가장 첫번째로 나오는 넘치는 정점을 $V$라고 합시다. $V$가 넘치므로 $P_j$가 $V$를 포함하는 $j(\neq i)$가 존재합니다. $j$를 그중 가장 큰 값으로 둡시다. 이제, 두 경로 $P_i$와 $P_j$를 다음과 같이 표현할 수 있습니다. \(P_i: a_i=u_0 \rightarrow u_1 \rightarrow u_2 ... u_{\alpha-1} \rightarrow u_\alpha \rightarrow u_{\alpha+1} ... \rightarrow u_r = b_{\sigma(i)}\) \(P_j: a_j=v_0 \rightarrow v_1 \rightarrow v_2 ... v_{\beta-1} \rightarrow v_\beta \rightarrow v_{\alpha+1} ... \rightarrow v_s = b_{\sigma(j)}\)
• 이때, $r$과 $s$는 각각 $P_i$와 $P_j$의 길이이며, $\sigma=\sigma(P)$이며, $V=u_\alpha=v_\beta$입니다. 이러한 $P_i$와 $P_j$로부터 다음과 같이, $P_i$와 $P_j$의 $V$ 이후의 경로를 교환하고 나머지 경로는 동일하게 유지하는 일대일대응 $f:\epsilon \to \epsilon$과 이를 통해 교환되는 경로 \({P_{i}' = f(P)_{i}, P_{j}' = f(P)_{j}}\)를 정의할 수 있습니다. \({P_{i}' : a_{i}=u_{0} \rightarrow u_1 \rightarrow u_2 ... u_{\alpha-1} \rightarrow v_\beta \rightarrow v_{\alpha+1} ... \rightarrow v_{s} = b_{\sigma(j)}}\) \({P_{j}' : a_{j}=v_{0} \rightarrow v_1 \rightarrow v_2 ... v_{\beta-1} \rightarrow u_\alpha \rightarrow u_{\alpha+1} ... \rightarrow u_{r} = b_{\sigma(i)}}\)
• 여기서, $f(P)$ 역시 섞인 교차 $N$-경로임이 자명합니다. 이러한 작업을 한 번 더 가한 $N$-경로 $f(f(P))$에 대해, $f(f(P))=P$임 역시 자명합니다. 따라서 이러한 함수 $f$는 대합이 됩니다. 즉 $f$가 $w(f(P))=w(P)$이고 $sign(\sigma(f(P)))=-sign(\sigma(P))$를 만족함을 증명하기만 하면 증명이 완성됩니다. 이는 상당히 직관적으로 알 수 있습니다.
  • 풀어서 쓰면, 위에서 모든 교차 $N$-경로들을 어떠한 방식으로 두 개가 한 쌍이 되도록 묶겠다고 했습니다. $P$와 $f(P)$가 한 쌍인 것이고, 위 증명은 $f$를 통해 모든 교차 $N$-경로가 두 개씩 한 쌍으로 묶인다는 것을 보인 것입니다. 이제 이 쌍의 $sign(\sigma(P))w(P)$의 합이 0임을 증명해봅시다.
• 우선, $\sigma(f(P))$는 $\sigma=\sigma(P)$에서 $\sigma(i)$와 $\sigma(j)$의 위치만을 바꾸어준 순열입니다. 따라서 $sign(\sigma(f(P))) = -\sigma(P)$입니다. 또한, 두 경로 $w(P_i’)$와 $w(P_j’)$는 동일한 간선 집합을 가지고 있으므로, $w(P_i’)w(P_j’)=w(P_i)w(P_j)$입니다. 즉,
  \({w(f(P))=\Pi_{k=1}^nw(f(P)_{k})=\Pi_{k=1,k\neq i,j}^nw(P_{k})\times w(P_{i}')w(P_{j}')}\)
  \({=\Pi_{k=1,k\neq i,j}^nw(P_{k})w(P_{i})w(P_{j})=\Pi_{k=1}^nw(P_{k})=w(P)}\)
• 따라서, 대합 $f$가 $w(f(P))=w(P)$이고 $sign(\sigma(f(P)))=-sign(\sigma(P))$를 만족하므로 $\sum_{P \in \epsilon} sign(\sigma(P))w(P) = 0$이며 $det(M) = \sum_P (sign(\sigma(P))\Pi_{i=1}^{N}w(P_i))$입니다. 따라서 LGV lemma가 증명됩니다.

증명 요약

• 식 정리를 통해, $det(M) = \sum_P (sign(\sigma(P))\Pi_{i=1}^{n}w(P_i))$라는 식이 ’($A$와 $B$ 사이에 존재하는) 모든 $P$에 대한 $\sum$의 상황’ 에서 참임을 알 수 있습니다. 따라서, 위 식의 우변 $\sum_P (sign(\sigma(P))\Pi_{i=1}^{n}w(P_i))$이 ‘교차하는 경로가 섞여 있는 모든 $P$에 대한 $\sum$의 상황’ 에서 0임을 보이면 LGV를 증명할 수 있습니다.
• 이를 보이기 위해, 교차하는 경로가 섞여 있는 $P$ 안에서 적절한 이분 매칭을 찾아서,($P$의 개수가 $T$개면 이를 $T/2$개의 쌍으로 나누는 것입니다) 한 쌍의 두 P에 대해 $(sign(\sigma(P))\Pi_{i=1}^{n}w(P_i))$의 합이 0임을 보이면 됩니다.
• 그리고, 교차하는 두 경로의 ‘꼬리를 바꾸는’ 식의 연산을 가하는 어떤 함수 $f$를 이용하면 $(sign(\sigma(P))\Pi_{i=1}^{n}w(P_i))$의 합이 0이도록 $P$들을 쌍으로 나타낼 수 있음을 보였습니다. 따라서 LGV가 증명됩니다.

응용

• 위에서 보인 LGV lemma는 그 claim이 매우 강력하기 때문에 상당히 범용적으로 사용할 수 있습니다. 예를 들어, 다음과 같은 문제를 생각합시다.
• Q1. (Diamond V) $N \times M$의 격자판 위에서, $(1,1)$에서 $(N,M)$으로 가는, 출발지와 도착지를 제외한 점에서는 겹치지 않는 2개의 최단경로 쌍의 수를 구하라.
• 이는 즉, $(1,2)$에서 $(N-1,M)$으로와 $(2,1)$에서 $(N,M-1)$으로 가는 교차하지 않는 경로쌍의 수를 묻는 문제입니다. LGV lemma를 사용하면, 이 문제를 다음과 같이 풀 수 있습니다.
  • 주어진 격자판을 모든 간선이 오른쪽 혹은 아래를 향하는 유향 간선인 그래프라고 생각합시다. 이때 모든 간선의 가중치를 1으로 둡시다.
  • $a_1=(1,2), a_2=(2,1), b_1=(N-1,M), b_2=(N,M-1), A={a_1,a_2}, B={b_1,b_2}$라 합시다.
  • $A$에서 $B$로 가는 경로쌍의 $\sigma$로 가능한 유일한 순열은 $[1,2]$임을 알 수 있습니다.
  • \({e(a_{1},b_{1})=(^{N+M-4}_{M-2}), e(a_{1},b_{2}) = (^{N+M-4}_{N-1})}, {e(a_2,b_1) = (^{N+M-4}_{M-1}), e(a_2,b_2) = (^{N+M-4}_{M-2})}\) 입니다.
  • 즉 \({det(M)=(^{N+M-4}_{M-2})^2-(^{N+M-4}_{N-1})(^{N+M-4}_{M-1})}\) 입니다.
  • $\sigma$가 유일하므로, $\sum_P (sign(\sigma(P))\Pi_{i=1}^{N}w(P_i)) = sign([1,2])\sum_P\Pi_{i=1}^{N}w(P_i)) = \sum_P1$은 이를 만족하는 겹치지 않는 경로쌍 $P$의 개수가 됩니다.
• 즉, 문제의 답은 \({2((^{N+M-4}_{M-2})^2-(^{N+M-4}_{N-1})(^{N+M-4}_{M-1}))}\)으로 매우 직관적인 식이 된다는 것을 알 수 있습니다! (순서가 없는 경로쌍이므로, 순서를 지정하는 데 $2$가 곱해집니다.)
• Q2. (Diamond I) $N \times M$ 격자의 1행에 $K$개의 바둑돌 \(\{(1, A_1), (1, A_2), ..., (1, A_K)\}\)가 있고, $n$행에 도착점 \(\{(n, B_1), (n, B_2), ..., (n, B_K)\}\)가 있다. 각 바둑돌을 아래로 한 칸 혹은 오른쪽으로 한 칸 이동시킬 수 있을 때, 이를 반복해 바둑돌을 $A$에서 출발하여 $B$로 보날 수 있는 교차하지 않는 경로쌍의 수를 구하여라.
• 비슷하게 풀어봅시다. 교차하지 않는 경로이므로 \((1, A_1)\)의 돌이 \((n, B_1)\)으로, \((1, A_2)\)의 돌이 \((n, B_2)\)으로… 가는 것이 유일한 방법임은 자명합니다. 따라서, $A$의 한 칸에서 $B$의 한 칸으로 갈 수 있는 $K^2$개의 경로쌍의 모든 가짓수를 구하고, 이로 행렬을 만들면 행렬식을 구해 문제를 해결할 수 있습니다. 행렬식을 구히는 것은 LU 분해 등을 사용해 $O(N^3)$에 할 수 있으므로 풀 수 있습니다.
• Q3. 어떤 $N \times M$ 행렬 $A$이 $1 \leq i \leq N-1, 1 \leq j \leq M$에 대해 $a_{i,j} \leq a_{i+1,j}$이고, $1 \leq i \leq N, 1 \leq j \leq M-1$에 대해 $a_{i,j} \leq a_{i,j+1}$이면 단조 증가 행렬이라고 하자. 모든 $i,j$에 대해 $1 \leq a_{i,j} \leq K$인 단조 증가 행렬의 개수를 구하여라.
  • 격자점이라는 제한 조건 아래에서는 LGV를 이용해 ‘서로를 넘나들지 않는’ 경로쌍의 수를 세는 것도 가능합니다. $N \times M$ 격자의 $(1,1)$에서 $(N,M)$으로 가는 서로를 넘나들지 않는 경로 $K$개 쌍의 개수는, 각 경로를 평행이동해서 \({A=\{(1-i+1, 1+i-1)}\) for \({1 \leq i \leq K\}}\)에서 \({B=\{(N-i+1, M+i-1)}\) for \({1 \leq i \leq K\}}\)으로 가는 $K$-경로의 개수와 같다는 사실을 직관적으로 알 수 있습니다.
  • 모든 $1 \leq i \leq K-1$에 대해, $i$ 이하의 원소와 $i+1$ 이상의 원소 사이의 경계를 그리면, 각 경계는 $(0,M)$에서 $(N,0)$으로 가는 정확히 한 개의 경로가 됩니다. 각 경계가 ‘서로 넘나들지 않으면’ 올바른 경계가 되며, 다시 말해 $(0,M)$에서 $(N,0)$으로 가는 넘나들지 않는 $K-1$개의 경로쌍은 모든 $i,j$에 대해 $1 \leq a_{i,j} \leq K$인 단조 증가 행렬과 일대일대응됩니다. 따라서 LGV lemma를 이용해 (마찬가지로 모든 경로의 가중치를 1으로 두고) \({A=\{(N+1-i, 1-i)}\) for \({1 \leq i \leq K-1\}}\)에서 \({B=\{(1-i, M+1-i)}\) for \({1 \leq i \leq K-1\}}\)으로 가는 $(K-1)$-경로쌍의 수를 세면 이가 답이 됩니다.
• Q3-1. (Ruby III)어떤 $N \times M$ 행렬 $A$이 $1 \leq i \leq N-1, 1 \leq j \leq M$에 대해 $a_{i,j} \leq a_{i+1,j}$이고, $1 \leq i \leq N, 1 \leq j \leq M-1$에 대해 $a_{i,j} \leq a_{i,j+1}$이면 단조 증가 행렬이라고 하자. 행렬의 정확히 한 원소에 대해서 ${a_{r,c}=v}$임이 주어지면, 모든 $i,j$에 대해 ${1 \leq a_{i,j} \leq K}$인 단조 증가 행렬의 개수를 구하여라.
  • 조건 하나를 추가했습니다. 이제 $a_{r,c}$ 위아래에 있는 경로의 개수가 고정됩니다. 이러한 상태에서도 LGV를 사용할 수 있을까요?
  • 지금까지는 경로의 가중치에 계속 1만 넣었습니다. 변수 $x$를 잡아 $a_{r,c}$ 오른쪽 아래에 있는 경로들이 각각 $x$라는 가중치곱을 가지도록 합시다. 이렇게 하면, 행렬식이 $x$에 대한 다항식이 됩니다.
    • 이는 다양한 방식으로 구현할 수 있습니다. 한 가지 방법을 제시하면, $a_{r,c}$의 오른쪽 아래를 지나는 모든 경로는 $a_{r+1,c} \rightarrow a_{r+1,c+1}, a_{r+2,c} \rightarrow a_{r+2,c+1}, …, a_{n,c} \rightarrow a_{n,c+1}$ 중 정확히 하나의 경로를 지나므로 이들 경로에만 가중치 $x$를 부여하고 나머지는 1으로 두면 됩니다. 비슷한 방식이 많으므로 구현이 편하겠다 싶은 방법을 고르면 됩니다.
  • 이제 $x$에 0, 1, 2…을 대입하면 각각에 대한 행렬식의 값을 구할 수 있으므로, 다항식의 interpolation을 통해 행렬식을 $x$에 대한 다항식 형태로 구할 수 있습니다. 이 다항식의 $x^{K-1}$항의 계수가 답이 됩니다.