Satz von Schützenberger

Der Satz von Schützenberger, benannt nach dem französischen Mathematiker Marcel Schützenberger, ist ein Satz aus der Theorie der Blockpläne, einem Teilgebiet der Mathematik, welches zwischen Kombinatorik und endlicher Geometrie angesiedelt ist. Der Satz gibt eine der ersten notwendigen Bedingungen für die Existenz gewisser symmetrischer Blockpläne an.^[1][2][3][4]

Formulierung des Satzes

Ist ${\displaystyle v}$ eine gerade Zahl, so ist es für die Existenz eines symmetrischen ${\displaystyle 2{\text{-}}(v,k,\lambda )}$-Blockplans notwendig, dass ${\displaystyle n=k-\lambda }$, die Ordnung des Blockplans, eine Quadratzahl ist.

Beweisskizze

Die zu dem Blockplan gehörige Inzidenzmatrix ${\displaystyle A}$ erfüllt stets die Gleichung

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

wobei ${\displaystyle I}$ die ${\displaystyle v\times v}$-Einheitsmatrix und ${\displaystyle J}$ die ${\displaystyle v\times v}$-Einsmatrix bezeichnet. Es sind also die Matrixelemente in der Hauptdiagonalen gleich ${\displaystyle k}$ und überall sonst gleich ${\displaystyle \lambda }$.

Man hat also:

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

Daraus ergibt sich nach elementaren Matrizenumformungen:

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

wobei ausgenutzt wurde, dass in symmetrischen ${\displaystyle 2{\text{-}}(v,k,\lambda )}$-Blockplänen ${\displaystyle k(k-1)=(v-1)\lambda }$ gilt, und weiter

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

Dann steht auf der rechten Seite der Gleichung eine Quadratzahl, denn nach Voraussetzung ist ${\displaystyle v}$ eine gerade Zahl. Da jedoch auf der linken Seite mit ${\displaystyle ({\det {A}})^{2}}$ eine weitere Quadratzahl steht, kann es nur so sein, dass ${\displaystyle n}$ selbst schon eine Quadratzahl ist.

Anmerkungen

Der Satz von Schützenberger deckt sich mit dem ersten Teil des fundamentalen Satzes von Bruck-Ryser-Chowla.^[5][6][7] Allerdings findet man in der Literatur, etwa in der Einführung in die Kombinatorik von Konrad Jacobs und Dieter Jungnickel, auch die Auffassung, dass beide Sätze nicht zusammengefasst gehören, sondern dass der Satz von Schützenberger als eigenständiger Lehrsatz zu betrachten ist. Jacobs und Jungnickel und ebenso Hall weisen darauf hin, dass neben und unabhängig von Schützenberger in 1950 dieses Resultat auch noch S. S. Shrikhande sowie von Sarvadaman Chowla und Herbert John Ryser veröffentlicht wurde.^[8][9]

Anwendung

Nach dem Satz von Schützenberger ist die Existenz eines symmetrischen ${\displaystyle 2{\text{-}}(22,7,2)}$-Blockplans ausgeschlossen.^[8][10]

Literatur

• M. P. Schützenberger: A nonexistence theorem for an infinite family of symmetrical block designs. In: Ann. Eugenics. Band 14, 1949, S. 286–287 (MR0030485). 
• S. S. Shrikhande: The impossibility of certain symmetrical balanced incomplete block designs. In: Ann. Math. Stat. Band 21, 1950, S. 106–111 (MR0032552). 
• Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. Bibliographisches Institut, Mannheim / Wien / Zürich 1985, ISBN 3-411-01675-2. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1. 
• Sarvadaman Chowla, Herbert John Ryser: Combinatorial Problems. In: Canadian J. Math. Band 2, 1950, S. 93–99. 
• Vladimir D. Tonchev: Combinatorial Configurations: Designs, Codes, Graphs (= Pitman Monographs and Surveys in Pure and Applied Mathematics. Band 40). Longman Scientific & Technical (u. a.), Harlow (England) 1988, ISBN 0-582-99483-7. 
• Daniel R. Hughes, Fred C. Piper: Design Theory. Cambridge University Press, Cambridge (u. a.) 1985, ISBN 0-521-25754-9. 
• Eric S. Lander: Symmetric Designs: An Algebraic Approach (= London Mathematical Society Lecture Note Series. Band 74). Cambridge University Press, Cambridge (u. a.) 1983, ISBN 0-521-28693-X. 
• Marshall Hall, Jr.: Combinatorial Theory (= Wiley-Interscience Series in Discrete Mathematics). 2. Auflage. John Wiley & Sons, New York (u. a.) 1968, ISBN 0-471-09138-3. 
• Herbert John Ryser: Combinatorial Mathematics (= The Carus Mathematical Monographs. Band 14). The Mathematical Association of America, Washington DC 1963, ISBN 0-88385-014-1. 

Einzelnachweise und Anmerkungen

1. ↑ Schützenberger: A nonexistence theorem for an infinite family of symmetrical block designs. In: Ann. Eugenics. Band 14, S. 286–287. 
2. ↑ Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. Bibliographisches Institut, Mannheim / Wien / Zürich 1985, ISBN 3-411-01675-2, S. 91. 
3. ↑ Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1, S. 244. 
4. ↑ Tonchev: S. 11, 69.
5. ↑ Hall: S. 133 ff.
6. ↑ Daniel R. Hughes, Fred C. Piper: Design Theory. Cambridge University Press, Cambridge (u. a.) 1985, ISBN 0-521-25754-9, S. 55–59. 
7. ↑ Ryser: S. 108 ff.
8. ↑ ^{a b} Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1, S. 244–249. 
9. ↑ Hall: S. 133.
10. ↑ Obwohl die üblichen Parameterbedingungen erfüllt sind!