Schützenberger's theorem

The set of Schützenberger , named after the French mathematician Marcel Schützenberger is a sentence from the theory of block designs , a branch of mathematics that between combinatorics and finite geometry is located. The sentence indicates one of the first necessary conditions for the existence of certain symmetrical block plans .

Formulation of the sentence

Is an even number , so it is for the existence of a symmetric necessary -Blockplans that , the order of the block schedule , a perfect square is ${\displaystyle v}$ ${\displaystyle 2{\text{-}}(v,k,\lambda )}$ ${\displaystyle n=k-\lambda }$

Evidence sketch

The incidence matrix belonging to the block diagram always satisfies the equation ${\displaystyle A}$

${\displaystyle A{A^{T}}=nI+\lambda J}$,

where the - identity matrix and the - one matrix denote. So the matrix elements in the main diagonal are the same and everywhere else the same . ${\displaystyle I}$ ${\displaystyle v\times v}$ ${\displaystyle J}$ ${\displaystyle v\times v}$ ${\displaystyle k}$ ${\displaystyle \lambda }$

So you have:

${\displaystyle A{A^{T}}={\begin{pmatrix}{k}&{\lambda }&\ldots &{\lambda }\\{\lambda }&{k}&\ldots &{\lambda }\\\vdots &\vdots &&\vdots \\{\lambda }&{\lambda }&\ldots &{k}\end{pmatrix}}}$.

This results after elementary matrix transformations :

${\displaystyle ({\det {A}})^{2}=\det({A{A^{T}}})=k^{2}\cdot n^{v-1}}$

and further

${\displaystyle ({\det {A}})^{2}\cdot n=k^{2}\cdot n^{v}={(k\cdot n^{\frac {v}{2}})}^{2}}$ .

Then there is a square number on the right side of the equation, because according to the assumption is an even number. However, since there is another square number on the left , it can only be that there is already a square number itself. ${\displaystyle v}$ ${\displaystyle ({\det {A}})^{2}}$ ${\displaystyle n}$

Remarks

Schützenberger's theorem coincides with the first part of Bruck-Ryser-Chowla's fundamental theorem . However, in the literature, for example in the introduction to combinatorics by Konrad Jacobs and Dieter Jungnickel , one also finds the view that both sentences do not belong together, but that Schützenberger's theorem should be viewed as an independent theorem. Jacobs and Jungnickel and Hall point out that in addition to and independently of Schützenberger, this result was also published in 1950 by SS Shrikhande and by Sarvadaman Chowla and Herbert John Ryser .

application

According to Schützenberger's theorem, the existence of a symmetrical block plan is excluded. ${\displaystyle 2{\text{-}}(22,7,2)}$

literature

• Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . Bibliographical Institute, Mannheim / Vienna / Zurich 1985, ISBN 3-411-01675-2 .
• Sarvadaman Chowla, Herbert John Ryser: Combinatorial Problems . In: Canadian J. Math . tape 2 , 1950, p. 93-99 .
• Marshall Hall, Jr .: Combinatorial Theory (=  Wiley-Interscience Series in Discrete Mathematics ). 2nd Edition. John Wiley & Sons, New York (et al.) 1968, ISBN 0-471-09138-3 .
• Daniel R. Hughes, Fred C. Piper: Design Theory . Cambridge University Press, Cambridge (et al.) 1985, ISBN 0-521-25754-9 .
• Konrad Jacobs, Dieter Jungnickel: Introduction to combinatorics (=  de Gruyter textbook ). 2nd, completely revised and expanded edition. de Gruyter, Berlin (et al.) 2004, ISBN 3-11-016727-1 .
• Eric S. Lander: Symmetric Designs: An Algebraic Approach (=  London Mathematical Society Lecture Note Series . Volume 74 ). Cambridge University Press, Cambridge (et al.) 1983, ISBN 0-521-28693-X .
• Herbert John Ryser: Combinatorial Mathematics (=  The Carus Mathematical Monographs . Volume 14 ). The Mathematical Association of America, Washington DC 1963, ISBN 0-88385-014-1 .
• MP Schützenberger : A nonexistence theorem for an infinite family of symmetrical block designs . In: Ann. Eugenics . tape 14 , 1949, pp. 286-287 ( MR0030485 ).
• SS Shrikhande: The impossibility of certain symmetrical balanced incomplete block designs . In: Ann. Math. Stat. tape 21 , 1950, pp. 106-111 ( MR0032552 ).
• Vladimir D. Tonchev: Combinatorial Configurations: Designs, Codes, Graphs (=  Pitman Monographs and Surveys in Pure and Applied Mathematics . Volume 40 ). Longman Scientific & Technical (et al.), Harlow (England) 1988, ISBN 0-582-99483-7 .

References and comments

1. ↑ Schützenberger: A nonexistence theorem for an infinite family of symmetrical block designs. In: Ann. Eugenics . tape 14 , p. 286-287 .
2. ^ Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . Bibliographisches Institut, Mannheim / Vienna / Zurich 1985, ISBN 3-411-01675-2 , p. 91 .
3. ↑ Konrad Jacobs, Dieter Jungnickel: Introduction to combinatorics (=  de Gruyter textbook ). 2nd, completely revised and expanded edition. de Gruyter, Berlin (among others) 2004, ISBN 3-11-016727-1 , p. 244 .
4. ↑ Tonchev: pp. 11, 69.
5. ^ Hall: p. 133 ff.
6. ^ Daniel R. Hughes, Fred C. Piper: Design Theory . Cambridge University Press, Cambridge (et al.) 1985, ISBN 0-521-25754-9 , pp. 55-59 .
7. ↑ Ryser: p. 108 ff.
8. ↑ ^{a b} Konrad Jacobs, Dieter Jungnickel: Introduction to combinatorics (=  de Gruyter textbook ). 2nd, completely revised and expanded edition. de Gruyter, Berlin (among others) 2004, ISBN 3-11-016727-1 , p. 244-249 .
9. ^ Hall: p. 133.
10. ↑ Although the usual parameter conditions are met!