संघ योजना

विचरण के विश्लेषण के लिए प्रयोगों के डिजाइन के सिद्धांत में, संघ योजनाओं का सिद्धांत सांख्यिकी में उत्पन्न हुआ। गणित में, साहचर्य योजनाएँ बीजगणित और संयोजन विज्ञान दोनों से संबंधित हैं। बीजगणितीय साहचर्य में, संघ स्कीम कई विषयों के लिए एक एकीकृत दृष्टिकोण प्रदान करती है, उदाहरण के लिए संयोजन डिजाइन और कोडिंग सिद्धांत|त्रुटि-सुधार कोड का सिद्धांत। बीजगणित में, साहचर्य योजनाएँ समूह (गणित) का सामान्यीकरण करती हैं, और साहचर्य योजनाओं का सिद्धांत समूह प्रतिनिधित्व के समूह चरित्र का सामान्यीकरण करता है।

परिभाषा

एक एन-क्लास संघ स्कीम में एक सेट (गणित) X होता है जिसमें X × X के एक सेट S का विभाजन n + 1 द्विआधारी संबंध, R में होता है₀, आर₁, ..., आर_n जो संतुष्ट करता है:

• $R_{0}=\{(x,x):x\in X\}$; इसे पहचान संबंध कहा जाता है।
• परिभाषित करना $R^{*}:=\{(x,y):(y,x)\in R\}$, यदि S में R है, तो S में R* है।
• अगर $(x,y)\in R_{k}$, की संख्या $z\in X$ ऐसा है कि $(x,z)\in R_{i}$ और $(z,y)\in R_{j}$ एक स्थिरांक है $p_{ij}^{k}$ इस पर निर्भर करते हुए $i$, $j$, $k$ लेकिन की विशेष पसंद पर नहीं $x$ और $y$.

एक संघ योजना क्रमविनिमेय है अगर $p_{ij}^{k}=p_{ji}^{k}$ सभी के लिए $i$, $j$ और $k$. अधिकांश लेखक इस संपत्ति को मानते हैं।

एक सममित संघ योजना वह है जिसमें प्रत्येक $R_{i}$ सममित संबंध है। वह है:

• अगर (एक्स, वाई) ∈ आर_i, तब (y, x) ∈ R_i. (या समकक्ष, आर* = आर।)

प्रत्येक सममित साहचर्य योजना क्रमविनिमेय होती है।

ध्यान दें, हालाँकि, जबकि एक संघ योजना की धारणा एक समूह की धारणा को सामान्य करती है, एक क्रमविनिमेय संघ योजना की धारणा केवल एक क्रमविनिमेय समूह की धारणा को सामान्य बनाती है।

दो बिंदुओं x और y को i th सहयोगी कहा जाता है यदि $(x,y)\in R_{i}$. परिभाषा बताती है कि यदि x और y i th सहयोगी हैं तो y और x भी हैं। अंकों की प्रत्येक जोड़ी ठीक एक के लिए iवें सहयोगी है $i$. प्रत्येक बिंदु का अपना स्वयं का ज़ीरोथ सहयोगी होता है जबकि विशिष्ट बिंदु कभी भी ज़ीरोथ सहयोगी नहीं होते हैं। यदि x और y k th सहयोगी हैं तो अंकों की संख्या $z$ जो दोनों के सहयोगी हैं $x$ और जे-वें के सहयोगी $y$ एक स्थिरांक है $p_{ij}^{k}$.

ग्राफ व्याख्या और आसन्न मैट्रिक्स

