Search
Duplicate

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

선형변환의 합성과 행렬 곱

앞서 행렬의 합과 스칼라 곱을 각각 선형변환의 합과 스칼라 곱에 대응하는 방식으로 두 개념을 연결하였다. 그렇다면 선형변환의 합성에 대응하는 행렬의 연산은 무엇일까? 바로 행렬 곱이다.
두 선형변환 U,TU, T의 합성을 나타낼 때 UTU \circ T 대신 간단하게 UTUT로 표현할 것이다.
정리 2.9)
FF-벡터공간 V,W,ZV, W, Z와 선형변환 T:VW,U:WZT : V \to W, U : W \to Z를 생각하자. 두 선형변환의 합성 UT:VZUT : V \to Z는 선형변환이다.
증명)
x,yV,aFx, 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,U2L(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})
선형변환의 정의역과 공역이 같지 않으면 이보다 일반적인 결과가 성립한다.
어떤 상황에서는 TL(V)T \in \mathcal{L}(V)TT를 자연스럽게 여러 번 합성하기도 한다. 예컨대 T:VV,T(f)=fT : V \to V, T(f) = f'를 생각해보자. (이때 VV는 무한 번 미분가능한 실함수의 집합)
TT(f)=T(f)=(f)=fTT(f) = T(f') = (f')' = f'': f의 이계도함수
TTT(f)=fTTT(f) = f''' : f이 삼계도함수
이런 상황에서 다음 표기법을 유용하게 사용할 수 있다.
TL(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=Tk1TT^{k} = T^{k-1}T이다.
편의를 위해 T0=lVT^{0} = l_{V}라 정의한다.
이제 행렬 곱에 대해 알아보자. 유한차원 벡터공간 V,W,ZV, W, Z와 선형변환 T:VW,U:WZT : 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 행렬 AAn×pn \times p 행렬 BB에 대하여 두 행렬 A,BA, B의 곱(product) ABAB는 다음과 같이 정의된 m×pm \times p 행렬이다.
1im,1jp1 \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가 모두 정의되더라도 ABBAAB \neq BA일 수 있다.
m×nm \times n 행렬 AAn×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:VW,U:WZT : V \to W, U : W \to Z에 대하여 다음이 성립한다.
[UT]αγ=[U]βγ[T]αβ[UT]_{\alpha}^{\gamma} = [U]_{\beta}^{\gamma} [T]_{\alpha}^{\beta}
따름정리)
유한차원 벡터공간 VV와 순서기저 β\beta, 선형연산자 T,UL(V)T, U \in \mathcal{L}(V)에 대하여 다음이 성립한다.
[UT]β=[U]β[T]β[UT]_{\beta} = [U]_{\beta}[T]_{\beta}
예제 2) 적분했다가 미분하면 원래 함수로 돌아온다는 예시 생략
정리 2.12)
AAm×nm \times n 행렬 BBCCn×pn \times p행렬, DDEEq×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 행렬 VVn×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=Ak1AA^{k} = A^{k-1}A 라 정의한다. 이때 A0=InA^{0} = I_{n} 이다.
이 표기법에 따르면 A=(0010)A = \left( \begin{array}{rr} 0 & 0 \\ 1 & 0 \end{array} \right)에 대하여 A0A \neq 0 이지만 A2=0A^{2} = 0이다.
행렬 곱에서 곱셈의 소거법칙은 성립하지 않는다.
정리 2.13)
m×nm \times n 행렬 AAn×pn \times p 행렬 BB를 생각하자. j=1,2,...,pj = 1, 2, ... , pjj에 대하여 ABABjj 열을 uju_{j}, BBjj열을 각각 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=1nA1kBkjk=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}
ABABjj열은 AA의 열벡터의 일차결합이다. 이때 계수는 행렬 BBjj열에 의해 주어진다.
행에 대해서도 이와 비슷한 결과가 성립한다. ABABii행은 BB의 행벡터의 일차결합이다. 이때 계수는 AAii행에 의해 주어진다.
다음 결과는 선형변환에 어떤 벡터를 입력하여 값을 구할 때, 먼저 선형변환에 벡터를 대입하고 행렬로 표현할지, 선형변환과 벡터를 각각 행렬로 표현하고 곱할지 고민할 필요가 없음을 보여준다. 둘 다 유효하기 때문이다.
정리 2.14)
V,WV, W는 유한차원 벡터공간이고, 순서기저는 각각 β,γ\beta, \gamma이다. 선형변환 T:VWT : V \to WuVu \in V에 대하여 다음이 성립한다.
[T(u)]γ=[T]βγ[u]β[T(u)]_{\gamma} = [T]_{\beta}^{\gamma}[u]_{\beta}
증명)
uVu \in V를 고정하고 다음과 같이 선형변환 f:FV,g:FWf : F \to V, g : F \to W를 정의하자.
모든 aFa \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)=24x+x2+3x3P3(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)(2413)=(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를 소개하며 이번 절을 마치겠다.
좌측 곱 변환은 선형변환의 성질을 바탕으로 행렬의 성질을 유추하거나 행렬의 성질을 바탕으로 선형변환의 성질을 유추할 때 가장 유용하게 사용할 수 있는 도구다.
좌측 곱 변환을 이용하면 행렬 곱에서 결합법칙이 성립함을 증명할 수 있다.
정의)
AAm×nm \times n 행렬이고, 성분은 체 FF의 원소이다. 다음 선형변환을 간단히 LAL_{A}라 표기하자.
LA:FnFmL_{A} : F^{n} \to F^{m}
LA(x)=AxL_{A}(x) = Ax
LAL_{A}는 좌측 곱 변환(left multiplication transformation)이라 한다. 이때 xxFnF^{n}의 열벡터이고 AxAxAAxx의 행렬 곱이다.
예제 4)
행렬 A=(121012)A = \left( \begin{array}{rrr} 1 & 2 & 1 \\ 0 & 1 & 2 \end{array} \right)와 선형변환 LA:R3R2L_{A} : R^{3} \to R^{2} 을 생각하자. x=(131)x = \left( \begin{array}{rrr} 1 \\ 3 \\ -1 \end{array} \right) 에 대하여 LA(x)=Ax=(121012)(131)=(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)
AAm×nm \times n 행렬이고, 성분은 체 FF의 원소라 하자. 좌측 곱 변환 LA:FnFmL_{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=LBA=BL_{A} = L_{B} \Leftrightarrow A = B
3.
LA+B=LA+LBL_{A+B} = L_{A} + L_{B}이고 모든 aFa \in F 에 대하여 LaA=aLAL_{aA} = aL_{A}이다.
4.
T:FnFmT : F^{n} \to F^{m}이 선형이면 T=LCT = L_{C}가 되도록 하는 m×nm \times n 행렬 CC 가 유일하게 존재한다. 실제로는 C=[T]βγC = [T]_{\beta}^{\gamma}이다.
5.
EEn×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)로부터 AAjj열임을 알 수 있다. 즉 [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} 이다. 모든 xFnx \in F^{n} 에 대하여 T(x)=Cx=LC(x),T=LCT(x) = Cx = L_{C}(x), T = L_{C}이다. CC의 유일성은 (2)에서 나온다.
5.
임의의 j(1jp)j (1 \leq j \leq p)에 대하여 정리 2.13을 몇 차례 적용하자. (AE)ej(AE)e_{j}AEAEjj 열이고, AEAEjj열은 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는 다음과 같이 정의한다.
iijj 사이에 관계가 있으면 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까지 가는 신호의 경우의 수를 의미한다. (이 경우에는 3213 \to 2 \to 13413 \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)
누가 클리크에 속하는지 결정하려면 행렬 BBB3B^{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라 하자. AAiji \neq j인 임의의 순서쌍 (i,j)(i, j)에 대하여 다음을 만족하면 지배관계(dominance relation)라 한다.
Aij=1Aji=0A_{ij} = 1 \Leftrightarrow A_{ji} = 0
즉 임의의 두 사람을 뽑으면 반드시 한 쪽이 다른 쪽을 지배하는 관계가 있다. (또는 임의의 두 사람 중 한 사람은 항상 다른 사람에게 신호를 보낼 수 있으나 반대로는 신호를 보낼 수 없다는 뜻이다)
AA가 결합행렬이므로 모든 ii에 대하여 Aii=0A_{ii} = 0이다. 이 경우 행렬 A+A2A + A^{2}의 대각성분을 제외한 모든 성분이 양수인 행 또는 열을 가짐을 보일 수 있다.
따라서 Aij=1A_{ij} = 1일 때 iijj를 지배한다고 하면 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단계 안에 모든 사람에게 지배를 받는다(신호를 받음)