Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp. [Formerly: Publ. I. R. M. A. Strasbourg, 1985, 266/S-11, p. 82 - 94.]

ÜBER DIE PERMANENTE GEWISSER ZIRKULANTER MATRIZEN UND DAMIT ZUSAMMENHÄNGENDER TOEPLITZ-MATRIZEN

von

Arnold Richard KRÄUTER

Zusammenfassung. Zur Einführung werden zwei Anwendungen der Permanente zirkulanter (0,1)-Matrizen auf klassische Abzählprobleme besprochen. Darauf folgt ein kurzer Überblick über die bisher erschienene einschlägige Literatur zu dem im Titel genannten Thema im Falle von (0,1)-Matrizen. Für das analoge Problem bei (1, −1)-Matrizen werden schließlich einige neue Ergebnisse angekündigt, wobei auf die Präsentation der zu ihrer Herleitung erforderlichen Methoden besonderer Wert gelegt wird. Eine dieser Methoden führt nebenbei auf einen neuen Beweis der Touchardschen Formel für die reduzierten Ménage-Zahlen.

Abstract. In the introductory section, a discussion of two applications of the permanent of circulant (0,1) matrices to classical enumeration problems is given, followed by a short survey of the hitherto published literature on the topic mentioned in the title in the case of (0,1) matrices. As to the analogous problem for (1, −1) matrices, we announce a couple of recent results, where special attention is given to the presentation of the methods needed to establish them. By the way, one of these methods gives rise to a new proof of Touchard’s formula for the reduced ménage numbers.

1. Zwei einführende Beispiele

Die Permanente einer n × n-Matrix A = (a_{ij}) ist definiert durch

per A = ∑_{σ∈S_{n}} a_{1σ(1)} · ... · a_{nσ(n)}, (1.1)

wobei S_{n} die symmetrische Gruppe der Ordnung n bezeichnet. Ferner bezeichne I_{n} die n × n-Einheitsmatrix, J_{n} die n × n-Matrix mit lauter Einsen und P_{n} jene n × n-Permutationsmatrix, deren Einsen in den Positionen (1,2), (2,3), ..., (n − 1, n), (n, 1) stehen. Das erste der hier zu behandelnden Beispiele ist das bekannte problème des rencontres (Montmort, 1708), welches sich so formulieren läßt: Auf wieviele Arten können sich n Ehepaare zu n Tanzpaaren formieren, so daß kein Herr mit seiner Ehefrau tanzt?

Es bezeichne X_{i} die Menge jener Damen, die mit dem i-ten Herrn tanzen dürfen (i = 1, ..., n). Die Inzidenzmatrix für die Mengen X_{1}, ..., X_{n} ist dann gerade J_{n}−I_{n} und die gesuchte Anzahl von Möglichkeiten ergibt sich gemäß [15, p. 31] zu

per (J_{n} − I_{n}) = d_{n}, (1.2)

wobei d_{n} die n-te Dérangement-Zahl

d_{n} = ∑_{k=0}^{n}(−1)^{k} \frac{n!}{k!} (1.3)

bezeichnet. Die Formel (1.2) läßt sich mithilfe elementarer permanententheoretischer Methoden induktiv herleiten (siehe [15, p. 44]). Im Vergleich dazu ist die Lösung des problème des ménages (Lucas, 1891) etwas aufwendiger: Auf wieviele Arten können sich n Ehepaare an einen runden Tisch setzen, so daß Damen und Herren abwechselnd sitzen und keine Dame neben ihrem Ehemann sitzt? Wir bestimmen diese Anzahl für den Fall, daß die Sitzordnung der Herren bereits feststeht (dafür gibt es klarerweise 2 · n! Möglichkeiten). Dann lautet die Inzidenzmatrix J_{n} − I_{n} − P_{n} und die gesuchte Antwort

per (J_{n} − I_{n} − P_{n}) = μ_{n}, (1.4)

wobei μ_{n} die n-te reduzierte Ménage-Zahl

μ_{n} = ∑_{k=0}^{n}(−1)^{k} \frac{2n}{2n − k} \binom{2n − k}{k}(n − k)! (1.5)

bezeichnet (zu dieser Formel siehe Touchard [21, p. 632]).

2. Zirkulante und Toeplitzsche (0,1)-Matrizen

