이중시그마에 대한 이해

이중 시그마와 삼중 시그마에 대한 이해

- 이중 시그마(또는 삼중 시그마)를 처음 보면, 변수 범위가 이리저리 얽혀 있어서 꽤 복잡하다는 느낌이 들 수 있다.
- 하지만 실제 계산에 들어가면, 순서만 바꿔도 생각보다 간단해지는 경우가 많다.

---

1) 이중 시그마의 기본 구도

이중 시그마의 대표적인 형태는 다음과 같다:

$$
\sum_{k=1}^n \sum_{t=k}^n f(k,t).
$$

이는 $(k,t)$가 $1 \le k \le t \le n$인 삼각형 격자 영역을 전부 훑는 것과 같다.
여기서 $t$를 먼저 고정하고 $k$를 뒤에서 돌리는 관점으로 바꾸면,

$$
\sum_{t=1}^n \sum_{k=1}^t f(k,t),
$$

이라는 식이 되며, 영역 자체는 동일하다.

---

2) 순서를 바꾸면 어떤 이점이 생길까?

예시 1: $f(k,t) = \frac{k}{t}$

이중 시그마 순서 바꾸기의 전형적인 사례는

$$
f(k,t) = \frac{k}{t}.
$$

원래대로면

$$
\sum_{k=1}^n \sum_{t=k}^n \frac{k}{t}
$$

이 되는데, 각 $k$마다

$$
\sum_{t=k}^n \frac{k}{t}
$$

을 처리해야 해서 꽤 귀찮을 수 있다.
순서를 뒤집어

$$
\sum_{t=1}^n \sum_{k=1}^t \frac{k}{t}
$$

로 쓰면, 안쪽 합이

$$
\sum_{k=1}^t \frac{k}{t}
= \frac{1}{t} \sum_{k=1}^t k
= \frac{1}{t} \cdot \frac{t(t+1)}{2}
= \frac{t+1}{2},
$$

같이 깔끔하게 정리된다. 그 결과 전체 합도 쉽게 계산할 수 있게 된다.

예시 2: $\gcd(k,t)$

$\gcd(k,t)$ 합산 문제에서도, 이중 시그마 순서를 어떻게 배치하느냐가 핵심적인 역할을 한다.
$\gcd$를 분해하거나 특정 공식을 적용할 때, $k$를 먼저 돌리고 $t$를 나중에 합산하는지, 혹은 그 반대 순서로 하는지에 따라 계산 과정이 크게 달라지기도 한다.

---

3) 삼중 시그마: $(i, j, k)$

변수가 두 개에서 세 개로 늘어나면,

$$
\sum_{i=1}^a \sum_{j=i}^b \sum_{k=j}^c F(i,j,k),
$$

처럼 확장된다. 여기서 $(i \le j \le k)$라는 3차원 쐐기 모양 영역을 전부 더하는 것이다.
하지만 $i \to j \to k$ 순서만 고집할 필요는 없고, $k$부터 먼저 고정하는 등 다른 순서를 시도해볼 수 있다.
$F(i,j,k)$의 형태에 따라, 어느 순서가 더 수월한 계산을 제공하는지 달라진다.

---

4) 적분과 같은 발상

이중 시그마가 이산적인 합이라면, 이중 적분은 연속적인 합이라 볼 수 있다.
적분에서도 같은 2차원 영역을 적분한다면, 어느 축을 먼저 적분해도 결과가 같다는 사실을 활용하여 순서를 뒤집을 수 있다.
이 원리는 이중 시그마에서 “영역이 같으면 순서를 바꿔도 합이 변하지 않는다”는 것과 정확히 일치한다.

적분 예시: 삼각형 영역

예를 들어,

$$
\int_{x=0}^1 \int_{y=0}^x f(x,y)\,dy\,dx
\quad\longleftrightarrow\quad
\int_{y=0}^1 \int_{x=y}^1 f(x,y)\,dx\,dy,
$$

같은 식에서, 영역은 $0 \le y \le x \le 1$인 삼각형이다. 이걸 “$x$ 먼저 적분” vs. “$y$ 먼저 적분”으로 바꾸는 건, 이중 시그마에서 순서를 뒤집는 것과 동일한 발상이다.

적분 공식에서의 활용

베타 함수나 감마 함수처럼, 특정 구간 또는 삼각형 영역을 적분할 때 순서를 뒤집으면 중간 계산이나 치환이 편해지는 예시가 많다. 예를 들어,

$$
\int_{0}^1 \int_{0}^x (x-y)^{a-1} \,dy \,dx
$$

같은 이중 적분이 있을 때, $x$와 $y$ 중 어느 축부터 처리하느냐에 따라 적분 과정이 크게 단순화되기도 한다.

---

5) 행렬 연산에서의 이중 시그마