एक सममित संघ योजना को लेबल वाले किनारों के साथ एक पूर्ण ग्राफ़ के रूप में देखा जा सकता है। ग्राफ है $v$ शीर्ष, प्रत्येक बिंदु के लिए एक $X$, और किनारों को जोड़ने वाला किनारा $x$ और $y$ अंकित है $i$ अगर $x$ और $y$ हैं $i$वें सहयोगी। प्रत्येक किनारे पर एक अद्वितीय लेबल होता है, और एक निश्चित आधार लेबल वाले त्रिकोणों की संख्या $k$ अन्य किनारों को लेबल करना $i$ और $j$ एक स्थिरांक है $p_{ij}^{k}$, इस पर निर्भर करते हुए $i,j,k$ लेकिन आधार के चुनाव पर नहीं। विशेष रूप से, प्रत्येक शीर्ष ठीक से आपतित होता है $p_{ii}^{0}=v_{i}$ किनारों को लेबल किया गया $i$; $v_{i}$ संबंध (गणित) का आसन्न संबंध है $R_{i}$. लेबल वाले लूप भी हैं $0$ प्रत्येक शीर्ष पर $x$, तदनुसार $R_{0}$.

संबंध (गणित) उनके आसन्न मैट्रिक्स द्वारा वर्णित हैं। $A_{i}$ का आसन्न मैट्रिक्स है $R_{i}$ के लिए $i=0,\ldots ,n$ और एक v × v मैट्रिक्स (गणित) है जिसमें पंक्तियों और स्तंभों को बिंदुओं द्वारा लेबल किया जाता है $X$.

$\left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i},\\0,&{\mbox{otherwise.}}\end{cases}}\qquad (1)$

एक सममित संघ योजना की परिभाषा यह कहने के बराबर है कि $A_{i}$ v × v (0,1)-मैट्रिक्स|(0,1)-मैट्रिसेस हैं जो संतुष्ट करते हैं

मैं। $A_{i}$ सममित है,

द्वितीय। $\sum _{i=0}^{n}A_{i}=J$ (ऑल-वन मैट्रिक्स),

III। $A_{0}=I$,

चतुर्थ। $A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots ,n$.

(X, y) - (IV) के बाईं ओर की प्रविष्टि ग्राफ़ में लेबल i और j के साथ x और y के बीच लंबाई दो के पथों की संख्या है। ध्यान दें कि की पंक्तियाँ और स्तंभ $A_{i}$ रोकना $v_{i}$ $1$'एस:

$A_{i}J=JA_{i}=v_{i}J.\qquad (2)$

शब्दावली

• संख्या $p_{ij}^{k}$ योजना के पैरामीटर कहलाते हैं। उन्हें संरचनात्मक स्थिरांक भी कहा जाता है।

इतिहास

टर्म संघ योजना के कारण है (Bose & Shimamoto 1952) लेकिन अवधारणा पहले से ही अंतर्निहित है (Bose & Nair 1939). ये लेखक अध्ययन कर रहे थे कि सांख्यिकीविदों ने आंशिक रूप से संतुलित अपूर्ण ब्लॉक डिज़ाइन (PBIBDs) को क्या कहा है। विषय प्रकाशन के साथ बीजगणितीय रुचि का एक उद्देश्य बन गया (Bose & Mesner 1959) और बोस-मेस्नर बीजगणित का परिचय। सिद्धांत के लिए सबसे महत्वपूर्ण योगदान पी। डेल्सर्ट की थीसिस थी (Delsarte 1973) जिन्होंने कोडिंग थ्योरी और डिज़ाइन थ्योरी के साथ कनेक्शन को पहचाना और पूरी तरह से इस्तेमाल किया। सामान्यीकरणों का अध्ययन डी.जी. हिगमैन (सुसंगत विन्यास) और बोरिस वेसफीलर|बी द्वारा किया गया है। Weisfeiler (दूरी नियमित रेखांकन)।

बुनियादी तथ्य

• $p_{00}^{0}=1$, यानी, अगर $(x,y)\in R_{0}$ तब $x=y$ और केवल $z$ ऐसा है कि $(x,z)\in R_{0}$ है $z=x$.
• $\sum _{i=0}^{k}p_{ii}^{0}=|X|$; यह इसलिए है क्योंकि $R_{i}$ PARTITION $X$.

बोस-मेस्नर बीजगणित