Die in Abschnitt 1 behandelten Matrizen

J_{n} − I_{n} = ∑_{k=1}^{n−1} P_{n}^{k} und J_{n} − I_{n} − P_{n} = ∑_{k=2}^{n−1} P_{n}^{k} (2.1)

sind Spezialfälle von

c_{0}I_{n} + c_{1}P_{n} + c_{2}P_{n}^{2} + ... + c_{n−1}P_{n}^{n−1}, (2.2) wobei die c_{k} entweder 0 oder 1 sind (k = 0, ..., n − 1). Eine solche Matrix nennen wir zirkulante (0, 1)-Matrix: bei gegebener erster Zeile der Matrix geht die (i+1)- te Zeile aus der i-ten (i = 1, ..., n − 1) durch Verschiebung um eine Spalte nach rechts hervor (das n-te Element der i-ten Zeile wird erstes Element der (i+1)-ten Zeile). Im allgemeinen ist die Permanente von (2.2) schwer zu berechnen, weshalb explizite Formeln bisher nur für Spezialfälle vorliegen. Wir wählen zunächst c_{0} = ... = c_{r−1} = 1 und c_{r} = ... = c_{n−1} = 0, betrachten also die Matrizen

Q(n, r) = ∑_{k=0}^{r−1} P_{n}^{k}. (2.3)

Erste Untersuchungen über die Permanente der Q(n, r) stammen von Mendelsohn [11]. Das weitere Interesse an dieser Matrizenklasse entspringt dem folgenden in [11, p. 32, Formel (12)] enthaltenen Ergebnis, welches in unserer Notation so lautet: für festes r gilt

per Q(n, r) ∼ K(r) α^{n}, (2.4)

wobei K(r) eine nur von r abhängige Konstante und α die im Intervall ]1, 2[ liegende Wurzel von x^{r} − 2x^{r−1} + 1 = 0 ist. Für festes r > 5 und hinreichend großes n folgt wegen α < 2

K(r) α^{n} < K(r) 2^{n} < (\frac{r}{e})^{n} < n! (\frac{r}{n})^{n} ,

also

per Q(n, r) < n! (\frac{r}{n})^{n} .

Damit wäre in \frac{1}{r} Q(n, r) eine einfache Matrizenklasse gefunden, welche die Vermutung von van der Waerden (mittlerweile von Falikman und Egoryčev bewiesen; siehe etwa [10, pp. 47 - 52]) ad absurdum führt. In der Tat konnte Minc [14] zeigen, daß (2.4) bereits für r ≥ 5 falsch ist. Ferner wies er darauf hin, daß die Formeln für per Q(n, 3) und per Q(n, 4) in [11] inkorrekt sind. Wir begnügen uns deshalb mit der Wiedergabe der folgenden trivialen beziehungsweise bekannten Formeln aus [11, p. 31]:

per Q(n, 1)  = 1,
per Q(n, 2)  = 2,
per Q(n, n − 2) = μ_{n},
per Q(n, n − 1) = d_{n},
per Q(n, n)  = n!.

(2.5)

Für r ≥ 3 stellt sich heraus, daß die Werte von per Q(n, r) eng zusammenhängen mit der Permanente der Toeplitzschen (0,1)-Matrizen

F (n, r) = [ \begin{matrix}1 & ⋯ & 1 & 0 & ⋯ & 0 \\ 1 & ... & & ... & ... & ⋮ \\ 0 & ... & ... & & ... & 0 \\ ⋮ & ... & ... & ... & & 1 \\ ⋮ & & ... & ... & ... & ⋮ \\ 0 & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} ]_{\} r−1} . (2.6)

(In einer Toeplitz-Matrix sind die Elemente mit gleicher Differenz von Zeilen- und Spaltenindex gleich.)

Satz 1 (Minc [14, p. 257]). Für alle n ≥ 2r − 2 gilt

per F (n, r) = f_{n,r−1}, (2.7)

wobei f_{n,r} die n-te Fibonacci-Zahl der Ordnung r,