행렬 곱셈 $(AB)_{ij} = \sum_{k=1}^n A_{ik} B_{kj}$에도 이미 이중 시그마 구조가 들어 있다고 볼 수 있다.
여기에 대각합(트레이스)를 취하면,

$$
\mathrm{tr}(AB)
= \sum_{i=1}^n (AB)_{ii}
= \sum_{i=1}^n \sum_{k=1}^n A_{ik} B_{ki}.
$$

인덱스를 바꾸면 $\mathrm{tr}(BA)$가 되므로,

$$
\mathrm{tr}(AB) = \mathrm{tr}(BA),
$$

라는 익숙한 성질을 쉽게 보여줄 수 있다.
또, 전치 연산 $A^T$에서 $(A^T)_{ij} = A_{ji}$가 되어, $\mathrm{tr}(A^T)=\mathrm{tr}(A)$라는 사실도 “이중 시그마 순서 교환” 관점에서 간단히 설명된다.

이중 시그마로 보는 행렬 곱셈과 전치

- 행렬 곱셈 자체
$$
(AB)_{ij}
= \sum_{k=1}^n A_{ik} B_{kj}.
$$
이는 $(i,j)$가 움직이고, 그 내부에서 $k$가 1부터 $n$까지 움직이는 이중 시그마 구조다. 인덱스 재배열을 잘 살피면, 예컨데 $i$와 $k$를 먼저 잡고 나중에 $j$를 잡는 식으로도 바꿔 쓸 수 있다.

- 전치 연산
$$
(A^T)_{ij} = A_{ji}.
$$
이를 “모든 $i,j$에 대해” 씌우면,
$$
A^T = (A^T)_{ij}
= A_{ji}.
$$
결국 이중 시그마에서 인덱스 $(i,j)$를 $(j,i)$로 스왑하는 과정을 그대로 반영한 것이며, 이러한 인덱스 교환이 가능하다는 점이 전치의 본질을 잘 보여준다.

더 나아간 행렬 성질

- 세 행렬 이상일 때
$$
\mathrm{tr}(ABC)
= \sum_{i,j,k} A_{ij} B_{jk} C_{ki}.
$$
인덱스 $(i,j,k)$를 순환적으로 재배열하면
$$
\mathrm{tr}(CAB) = \mathrm{tr}(BCA) = \mathrm{tr}(ABC),
$$
가 되어, $\mathrm{tr}(ABC)$는 행렬의 곱 순서를 순환시켜도 값이 변하지 않는다는 사실이 드러난다.

- $\mathrm{tr}(A^T B) = \sum_{i,j} A_{ij} B_{ij}$
$$
\mathrm{tr}(A^T B)
= \sum_{i,j} (A^T)_{ij} B_{ji}
= \sum_{i,j} A_{ji} B_{ji}
= \sum_{i,j} A_{ij} B_{ij}.
$$

- $\mathrm{tr}(A^2) \ge 0$ (대칭 행렬일 때)
실대칭행렬 $A$에서 $A_{ij} = A_{ji}$를 적용해 보면,
$$
\mathrm{tr}(A^2)
= \sum_{i,j} A_{ij} A_{ji}
= \sum_{i,j} (A_{ij})^2
\ge 0.
$$

---

6) 그래프 이론 예시

무방향 그래프에서 노드가 $n$개 있고, 간선 가중치가 $w(i,j)$로 주어진다고 하자. 모든 간선의 합은

$$
\sum_{i=1}^n \sum_{j=i+1}^n w(i,j)
$$

같이 표현할 수 있다. 여기서 $i < j$가 중복을 막아주는 조건이 된다.
순서를 바꾸면

$$
\sum_{j=2}^n \sum_{i=1}^{j-1} w(i,j)
$$

로 쓸 수도 있고, 실제 코드 구현에서 바깥 루프와 안쪽 루프를 어떻게 잡느냐에 따라 효율이나 단순화가 달라질 수 있다.

그래프 예시: 완전 그래프의 간선 수 증명

완전 그래프 $K_n$은 노드가 $n$개 있고, 모든 노드 쌍 $(i,j)$가 간선으로 연결되어 있다.
- 각 간선은 $(i,j)$ 형태이고, $1 \le i < j \le n$으로 한정하면 중복 없이 세도록 할 수 있다.

해당 간선들의 총 개수를 구해 보자:

$$
\sum_{i=1}^n \sum_{j=i+1}^n 1.
$$

여기서 안쪽 합 $\sum_{j=i+1}^n 1$ 은 $(n - i)$개가 된다. 따라서

$$
\sum_{i=1}^n (n - i)
= \sum_{i=1}^n (n - i)
= n \cdot n - \sum_{i=1}^n i
= n^2 - \frac{n(n+1)}{2}
= \frac{n(n-1)}{2}.
$$

