결합 도식

testwiki
둘러보기로 이동 검색으로 이동

틀:위키데이터 속성 추적 조합론에서 결합 도식(結合圖式, 틀:Llang) 또는 일관 구조(一貫構造, 틀:Llang)는 어떤 특별한 조건을 만족시키는 일련의 이항 관계들이 주어진 유한 집합이며, 변 색칠이 주어진 완전 그래프로도 간주될 수 있다.[1][2][3][4] 주어진 결합 도식으로부터 그 구조를 나타내는 결합 대수보스-메스너 대수(बसु-Mesner代數, 틀:Llang)가 존재한다.

정의

결합 도식의 개념은 여러 가지로 정의될 수 있으나, 이 정의들은 모두 서로 동치이다.

조합론적 정의

결합 도식 (X,)은 다음과 같은 데이터로 주어진다.[3]틀:Rp[1]틀:Rp

이는 다음 조건들을 만족시켜야 한다.

  • X×X분할을 이룬다. 즉, R,R이며 RR이라면 RR=이며, 또한 =X×X이다.
  • {(x,x):xX}=부분 집합 가 존재한다.
  • ∉
  • ㉣ 임의의 R에 대하여, Rop
  • ㉤ 임의의 R,R,R(x,y)R에 대하여, |{zX:xRyRz}|(x,y)에 의존하지 않는다.

여기서

  • R에 대하여, xRy(x,y)R를 뜻한다.
  • Rop={(y,x):(x,y)R}R의 반대 이항 관계이다.

흔히, 의 원소는 (R0,R1,,Rn)으로 표기되며, 이 경우 R0={(x,x):xX}이다. 또한,

pijk=|{zX:xiyjz}|(xky)

는 결합 도식의 구조 상수(構造常數, 틀:Llang)라고 한다.

행렬을 통한 정의

결합 도식 (X,n,𝒜)은 다음과 같은 데이터로 주어진다.[1]틀:Rp

이는 다음 조건들을 만족시켜야 한다.

  • i=0nAi는 모든 성분이 1인 k×k 정사각 행렬이다.
  • 1k×k=𝒜𝒜𝒜가 존재한다.
  • 0k×k∉𝒜.
  • ㉣ 임의의 A𝒜에 대하여, A𝒜
  • ㉤ 임의의 Ai,Aj𝒜에 대하여, 그 곱 AiAj𝒜의 원소들의 자연수 계수 선형 결합이다. 즉, 각 0i,j,kk에 대하여, AiAj=k=0npijkAk인 자연수 pijk가 존재한다.

이 두 정의는 서로 동치이다. 즉, 두 정의 사이를 번역하려면, 각 이항 관계 i를 대신 정사각 행렬

(Ai)x,y=xiy(x,yX)

로 치환하면 된다.

기하학적 정의

결합 도식의 개념은 거리 공간과 유사하게 정의될 수도 있다.[3]틀:Rp

결합 도식 (X,D,)은 다음과 같은 데이터로 주어진다.

이는 다음 조건들을 만족시켜야 한다.

  • ㉡ 임의의 x,y,zX에 대하여, 만약 (x,x)=(y,z)라면, y=z이다.
  • 전사 함수이다.
  • ㉣ 임의의 x,y,x,yX에 대하여, (x,y)=(x,y)라면 (y,x)=(y,x)
  • ㉤ 임의의 x,y,x,yX에 대하여, 만약 (x,y)=(x,y)라면, zX:(x,z)=(x,f(z))이자 zX:(z,y)=(f(z),y)가 되는 전단사 함수 f:XX가 존재한다.

이 정의 역시 나머지 두 정의와 서로 동치이다. 즉, 각 αD에 대하여 이항 관계

xαy(x,y)=α

를 대응시키면 된다.

부분 결합 도식

같은 집합 X 위의 두 결합 도식 (X,)(X,)에 대하여, 만약 이라면, (X,)(X,)부분 결합 도식(部分結合圖式, 틀:Llang)이라고 한다.

결합 도식 준동형

다음이 주어졌다고 하자.

그렇다면, 결합 도식 사상(틀:Llang) (f,g):(X,)(X,)은 다음과 같은 데이터로 구성된다.[2]틀:Rp

  • 함수 f:XX
  • 함수 g:

이는 다음 조건을 만족시켜야 한다.

임의의 x,yXR에 대하여, 만약 xRy라면, f(x)g(R)f(y)이다.

이는 사실 이항 관계가 주어진 구조 사이의 준동형의 특수한 경우이다.

종류

