인접행렬과 행렬 곱셈 A²

1. 오늘의 네트워크 (Today's Network)

학생 5명($M_1,\dots,M_5$)에게 "친하게 지내는 친구"를 지명하게 한 방향 네트워크. 지명 목록은 다음 7건이다:

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

2. 단원 1-1: 인접행렬의 정의와 표기 (Adjacency Matrix: Definition & Notation)

위 7건의 지명을 행렬로 옮기면:

행과 열을 읽는 법 (Reading Rows and Columns)

• $i$번째 행 $A[i,\,]$ = "$i$가 지명한 사람 목록". 예: $A[1,\,]=(0,1,1,0,1)$ → M1은 M2, M3, M5를 지명.
• $j$번째 열 $A[\,,j]$ = "$j$를 지명한 사람 목록". 예: $A[\,,1]=(0,0,1,0,1)$ → M1을 지명한 사람은 M3, M5.
• 비대칭: $A[1,2]=1$이지만 $A[2,1]=0$. 방향 네트워크에서는 $A[i,j]\ne A[j,i]$일 수 있고, 이 어긋남 자체가 정보다(일방 지명 = 관계 인식의 불일치).

3. 행렬 곱셈의 일반 정의 — "행 × 열" (Matrix Multiplication: Row × Column)

3-1. 먼저 보통 숫자로 — 2×2 곱셈을 사람이 푸는 과정 (A Worked Example with Ordinary Numbers)

규칙은 하나뿐이다: 왼쪽 행렬에서 $i$행을 가로로, 오른쪽 행렬에서 $j$열을 세로로 읽어서, 첫째끼리·둘째끼리 곱한 뒤 더한다. 결과의 $[1,1]$ 자리를 구해 보자:

나머지 세 자리도 전부 같은 동작의 반복이다. 행과 열만 바꿔 가면서:

3-2. 같은 요령을 $A\times A$에 — 행렬을 실제로 나란히 놓고 (The Same Method Applied to $A\times A$)

$A^2$은 $A$ 두 개를 나란히 놓고 곱하는 것이다. $(A^2)[1,1]$을 구하려면 왼쪽 $A$에서 M1의 행, 오른쪽 $A$에서 M1의 열만 보면 된다:

파란 행을 가로로, 주황 열을 세로로 꺼내 짝을 맞추면:

이 2가 결과 행렬의 (1행, 1열) 자리에 들어간다. $A^2$의 나머지 24칸도 전부 "행 하나, 열 하나 골라 짝 곱을 더한다"는 같은 동작의 반복일 뿐이다.

3-3. 일반식과 0·1의 논리 (General Formula & Boolean Logic)

지금 한 손 계산을 일반식으로 쓰면 ($B$ 자리에 $A$):

0과 1로만 이루어진 행렬에서는 항 하나하나가 논리 판정이 된다:

곱셈이 AND 역할을 하는 것이다. 그리고 $k=1,\dots,5$에 대한 합은 "중간에 거칠 수 있는 사람 $k$를 모두 시험해 본 개수"이므로:

4. $(A^2)[1,1]$ 완전 전개 (Full Expansion)

§3-2에서 기계적으로 얻은 값 2를, 이번에는 각 항이 관계에서 무엇을 뜻하는지로 다시 읽는다. 같은 행과 열을 꺼내 놓고:

"자기 자신으로 돌아오는 2단계 경로"란 곧 상호 지명이다. 내가 지명한 $k$가 나를 되지명해야만 $i\to k\to i$가 성립하기 때문. M1은 M3, M5와 서로 지명하는 사이라 값이 2다.

5. 1행의 나머지 항 (Remaining Terms of Row 1)

같은 방법으로 $A[1,\,]=(0,1,1,0,1)$을 각 열과 곱한다. 0이 되는 항은 생략하지 않고 모두 쓴다.

$(A^2)[1,2]$ — 열 $A[\,,2]=(1,0,0,0,0)$

M2를 지명하는 사람은 M1뿐인데($A[1,2]=1$이 열에서 유일한 1), 정작 M1 자신은 자기를 지명할 수 없다. 그래서 M2로 가는 2단계 길은 없다 — M1→M2는 직접 지명 하나뿐.

$(A^2)[1,3]$ — 열 $A[\,,3]=(1,1,0,0,0)$

M1은 M3을 직접 지명하면서(1단계), M2를 거치는 2단계 길도 갖고 있다 — 연결이 이중으로 든든한 관계.

$(A^2)[1,4]$ — 열 $A[\,,4]=(0,0,1,0,0)$

M1은 M4를 직접 지명하지 않지만 M3을 거치면 닿는다 — 직접 관계 없이 존재하는 간접 채널.

$(A^2)[1,5]$ — 열 $A[\,,5]=(1,0,0,0,0)$

M5를 지명하는 사람 역시 M1뿐이라, [1,2]와 같은 이유로 0.

6. 지름길: $A^2$의 $i$행 = 내가 지명한 사람들의 행을 합친 것 (Shortcut: Sum of Out-Neighbors' Rows)

행 단위로 보면 계산이 훨씬 빨라진다. $i$행에서 1인 위치(= $i$가 지명한 사람들)만 살아남으므로:

• M2는 M3만 지명 → $(A^2)[2,\,] = A[3,\,] = (1,0,0,1,0)$. M2의 2단계 세계는 M3의 1단계 세계와 같다.
• M5는 M1만 지명 → $(A^2)[5,\,] = A[1,\,] = (0,1,1,0,1)$.
• M1은 M2, M3, M5를 지명 → $(A^2)[1,\,] = A[2,\,]+A[3,\,]+A[5,\,] = (0,0,1,0,0)+(1,0,0,1,0)+(1,0,0,0,0) = (2,0,1,1,0)$. §4~5의 결과와 정확히 일치.

7. $A^2$ 전체와 모든 경로 (The Full $A^2$ & All 2-Step Paths)

0이 아닌 모든 원소의 경로:

M4의 행이 전부 0인 이유: $A[4,\,]=(0,0,0,0,0)$ — 지명이 하나도 없으니 어떤 2단계 경로의 출발점도 될 수 없다.

8. 대각선과 상호 지명 (Diagonal & Reciprocated Ties)

9. 주의: $A^k$가 세는 것은 '걷기(walk)' (Caution: Walks, Not Paths)

10. 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), byrow=TRUE, nrow=5,
            dimnames=list(paste0("M",1:5), paste0("M",1:5)))