결국 완전 그래프 $K_n$의 간선 수는 $\frac{n(n-1)}{2}$임이 증명된다.
(순서를 바꾸면 $\sum_{j=2}^n \sum_{i=1}^{j-1} 1$ 꼴이 되지만, 계산 결과는 동일하다.)

---

7) 클러스터링: 거리 합 예시

클러스터링 등에서 샘플 $\{x_1,\dots,x_N\}$마다 모든 쌍의 거리를 합산하려면,

$$
\sum_{i=1}^N \sum_{j=i+1}^N \mathrm{dist}(x_i, x_j)
$$

라는 식을 쓰는 경우가 많다. 여기서도 $i < j$를 $j < i$로 뒤집어도 같은 영역을 표현한다.
구현상, 어떤 순서를 바깥 루프로 잡느냐에 따라 메모리 접근이나 알고리즘 최적화에 유불리가 생길 수 있다.

---

8) 이항계수 예시

이중 시그마가 $\binom{t}{k}$ 형태를 갖는 경우에도 순서 교환이 크게 유용하다. 예를 들어,

$$
\sum_{t=0}^n \sum_{k=0}^t \binom{t}{k}
$$

는 안쪽 합이 $2^t$가 되어, $\sum_{t=0}^n 2^t = 2^{n+1}-1$이라는 결론을 얻을 수 있다.
순서를 뒤집어

$$
\sum_{k=0}^n \sum_{t=k}^n \binom{t}{k}
$$

로 쓰면, $\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}$ 같은 식을 적용할 수도 있다. 결국 같은 값을 얻지만, 문제 풀이 과정에서 어떤 공식을 사용하는지 달라지는 점이 흥미롭다.

---

9) 정수론 예시: $\gcd$ 이중합의 재배열

가장 널리 알려진 예시 중 하나는 다음과 같은 정수론 문제다:

$$
S(n) = \sum_{k=1}^n \sum_{t=1}^n \gcd(k,t).
$$

이를 직접 계산하기는 꽤 까다롭지만, $\gcd$를 재해석하고 이중 시그마 순서를 적절히 뒤집어 보면 놀라운 정리가 나온다:

> 정리:
> $$
> S(n) = \sum_{k=1}^n \sum_{t=1}^n \gcd(k,t)
> = \sum_{d=1}^n \varphi(d) \Big\lfloor \frac{n}{d} \Big\rfloor^2,
> $$
> 여기서 $\varphi$는 오일러의 totient 함수다.

증명 아이디어 (간단 버전)

1. $\gcd(k,t) = d$라고 하자. 그러면 $k = d k'$, $t = d t'$이고 $\gcd(k', t') = 1$이다.
2. 이 로직을 “$\gcd(k,t) = d$”라는 구역으로 다시 분해하면,
   $$
   \sum_{k=1}^n \sum_{t=1}^n \gcd(k,t)
   = \sum_{d=1}^n \sum_{\substack{k=1 \\ d \mid k}}^n \sum_{\substack{t=1 \\ d \mid t}}^n \gcd(k,t) \quad (\text{각 } d \text{마다})
   $$
   이때 $\gcd(k,t) = d \cdot \gcd(k',t')$, $k' = k/d$, $t' = t/d$.
3. $\gcd(k',t')=1$인 경우만 합에 기여하므로, 이 과정을 재배열해 보면 각 $d$별로 $\lfloor n/d \rfloor \times \lfloor n/d \rfloor$ 범위에서 $k',t'$를 1부터 $\lfloor n/d \rfloor$까지 훑을 때, $\gcd(k',t')=1$인 쌍을 전부 포함한다.
4. 결국 $\varphi$ 함수(1부터 주어진 범위까지 서로소 쌍 개수를 세는 성질)와 맞물려서, 모든 계산이
   $$
   \sum_{d=1}^n \varphi(d) \Big(\lfloor \tfrac{n}{d} \rfloor\Big)^2
   $$
   꼴로 정리된다.

이를 통해 이중 시그마에서 $\gcd$를 직접 다루기보다, “$\gcd(k,t)=d$”라는 조건으로 영역을 새롭게 뒤집고 쪼개는 방식을 쓰는 편이 훨씬 효율적이라는 사실을 알 수 있다.

---

결론

- 이중 시그마(혹은 삼중 시그마)는 변수 범위가 복잡해 보이지만, “순서를 바꿀 수 있다”는 자유 덕분에 계산상 놀라운 단순화를 유도한다.
- 적분, 행렬 연산, 그래프 이론, 클러스터링, 이항계수, $\gcd$ 문제 등 다양한 분야에서 응용이 나타난다.
- 동일한 2차원(또는 3차원) 영역을 다른 순서로 훑어도, 영역이 변하지 않는 한 합(또는 적분)은 그대로이므로, 그 재배열 과정에서 고정된 시점을 사용해서 재배열하면 문제의 난이도가 낮아진다.