निकटता मैट्रिक्स $A_{i}$ ग्राफ का (असतत गणित) $\left(X,R_{i}\right)$ क्रमविनिमेय बीजगणित (संरचना) और साहचर्य बीजगणित उत्पन्न करें ${\mathcal {A}}$ (वास्तविक संख्या या जटिल संख्या पर) मैट्रिक्स उत्पाद और हैडमार्ड उत्पाद (मैट्रिसेस) दोनों के लिए। इस साहचर्य, क्रमविनिमेय बीजगणित को संघ योजना का बोस-मेस्नर बीजगणित कहा जाता है।

चूंकि मेट्रिसेस में ${\mathcal {A}}$ सममित मैट्रिक्स हैं और एक दूसरे के साथ आने वाले मैट्रिक्स हैं, वे एक साथ विकर्ण मैट्रिक्स हो सकते हैं। इसलिए, ${\mathcal {A}}$ सेमीसिंपल ऑपरेटर है | सेमी-सिंपल और आदिम idempotents का एक अनूठा आधार है $J_{0},\ldots ,J_{n}$.

का एक और बीजगणित है $(n+1)\times (n+1)$ मैट्रिसेस जो समरूप है ${\mathcal {A}}$, और अक्सर इसके साथ काम करना आसान होता है।

उदाहरण

• J(v, k) द्वारा निरूपित जॉनसन योजना को निम्नानुसार परिभाषित किया गया है। मान लीजिए कि S, v अवयवों वाला एक समुच्चय है। योजना J(v, k) के बिंदु हैं ${v \choose k}$ k तत्वों के साथ S का सबसेट। S के दो k-तत्व उपसमुच्चय A, B i th सहयोगी होते हैं जब उनके प्रतिच्छेदन का आकार k − i होता है।
• H(n, q) द्वारा निरूपित हैमिंग योजना को निम्नानुसार परिभाषित किया गया है। H(n, q) के बिंदु q हैंⁿ ने आकार q के सेट पर n-tuples का आदेश दिया। दो n-tuples x, y को iवें सहयोगी कहा जाता है यदि वे बिल्कुल i निर्देशांक में असहमत हैं। उदाहरण के लिए, यदि x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), तो x और y पहले सहयोगी हैं, x और z पहले सहयोगी हैं और एच (4,2) में वाई और जेड दूसरे सहयोगी हैं।
• एक दूरी-नियमित ग्राफ़, G, दो शीर्षों को i th सहयोगियों के रूप में परिभाषित करके एक संघ योजना बनाता है यदि उनकी दूरी i है।
• एक परिमित समूह जी एक संघ योजना का उत्पादन करता है $X=G$, कक्षा आर के साथ_g प्रत्येक समूह तत्व के लिए, इस प्रकार है: प्रत्येक के लिए $g\in G$ होने देना $R_{g}=\{(x,y)\mid x=g*y\}$ कहाँ $*$ समूह संक्रिया (गणित) है। पहचान तत्व का वर्ग आर है₀. यह संघ योजना क्रमविनिमेय है यदि और केवल यदि G एबेलियन समूह है।
• एक विशिष्ट 3-श्रेणी संघ योजना:

चलो ए (3) सेट एक्स = {1,2,3,4,5,6} पर तीन सहयोगी वर्गों के साथ निम्नलिखित संघ योजना बनें। (i, j ) प्रविष्टि s है यदि तत्व i और j संबंध R में हैं_s.

	1	2	3	4	5	6
1	0	1	1	2	3	3
2	1	0	1	3	2	3
3	1	1	0	3	3	2
4	2	3	3	0	1	1
5	3	2	3	1	0	1
6	3	3	2	1	1	0

कोडिंग सिद्धांत

शास्त्रीय कोडिंग सिद्धांत में हैमिंग योजना और जॉनसन योजना का बड़ा महत्व है।

कोडिंग थ्योरी में, संघ स्कीम थ्योरी मुख्य रूप से एक कोड की हैमिंग दूरी से संबंधित है। रैखिक प्रोग्रामिंग पद्धति दी गई न्यूनतम हैमिंग दूरी के साथ एक कोड के आकार के लिए ऊपरी सीमा और एक दी गई ताकत के साथ टी डिजाइन के आकार के लिए निचली सीमा बनाती है। सबसे विशिष्ट परिणाम उस मामले में प्राप्त होते हैं जहां अंतर्निहित संघ योजना कुछ बहुपद गुणों को संतुष्ट करती है; यह व्यक्ति को ओर्थोगोनल बहुपदों के दायरे में ले जाता है। विशेष रूप से, बहुपद-प्रकार की संघ योजनाओं में कोड और टी-डिज़ाइन के लिए कुछ सार्वभौमिक सीमाएँ प्राप्त की जाती हैं।