A[1,] * A[,1]        # (A²)[1,1]의 항별 곱
## M1 M2 M3 M4 M5
##  0  0  1  0  1        ← §4 표의 '곱' 열과 일치

sum(A[1,] * A[,1])
## [1] 2

A2 <- A %*% A        # %*% : 행렬 곱 (일반 * 는 원소별 곱이므로 주의)
A2
##    M1 M2 M3 M4 M5
## M1  2  0  1  1  0
## M2  1  0  0  1  0
## M3  0  1  1  0  1
## M4  0  0  0  0  0
## M5  0  1  1  0  1

diag(A2)             # 상호 지명 수
## M1 M2 M3 M4 M5
##  2  0  1  0  1

sum(diag(A2))/2      # 학급 전체 상호 쌍 수
## [1] 2

11. 교실 해석 (Classroom Interpretation)

12. 연습문제 (다음 세션 시작 때 확인) (Exercises)

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

13-1. 문제 1 — $(A^2)[5,3]$ (Two-Step Paths from M5 to M3)

무엇을 곱하는가. $(A^2)[5,3]$이니 왼쪽 $A$에서 M5의 행(=M5가 지명한 사람), 오른쪽 $A$에서 M3의 열(=M3을 지명한 사람)을 꺼낸다. §3-2와 똑같은 동작이고 고르는 행·열만 바뀐다:

다섯 항 완전 전개. 0이 되는 항도 하나도 빼지 않고 쓴다.

왜 이 값이 중요한가. 원래 행렬에서 $A[5,3]=0$이다 — M5는 M3을 직접 지명하지 않았다. 그런데 $(A^2)[5,3]=1$이다. 즉 0에서 1로 바뀐 자리이고, 이것이 $A^2$을 계산하는 이유다.

13-2. 문제 2 — $(A^3)[1,1]$ (Three-Step Closed Walks from M1)

그러니 이번에 꺼낼 두 벡터는 $A^2$의 M1 행과 $A$의 M1 열이다. $A^2$은 §7에서 이미 다 구해 놓았으므로 새로 계산할 것이 없다:

경로 복원. 살아남은 항 $k=3$을 두 조각으로 되짚으면 경로가 완성된다. $(A^2)[1,3]=1$이 어떤 경로였는지는 §5·§7에 있다 — M1→M2→M3. 여기에 마지막 걸음 $A[3,1]=1$인 M3→M1을 이어 붙인다:

A2 <- A %*% A
A3 <- A2 %*% A

sum(A[5,] * A[,3])      # 1   ← 문제 1
sum(A2[1,] * A[,1])     # 1   ← 문제 2
A2[1,] * A[,1]          # 0 0 1 0 0  (k=3 항만 살아남음)

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

diag(A3)                # 1 1 1 0 0  ← 삼각 순환에 참여하는 학생: M1, M2, M3
sum(diag(A3)) / 3       # 1  ← 삼각 순환 1개 (세 학생에서 한 번씩 세어지므로 3으로 나눔)

$\operatorname{diag}(A^3)=(1,1,1,0,0)$을 보면 답이 한눈에 검증된다. 값이 1인 학생은 M1, M2, M3 — 정확히 그 삼각 순환에 참여하는 세 명이고, M4·M5는 0이다. 같은 고리가 세 학생의 대각선에 한 번씩 세어지므로 학급 전체 삼각 순환 수는 $3/3=1$개다. (§8에서 상호 지명 쌍을 $\div 2$로 셌던 것과 같은 논리, 이번엔 $\div 3$.)

다음 단원 — 1-3: $A^3$와 걷기(walk) vs 경로(path), 삼각 순환. 연습문제 2가 그 예고편이다. → 단원 1-3 노트 열기 · 이 문서: notes/02_단원1-2_행렬곱셈과_2단계경로.html