Search
Duplicate

프리드버그 선형대수학/ 선형변환과 행렬/ 선형변환의 합성과 행렬 곱

선형변환의 합성과 행렬 곱

•
앞서 행렬의 합과 스칼라 곱을 각각 선형변환의 합과 스칼라 곱에 대응하는 방식으로 두 개념을 연결하였다. 그렇다면 선형변환의 합성에 대응하는 행렬의 연산은 무엇일까? 바로 행렬 곱이다.
•
두 선형변환 U,TU, T의 합성을 나타낼 때 U∘TU \circ T 대신 간단하게 UTUT로 표현할 것이다.
•
정리 2.9)
◦
FF-벡터공간 V,W,ZV, W, Z와 선형변환 T:V→W,U:W→ZT : V \to W, U : W \to Z를 생각하자. 두 선형변환의 합성 UT:V→ZUT : V \to Z는 선형변환이다.
◦
증명)
▪
x,y∈V,a∈Fx, y \in V, a \in F에 대하여 다음이 성립한다.
•
UT(ax+y)+U(T(ax+y))=U(aT(x)+T(y))=aU(T(x))+U(T(y))=a(UT)(x)+UT(y)UT(ax + y) + U(T(ax + y)) \\ = U(aT(x) + T(y)) \\ = aU(T(x)) + U(T(y)) \\ = a(UT)(x) + UT(y)
•
정리 2.10)
◦
벡터공간 VV와 선형변환 T,U1,U2∈L(V)T, U_{1}, U_{2} \in \mathcal{L}(V)에 대하여 다음이 성립한다.
1.
T(U1+U2)=TU1+TU2T(U_{1} + U_{2}) = TU_{1} + TU_{2} 이고 (U1+U2)T=U1T+U2T(U_{1} + U_{2})T = U_{1}T + U_{2}T
2.
T(U1U2)=(TU1)U2T(U_{1}U_{2}) = (TU_{1})U_{2}
3.
TI=IT=TTI = IT = T
4.
모든 스칼라 aa에 대하여 a(U1U2)=(aU1)U2=U1(aU2)a(U_{1}U_{2}) = (aU_{1})U_{2} = U_{1}(aU_{2})
•
선형변환의 정의역과 공역이 같지 않으면 이보다 일반적인 결과가 성립한다.
•
어떤 상황에서는 T∈L(V)T \in \mathcal{L}(V)인 TT를 자연스럽게 여러 번 합성하기도 한다. 예컨대 T:V→V,T(f)=f′T : V \to V, T(f) = f'를 생각해보자. (이때 VV는 무한 번 미분가능한 실함수의 집합)
◦
TT(f)=T(f′)=(f′)′=f′′TT(f) = T(f') = (f')' = f'': f의 이계도함수
◦
TTT(f)=f′′′TTT(f) = f''' : f이 삼계도함수
•
이런 상황에서 다음 표기법을 유용하게 사용할 수 있다.
◦
T∈L(V)T \in \mathcal{L}(V) 일 때, T1=T,T2=TT,T3=T2T,...T^{1} = T, T^{2} = TT, T^{3} = T^{2}T, ... 라 정의한다. 즉 2 이상의 자연수 kk에 대하여 Tk=Tk−1TT^{k} = T^{k-1}T이다.
◦
편의를 위해 T0=lVT^{0} = l_{V}라 정의한다.
•
이제 행렬 곱에 대해 알아보자. 유한차원 벡터공간 V,W,ZV, W, Z와 선형변환 T:V→W,U:W→ZT : V \to W, U : W \to Z가 있다.
◦
VV의 순서기저 α={v1,v2,...,vn}\alpha = \{ v_{1}, v_{2}, ... , v_{n} \}, WW의 순서기저 β={w1,w2,...,wn}\beta = \{ w_{1}, w_{2}, ... , w_{n} \}, ZZ 의 순서기저 γ={z1,z2,...,zn}\gamma = \{ z_{1}, z_{2}, ... , z_{n} \}에 대하여 A=[U]βγ,B=[T]αβA = [U]_{\beta}^{\gamma}, B = [T]_{\alpha}^{\beta}라 하자.
◦
AB=[UT]αγAB = [UT]_{\alpha}^{\gamma}가 되도록 하는 두 행렬 곱 ABAB를 정의하려 한다.
◦
[UT]αγ[UT]_{\alpha}^{\gamma} 가 어떤 모양일지 생각해 보자. j=1,2,...,nj = 1, 2, ... , n에 대하여 다음이 성립한다.
▪
(UT)(vj)=U(T(vj))=U(∑k=1mBkjwk)=∑k=1mBkjU(wk)=∑k=1mBkj(∑i=1pAikzi)=∑i=1p(∑k=1mAikBkj)zi=∑i=1pCijzi(UT)(v_{j}) = U(T(v_{j})) \\ = U(\sum_{k = 1}^{m} B_{kj}w_{k}) \\ = \sum_{k=1}^{m} B_{kj} U(w_{k}) \\ = \sum_{k=1}^{m} B_{kj} (\sum_{i=1}^{p} A_{ik} z_{i}) \\ = \sum_{i=1}^{p} (\sum_{k=1}^{m} A_{ik} B_{kj})z_{i} \\ = \sum_{i=1}^{p} C_{ij} z_{i}
▪
(이때 Cij=∑k=1mAikBkjC_{ij} = \sum_{k=1}^{m} A_{ik} B_{kj})
◦
이 계산에 따르면 행렬 곱을 다음과 같이 자연스럽게 정의할 수 있다.
•
정의) m×nm \times n 행렬 AA와 n×pn \times p 행렬 BB에 대하여 두 행렬 A,BA, B의 곱(product) ABAB는 다음과 같이 정의된 m×pm \times p 행렬이다.
◦
1≤i≤m,1≤j≤p1 \leq i \leq m, 1 \leq j \leq p에 대하여 (AB)ij=∑k=1nAikBkj(AB)_{ij} = \sum_{k=1}^{n} A_{ik}B_{kj}
•
행렬 A,BA, B의 크기가 서로 맞아야 행렬곱 ABAB를 정의할 수 있다는 사실에 주의해야 한다. 다음과 같이 연상하면 쉽게 기억할 수 있다.
◦
(m×n)⋅(n×p)=(m×p)(m \times n) \cdot (n \times p) = (m \times p)
◦
내부의 차원이 같아야 행렬곱 ABAB를 정의할 수 있고, 외부의 차원이 행렬 ABAB의 크기를 결정한다.
•
예제 1) 단순 행렬 계산이라 생략
•
함수의 합성과 마찬가지로 행렬 곱 또한 교환법칙이 성립하지 않는다.
◦
AB,BAAB, BA가 모두 정의되더라도 AB≠BAAB \neq BA일 수 있다.
•
m×nm \times n 행렬 AA와 n×pn \times p 행렬 BB에 대하여 (AB)t=BtAt(AB)^{t} = B^{t} A^{t}이다. 행렬의 성분을 각각 비교하면 다음과 같기 때문이다.
◦
(AB)ijt=(AB)ji=∑k=1nAjkBki(AB)_{ij}^{t} = (AB)_{ji} = \sum_{k=1}^{n} A_{jk} B_{ki}
◦
(BtAt)ij=∑k=1n(Bt)ik(At)kj=∑k=1nBkiAjk(B^{t}A^{t})_{ij} = \sum_{k=1}^{n} (B^{t})_{ik}(A^{t})_{kj} = \sum_{k=1}^{n} B_{ki}A_{jk}
◦
즉 '행렬 곱의 전치'는 순서가 뒤집힌 전치행렬의 곱'이 된다.
•
정리 2.11)
◦
유한차원 벡터공간 V,W,ZV, W, Z와 각각의 순서기저 α,β,γ\alpha, \beta, \gamma, 선형변환 T:V→W,U:W→ZT : V \to W, U : W \to Z에 대하여 다음이 성립한다.
▪
[UT]αγ=[U]βγ[T]αβ[UT]_{\alpha}^{\gamma} = [U]_{\beta}^{\gamma} [T]_{\alpha}^{\beta}
•
따름정리)
◦
유한차원 벡터공간 VV와 순서기저 β\beta, 선형연산자 T,U∈L(V)T, U \in \mathcal{L}(V)에 대하여 다음이 성립한다.
▪
[UT]β=[U]β[T]β[UT]_{\beta} = [U]_{\beta}[T]_{\beta}
•
예제 2) 적분했다가 미분하면 원래 함수로 돌아온다는 예시 생략
•
정리 2.12)
◦
AA가 m×nm \times n 행렬 BB와 CC가 n×pn \times p행렬, DD와 EE가 q×mq \times m 행렬일 때, 다음이 성립한다.
▪
A(B+C)=AB+AC,(D+E)A=DA+EAA(B+C) = AB + AC, (D + E)A = DA + EA
▪
임의의 스칼라 aa에 대하여 a(AB)=(aA)B=A(aB)a(AB) = (aA)B = A(aB)
▪
ImA=A=AInI_{m}A = A = AI_{n}
•
따름정리)
◦
m×nm \times n 행렬 VV와 n×pn \times p 행렬 B1,B2,...,BkB_{1}, B_{2}, ... , B_{k}, q×mq \times m 행렬 C1,C2,...,CkC_{1}, C_{2}, ... , C_{k}, 스칼라 a1,a2,...,aka_{1}, a_{2}, ... , a_{k}에 대하여 다음이 성립한다.
▪
A(∑i=1kaiBi)=∑i=1kaiABiA(\sum_{i=1}^{k} a_{i}B_{i}) = \sum_{i=1}^{k} a_{i}AB_{i}
▪
(∑i=1kaiCi)A=∑i=1kaiCiA(\sum_{i=1}^{k} a_{i}C_{i})A = \sum_{i=1}^{k} a_{i}C_{i}A
•
n×nn \times n 행렬 AA에 대하여 A1=A,A2=AA,A3=A2AA^{1} = A, A^{2} = AA, A^{3} = A^{2}A이다.
◦
일반화하면 22 이상의 자연수 kk에 대하여 Ak=Ak−1AA^{k} = A^{k-1}A 라 정의한다. 이때 A0=InA^{0} = I_{n} 이다.
•
이 표기법에 따르면 A=(0010)A = \left( \begin{array}{rr} 0 & 0 \\ 1 & 0 \end{array} \right)에 대하여 A≠0A \neq 0 이지만 A2=0A^{2} = 0이다.
◦
행렬 곱에서 곱셈의 소거법칙은 성립하지 않는다.
•
정리 2.13)
◦
m×nm \times n 행렬 AA와 n×pn \times p 행렬 BB를 생각하자. j=1,2,...,pj = 1, 2, ... , p 인 jj에 대하여 ABAB의 jj 열을 uju_{j}, BB의 jj열을 각각 vjv_{j}라 표기하면 다음이 성립한다.
1.
uj=Avju_{j} = Av_{j}
2.
vj=Bejv_{j} = Be_{j} (이때 eje_{j}는 FpF^{p}의 jj번째 표준 벡터)
◦
증명)
1.
uju_{j}를 전개하면 다음과 같다.
•
uj=((AB)1j(AB)2j...(AB)mj)=(∑k=1nA1kBkj∑k=1nA2kBkj...∑k=1nAmkBkj)=A(B1jB2j...Bnj)=Avju_{j} = \left( \begin{array}{rrrr} (AB)_{1j} \\ (AB)_{2j} \\ ... \\ (AB)_{mj} \end{array} \right) = \left( \begin{array}{rrrr} \sum_{k=1}^{n} A_{1k} B_{kj} \\ \sum_{k=1}^{n} A_{2k} B_{kj} \\ ... \\ \sum_{k=1}^{n} A_{mk} B_{kj} \end{array} \right) = A \left( \begin{array}{rrrr} B_{1j} \\ B_{2j} \\ ... \\ B_{nj} \end{array} \right) = Av_{j}
•
ABAB의 jj열은 AA의 열벡터의 일차결합이다. 이때 계수는 행렬 BB의 jj열에 의해 주어진다.
◦
행에 대해서도 이와 비슷한 결과가 성립한다. ABAB의 ii행은 BB의 행벡터의 일차결합이다. 이때 계수는 AA의 ii행에 의해 주어진다.
•
다음 결과는 선형변환에 어떤 벡터를 입력하여 값을 구할 때, 먼저 선형변환에 벡터를 대입하고 행렬로 표현할지, 선형변환과 벡터를 각각 행렬로 표현하고 곱할지 고민할 필요가 없음을 보여준다. 둘 다 유효하기 때문이다.
•
정리 2.14)
◦
V,WV, W는 유한차원 벡터공간이고, 순서기저는 각각 β,γ\beta, \gamma이다. 선형변환 T:V→WT : V \to W와 u∈Vu \in V에 대하여 다음이 성립한다.
▪
[T(u)]γ=[T]βγ[u]β[T(u)]_{\gamma} = [T]_{\beta}^{\gamma}[u]_{\beta}
◦
증명)
▪
u∈Vu \in V를 고정하고 다음과 같이 선형변환 f:F→V,g:F→Wf : F \to V, g : F \to W를 정의하자.
•
모든 a∈Fa \in F에 대하여 f(a)=au,g(a)=aT(u)f(a) = au, g(a) = aT(u)
▪
α={1}\alpha = \{ 1 \}를 FF의 표준 순서기저라 하자. g=Tfg = Tf임은 당연하다. 행렬의 각 열을 벡터로 보고 정리 2.11을 적용하면 다음이 성립한다.
•
[T(u)]γ=[g(1)]γ=[g]αγ=[Tf]αγ=[T]βγ[f]αβ=[T]βγ[f(1)]β=[T]βγ[u]β[T(u)]_{\gamma} = [g(1)]_{\gamma} = [g]_{\alpha}^{\gamma} = [Tf]_{\alpha}^{\gamma} = [T]_{\beta}^{\gamma} [f]_{\alpha}^{\beta} = [T]_{\beta}^{\gamma}[f(1)]_{\beta} = [T]_{\beta}^{\gamma}[u]_{\beta}
•
예제 3)
◦
선형변환 T:P3(R)→P2(R)T : P_{3}(R) \to P_{2}(R)를 T(f(x))=f′(x)T(f(x)) = f'(x)라 정의하자. P3(R)P_{3}(R)의 표준 순서기저는 β\beta, P2(R)P_{2}(R)의 표준순서기저는 γ\gamma이다. A=[T]βγA = [T]_{\beta}^{\gamma}라 하면 2.2절 예제 4로부터 행렬 AA는 다음과 같다.
▪
A=(010000200003)A = \left( \begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{array} \right)
◦
p(x)=2−4x+x2+3x3∈P3(R)p(x) = 2 - 4x + x^{2} + 3x^{3} \in P_{3}(R)라 하자. 정리 2.14에 의하면 [T(p(x))]γ=[T]βγ[p(x)]β[T(p(x))]_{\gamma} = [T]_{\beta}^{\gamma} [p(x)]_{\beta} 가 성립해야 한다. q(x)=T(p(x))=p′(x)=−4+2x+9x2q(x) = T(p(x)) = p'(x) = -4 + 2x + 9x^{2}이므로 다음이 성립한다.
▪
[T(p(x))]γ=[q(x)]γ=(−429)[T(p(x))]_{\gamma} = [q(x)]_{\gamma} = \left( \begin{array}{rrr} -4 \\ 2 \\ 9 \end{array} \right)
◦
한편으로 다음 식도 성립한다.
▪
[T]βγ[p(x)]β=(010000200003)(2−413)=(429)[T]_{\beta}^{\gamma}[p(x)]_{\beta} = \left( \begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{array} \right) \left( \begin{array}{rrrr} 2 \\ -4 \\ 1 \\ 3 \end{array} \right) = \left( \begin{array}{rrr} 4 \\ 2 \\ 9 \end{array} \right)
◦
(함수의 합성이나 행렬의 곱이 동치라는 내용)
•
AA행렬 AA의 좌측 곱 변환 AA를 소개하며 이번 절을 마치겠다.
◦
좌측 곱 변환은 선형변환의 성질을 바탕으로 행렬의 성질을 유추하거나 행렬의 성질을 바탕으로 선형변환의 성질을 유추할 때 가장 유용하게 사용할 수 있는 도구다.
◦
좌측 곱 변환을 이용하면 행렬 곱에서 결합법칙이 성립함을 증명할 수 있다.
•
정의)
◦
AA는 m×nm \times n 행렬이고, 성분은 체 FF의 원소이다. 다음 선형변환을 간단히 LAL_{A}라 표기하자.
▪
LA:Fn→FmL_{A} : F^{n} \to F^{m}
▪
LA(x)=AxL_{A}(x) = Ax
◦
LAL_{A}는 좌측 곱 변환(left multiplication transformation)이라 한다. 이때 xx는 FnF^{n}의 열벡터이고 AxAx는 AA와 xx의 행렬 곱이다.
•
예제 4)
◦
행렬 A=(121012)A = \left( \begin{array}{rrr} 1 & 2 & 1 \\ 0 & 1 & 2 \end{array} \right)와 선형변환 LA:R3→R2L_{A} : R^{3} \to R^{2} 을 생각하자. x=(13−1)x = \left( \begin{array}{rrr} 1 \\ 3 \\ -1 \end{array} \right) 에 대하여 LA(x)=Ax=(121012)(13−1)=(61)L_{A}(x) = Ax = \left( \begin{array}{rrr} 1 & 2 & 1 \\ 0 & 1 & 2 \end{array} \right) \left( \begin{array}{rrr} 1 \\ 3 \\ -1 \end{array} \right) = \left( \begin{array}{rr} 6 \\ 1 \end{array} \right) 이다.
•
다음 정리를 통해 LAL_{A} 가 선형이라는 사실 뿐 아니라 유용한 성질을 많이 가지고 있음을 확인할 수 있다. 이 성질은 모두 자연스럽고 기억하기 쉽다.
•
정리 2.15)
◦
AA는 m×nm \times n 행렬이고, 성분은 체 FF의 원소라 하자. 좌측 곱 변환 LA:Fn→FmL_{A} : F^{n} \to F^{m}은 선형이다. 또한 임의의 m×nm \times n 행렬 BB (성분은 체 FF의 원소)와 FnF^{n}의 표준 순서기저 β\beta, FmF^{m} 의 표준순서기저 γ\gamma에 대하여 다음이 성립한다.
1.
[LA]βγ=A[L_{A}]_{\beta}^{\gamma} = A
2.
LA=LB⇔A=BL_{A} = L_{B} \Leftrightarrow A = B
3.
LA+B=LA+LBL_{A+B} = L_{A} + L_{B}이고 모든 a∈Fa \in F 에 대하여 LaA=aLAL_{aA} = aL_{A}이다.
4.
T:Fn→FmT : F^{n} \to F^{m}이 선형이면 T=LCT = L_{C}가 되도록 하는 m×nm \times n 행렬 CC 가 유일하게 존재한다. 실제로는 C=[T]βγC = [T]_{\beta}^{\gamma}이다.
5.
EE가 n×pn \times p 행렬이면 LAE=LALEL_{AE} = L_{A} L_{E} 이다.
6.
m=nm = n 이면 LIn=LFnL_{I_{n}} = L_{F^{n}} 이다.
◦
증명)
1.
[LA]βγ[L_{A}]_{\beta}^{\gamma}의 jj 열은 LA(ej)L_{A}(e_{j})와 같다. 한편, LA(ej)=AejL_{A}(e_{j}) = Ae_{j} 는 정리 2.13(2)로부터 AA의 jj열임을 알 수 있다. 즉 [LA]βγ=A[L_{A}]_{\beta}^{\gamma} = A이다.
2.
LA=LBL_{A} = L_{B}이면 (1)에 의해 A=[LA]βγ=[LB]βγ=BA = [L_{A}]_{\beta}^{\gamma} = [L_{B}]_{\beta}^{\gamma} = B, 즉 A=BA = B이다. 그 역은 자명하다.
3.
연습문제
4.
C=[T]βγC = [T]_{\beta}^{\gamma} 라 하자. 정리 2.14로부터 [T(x)]γ=[T]βγ[x]β[T(x)]_{\gamma} = [T]_{\beta}^{\gamma} [x]_{\beta} 이다. 모든 x∈Fnx \in F^{n} 에 대하여 T(x)=Cx=LC(x),T=LCT(x) = Cx = L_{C}(x), T = L_{C}이다. CC의 유일성은 (2)에서 나온다.
5.
임의의 j(1≤j≤p)j (1 \leq j \leq p)에 대하여 정리 2.13을 몇 차례 적용하자. (AE)ej(AE)e_{j}는 AEAE의 jj 열이고, AEAE의 jj열은 A(Eej)A(Ee_{j})와 같다. 즉 (AE)ej=A(Eej)(AE)e_{j} = A(Ee_{j})이다. 따라서 다음이 성립한다.
•
LAE(ej)=(AE)ej=A(Eej)=LA(Eej)=LA(LE(ej))L_{AE}(e_{j}) = (AE)e_{j} = A(Ee_{j}) = L_{A}(Ee_{j}) = L_{A}(L_{E}(e_{j}))
•
정리 2.6의 따름정리로부터 LAE=LALEL_{AE} = L_{A}L_{E}이다.
6.
연습문제
•
좌측 곱 변환을 이용하여 행렬 곱에서 결합법칙이 성립함을 보이자.
•
정리 2.16)
◦
A(BC)A(BC)를 정의할 수 있는 행렬 A,B,CA, B, C는 (AB)C(AB)C도 정의할 수 있고 A(BC)=(AB)CA(BC) = (AB)C이다. 즉, 행렬 곱에서 결합법칙이 성립한다.
◦
증명)
▪
(AB)C(AB)C 를 정의하는 것을 보이는 것은 여러분의 몫으로 남긴다. 정리 2.15(5)와 함수의 합성에서 결합법칙이 성립함을 이용하면 (부록 B) 다음 관계식을 얻을 수 있다.
•
LA(BC)=LALBC=LA(LBLC)=(LALB)LC=LABLC=L(AB)CL_{A(BC)} = L_{A}L_{BC} = L_{A}(L_{B}L_{C}) = (L_{A}L_{B})L_{C} = L_{AB}L_{C} = L_{(AB)C}
▪
정리 2.15(2)에 의해 A(BC)=(AB)CA(BC) = (AB)C 이다.
◦
이 증명은 행렬 곱의 정의로부터 바로 증명할 수 있지만 위와 같은 방식으로 증명하면 선형변환과 행렬 사이의 관계를 이용하여 여러 명제를 증명하는 훈련을 할 수 있다.
◦
(동치 관계이면 풀기 쉬운 쪽을 증명해서 풀기 어려운 쪽을 증명한다)

응용

•
인구 성장을 연구할 때 행렬 곱이 어떻게 사용되는지 확인하고 싶으면 https://goo.gl/x5XDLw를 방문해 보자
•
결합행렬을 이용한 연구는 매우 광범위하게 진행되고 있다. 결합행렬(incidence matrix)은 모든 성분이 00 또는 11이고, (편의를 위해) 대각성분은 모두 00인 정사각행렬이다. nn개의 대상 (1,2,...,n1, 2, ... , n라 표기)으로 구성된 집합에 어떤 관계가 주어질 때, 대응하는 결합행렬 AA는 다음과 같이 정의한다.
◦
ii와 jj 사이에 관계가 있으면 Aij=1A_{ij} = 1, 그렇지 않으면 Aij=0A_{ij} = 0
•
다음 예를 생각해 보자.
◦
네 사람이 통신 장비를 갖고 있다. 신호를 보낼 수 있는지 여부로 이들의 관계를 정의하자. 인물 ii가 인물 jj에게 신호를 보낼 수 있으면 Aij=1A_{ij} = 1이고 그렇지 못하면 Aij=0A_{ij} = 0이다. 결합행렬이 다음과 같이 주어졌다고 하자.
▪
A= (0100100101011100)A = \left( \begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right)
◦
A34=1A_{34} = 1 이고 A14=0A_{14} = 0 이므로 인물 33은 인물 44에게 신호를 보낼 수 있지만 인물 11은 인물 44에게 신호를 보낼 수 없다.
◦
A2A^{2}의 성분에는 어떤 의미가 있는가? 예컨대 다음과 같은 관계식이 있다고 하자.
▪
(A2)31=A31A11+A32A21+A33A31+A34A41(A^{2})_{31} = A_{31}A_{11} + A_{32}A_{21} + A_{33}A_{31} + A_{34}A{41}
◦
다음과 같은 해석이 가능하다.
▪
A3kAk1=1A_{3k}A_{k1} = 1
▪
⇔A3k=1\Leftrightarrow A_{3k} = 1 이고 Ak1=1A_{k1} = 1
▪
⇔\Leftrightarrow 인물 33이 인물 kk에게 신호를 보낼 수 있고, 인물 kk가 인물 11에게 신호를 보낼 수 있다.
◦
즉 (A2)31(A^{2})_{31}은 두 단계에 걸쳐 인물 33에서 인물 11까지 가는 신호의 경우의 수를 의미한다. (이 경우에는 3→2→13 \to 2 \to 1과 3→4→13 \to 4 \to 1이 가능) 이때 A2A^{2}은 다음과 같다.
▪
A2=(1001120021011101)A^{2} = \left( \begin{array}{rrrr} 1 & 0 & 0 & 1 \\ 1 & 2 & 0 & 0 \\ 2 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{array} \right)
◦
따라서 두 단계에 걸쳐 인물 33에서 인물 11까지 가는 신호의 경우의 수는 모두 두 가지임을 알 수 있다.
▪
일반적으로 (A+A2+...+Am)ij(A+A^{2}+ ... + A^{m})_{ij}는 최대 mm 단계에 걸쳐 인물 ii에서 인물 jj까지 갈 수 있는 신호의 경우의 수를 의미한다.
◦
한편 여러 명으로 이루어진 집합의 부분집합으로, 모든 인물이 서로 신호를 주고 받는 관계를 가진 3명 이상의 극대 부분집합을 클리크(clique)라 한다. 클리크를 찾는 문제는 어렵다. 그러나 어떤 인물이 클리크에 속하는지는 비교적 쉽게 판별할 수 있다.
◦
행렬 BB를 다음과 같이 정의하자.
▪
인물 ii와 인물 jj가 서로 신호를 주고받을 수 있으면 Bij=1B_{ij} = 1 그렇지 않으면 Bij=0B_{ij} = 0
◦
인물 ii가 클리크에 속하기 위한 필요충분조건은 (B3)ii>0(B^{3})_{ii} > 0임을 보일 수 있다. 예컨대 어떤 관계에 대한 결합행렬 AA가 다음과 같이 주어졌다고 하자.
▪
A= (0101101011011110)A = \left( \begin{array}{rrrr} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \right)
◦
누가 클리크에 속하는지 결정하려면 행렬 BB와 B3B^{3}를 계산하면 된다.
▪
B= (0101101001011010),B3=(0404404004044040)B = \left( \begin{array}{rrrr} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right), B^{3} = \left( \begin{array}{rrrr} 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \\ 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \end{array} \right)
◦
B3B^{3}의 모든 대각성분이 00이므로 이 관계에서 클리크가 존재하지 않는다.
◦
결합행렬을 이용하는 마지막 예는 '지배'와 관련있다. 여러 사람으로 구성된 집단에 주어진 관계의 결합행렬을 AA라 하자. AA가 i≠ji \neq j인 임의의 순서쌍 (i,j)(i, j)에 대하여 다음을 만족하면 지배관계(dominance relation)라 한다.
▪
Aij=1⇔Aji=0A_{ij} = 1 \Leftrightarrow A_{ji} = 0
◦
즉 임의의 두 사람을 뽑으면 반드시 한 쪽이 다른 쪽을 지배하는 관계가 있다. (또는 임의의 두 사람 중 한 사람은 항상 다른 사람에게 신호를 보낼 수 있으나 반대로는 신호를 보낼 수 없다는 뜻이다)
◦
AA가 결합행렬이므로 모든 ii에 대하여 Aii=0A_{ii} = 0이다. 이 경우 행렬 A+A2A + A^{2}의 대각성분을 제외한 모든 성분이 양수인 행 또는 열을 가짐을 보일 수 있다.
◦
따라서 Aij=1A_{ij} = 1일 때 ii가 jj를 지배한다고 하면 22단계 안에 모든 사람을 지배하거나 모든 사람에게 지배를 받는 인물이 적어도 한 명 존재한다. 그 인물은 첫 번째 단계에서 가장 많은 사람을 지배하거나 가장 많은 사람에게 지배를 받는 사람이다.
◦
그 예로 다음 행렬을 생각해보자. 이 행렬이 지배관계에 대응함은 각자 확인해 보라.
▪
A=(0101000100100100100111100),A+A2=(0211110110120211220122220)A = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right), A + A^{2} = \left( \begin{array}{rrrrr} 0 & 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 2 & 0 & 2 & 1 \\ 1 & 2 & 2 & 0 & 1 \\ 2 & 2 & 2 & 2 & 0 \end{array} \right)
◦
위 계산에 따르면 인물 1,3,4,51, 3, 4, 5는 최대 22단계 안에 다른 모든 사람을 모두 지배할 수 있고(신호를 보냄), 인물 1,2,3,41, 2, 3, 4는 최대 22단계 안에 모든 사람에게 지배를 받는다(신호를 받음)
Made with