शास्त्रीय कोडिंग सिद्धांत में, एक हैमिंग योजना में कोड से निपटने के लिए, मैकविलियम्स रूपांतरण में ऑर्थोगोनल बहुपदों का एक परिवार शामिल होता है जिसे क्रॉचौक बहुपद के रूप में जाना जाता है। ये बहुपद हैमिंग स्कीम के डिस्टेंस रिलेशन मैट्रिसेस के eigenvalue देते हैं।

यह भी देखें

• ब्लॉक डिजाइन
• बोस-मेस्नर बीजगणित
• संयुक्त डिजाइन

संदर्भ

• Bailey, Rosemary A. (2004), Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge University Press, ISBN 978-0-521-82446-0, MR 2047311. (Chapters from preliminary draft are available on-line.)
• Bannai, Eiichi; Ito, Tatsuro (1984), Algebraic combinatorics I: Association schemes, Menlo Park, CA: Benjamin/Cummings, ISBN 0-8053-0490-8, MR 0882540
• Bose, R. C.; Mesner, D. M. (1959), "On linear associative algebras corresponding to association schemes of partially balanced designs", Annals of Mathematical Statistics, 30 (1): 21–38, doi:10.1214/aoms/1177706356, JSTOR 2237117, MR 0102157
• Bose, R. C.; Nair, K. R. (1939), "Partially balanced incomplete block designs", Sankhyā, 4 (3): 337–372, JSTOR 40383923
• Bose, R. C.; Shimamoto, T. (1952), "Classification and analysis of partially balanced incomplete block designs with two associate classes", Journal of the American Statistical Association, 47 (258): 151–184, doi:10.1080/01621459.1952.10501161
• Camion, P. (1998), "18. Codes and Association Schemes: Basic Properties of Association Schemes Relevant to Coding", in Pless, V.S.; Huffman, W.C.; Brualdi, R.A. (eds.), Handbook of Coding Theory, vol. 1, Elsevier, pp. 1441–, ISBN 978-0-444-50088-5
• Delsarte, P. (1973), "An Algebraic Approach to the Association Schemes of Coding Theory", Philips Research Reports (Supplement No. 10), OCLC 641852316
• Delsarte, P.; Levenshtein, V. I. (1998). "Association schemes and coding theory". IEEE Transactions on Information Theory. 44 (6): 2477–2504. doi:10.1109/18.720545.
• Dembowski, P. (1968), Finite Geometries, Springer, ISBN 978-3-540-61786-0
• Godsil, C. D. (1993), Algebraic Combinatorics, New York: Chapman and Hall, ISBN 0-412-04131-6, MR 1220704
• MacWilliams, F.J.; Sloane, N.J.A. (1977), The Theory of Error Correcting Codes, North-Holland Mathematical Library, vol. 16, Elsevier, ISBN 978-0-444-85010-2
• Street, Anne Penfold; Street, Deborah J. (1987), Combinatorics of Experimental Design, Oxford U. P. [Clarendon], ISBN 0-19-853256-3

• van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge University Press, ISBN 0-521-00601-5
• Zieschang, Paul-Hermann (2005a), "Association Schemes: Designed Experiments, Algebra and Combinatorics by Rosemary A. Bailey, Review" (PDF), Bulletin of the American Mathematical Society, 43 (2): 249–253, doi:10.1090/S0273-0979-05-01077-3
• Zieschang, Paul-Hermann (2005b), Theory of association schemes, Springer, ISBN 3-540-26136-2
• Zieschang, Paul-Hermann (2006), "The exchange condition for association schemes", Israel Journal of Mathematics, 151 (3): 357–380, doi:10.1007/BF02777367, MR 2214129, S2CID 120009352