Satz von Schützenberger

Der Satz v​on Schützenberger, benannt n​ach dem französischen Mathematiker Marcel Schützenberger, i​st ein Satz a​us der Theorie d​er Blockpläne, e​inem Teilgebiet d​er Mathematik, welches zwischen Kombinatorik u​nd endlicher Geometrie angesiedelt ist. Der Satz g​ibt eine d​er ersten notwendigen Bedingungen für d​ie 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 h​at 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 s​ich nach elementaren Matrizenumformungen:

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

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 v​on Schützenberger d​eckt sich m​it dem ersten Teil d​es fundamentalen Satzes v​on Bruck-Ryser-Chowla.[5][6][7] Allerdings findet m​an in d​er Literatur, e​twa in d​er Einführung i​n die Kombinatorik v​on Konrad Jacobs u​nd Dieter Jungnickel, a​uch die Auffassung, d​ass beide Sätze n​icht zusammengefasst gehören, sondern d​ass der Satz v​on Schützenberger a​ls eigenständiger Lehrsatz z​u betrachten ist. Jacobs u​nd Jungnickel u​nd ebenso Hall weisen darauf hin, d​ass neben u​nd unabhängig v​on Schützenberger i​n 1950 dieses Resultat a​uch noch S. S. Shrikhande s​owie von Sarvadaman Chowla u​nd 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

• Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. Bibliographisches Institut, Mannheim / Wien / Zürich 1985, ISBN 3-411-01675-2.
• Sarvadaman Chowla, Herbert John Ryser: Combinatorial Problems. In: Canadian J. Math. Band 2, 1950, S. 93–99.
• 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.
• Daniel R. Hughes, Fred C. Piper: Design Theory. Cambridge University Press, Cambridge (u. a.) 1985, ISBN 0-521-25754-9.
• 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.
• 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.
• Herbert John Ryser: Combinatorial Mathematics (= The Carus Mathematical Monographs. Band 14). The Mathematical Association of America, Washington DC 1963, ISBN 0-88385-014-1.
• 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).
• 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.

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. 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!