결합 도식 X에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 결합 도식을 대칭 결합 도식(對稱結合圖式, 틀:Llang)이라고 한다.[3]틀:Rp

  • 조합론적 정의 (X,)에서, 의 모든 원소는 대칭 관계이다. 즉, 만약 R라면, R=Rop이다.
  • 행렬을 통한 정의 (X,𝒜)에서, 모든 A𝒜대칭 행렬이다.
  • 기하학적 정의 (X,)에서, 임의의 x,yX에 대하여 (x,y)=(y,x)이다.

결합 도식 (X,)에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 결합 도식을 가환 결합 도식(可換結合圖式,틀:Llang)이라고 한다.

  • 그 보스-메스너 대수가 가환환이다.
  • 조합론적 정의에서, 임의의 R,R,R(x,y)R에 대하여, |{zX:xRzRy}|=|{zX:xRzRy}|
  • 행렬을 통한 정의 (X,𝒜)에서, 임의의 A,B𝒜에 대하여 AB=BA이다.
  • 기하학적 정의 (X,)에서, 임의의 x,yX에 대하여, zX:((x,z),(z,y))=((y,f(z)),(f(z),x))가 되는 자기 전단사 함수 f:XX가 존재한다.

결합 도식 (X,)이 다음 조건을 만족시킨다면, 균등 결합 도식(均等結合圖式, 틀:Llang)이라고 한다.

  • 조합론적 정의 (X,)에서, {(x,x):xX}이다.
  • 행렬을 통한 정의 (X,𝒜)에서, 1|X|×|X|𝒜이다.
  • 기하학적 정의 (X,)에서, x,yX:(x,x)=(y,y)이다.

다음과 같은 포함 관계가 성립한다.

대칭 결합 도식 ⊊ 가환 결합 도식 ⊊ 균등 결합 도식 ⊊ 결합 도식

연산

결합 도식 (X,)이 주어졌을 때, X 위에 다음과 같은 동치 관계를 정의할 수 있다.

xy(x,x)=(y,y)

이 동치 관계에 대한 동치류를 X(틀:Llang)이라고 하자. 올들로 구성된 집합의 분할(Xα)αI로 표기할 때, 다음이 성립한다.

Rα,βI:RXα×Xβ

증명:

임의의 x,y,yX가 주어졌으며, 귀류법을 사용하여

(x,y)=(x,y)
(y,y)(y,y)

이라고 가정하자. 그렇다면,

{zX:(x,z)=(x,y),(z,y)=(y,y)}={y}
{zX:(x,z)=(x,y),(z,y)=(y,y)}=

이므로, 이는 결합 도식의 정의와 모순된다.

이에 따라, 결합 도식 (X,)의 임의의 올 Xi이 주어졌을 때,

(Xi,Xi2)

는 균등 결합 도식을 이룬다.

직접곱

유한 개의 결합 도식

(Xi,i)iI
|I|<0

이 주어졌다고 하자. 그렇다면, 곱집합

X=iIXi

위에 이항 관계

=iIi
(xi)iI(Ri)iI(yi)iIiI:xiRiyi

를 줄 수 있다. 그렇다면, (X,)는 결합 도식을 이루며, 이를 (Xi,i)iI직접곱(直接곱, 틀:Llang)이라고 한다.[2]틀:Rp

이는 직접곱의 개념의 일반화이다.

성질

구조 상수

임의의 결합 도식 X의 구조 상수들 (pijk)1i,j,kn은 다음을 만족시킨다.

i,j,k=0npijk|Rk|=|X|3

만약

Riop=Rı¯
Rjop=Rȷ¯
Rkop=Rk¯

일 때, 다음이 성립한다.

pjki=pk¯ȷ¯ı¯

균등 결합 도식 (X,)의 구조 상수들 (pijk)1i,j,kn은 다음을 만족시킨다.[1]틀:Rp

p0ij=pi0j=δij
pij0=pȷ¯ı¯0=δjı¯piı¯0
i,j=0npij0=i=0npiı¯0=|X|

(여기서 δij크로네커 델타이다.)

대칭 결합 도식에 대응되는 변 색칠

대칭 결합 도식 (X,)이 주어졌다고 하자. 그렇다면, X의 원소를 꼭짓점들로 하는 완전 그래프 KX 위에, {R0}의 원소를 색으로 하는 변 색칠 c:E(KX){R0}을 정의할 수 있다.

c:(x,y)R(x,y)R(R,RR0)

이에 따라, 대칭 결합 도식은 특별한 변 색칠이 주어진 유한 완전 그래프로 여겨질 수 있다.[1]틀:Rp

보스-메스너 대수

(행렬을 통한 정의의) 결합 도식 (X,𝒜)이 주어졌을 때, 𝒜선형 생성

Span𝒜Mat(|X|,|X|;)

