Lit-only σ-games的代數結構

The Algebra Behind Lit-only σ-games

劉侖欣

指導教授 ： 翁志文 ； Chih-Wen Weng

國立交通大學/理學院/應用數學系暨研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00281

摘要

令S={s_1,s_2,...,s_n}是一個有限的集合。如果給定一個函數m:S×S→N∪{∞} 定義為m(s,s)=1；而對不同的s,s'滿足m(s,s')=m(s',s)∈ {2,3}。那麼此集合S可以被聯想成一個圖(也把此圖用S表示)，圖的點集合為集合S，邊集合為{ss'| m(s,s')=3}。一個simply-laced Coxeter group W_S 是一個跟(S,m)有關的群。在此篇論文中證明了當圖S是一個有n個頂點的路徑(path)時，W_S是同構(isomorphic)於一個對稱群S_{n+1}的群。我們考慮一個很自然的同態函數(homomorphsim)σ:W_S→GL(R^n)將W_S 對映到線性群GL(R^n)中，使得σ(W_S)是一個可以作用在R^n空間上的線性群(矩陣所構成的群)。當我們把σ(W_S)  中的矩陣都轉置後，可得到這些轉置矩陣形成的群σ*(W_S)。若將群σ*(W_S)作用在R^n上，可證明群σ*(W_S)會同構(isomorphic)於一個對稱群S_{n+1}。因為群σ*(W_S)中的矩陣都是整係數矩陣，若將這些整係數矩陣的係數同餘(modulo) 2，則可得到一些新的矩陣形成一個新的群。在此篇論文中，我們規定這個新的群只有左乘運算，且將這個群作用在一個二元體(binary field)F_2所形成的n維空間{F_2}^n ，並佈於一個二元體F_2上。我們稱這個新的群作用在{F_2}^n上是一個作用在圖S的lit only σ-game。我們討論當圖S是3個頂點的cycle 時，W_S中的子群G之生成集的樣子且G滿足σ*(G)={I} (mod2)。

關鍵字

西格瑪遊戲 ； lit only σ-game

並列摘要

Let S={s_1,s_2,...,s_n} be a finite set and m be a function with m:S×S→N∪{∞} satisfying m(s,s)=1 and m(s,s')=m(s',s)∈ {2,3} for distinct s,s'∈S. The set S is associated with the graph, also denoted by S, with the vertex set S and the edge set {ss'|m(s,s')=3}. A simply-laced Coxeter group W_S associated with (S,m) is the group
generated by S subject to the relations (s,s')^{m(s,s')} for s,s'∈ S. We consider a homomorphism σ:W_S→GL(R^n), which is referred as canonical representation of W_S, where GL(R^n) is the group of invertible linear transformations of R^n into itself. We consider the canonical representation σ of W_S into R^n and use its dual representation σ* to show that W_S is isomorphic to the symmetric group S_{n+1} if the graph S is an n-vertex path. The matricesσ*(W_S)have integral coefficients. The left multiplication of these matrices modulo 2 on the n-dimensional space {F_2}^n over a binary field is usually called the lit only σ-game on the graph S in literatures. In the special case when S is a 3-vertex cycle, we determine the subgroup G of S W with σ*(G)={I} (mod2) .

並列關鍵字

lit only sigma-game

參考文獻

[1] David S. Dummit and Richard M. Foote, Abstract algebra, Prentice-Hall Inc, (1991)

[2] Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand, Note on the Lamp Lighting Problem, Advances in Applied Mathematics 27(2001), (Pages 357-366)

[3] J. Goldwasser, X. Wang, Y. Wu, Does the lit-only restriction make any dierence for the sigma-game and sigma-plus game?, European Journal of Combinatorics,(2008), doi:10.1016/j.ejc.2008.09.020.

[5] Hau-wen Huang and Chih-wen Weng, The edge-pping group of a graph,

[6] James E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, (1990)