(2.8)  f_{n,r} = \{ \begin{matrix}0  für & n < 0, \\ 1  für & n = 0, \\ f_{n−1,r} + ... + f_{n−r,r} für & n > 0, \end{matrix}

bezeichnet (siehe Miles [13, p. 745]).

Unter Verwendung dieses Satzes lassen sich nun folgende Beziehungen herleiten:

Satz 2 (Minc [14, pp. 257 - 258]). Für alle n ≥ 5 gilt

per Q(n, 3) = f_{n−1,2} + 2 f_{n−2,2} + 2,
per Q(n, 3) = per Q(n − 1, 3) + per Q(n − 2, 3) − 2,
per Q(n, 3) = [\frac{1}{2} (1 + \sqrt{5})]^{n} + [\frac{1}{2} (1 − \sqrt{5})]^{n} + 2

(2.9)

und für alle n ≥ 7 gilt

per Q(n, 4) = 2 (f_{n−1,3} + 2 f_{n−2,3} + 3 f_{n−3,3} + 1),
per Q(n, 4) = per Q(n − 1, 4) + per Q(n − 2, 4) +
+ per Q(n − 3, 4) − 4,
per Q(n, 4) = 2 (α_{1}^{n} + α_{2}^{n} + α_{3}^{n} + 1),

(2.10) wobei α_{1}, α_{2}, α_{3} die Wurzeln von x^{3} − x^{2} − x − 1 = 0 sind.

Die in Satz 2 erwähnten Rekursionsformeln für per Q(n, r) führen zu der folgenden

Vermutung. Für alle n ≥ 3 gilt

per Q(n, r) = ∑_{k=1}^{r−1} per Q(n − k, r) + C(r), (2.11)

worin C(r) eine nur von r abhängige Konstante bezeichnet.

Bereits für r = 5 konnte aber ein Gegenbeispiel gefunden werden.

Satz 3 (Metropolis-Stein-Stein [12, p. 292]). Für alle n ≥ 15 gilt

per Q(n, 5) = ∑_{k=1}^{10} a_{k} per Q(n − k, 5) + 24, (2.12)

wobei (a_{1}, ..., a_{10}) = (2, 2, 0, −2, −8, −6, −2, 0, 2, 1) ist.

In [12] findet man überdies neben einer expliziten Rekursion für per Q(n, 6) ausführliche Tabellen der Werte von per Q(n, r) für 4 ≤ r ≤ 9, r ≤ n ≤ 80. Eine gegenüber den bereits bekannten Formeln (2.9) neue Darstellung von per Q(n, 3) durch Summen von Binomialkoeffizienten wurde übrigens von King und Parker [7] hergeleitet. Permanenten von zirkulanten (0,1)-Matrizen, welche sich von den Q(n, r) unterscheiden, wurden im Zusammenhang mit verschiedenen Aufgabenstellungen betrachtet, so beispielsweise bei der Behandlung des mehrdimensionalen Dimerenproblems (einen schönen Überblick über den aktuellen Stand dieses von zahlreichen Forschern in Angriff genommenen Problems findet man bei Minc [16, pp. 233 - 236]). Andere erwähnenswerte Untersuchungen stammen von Tinsley [20] (Charakterisierung der Gleichheit von Permanente und Betrag der Determinante bei sogenannten Abelschen (0,1)-Matrizen), Brualdi-Newman [2] (Studium des asymptotischen Verhaltens der minimalen Permanente zirkulanter (0,1)-Matrizen), Kim-Roush [6] (Behandlung einer abgeschwächten Version der Vermutung von van der Waerden), Nemeth-Seberry-Shu [17] (Bestimmung der Mächtigkeit des Wertebereiches der Permanente auf der Menge aller zirkulanten n × n-(0,1)-Matrizen) sowie Eades-Praeger-Seberry [5].

3. Zirkulante und Toeplitzsche (1,–1)-Matrizen

Zirkulante Matrizen und Toeplitz-Matrizen aus den Elementen 1 und −1 treten als extremale Matrizen bei Problemen auf, welche mit der Bestimmung guter oberer Schranken für die Permanente nichtsingulärer (1, −1)-Matrizen zusammenhängen (siehe Kräuter-Seifter [8], [9] und Seifter [19]). Es sind dies Matrizen der Bauart

T (n, r) = [ \begin{matrix}−1 & ⋯ & −1 & 1 & ⋯ & 1 \\ 1 & ... & & ... & ... & ⋮ \\ ⋮ & ... & ... & & ... & 1 \\ ⋮ & & ... & ... & & −1 \\ ⋮ & & & ... & ... & ⋮ \\ 1 & ⋯ & ⋯ & ⋯ & 1 & −1 \end{matrix} ] _{\} r} (3.1)

