A³, 걷기 vs 경로, 삼각 순환

1. 오늘의 질문 (Today's Question)

단원 1-2에서 $(A^2)[i,j]$를 "$i$에서 $j$로 가는 2단계 경로의 개수"라고 읽었다. 자연스러운 다음 질문은 이것이다:

아니다. 오늘 단원의 목적은 이 "아니다"를 정확히 이해하는 것이다. $A^2$까지는 우연히 맞았고, $A^3$부터 어긋난다. 어디서 어긋나는지, 왜 어긋나는지, 그럼 $A^3$의 값은 정확히 무엇을 세는지를 손으로 확인한다.

네트워크는 단원 1-1·1-2와 같은 학생 5명의 지명 데이터를 계속 쓴다. 지명 7건:

M1→M2 M1→M3 M1→M5 M2→M3 M3→M1 M3→M4 M5→M1

$A^2$은 단원 1-2 §7에서 손으로 다 구해 놓은 것이므로 오늘은 그대로 가져다 쓴다.

2. 걷기·경로·순환의 정의 (Walk, Path, Cycle: Definitions)

어긋남을 이해하려면 먼저 세 가지를 구별하는 말이 필요하다. 지금까지 뭉뚱그려 "경로"라고 불렀던 것을 쪼갠다.

우리 네트워크에서 실제로 존재하는 3걸음 걷기 몇 개를 이 자로 재 보면:

세 번째·네 번째를 "M1에서 M3으로 가는 3단계 경로"라고 부르면 틀린다. M1을 다시 밟았으니 제자리로 돌아왔다 다시 출발한 것이지, 새로운 사람을 셋 거쳐 간 것이 아니다. 교실 언어로 말하면 "친구의 친구의 친구"가 아니라 "내 친구 → 나 → 내 친구"일 뿐이다.

3. 손으로 $A^3$ 만들기 (Building $A^3$ by Hand)

3-1. 먼저 보통 숫자로 — 세제곱은 곱셈을 한 번 더 (Ordinary Numbers First)

새 규칙은 없다. 단원 1-2 §3의 "왼쪽 행렬의 행을 가로로, 오른쪽 행렬의 열을 세로로 읽어 짝끼리 곱해 더한다"를 한 번 더 하는 것이 전부다. 익숙한 숫자로 확인하자.

($B^2$의 첫 칸: $1\cdot1+2\cdot3=7$.) 이제 $B^3 = B^2 \times B$이므로 $B^2$의 행과 $B$의 열을 짝지으면 된다:

같은 식으로 네 칸을 다 채우면:

3-2. $A^3 = A^2 \times A$ — 무엇을 곱하는가 (What Gets Multiplied)

$A^3$도 똑같다. 왼쪽에 $A^2$, 오른쪽에 $A$를 놓는다:

단원 1-2의 식과 모양은 같지만 $k$의 정체가 다르다. 이 차이가 오늘 계산의 전부다:

즉 "$i$에서 두 걸음 걸어 $k$에 도착한 걷기의 수" × "$k$에서 $j$로 가는 마지막 한 걸음"이다. 그리고 여기서 이미 함정의 씨앗이 보인다 — 이어 붙일 때 "앞의 두 걸음에서 이미 $j$를 지났는지" 아무도 확인하지 않는다.

4. $(A^3)[3,3]$ 완전 전개 — 삼각 순환 (Full Expansion: a Triangle)

먼저 잘 작동하는 경우부터. M3에서 출발해 3걸음 뒤 M3으로 돌아오는 걷기를 센다. 왼쪽 $A^2$에서 M3의 행, 오른쪽 $A$에서 M3의 열을 꺼낸다:

다섯 항을 하나도 빼지 않고 전개한다:

경로 복원. 살아남은 항 $k=2$를 두 조각으로 되짚는다. $(A^2)[3,2]=1$은 단원 1-2 §7에서 M3→M1→M2였고, 여기에 $A[2,3]=1$인 M2→M3을 이어 붙이면:

5. $(A^3)[1,3]=2$ — 함정 (The Trap: 2 Walks, 0 Paths)

이번엔 어긋나는 자리다. M1에서 M3으로 가는 3걸음을 센다. 왼쪽 $A^2$의 M1 행, 오른쪽 $A$의 M3 열:

걷기 복원. 문제는 $k=1$ 항의 2다. $(A^2)[1,1]=2$는 단원 1-2 §4에서 "M1이 맺은 상호 지명 2건", 즉 2걸음으로 제자리로 돌아오는 걷기 M1→M3→M1과 M1→M5→M1이었다. 각각에 마지막 걸음 M1→M3을 이어 붙이면:

6. $A^3$ 전체와 19개 걷기 전수 분류 (All 19 Walks Classified)

모든 원소의 값이 어떤 걷기들인지 전부 적으면 이렇다. 색으로 분류했다 — 초록 = 진짜 경로, 보라 = 삼각 순환, 빨강 = 재방문 걷기.

연습문제로 남긴 두 칸을 빼고 세면 17개 걷기 중 진짜 경로는 3개, 삼각 순환 3개, 재방문 걷기가 11개다. 즉 $A^3$의 값 대부분은 "왔다 갔다 한 것"이다.

7. 왜 행렬 곱은 경로를 못 세는가 (Why Matrix Powers Cannot Count Paths)

이유는 §3-2의 식 하나에 다 들어 있다:

7-1. 나쁜 항은 행렬의 어느 칸에서 오는가 (Locating the Bad Term in the Matrix)

말로만 하면 와닿지 않으니 행렬을 직접 놓고 확인한다. §5의 $(A^3)[1,3]=2$를 다시 본다. 왼쪽 $A^2$의 M1 행과 오른쪽 $A$의 M3 열을 곱한다:

7-2. $A^2$의 대각선 = 상호 지명 수 (The Diagonal of $A^2$ Counts Mutual Nominations)

$(A^2)[1,1]$을 정의대로 다섯 항 전부 전개한다(0인 항도 생략하지 않는다):

항 $A[1,k]\,A[k,1]$이 1이 되려면 M1→$k$와 $k$→M1이 동시에 있어야 한다. 곧 상호 지명이다. 살아남은 $k=3,\,5$가 바로 M1의 상호 지명 상대다. 이 곱을 행렬 전체에 대해 한 번에 하려면 $A$와 그 전치 $A^{\mathsf T}$를 같은 자리끼리 곱하면(아다마르 곱 $\odot$) 된다:

이 행 합을 $m_i$("$i$의 상호 지명 친구 수")라 부르자. $A^2$의 대각선과 나란히 놓으면 완전히 같다:

7-3. 그럼 왜 $A^2$까지는 맞았나 (Why $A^2$ Was Safe)

$A^2$를 대각선과 나머지로 갈라 놓고 보면 사정이 한눈에 보인다:

대각선의 4개는 M1→M3→M1, M1→M5→M1, M3→M1→M3, M5→M1→M5 — 모두 상호 지명을 왕복한 것이다(§7-2). 그리고 $i\neq j$인 칸 8개는 하나도 빠짐없이 경로다. 왜 그런가:

자기 지명 금지가 정말 방패였는지 확인해 보자. M3이 자기 자신을 지명했다고 가정하고 $A[3,3]=1$ 한 칸만 바꿔 본다:

$i=1\neq j=3$인데도 경로가 아닌 걷기가 끼어들었다. 즉 $A^2$가 안전했던 것은 운이 아니라 $\operatorname{diag}(A)=0$이라는 구조 덕분이었다.

7-4. 길이 3에서는 무엇이 뚫리는가 (When Length 3 Breaks)

3걸음 걷기 $i\to a\to b\to j$에는 학생이 네 명 등장한다. 재방문이란 이 넷 중 어느 둘이 같다는 뜻이므로, 가능한 짝 $\binom{4}{2}=6$가지를 하나도 빠뜨리지 않고 따져야 한다:

살아남은 두 형태를 우리 예제의 실제 걷기로 확인한다(§6의 19개 목록에서 그대로 가져온 것):

7-5. 헛걸음을 행렬만으로 세는 공식 (Counting Bad Walks with Matrices Alone)

§7-4의 두 형태를 그대로 개수로 옮기면 된다. $i\neq j$일 때:

여기서 $m=(2,0,1,0,1)$이다(§7-2). 이제 §6에서 분류했던 칸들을 이 공식으로 다시 세어 본다. 손으로 하나씩 걷기를 복원하지 않아도 행렬 세 개($A$, $\operatorname{diag}(A^2)$, $A^3$)만으로 답이 나온다:

8. 삼각 순환 세기 — $\operatorname{tr}(A^3)/3$ (Counting 3-Cycles)

$A^3$의 대각선만 뽑으면:

값이 1인 학생은 M1, M2, M3 — 그리고 삼각 순환에 참여하는 학생이 정확히 이 셋이다. M4, M5는 0이니 어떤 삼각 순환에도 들어 있지 않다. 그런데 삼각 순환은 1개인데 합은 3이다. 같은 고리가 세 번 세어졌기 때문이다:

무방향이면 6으로 나눈다 (Undirected: Divide by 6)

지명 방향을 무시하고 "둘 중 한 명이라도 지명했으면 친구"로 보면 대칭 행렬 $S$($S[i,j]=S[j,i]$)가 된다:

이번엔 6으로 나눈다. 무방향 삼각형 하나는 출발점 3가지 × 도는 방향 2가지 = 6번 세어지기 때문이다(M1→M2→M3→M1과 M1→M3→M2→M1이 같은 삼각형). 삼각형은 $\{M_1,M_2,M_3\}$ 하나다.

9. R 검증 (Verification in R)

A <- matrix(c(0,1,1,0,1,
              0,0,1,0,0,
              1,0,0,1,0,
              0,0,0,0,0,
              1,0,0,0,0), 5, 5, byrow = TRUE)
dimnames(A) <- list(paste0("M",1:5), paste0("M",1:5))

A2 <- A %*% A
A3 <- A2 %*% A
A3
#    M1 M2 M3 M4 M5
#  M1  1  2  2  1  2
#  M2  0  1  1  0  1
#  M3  2  0  1  1  0
#  M4  0  0  0  0  0
#  M5  2  0  1  1  0

sum(A3)                    # 19  ← 3걸음 걷기 총 개수
sum(A2[3,] * A[,3])        # 1   ← §4
sum(A2[1,] * A[,3])        # 2   ← §5
A2[1,] * A[,3]             # 2 0 0 0 0  (k=1 항이 2를 만든다)

M <- A * t(A)              # 상호 지명 행렬 (아다마르 곱) ← §7-2
rowSums(M)                 # 2 0 1 0 1  ← m_i
diag(A2)                   # 2 0 1 0 1  ← 정확히 같다
all(rowSums(M) == diag(A2))            # TRUE

m <- diag(A2)                          # ← §7-5 헛걸음 공식
bad <- A * (outer(m, m, "+") - t(A)); diag(bad) <- 0
bad
#    M1 M2 M3 M4 M5
#  M1  0  2  2  0  2
#  M2  0  0  1  0  0
#  M3  2  0  0  1  0
#  M4  0  0  0  0  0
#  M5  2  0  0  0  0

A3 - bad                   # 대각선 밖 = 3걸음 '진짜 경로' 수 (대각선은 삼각 순환 그대로)
#    M1 M2 M3 M4 M5
#  M1  1  0  0  1  0
#  M2  0  1  0  0  1
#  M3  0  0  1  0  0
#  M4  0  0  0  0  0
#  M5  0  0  1  1  0   ← 연습문제를 푼 뒤 [3,4]와 [5,3] 칸을 맞춰 볼 것

diag(A3)                   # 1 1 1 0 0
sum(diag(A3)) / 3          # 1   ← 방향 삼각 순환 1개

S <- pmax(A, t(A))                     # 대칭화(방향 무시)
sum(diag(S %*% S %*% S)) / 6           # 1   ← 무방향 삼각형 1개

여기까지는 걷기의 개수일 뿐이다. 진짜 경로를 보려면 igraph의 경로 탐색을 쓴다. $(A^3)[1,3]=2$가 경로가 아니라는 §5의 주장이 이것으로 확인된다:

library(igraph)
g <- graph_from_adjacency_matrix(A, mode = "directed")

all_simple_paths(g, from = "M1", to = "M3")
# M1→M2→M3   (2걸음)
# M1→M3      (1걸음)
# ← 3걸음 단순경로는 하나도 없다. A3[1,3]=2 는 전부 재방문 걷기였다.

all_simple_paths(g, from = "M5", to = "M3")
# M5→M1→M2→M3  (3걸음)  ← 연습문제 1의 답과 비교해 볼 것
# M5→M1→M3     (2걸음)

triangles(g)               # M1 M3 M2  ← 방향 무시한 삼각형
count_triangles(g)         # 1 1 1 0 0 ← 학생별 참여 삼각형 수

all_simple_paths()는 이름 그대로 단순경로(simple path), 즉 재방문 없는 경로만 찾는다. 행렬 거듭제곱과 결과가 다른 이유가 여기에 있다.

10. 교실 해석 (Classroom Interpretation)

11. 연습문제 (Exercises)

12. 연습문제 해설과 답 (Solutions)

12-1. 문제 1 — $(A^3)[5,3]$ (A Genuine 3-Step Path)

무엇을 곱하는가. 왼쪽 $A^2$의 M5 행, 오른쪽 $A$의 M3 열:

걷기 복원. 살아남은 항 $k=2$: $(A^2)[5,2]=1$은 단원 1-2 §7에서 M5→M1→M2였고, 마지막 걸음 $A[2,3]=1$은 M2→M3이다.

왜 §5와 갈렸는가. $(A^3)[1,3]$에서 함정을 만든 것은 $k=1$ 항, 즉 "제자리로 돌아오는 2걸음"이 목적지 M3의 지명자와 겹친 것이었다. 여기서는 제자리로 돌아오는 항($k=5$, M5→M1→M5)이 있긴 하지만 M5→M3 지명이 없어서 $A[5,3]=0$에 막혀 죽는다. 살아남은 길은 새 사람만 밟는 $k=2$ 뿐이었다.

12-2. 문제 2 — $(A^3)[3,4]$ (A Walk That Is Not a Path)

왼쪽 $A^2$의 M3 행, 오른쪽 $A$의 M4 열:

$A[\,,4]$에 1이 단 하나(M3)뿐이라는 점을 먼저 눈여겨보자. M4를 지명한 사람이 M3 한 명이므로, M4로 가는 마지막 걸음은 반드시 M3→M4다.