은 정수 계수 결합 대수를 이룬다. 이를 X에 대응하는 보스-메스너 대수라고 한다 (흔히, 정수 계수 대신 실수나 복소수 계수가 사용된다).[3]틀:Rp

에르미트 수반에 대하여 닫혀 있는 복소수 행렬 결합 대수이므로, 복소수 계수 보스-메스너 대수는 항상 반단순 대수이다.

아르틴-웨더번 정리에 따라서, 복소수 계수 보스-메스너 계수는 다음과 같은 꼴로 유일하게 표현된다.

a=1kMat(ma,ma;)

이에 따라, 위 분해에 등장하는 멱등원

Ea=(0,0,,0,1ma×ma,0,,0)

들을 정의할 수 있으며, 이들은

EaEb=δabEa(a,b{0,,k})

를 만족시킨다 (δab크로네커 델타). 또한, 편의상

E0=1|X|𝖩|X|×|X|.

로 놓는다. 여기서 𝖩|X|×|X|는 모든 성분이 1인 |X|×|X| 정사각 행렬(즉, 아다마르 곱의 항등원)이다. 이는 결합 도식의 공리에 따라 보스-메스너 대수의 원소이며, 0이 아닌 고윳값이 1개 밖에 없는 멱영원이므로 위 분해에 항상 등장한다.

특히, EaDi로 전개하였을 때의 계수

|X|Ea=i=0nQaiDj

를 정의할 수 있다.

가환 결합 도식의 쌍대성

가환 결합 도식 X의 경우, 최소 멱등원의 수는 |X|=n와 같으며, 멱영원(Ea)0an은 보스-메스너 대수 𝒜기저를 이룬다. 이에 따라, 다음을 정의할 수 있다.

Di=a=0nPi,aEa

또한, Di들은 모두 아다마르 곱에 대하여 닫혀 있으므로, Ea들의 아다마르 곱에 대한 구조 상수

EaEb=qabcEc

를 정의할 수 있다. (아다마르 곱은 교환 법칙을 따르므로 qabc=qbac이다.)

이에 따라, 다음과 같은 쌍대성이 존재한다.

이항 연산 아다마르 곱 행렬의 곱
기저 Di Ea
기저의 직교성 DiDj=δijDi EaEb=δabEa
멱등원 조건 Di의 모든 성분은 0 또는 1 (아다마르 곱멱등원) Ea의 모든 고윳값은 0 또는 1 (행렬곱의 멱등원)
항등원 D0=1n×n E0=𝖩n×n/|X|
기저 원소의 쌍대성 Dı¯=Di Ea¯=Ea=E¯a (각 성분의 복소켤레)
기저의 합 iDi=𝖩|X|×|X| aEa=1|X|×|X|
차수 vi={yX:xiy}(xX) ma=dimimEa
차수의 합 ivi=|X| ama=|X|
구조 상수 DiDj=pijkDk |X|EaEb=qabcEc
기저 변환 Di=a=0nPiaEa Ea=i=0nQaiDi

이 표에서, 배경색이 노란 칸은 가환 결합 도식일 경우에만 정의되는 것이다.

이에 따라, 만약 두 결합 도식 X, Y의 복소수 계수 보스-메스너 대수 𝒜X, 𝒜Y가 각각

(𝒜X,,,(Di)i)(𝒜Y,,,(Ea)a)

라면, 서로 쌍대(틀:Llang)라고 한다. 즉, 반선형 변환(틀:Llang)

f:𝒜X𝒜Y
f(λM)=λ¯f(M)(λ,M𝒜X)
f(MN)=f(M)f(N)
f(MN)=f(M)f(N)

를 만족시킬 경우, 이들이 서로 쌍대라고 한다.

아다마르 곱은 항상 교환 법칙을 따르므로, 쌍대성은 오직 두 가환 결합 도식 사이에만 존재할 수 있다.[5]

특히, 해밍 결합 도식은 스스로의 쌍대이다.[3]틀:Rp

다음은 n=3인 대칭 결합 도식의 한 예이다. 여기서 X={𝖠,𝖡,𝖢,𝖣,𝖤,𝖥}이다.

A B C D E F
A 0 1 1 2 3 3
B 1 0 1 3 2 3
C 1 1 0 3 3 2
D 2 3 3 0 1 1
E 3 2 3 1 0 1
F 3 3 2 1 1 0

그 구조 상수는 다음과 같다.

1=p000=p011=p022=p033=p111=p231=p331=p222=p123=p133
2=p110=p330=p132

여기서 pijk가 수록되었다면 pjik는 생략하였으며, 수록되지 않은 구조 상수는 모두 0이다.

자명한 결합 도식

크기가 2 이상인 임의의 유한 집합 X 위에