und

Z(n, r) = [ \begin{matrix}−1 & ⋯ & −1 & 1 & ⋯ & ⋯ & 1 \\ 1 & ... & & ... & ... & & ⋮ \\ ⋮ & ... & ... & & ... & ... & ⋮ \\ 1 & & ... & ... & & ... & 1 \\ −1 & ... & & ... & ... & & −1 \\ ⋮ & ... & ... & & ... & ... & ⋮ \\ −1 & ⋯ & −1 & 1 & ⋯ & 1 & −1 \end{matrix} ] _{\} r} . (3.2)

Die im vorigen Abschnitt erwähnte Arbeit [5] verdient wegen der darin enthaltenen Methoden zur Berechnung der Permanente besonderes Interesse. Hier sollen nun zwei weitere Methoden vorgestellt werden, welche bei der Betrachtung von (1, −1)-Matrizen von Nutzen sind. Dazu führen wir einige Bezeichnungen ein. Für k ≤ n bezeichne Q_{k,n} die Menge

Q_{k,n} = {α = (α_{1}, ..., α_{k}) ∈ N^{k} : 1 ≤ α_{1} < ... < α_{k} ≤ n} . (3.3)

Für α, β ∈ Q_{k,n} sei A(α|β) jene (n − k) × (n − k)-Untermatrix von A, welche aus A durch Streichung der Zeilen mit den Indizes α und der Spalten mit den Indizes β entsteht (für k = 0 ist A(α|β) = A). A[α|β] bezeichne das Komplement von A(α|β) in A.

Zu jeder n × n-(1, −1)-Matrix A gibt es eine geeignete n × n-(0,1)-Matrix B, so daß

A = J_{n} − 2B (3.4)

gilt. Nach einem Satz über die Permanente der Summe zweier Matrizen (Caianiello [3, p. 644, Formel (18)]; siehe auch [15, p. 18, Theorem 1.4]) haben wir dann

per A = ∑_{k=0}^{n} ∑_{α,β∈Q_{k,n}} per (J_{n}[α|β]) per (−2B(α|β)) =
= ∑_{k=0}^{n}(−2)^{k}(n − k)! σ_{k}(B),

(3.5)

wobei

σ_{k}(B) = ∑_{α,β∈Q_{n−k,n}} per (B(α|β)) für 1 ≤ k ≤ n − 1,
σ_{0}(B) = 1,
σ_{n}(B) = per B

(3.6)

ist. Die Bestimmung der Permanente einer (1, −1)-Matrix ist somit zurückgeführt auf die Berechnung der Summen aller k-reihigen Unterpermanenten einer entsprechenden (0,1)-Matrix. Die explizite Bestimmung von σ_{k}(B) läßt sich für kleine k noch mit vertretbarem Aufwand durchführen. In bezug auf die Matrizen (3.1) und (3.2) erhalten wir für r = 1 und r = 2 folgende Resultate:

Satz 4.

per T (n, 1) = ∑_{k=0}^{n}(−2)^{k} \frac{n!}{k!}. (3.7)

per Z(n, 1) = per T (n, 1). (3.8)

Für A = T (n, 1) ist nämlich in (3.4) B = I_{n} und somit für 0 ≤ k ≤ n

σ_{k}(B) = \binom{n}{k}. (3.9)

Satz 5.

per T (n, 2) = ∑_{k=0}^{n}(−2)^{k} \binom{2n − k}{k} (n − k)!. (3.10)

(3.11) per Z(n, 2) = per T (n, 2) − 2 per T (n − 1, 2).

perZ(n, 2) = ∑_{k=0}^{n}(−2)^{k} \frac{2n}{2n − k} \binom{2n − k}{k} (n − k)!. (3.12)

Auf die Präsentation detaillierter Beweise sowie auf die Behandlung der Fälle r ≥ 3 wollen wir hier verzichten; dies soll im Rahmen einer in Vorbereitung befindlichen ausführlicheren Note geschehen.

Bemerkung. Ersetzt man in (3.4) 2B durch B, erhält man auf die gleiche Weise anstelle der Beziehungen (3.7) und (3.12) die Formeln (1.3) und (1.5). Die eben skizzierte Methode liefert somit unter anderem einen neuen Zugang zur Touchardschen Formel für die reduzierten Ménage-Zahlen. Für große Werte von r ist es nützlich, einen anderen Weg einzuschlagen. Im problème des rencontres ist - mathematisch formuliert - die Anzahl jener Permutationen aus S_{n} zu bestimmen, welche keinen Fixpunkt besitzen, das heißt kein i wiederum in i überführen. Man kann also sagen, alle (i, j)-ten Elemente der Inzidenzmatrix mit j = σ(i) = i für ein σ ∈ S_{n} repräsentieren verbotene Positionen von σ. Diesen Sachverhalt wollen wir folgendermaßen verallgemeinern: Die Matrix A = (a_{ij}) sei gegeben durch

(3.13) a_{ij} = \{ \begin{matrix}t, falls j = σ(i) für ein σ ∈ S_{n} verboten ist, \\ 1 sonst. \end{matrix}

Jedem σ ∈ S_{n} entspricht umkehrbar eindeutig das Produkt a_{1σ(1)} · ... · a_{nσ(n)}; daraus und aus (3.13) folgt somit: σ ∈ S_{n} ist eine Permutation mit k verbotenen Positionen genau dann, wenn a_{1σ(1)} · ... · a_{nσ(n)} = t^{k} gilt. Bezeichnet man nun mit ν_{k} die Anzahl der Permutationen mit k verbotenen Positionen, so erhält man bei Summation über alle σ ∈ S_{n}

∑_{σ∈S_{n}} a_{1σ(1)} · ... · a_{nσ(n)} = ∑_{k=0}^{n} ν_{k}t^{k} =: N_{n}(t). (3.14)

Der Ausdruck auf der linken Seite von (3.14) ist gemäß (1.1) gerade per A. Wir fassen zusammen:

per A = N_{n}(t). (3.15)

Diese Beziehung soll im folgenden zur Berechnung von per T (n, n) herangezogen werden (siehe Kräuter-Seifter [8, pp. 57 - 58, Lemma 2]). Die Matrix S_{n}(t) = (s_{ij}) sei definiert durch

zirkulante matrizen 9

(3.16) s_{ij} = \{ \begin{matrix}t für 1 ≤ i ≤ j ≤ n, \\ 1 sonst. \end{matrix}

Dann gilt für das gemäß den obigen Ausführungen konstruierte, zur Matrix S_{n}(t) gehörige Polynom N_{n}(t) gemäß (3.15) per S_{n}(t) = N_{n}(t). (3.17) Nach Riordan [18, p. 215] hat die Folge der Polynome N_{n}(t) die exponentiell erzeugende Funktion (man definiert N_{0}(t) := 0)

∑_{n=0}^{∞} N_{n}(t) \frac{x^{n}}{n!} = \frac{1 − t}{1 − t exp[x(1 − t)]}, (3.18)

aus welcher für t = −1 mit (3.17) sofort

∑_{n=0}^{∞} per T (n, n) \frac{x^{n}}{n!} = \frac{2}{1 + e^{2x}} (3.19)

folgt. Die gleiche exponentiell erzeugende Funktion besitzt die Zahlenfolge 2^{n}E_{n}(0), wobei E_{n}(y) das n-te Euler-Polynom bezeichnet (siehe [4, p. 48, Formel (14b)]). Somit ist für alle n ≥ 0 per T (n, n) = 2^{n}E_{n}(0). (3.20) Der bekannte Zusammenhang von E_{n}(0) mit den Bernoulli-Zahlen (siehe etwa [1, p. 805, Formel 23.1.20]) führt bei geeigneter Zusammenfassung [1, p. 75, Formel 4.3.67]) letztlich auf das folgende Ergebnis:

Satz 6. per T (n, n) = (−1)^{(n+1)/2} τ_{n}, (3.21) wobei τ_{n} die n-te Tangenszahl [4, p. 259], definiert durch

∑_{n=0}^{∞} τ_{n} \frac{x^{n}}{n!} = tan x, (3.22)

ist.

10 a. r. kräuter

Bemerkung. Wegen τ_{2k} = 0 ist auch per T (2k, 2k) = 0 für alle k ≥ 0. Dieses Resultat findet man bereits bei Wang [22, p. 359, Example 2]. Abschließend notieren wir noch die (triviale) Formel für per Z(n, n) :

Satz 7.

per Z(n, n) = (−1)^{n}n!. (3.23)

Literatur

[1] Milton Abramowitz and Irene A. Stegun (editors), Handbook of Mathematical Functions. Ninth printing. New York: Dover, 1972.

[2] Richard Anthony Brualdi and Morris Newman, Some theorems on the permanent. Journal of Research of the National Bureau of Standards (B) 69, 159 - 163 (1965).

[3] Eduardo E. Caianiello, Regularization and renormalization I. General Part. Il Nuovo Cimento (10) 13, 637 - 661 (1959).

[4] Louis Comtet, Advanced Combinatorics. Revised and enlarged edition. Translated from the French by J. W. Nienhuys. Dordrecht: Reidel, 1974.

[5] Peter Eades, Cheryl Elisabeth Praeger, and Jennifer Roma Seberry, Some remarks on the permanents of circulant (0,1) matrices. Utilitas Mathematica 23, 145 - 159 (1983).

[6] Ki Hang Kim and Fred William Roush, On a conjecture of Erdős and Rényi. Linear Algebra and Its Applications 23, 179 - 189 (1979).

[7] Bruce W. King and Francis Dunbar Parker, A Fibonacci matrix and the permanent function. The Fibonacci Quarterly 7, 539 - 544 (1969).

[8] Arnold Richard Kräuter and Norbert Seifter, On some questions concerning permanents of (1, −1)-matrices. Israel Journal of Mathematics 45, 53 - 62 (1983).

[9] Arnold Richard Kräuter and Norbert Seifter, Some properties of the permanent of (1, −1)-matrices. Linear and Multilinear Algebra 15, 207 - 223 (1984).

[10] Arnold Richard Kräuter, Permanenten - Ein kurzer Überblick. Publications de l’Institut de Recherche Mathématique Avancée Strasbourg 230, 39 - 83 (1984).

[11] Nathan Saul Mendelsohn, Permutations with confined displacements. Canadian Mathematical Bulletin 4, 29 - 38 (1961).

[12] Nicholas Metropolis, Marvin Leonard Stein, and Paul R. Stein, Permanents of cyclic (0,1) matrices. Journal of Combinatorial Theory 7, 291 - 321 (1969).

[13] Ernest P. Miles, Jr., Generalized Fibonacci numbers and associated matrices. The American Mathematical Monthly 67, 745 - 752 (1960).

[14] Henryk Minc, Permanents of (0,1)-circulants. Canadian Mathematical Bulletin 7, 253 - 263 (1964).

[15] Henryk Minc, Permanents. Encyclopedia of Mathematics and Its Applications, Volume 6. Reading: Addison-Wesley, 1978.

zirkulante matrizen 11

[16] Henryk Minc, Theory of permanents 1978 - 1981. Linear and Multilinear Algebra 12, 227 - 263 (1983).

[17] Evi Nemeth, Jennifer Seberry, and Michael Shu, On the distribution of the permanent of cyclic (0,1) matrices. Utilitas Mathematica 16, 171 - 182 (1979).

[18] John Riordan, An Introduction to Combinatorial Analysis. Fourth printing. New York: Wiley, 1967.

[19] Norbert Seifter, Upper bounds for permanents of (1, −1)-matrices. Israel Journal of Mathematics 48, 69 - 78 (1984).

[20] Marion Franklin Tinsley, Permanents of cyclic matrices. Pacific Journal of Mathematics 10, 1067 - 1082 (1960).

[21] Jacques Touchard, Sur un problème de permutations. Comptes Rendus de l’Académie des Sciences Paris 198, 631 - 633 (1934).

[22] Edward Tzu-Hsia Wang, On permanents of (1, −1)-matrices. Israel Journal of Mathematics 18, 353 - 361 (1974).

Arnold Richard Kräuter Institut für Mathematik und Angewandte Geometrie Montanuniversität Leoben Franz-Josef-Straße 18 A-8700 Leoben, Österreich E-mail: kraeuter@unileoben.ac.at