R0={(x,x):xX}
R1=X×XR0
={R0,R1}

을 정의하면, (X,2,)는 결합 도식을 이루며, 이를 자명한 결합 도식(自明-結合圖式, 틀:Llang)이라고 한다.[6]틀:Rp 그 구조 상수는 다음과 같다.

p000=p011=p101=1
p001=p010=p100=0
p110=|X|1
p111=|X|2

이는 사실 n=1해밍 결합 도식과 같다.

이산 결합 도식

임의의 유한 집합 X 위에,

={{(x,y)}:x,yX}

를 정의하면, (X,) 역시 결합 도식을 이룬다. 이를 이산 결합 도식(離散結合圖式, 틀:Llang)이라고 한다.[6]틀:Rp 그러나 |X|2일 경우 이는 균등 결합 도식이 아니다.

작은 결합 도식

크기 1의 결합 도식은 유일하며, 이는 대칭 결합 도식이다.

A
A 0

크기 2의 결합 도식은 다음 두 가지가 있다.

(가)
A B
A 0 1
B 1 0
(나)
A B
A 0 2
B 3 1

(가)는 자명한 결합 도식이며, (나)는 이산 결합 도식이다. (가)는 대칭 결합 도식이지만, (나)는 균등 결합 도식이 아니다.

주어진 집합 X 위의, 특별한 조건을 만족시키는 결합 도식의 수는 다음과 같다.[6]틀:Rp

|X| 균등 결합 도식의 수
틀:OEIS
대칭 결합 도식의 수
1 1 1
2 1 1
3 2 1
4 4 3
5 3 2
6 8 4
7 4 2
8 21 10
9 12 6
10 13 8
11 4 2
12 59 21

해밍 결합 도식과 존슨 결합 도식

틀:본문 틀:본문 임의의 곱집합 X=Fn 위에, 두 벡터 사이의 해밍 거리0,1,,n인 것을 각각 이항 관계로 삼으면, 이는 결합 도식을 이룬다. 이를 해밍 결합 도식이라고 한다.

특히, F={0,1}일 때, 주어진 해밍 무게의 벡터들만을 취한 부분 결합 도식을 존슨 결합 도식이라고 한다.

정추이적 작용

유한군 G의, 유한 집합 X 위의 왼쪽 정추이적 작용이 주어졌다고 하자. (특히, |G|=|X|이다.) 그렇다면,

n=|G|
={{(x,gx):xX}:gG}

를 정의하면, (X,n,)는 결합 도식을 이루며, 그 구조 상수는

pghk={1gh=k0ghk(g,h,kG)

이다.

이에 대응하는 보스-메스너 대수는 군환

[G]

과 동형이다.

또한, G에 대응하는 결합 도식이 가환 결합 도식일 필요 충분 조건G아벨 군인 것이다.

일반적 군 작용

유한군 G의, 유한 집합 X 위의 왼쪽 작용이 주어졌다고 하자. 그렇다면, GX2=X×X 위에 다음과 같이 작용한다.

g(x,y)=(gx,gy)(x,yX,gG)

그렇다면, G의 작용에 대한 궤도들은 X2분할 X2/G을 정의한다.

이 경우, (X,X2/G)는 결합 도식을 이룬다.[3]틀:Rp 또한, 이 결합 도식이 각종 조건을 만족시킬 필요 충분 조건은 다음과 같다.

결합 도식 군의 작용
X 위의 G-작용의 궤도
균등 결합 도식 GSym(X)추이적 작용
대칭 결합 도식 임의의 x,yX에 대하여, (gx,gy)=(y,x)가 되는 gG가 존재
자명 결합 도식 GSym(X)가 2-추이적 작용
이산 결합 도식 GSym(X)가 자명한 작용 (즉, gx=xgG,xX)

역사

1952년에 라지 찬드라 보스와 시마모토(T. Shimamoto)가 블록 설계의 이론에 대한 응용을 위해 결합 도식의 개념 및 용어를 도입하였다.[7] 보스와 시마모토의 논문에서, “결합 도식”(틀:Llang)이라는 용어는 대칭 결합 대수를 뜻했다.

1959년에 라지 찬드라 보스와 데일 마시 메스너(틀:Llang)는 보스-메스너 대수를 도입하였다.[8]

이후 도널드 고든 히그먼(틀:Llang, 1928~2006)이 1970년에 군론에서의 응용을 위하여 본 문서의 결합 도식과 동치인 개념을 도입하였으며, 히그먼은 이 개념을 “일관 구조”(틀:Llang)라고 불렀다.[9]틀:Rp

같이 보기

각주

틀:각주

외부 링크

틀:전거 통제