Séminaire Lotharingien de Combinatoire, B09b (1983), 34 pp. [Formerly: Publ. I. R. M. A. Strasbourg, 1984, 230/S-09, p. 39 - 83.]

PERMANENTEN - EIN KURZER ÜBERBLICK

von

Arnold Richard KRÄUTER

Zusammenfassung. Der vorliegende Artikel bringt eine knappe Übersicht über zentrale Fragestellungen der Permanententheorie. Auf die Definition der Permanente einer Matrix und die Zusammenstellung wichtiger Eigenschaften dieser Funktion folgt eine Behandlung des Problems der Umwandlung von Permanenten in Determinanten sowie der Vermutung von van der Waerden und ihres vor kurzem erbrachten Beweises. Eine wichtige Rolle spielen untere und obere Schranken für Permanenten, deren Präsentation für (0,1)-Matrizen, nichtnegative Matrizen und (1, −1)-Matrizen erfolgt. Soweit nicht bereits in den genannten Themenkreisen enthalten, werden abschließend neueste Entwicklungen in der Permanententheorie vorgestellt.

Abstract. This article gives a concise survey on important problems of the theory of permanents. The definition of the permanent of a matrix and a summary of some of its basic properties are followed by a treatment of the problem of converting permanents into determinants, and a discussion of the van der Waerden conjecture that has been proved quite recently. Very important are lower and upper bounds for permanents; these are presented for (0,1)-matrices, nonnegative matrices, and (1, −1)-matrices. Finally, we give a brief review of a selection of other attractive topics in the theory of permanents, particularly very recent developments.

1. Grundlagen

1.1. Definition der Permanente. Einleitende Bemerkungen. Die Permanente per A einer n × n-Matrix A = (a_{ij}) mit Elementen aus einem beliebigen kommutativen Ring 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. Für eine beliebige Permutation σ ∈ S_{n} heiße die Folge (a_{1σ(1)}, …, a_{nσ(n)}) Diagonale von A und das Produkt a_{1σ(1)} · . . . · a_{nσ(n)} Diagonalprodukt von A. Die Permanente von A kann also aufgefaßt werden als Summe der Diagonalprodukte von A. Der Name Permanente wird in der heute gebräuchlichen Bedeutung 1882 von Muir [51, p. 410] eingeführt, doch treten Permanenten sinngemäß bereits 1813/15 in den Arbeiten [5] und [10] von Binet und Cauchy auf. Seitdem sind über vierhundert Veröffentlichungen zum Thema Permanenten erschienen, darunter 1978 die hervorragende Monografie [46] von Minc. Die Entwicklungen zwischen 1978 und 1981 (unter Einschluß des Beweises für die Vermutung von van der Waerden) behandelt Minc im Übersichtsartikel [50]. Die zwei zuletzt genannten Publikationen stellen die wichtigste Grundlage für Gliederung und Auswahl des Stoffes im vorliegenden Aufsatz dar, doch fanden auch neueste Ergebnisse Berücksichtigung (dies gilt insbesondere für den letzten Abschnitt). Dem Überblickscharakter Rechnung tragend wird auf Beweise weitgehend verzichtet und diesbezüglich auf die zitierte Originalliteratur verwiesen. Überdies wurde in der Darstellung weder Vollständigkeit noch größte Allgemeinheit angestrebt. Anwendungen von Permanenten auf Probleme der Kombinatorik und anderer Bereiche behandelt der in diesem Band enthaltene Aufsatz von Herrn Seifter.

1.2. Eigenschaften der Permanente. Entwicklungssätze. Der bequemeren Formulierung halber werden wir uns der folgenden Bezeichnungen bedienen. Für r ≤ n sei Q_{r,n} definiert durch

Q_{r,n} = {(ω_{1}, …, ω_{r}) ∈ N^{r} : 1 ≤ ω_{1} < … < ω_{r} ≤ n} . (1.2)

Für eine n × n-Matrix A = (a_{ij}) sowie für Vektoren α = (α_{1}, …, α_{r}) ∈ Q_{r,n} und β = (β_{1}, …, β_{r}) ∈ Q_{r,n} bezeichne A[α|β] jene r × r-Untermatrix von A, deren (i, j)-tes Element a_{α_{i}β_{j}} ist. Ferner bezeichne A(α|β) die zu A[α|β] komplementäre (n − r) × (n − r)-Untermatrix von A. (Man erhält also A(α|β) durch Streichung der Zeilen mit den Indizes α_{1}, …, α_{r} und der Spalten mit den Indizes β_{1}, …, β_{r} von A.)

Satz 1.1. Es sei A = (a_{ij}) eine n × n-Matrix.

(a) Die Funktion per A ist multilinear in den Zeilen und Spalten von A.

(b) Für n × n-Permutationsmatrizen P und Q gilt

per P AQ = per A. (1.3)

(c) Für die transponierte Matrix A^{T} von A gilt

per A^{T} = per A. (1.4)

(d) Für einen beliebigen Vektor α ∈ Q_{r,n} gilt

permanenten 3

(1.5) per A = ∑_{ω∈Q_{r,n}} per A[α|ω] per A(α|ω) (Laplacescher Entwicklungssatz für die Entwicklung der Permanente nach den Zeilen mit den Indizes α_{1}, …, α_{r}). Insbesondere gilt für r = 1

per A = ∑_{j=1}^{n} a_{ij} per A(i|j). (1.6)

(Analoge Formeln gelten für die Entwicklung nach Spalten.)

Zur Illustration von Satz 1.1 wollen wir die Permanente der Matrix

K_{n} = [ \begin{matrix}0 & 1 & … & 1 \\ 1 & ... & ... & ⋮ \\ ⋮ & ... & ... & 1 \\ 1 & … & 1 & 0 \end{matrix} ] (1.7)

berechnen. (1.6) liefert für i = 1

per K_{n} = ∑_{j=2}^{n} per K_{n}(1|j). (1.8)

Da jede der (n − 1) × (n − 1)-Matrizen K_{n}(1|j) insgesamt n − 2 Nullen enthält, welche in paarweise verschiedenen Zeilen und Spalten stehen, gilt ferner bei Verwendung von (1.3) sowie der Multilinearität in der ersten Spalte (1.9) per K_{n}(1|j) = per K_{n−1} + per K_{n−2}, woraus mit (1.8) (1.10) per K_{n} = (n − 1)(per K_{n−1} + per K_{n−2}) folgt und weiter induktiv

per K_{n} = n! ∑_{k=0}^{n} \frac{1}{k!} (−1)^{k}. (1.11)

Dies ist die n-te Dérangement-Zahl d_{n} (siehe etwa Comtet [12, p. 180]) aus dem bekannten problème des rencontres. Wie die Matrix K_{n} mit diesem Problem zusammenhängt, geht aus den Bemerkungen über Inzidenzmatrizen im bereits erwähnten Aufsatz von Herrn Seifter hervor, weshalb wir hier auf Details nicht eingehen. Im Anschluß an Satz 1.1 ist zu bemerken, daß zwei für das Rechnen mit Determinanten außerordentlich wichtige Eigenschaften auf die Permanente bedauerlicherweise nicht zutreffen:

(a) Die Permanentenfunktion ist nicht invariant gegenüber beliebigen elementaren Zeilen- und Spaltenoperationen.

(b) Für Permanenten gibt es kein Analogon zum Determinanten-Produktsatz. Die erste dieser Bemerkungen hat zur Folge, daß die Berechnung der Permanente mithilfe einer derart effizienten Methode, wie sie der Gaußsche Algorithmus für Determinanten darstellt, unmöglich ist. Andererseits würde man bei Verwendung des Laplaceschen Entwicklungssatzes n!(n−1) Multiplikationen benötigen. Es ist daher naheliegend, nach Methoden zu suchen, welche erheblich weniger Multiplikationen erfordern. Dies ist der Fall bei den folgenden zwei Entwicklungssätzen, welche ursprünglich für beliebige m×n-Matrizen, m ≤ n, formuliert worden sind.

Satz 1.2 (Ryser [58, p. 26]). Es sei A eine n × n-Matrix, es sei Λ_{k} die Menge aller n × k-Untermatrizen X von A und es bezeichne r_{i}(X) die i-te Zeilensumme von X (i = 1, …, n). Dann gilt

per A = ∑_{t=0}^{n−1}(−1)^{t} ∑_{X∈Λ_{n−t}} r_{1}(X) · . . . · r_{n}(X). (1.12)

Es sei A = (a_{ij}) eine n×n-Matrix. r_{i_{1}∗...∗i_{s}} bezeichne die Summe der Elemente im Hadamard-Produkt der Zeilen mit den Indizes i_{1}, …, i_{s} von A, das heißt

r_{i_{1}∗...∗i_{s}} = ∑_{j=1}^{n} a_{i_{1}j} · . . . · a_{i_{s}j}. (1.13)

Weiters bezeichne D(n) die Menge

\begin{aligned}D(n) = & \{(ω_{1}, …, ω_{k}) ∈ N^{k} : 1 ≤ ω_{1} ≤ … ≤ ω_{k} ≤ n; \\ & ω_{1} + … + ω_{k} = n; k = 1, …, n\} \end{aligned} (1.14)

und R(ω) für ω = (ω_{1}, …, ω_{k}) ∈ D(n) die symmetrisierte Summe aller verschiedenen Produkte der r_{i_{1}∗...∗i_{s}} (s = ω_{1}, …, ω_{k}), so daß in jedem Produkt die Folgen (i_{1}, …, i_{s}) ∈ Q_{s,n} (s = ω_{1}, …, ω_{k}) eine Partition der Menge {1, …, n} bilden.

Satz 1.3 (Minc [47, p. 31]). Es sei A eine n × n-Matrix. Dann gilt

per A = ∑_{ω∈D(n)} (−1)^{n+k} ∏_{i=1}^{k}(ω_{i} − 1)! R(ω). (1.15)

Während in (1.15) mehr als (\frac{n}{2})^{n/2}(n − 1) Multiplikationen erforderlich sind, reichen in (1.12) (2^{n} − 1)(n − 1) Multiplikationen aus. Damit ist die Formel von Ryser das momentan brauchbarste Hilfsmittel für die Entwicklung von Permanenten. Abschließend sei noch die vor kurzem erschienene Arbeit [4] von Bebiano erwähnt, die mithilfe einer Identität, in welcher Permanenten als Koeffizienten von Polynomen auftreten, die Formeln (1.12) und (1.15) gewinnt.

2. Permanenten und Determinanten

2.1. Das Problem von Pólya. Wir haben im vorigen Abschnitt bemerkt, daß die Berechnung der Permanente gegenüber der Determinante sehr schwierig ist. Die Ähnlichkeit der Definitionen beider Funktionen legt jedoch den Gedanken nahe, Permanenten mithilfe linearer Transformationen des Arguments auf Determinanten zurückzuführen. Präzise formuliert lautet das Problem: Gibt es zu einer beliebigen Menge S von n × n-Matrizen stets eine lineare Abbildung T, so daß

per A = det T (A) (2.1)

für alle A ∈ S gilt? Wählt man beispielsweise für S die Menge aller 2×2-Matrizen

A = [ \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ] (2.2)

und für T die Abbildung

T (A) = [ \begin{matrix}a_{11} & −a_{12} \\ a_{21} & a_{22} \end{matrix} ] , (2.3)

dann gilt (2.1) tatsächlich für alle A ∈ S. Dies ist für n ≥ 3 nicht mehr der Fall. 1913 stellte nämlich Pólya [55] die folgende, von Szegő [64] gelöste Aufgabe: Es sei S die Menge aller n × n-Matrizen. Man zeige, daß es für n ≥ 3 im allgemeinen keine Abbildung T gibt, welche in ihrem Argument einen einheitlichen Vorzeichenwechsel bewirkt, so daß (2.1) für alle A ∈ S gilt. Rund fünfzig Jahre später wurde dieses Problem wieder aufgegriffen. Dabei konnte die folgende wesentliche Verbesserung erzielt werden:

Satz 2.1 (Marcus-Minc [38, p. 381]). Es sei S die Menge aller n × n-Matrizen, n ≥ 3. Dann gibt es im allgemeinen keine lineare Abbildung T, so daß (2.1) für alle A ∈ S gilt.

Mit diesem Ergebnis war nun endgültig klar, daß es keine allgemeine Möglichkeit gibt, Permanenten auf Determinanten zurückzuführen.

2.2. Konvertible Matrizen. Im Anschluß an Satz 2.1 haben einige Forscher versucht, hinreichende Bedingungen für Matrizen herzuleiten, so daß (2.1) gilt. Wir wollen Matrizen mit dieser Eigenschaft konvertibel nennen. Wir vereinbaren überdies, daß alle folgenden Abbildungen T lediglich Vorzeichenänderungen in ihrem Argument bewirken mögen. ν(A) bezeichne die Anzahl der Nullen in A, μ(T (A)) bezeichne die Anzahl der von T in A hervorgerufenen Vorzeichenwechsel und N_{n} sei die Zahl

N_{n} = \frac{1}{2}(n^{2} − 3n + 2). (2.4)

Satz 2.2 (Gibson [20, p. 474]). Es sei A eine konvertible n × n-(0,1)- Matrix mit positiver Permanente. Dann gilt

ν(A) ≥ N_{n}. (2.5)

Das Gleichheitszeichen gilt in (2.5) genau dann, wenn A durch Zeilen- oder Spaltenvertauschungen auf die Gestalt

T_{n} = [ \begin{matrix}1 & 1 & 0 & … & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & & ... & ... & 0 \\ ⋮ & & & ... & 1 \\ 1 & … & … & … & 1 \end{matrix} ] . (2.6)

gebracht werden kann.

Die Charakterisierung der Matrizen A mit ν(A) = N_{n} gestattet es, für diese Klasse detaillierte Aussagen über die Abbildungen T zu machen, so daß (2.1) gilt.

Satz 2.3 (Kräuter-Seifter [28, passim]). Es sei A eine n × n-(0,1)-Matrix mit positiver Permanente, ferner sei ν(A) = N_{n}, n ≥ 4, und es gelte per A = det T (A). Dann gilt

n − 1 ≤ μ(T (A)) ≤ \binom{n + 1}{2}, (2.7)

wobei jeder ganzzahlige Wert in diesem Intervall für ein geeignetes T tatsächlich angenommen wird. Auf der linken beziehungsweise rechten Seite von (2.7) gilt das Gleichheitszeichen genau dann, wenn die Matrix T (A) bis auf Zeilen- oder Spaltenvertauschungen mit der Matrix

U_{n} = [ \begin{matrix}1 & −1 & 0 & … & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & & ... & ... & 0 \\ ⋮ & & & ... & −1 \\ 1 & … & … & … & 1 \end{matrix} ]

beziehungsweise −U_{n} übereinstimmt.

3. Die Vermutung von van der Waerden

3.1. Von Marcus und Newman bis Friedland und Bang. 1926 stellte van der Waerden [67] (in moderner Terminologie formuliert) die folgende Frage: Wie groß ist das Minimum der Permanente auf der Menge Ω_{n} aller doppeltstochastischen n×n-Matrizen? (Eine quadratische Matrix heißt doppeltstochastisch, wenn ihre Elemente nichtnegativ sind und überdies ihre Zeilen- und Spaltensummen 1 sind.) Die Anregung zu dieser Aufgabe geht zurück auf den

Satz 3.1 (Kőnig [26, p. 458]). Es sei A eine nichtnegative n × n-Matrix, deren Zeilen- und Spaltensummen denselben positiven Wert besitzen. Dann gilt

per A > 0. (3.1)

Marcus und Newman sind die ersten Autoren, die sich mit dem genannten Problem beschäftigt haben. Ihre Arbeit [37] stellt ein sorgfältiges Studium der Eigenschaften von Matrizen aus Ω_{n} mit minimaler Permanente dar mit dem Ziel nachzuweisen, daß all diese Eigenschaften von genau einer Matrix erfüllt werden, nämlich

J_{n} = [ \begin{matrix}\frac{1}{n} & … & \frac{1}{n} \\ ⋮ & ... & ⋮ \\ \frac{1}{n} & … & \frac{1}{n} \end{matrix} ] . (3.2)

Dieses (von den erwähnten Autoren nur teilweise erreichte) Ziel ist der Inhalt der ”Vermutung von van der Waerden“: Für alle A ∈ Ω_{n} gilt

per A ≥ \frac{n!}{n^{n}} . (3.3)

Die verschärfte Fassung enthält überdies folgende Charakterisierung des Gleichheitsfalles: In (3.3) tritt Gleichheit genau dann ein, wenn A = J_{n} ist. Der Arbeit von Marcus und Newman kommt das große Verdienst zu, mit ihrer Vermutung und mit ihren Ergebnissen das innerhalb der darauffolgenden zweieinhalb Jahrzehnte stark gestiegene Interesse an der Permanententheorie geweckt und wichtige Ideen zur vollständigen Lösung des genannten Problems beigetragen zu haben. In bezug auf die Geschichte der Vermutung von van der Waerden verweisen wir auf Minc [46, pp. 95 - 99], [49, pp. 25 - 28]. Aus der Fülle von Teilresultaten, welche vor dem Beweis von (3.3) erschienen sind, sollen lediglich zwei angeführt werden (beide sind 1979 erschienen):

Satz 3.2 (Friedland [17, p. 175]). Für alle A ∈ Ω_{n} gilt

per A ≥ e^{−n}. (3.4)

Satz 3.3 (Bang [3, p. 3]). Für alle A ∈ Ω_{n} gilt

per A ≥ e^{1−n}. (3.5)

Man beachte, daß die Schranken in (3.3), (3.4) und (3.5) von nahezu gleicher Größenordnung sind; es folgt nämlich aus der Stirlingschen Formel

\frac{n!}{n^{n}} ≈ \sqrt{2πn} e^{−n}. (3.6)

3.2. Falikman und Egoryčev. Nach zahlreichen vergeblichen Versuchen mehrerer Mathematiker gelang es schließlich den sowjetischen Forschern Falikman [15] und Egoryčev [14], unabhängig voneinander den Nachweis für die Richtigkeit der Vermutung von van der Waerden zu erbringen. (Falikman reichte seinen Beweis 1979 ein, Egoryčev 1980.) Beide erhielten für ihre Leistung den Fulkerson-Preis 1982. Beide Beweise beruhen im Grunde genommen auf einem Spezialfall einer Ungleichung für gemischte Diskriminanten quadratischer Formen von Aleksandrov [2, pp. 231 - 232], welche in der hier benötigten Form folgendermaßen lautet:

Satz 3.4. Es sei A eine nichtnegative n × (n − 2)-Matrix, es seien x und y Spaltenvektoren mit n Komponenten und es sei überdies x nichtnegativ. Dann gilt

(3.7) [per (A, x, y)]^{2} ≥ per (A, x, x) per (A, y, y).

Sind A und x positiv, dann gilt in (3.7) das Gleichheitszeichen genau dann, wenn x und y kollinear sind.

Ein expliziter Beweis dieses Satzes findet sich bei Knuth [25, p. 735] und van Lint [34, pp. 3 - 4]. (Egoryčev hat die Ungleichung von Aleksandrov unmittelbar verwendet und konnte daher auf einen Beweis verzichten. Falikman hingegen bewies (3.7) für den Fall per (A, x, y) = 0.) Während Falikman keine weiteren Hilfsmittel benötigt, benützt Egoryčev überdies den

Satz 3.5 (London [36, p. 156]). Es sei A = (a_{ij}) ∈ Ω_{n} eine Matrix mit minimaler Permanente. Dann gilt für alle i und j

per A(i|j) ≥ per A. (3.8)

Ist a_{ij} > 0, dann gilt in (3.8) das Gleichheitszeichen.

Eine Gegenüberstellung beider Beweise enthalten die schönen Übersichtsartikel von Lagarias [31], van Lint [35] und Minc [49]. Wir begnügen uns hier mit einer modifizierten Fassung des Beweises von Egoryčev (siehe Schrijver [60, pp. 117 - 118]).

Satz 3.6 (Falikman [15, p. 932]; Egoryčev [14, p. 66]). Für alle A ∈ Ω_{n} gilt

per A ≥ \frac{n!}{n^{n}} . (3.9)

Beweis: Es sei im folgenden A = (B, x, y) ∈ Ω_{n} stets eine Matrix mit minimaler Permanente, wobei B eine n × (n − 2)-Matrix ist und x = (x_{1}, …, x_{n})^{T} sowie y = (y_{1}, …, y_{n})^{T} Spaltenvektoren sind. Entwickelt man per (B, x, x) nach der letzten Spalte, dann erhält man mit Satz 3.5

per (B, x, x) = ∑_{i=1}^{n} x_{i} per (B, x, e^{(i)}) ≥
≥ ∑_{i=1}^{n} x_{i} per (B, x, y) =
= per (B, x, y)

aufgrund der Doppeltstochastizität, wobei e^{(i)} = (0, …, 1, …, 0)^{T} ist mit 1 an der i-ten Stelle. Analog erhält man

per (B, y, y) ≥ per (B, x, y),

also

(3.10) [per (B, x, y)]^{2} ≤ per (B, x, x) per (B, y, y).

Andererseits folgt aus Satz 3.4

(3.11) [per (B, x, y)]^{2} ≥ per (B, x, x) per (B, y, y).

Nach Satz 3.1 ist nun per (B, x, y) > 0, und somit folgt aus (3.10) und (3.11)

(3.12) per (B, x, x) = per (B, y, y) = per (B, x, y).

Daraus folgt wiederum

per (B, \frac{x+y}{2}, \frac{x+y}{2}) = \frac{1}{4} per (B, x, x) + \frac{1}{2} per (B, x, y) +
+ \frac{1}{4} per (B, y, y) =
= per (B, x, y).

(3.13)

Da die Matrix (B, \frac{x+y}{2}, \frac{x+y}{2}) doppeltstochastisch ist, besitzt sie somit ebenfalls minimale Permanente. Es sei nun die Matrix A = (a_{ij}) so gewählt, daß

Φ(A) = ∑_{i,j} a_{ij}^{2}

möglichst klein ist. (Dies ist stets möglich, da die Menge Ω_{n} aufgrund des Satzes von Birkhoff [6, p. 147] kompakt ist.) Angenommen, es sei A ≠ J_{n}. Dann sind ohne Beschränkung der Allgemeinheit die letzten zwei Spalten von A = (B, x, y) verschieden. Da A minimale Permanente besitzt, ist dies nach der obigen Rechnung auch bei Ã = (B, \frac{x+y}{2}, \frac{x+y}{2}) der Fall, jedoch gilt (wie man leicht nachprüft) wegen x ≠ y Φ(Ã) < Φ(A) im Widerspruch zur Minimalität von Φ(A). Somit ist A = J_{n} und per (A) = \frac{n!}{n^{n}} . □

Egoryčev konnte darüber hinaus die Eindeutigkeit der Matrix J_{n} zeigen:

Satz 3.7 (Egoryčev [14, p. 66]). In (3.9) gilt das Gleichheitszeichen genau dann, wenn A = J_{n} ist.

Beweis: Es genügt zu zeigen, daß die Bedingung notwendig ist. Wir nehmen an, es gäbe eine Matrix A ∈ Ω_{n} mit per (A) = n! n^{−n}, jedoch A ≠ J_{n}. Ferner sei A so gewählt, daß die Anzahl der verschwindenden Matrizenelemente von A möglichst klein ist. Sind mindestens n − 1 Spalten von A positiv, dann dürfen wir ohne Beschränkung der Allgemeinheit annehmen, daß A = (B, x, y) mit B und x positiv und x ≠ y ist. Dann folgt aus (3.12) die Gleichheit in (3.7). Nach der Gleichheitsbedingung in Satz 3.4 ist dies äquivalent dazu, daß y = λx für ein geeignetes λ gilt. Aufgrund der Doppeltstochastizität von A muß λ = 1 gelten, also x = y sein im Widerspruch zur Annahme. Somit ist A = J_{n}. Besitzt A höchstens n − 2 positive Spalten, dann dürfen wir A in der Gestalt A = (B, x, y) annehmen, so daß nicht alle Spalten von B positiv sind und ferner y mindestens eine verschwindende Komponente besitzt, wo die entsprechende Komponente von x positiv ist. Gemäß (3.13) ist (B, \frac{x+y}{2}, \frac{x+y}{2}) wiederum eine Matrix mit minimaler Permanente, welche zwar von J_{n} verschieden ist, aber mindestens eine Null weniger enthält als A , womit wiederum ein Widerspruch vorliegt. Also ist auch hier A = J_{n}. □

Mithilfe des entscheidenden Satzes 3.4 konnte mittlerweile ein weiteres Problem erfolgreich behandelt werden:

Satz 3.8 (Friedland [18, p. 120]). Es sei A ∈ Ω_{n} und es bezeichne σ_{k}(A) die Summe aller k-reihigen Unterpermanenten von A. Dann gilt für alle 2 ≤ k ≤ n und A ≠ J_{n}

σ_{k}(A) > σ_{k}(J_{n}). (3.14)

Dies bestätigt eine Vermutung von Tverberg [65, p. 26] (Tverberg bewies (3.14) für k = 2 und k = 3). Offensichtlich handelt es sich dabei um eine Verallgemeinerung der Vermutung von van der Waerden, welche man für k = n erhält.

4. Untere Schranken für Permanenten

Es wurde bereits erwähnt, daß die explizite Berechnung von Permanenten im allgemeinen ein schwieriges Problem darstellt. Daher sind Schranken für Permanenten, ausgedrückt durch leicht zu berechnende Funktionen (beispielsweise Zeilensummen), von großer Wichtigkeit. Da für beliebige Matrizen keine scharfen Abschätzungen zu erwarten sind, werden wir uns hier auf einige wichtige Klassen von Matrizen beschränken. Im vorliegenden Abschnitt soll die Frage nach unteren Schranken für Permanenten dieser Matrizen behandelt werden.

4.1. (0,1)-Matrizen. Die große kombinatorische Bedeutung von Permanenten auf der Menge der (0, 1)-Matrizen wird in der Arbeit von Herrn Seifter gebührend herausgestellt. Wir beginnen mit dem

Satz 4.1 (Hall [21, p. 923]). Es sei A eine n × n-(0,1)-Matrix mit mindestens k ≤ n Einsen je Zeile und es sei per A > 0. Dann gilt

per A ≥ k!. (4.1)

Man beachte in Satz 4.1 die Zusatzbedingung per A > 0. Ohne sie blieben die unteren Schranken unscharf, da der Wert der Permanente wesentlich von der Anordnung der Nullen abhängt und erst in zweiter Linie von der Anzahl der Einsen je Zeile. In der Tat kann die Permanente einer n × n-(0,1)-Matrix mit n(n − 1) positiven Elementen verschwinden (Vorliegen einer Nullspalte). Für die Behandlung weiterer Ergebnisse ist es nützlich, folgende Bezeichnungen einzuführen. Es sei α = (α_{1}, …, α_{n}) ein n-Tupel reeller Zahlen. Dann bezeichne α^{∗} = (α_{1}^{∗}, …, α_{n}^{∗}) jenes n-Tupel, welches man durch Anordnung der Komponenten von α in der Reihenfolge α_{1}^{∗} ≥ … ≥ α_{n}^{∗} erhält, und es bezeichne α′ = (α′_{1}, …, α′_{n}) jenes n-Tupel, welches man durch Anordnung der Komponenten von α in der Reihenfolge α′_{1} ≤ … ≤ α′_{n} erhält. Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann bezeichne \overline{A} jene n × n-(0,1)-Matrix, in deren i-ter Zeile die ersten r_{i} Elemente 1 sind und die restlichen n − r_{i} Elemente 0 (i = 1, …, n). Beispielsweise hat für

A = [ \begin{matrix}1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \end{matrix} ] . (4.2)

\overline{A} die Gestalt

\overline{A} = [ \begin{matrix}1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{matrix} ] . (4.3)

Satz 4.2 (Jurkat-Ryser [22, p. 26]; Minc [43, pp. 1129 - 1130]). Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann gilt

per A ≥ ∏_{i=1}^{n} max (0, r_{i} + i − n). (4.4)

Für per A > 0 tritt Gleichheit in (4.4) genau dann auf, wenn es eine n × n-(0,1)- Permutationsmatrix P gibt mit AP = \overline{A}.

Leider liefert Satz 4.2 keine guten Schranken. Treten nämlich in der i-ten Zeile mindestens i Nullen auf, dann verschwindet das Produkt auf der rechten Seite der Ungleichung (4.4) und die Aussage wird trivial. Jedoch ist eine Verbesserung mithilfe einer einfachen Überlegung möglich. Da die Permanentenfunktion unverändert gegenüber Zeilenvertauschungen bleibt, kann man diese gerade so vornehmen, daß die Zeilensummen in nichtaufsteigender Reihenfolge angeordnet sind.

Satz 4.3 (Minc [45, p. 503]). Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann gilt

per A ≥ ∏_{i=1}^{n} max(0, r_{i}^{∗} + i − n). (4.5)

(Gleichheitsbedingung wie in Satz 4.2.)

Daß die Abschätzung (4.5) besser als (4.4) ist, geht hervor aus dem folgenden

Hilfssatz (Minc [45, p. 503]). Es seien r_{1}, …, r_{n} nichtnegative ganze Zahlen ≤ n. Dann gilt

∏_{i=1}^{n} max (0, r_{i}^{∗} + i − n) ≥ ∏_{i=1}^{n} max (0, r_{i} + i − n). (4.6)

In (4.6) tritt Gleichheit genau dann auf, wenn entweder die linke Seite verschwindet oder r_{i}^{∗} = r_{i} für alle i = 1, …, n gilt.

Jene n×n-(0,1)-Matrizen, welche genau k Einsen je Zeile und Spalte besitzen, verdienen besonderes Interesse; wir bezeichnen die Menge dieser Matrizen mit Λ_{n}^{k}. Für A ∈ Λ_{n}^{k} ist offenbar \frac{1}{k}A ∈ Ω_{n}; somit gilt nach Satz 3.6

per A ≥ n! (\frac{k}{n})^{n} (4.7)

aufgrund der Multilinearität der Permanente. Da die Matrizen in Λ_{n}^{k} in jeder Zeile und Spalte n − k Nullen enthalten, ist eine Verbesserung der Abschätzung (4.7) zu erwarten. In der Tat folgt aus Minc [46, p. 72, Problem 19] für alle A ∈ Λ_{n}^{2}

per A ≥ 2. (4.8)

Im Fall k = 3 ist es gelungen, eine wesentlich bessere Schranke zu finden:

Satz 4.4 (Voorhoeve [66, p. 85]). Für alle A ∈ Λ_{n}^{3} gilt

per A ≥ 6 · (\frac{4}{3})^{n−3} . (4.9)

Leider läßt sich die von Voorhoeve benützte Beweismethode nicht auf n > 3 ausdehnen. Wir definieren nun μ_{k}(n) durch

μ_{k}(n) = min_{A∈Λ_{n}^{k}}(per A). (4.10)

Satz 4.5 (Schrijver-Valiant [59, p. 426]).

μ_{k}(n) ≤ k^{2n}\binom{nk}{n}^{−1}. (4.11)

Eine Folgerung aus diesem Satz betrifft die bei der Behandlung des n-dimen-sionalen Dimerenproblems wichtige Größe

θ_{k} = lim_{n→∞} ^{n} \sqrt{μ_{k}(n)}. (4.12)

Mithilfe der Stirlingschen Formel erhält man aus (4.11) unmittelbar

θ_{k} ≤ \frac{(k − 1)^{k−1}}{k^{k−2}} . (4.13)

Die Tatsache, daß für k = 1, 2, 3 (in letzterem Fall unter Verwendung von Satz 4.4) die Gleichheit in (4.13) bewiesen werden kann, veranlaßte Schrijver und Valiant zu der folgenden

Vermutung.

θ_{k} = \frac{(k − 1)^{k−1}}{k^{k−2}} . (4.14)

4.2. Beliebige nichtnegative Matrizen. Von grundlegender Bedeutung für die kombinatorische Matrizentheorie ist der

Satz 4.6 (Frobenius [19, p. 274]; Kőnig [27, p. 169]). Es sei A eine nichtnegative n × n-Matrix. Dann gilt

per A > 0 (4.15)

genau dann, wenn A keine s×(n−s+1)-Null-Untermatrix enthält (s = 1, …, n− 1).

Nähere Informationen über die Matrix A erlauben es, Verbesserungen von (4.15) anzugeben. Für eine positive n × n-Matrix A = (a_{ij}) definieren wir a = min_{i,j}(a_{ij}). Wegen a_{ij} > 0 für alle i und j ist dann a > 0 und es gilt offensichtlich

per A ≥ n! a^{n}. (4.16)

Gleichheit gilt in (4.16) genau dann, wenn a_{ij} = a ist für alle i und j. Da bei der Bildung der Diagonalprodukte stets Matrizenelemente aus verschiedenen Zeilen und Spalten genommen werden, genügt es für unseren Zweck, das jeweils kleinste Element in jeder Zeile zu wählen, wodurch sich (4.16) verbessert zu

per A ≥ n! ∏_{i=1}^{n} a_{in}^{∗}. (4.17)

Gleichheit gilt in (4.17) genau dann, wenn alle Zeilen kollinear zum Vektor (1, …, 1) sind. Eine weitere, wesentliche Verbesserung von (4.17) enthält der

Satz 4.7 (Jurkat-Ryser [22, p. 26]; Minc [44, p. 234]). Es sei A = (a_{ij}) eine nichtnegative n × n-Matrix. Dann gilt

per A ≥ ∏_{i=1}^{n} ∑_{t=1}^{i} a′_{it}. (4.18)

Ist A positiv, dann tritt in (4.18) Gleichheit genau dann auf, wenn die ersten n − 1 Zeilen von A kollinear zum Vektor (1, …, 1) sind.

Satz 4.7 besagt also, daß per A nicht übertroffen wird vom Produkt des kleinsten Elements in der ersten Zeile mit der Summe der zwei kleinsten Elemente in der zweiten Zeile und so fort. Macht man sich wiederum die Invarianz der Permanente gegenüber Zeilenvertauschungen zunutze, dann kann man die rechte Seite von (4.18) ersetzen durch das Maximum dieser Ausdrücke über alle Permutationen der Zeilenindizes. Auf die Erwähnung weiterer möglicher Verschärfungen sei hier verzichtet. Wir verweisen diesbezüglich auf Minc [44].

4.3. (1,-1)-Matrizen. Als einzige Klasse von Matrizen, in welchen auch negative Elemente auftreten können, wollen wir jene der n × n-(1, −1)-Matrizen näher betrachten. Die Menge dieser Matrizen werde mit Γ_{n} bezeichnet. Eine wichtige Teilmenge von Γ_{n} bilden die Hadamard-Matrizen H (HH^{T} = nI). Beim Studium von Permanenten auf Γ_{n} kann man sich auf den Absolutbetrag beschränken. Ist nämlich die Permanente einer Matrix A ∈ Γ_{n} negativ, dann erhält man durch Multiplikation einer Zeile von A mit dem Faktor −1 eine Matrix A′ ∈ Γ_{n} mit

per A′ = −per A > 0 (4.19)

aufgrund der Multilinearität. Als erster befaßte sich Wang [68] mit der Frage, wann |per A| für A ∈ Γ_{n} den Minimalwert 0 tatsächlich annimmt.

Satz 4.8 (Wang [68, p. 257]). Es sei n ≥ 2 von der Form n = 2k oder n = 4k + 1 für k ∈ N. Dann gibt es stets eine Matrix A ∈ Γ_{n} mit

per A = 0. (4.20)

Wang konstruiert in seinem Beweis folgende Beispiele:

A = [ 1 −1 1 … 1 −1 ; 1 ; ⋮ ; ⋮ J^{(n−1)} ; ⋮ ; 1 ] (4.21)

für n = 2k und

A = \begin{matrix}k & \{ \\ 3k & \{ \end{matrix}[ 1 1 … 1 −1 … −1 ; 1 ; ⋮ ; 1 ; −1 J^{(n−1)} ; ⋮ ; −1 ]^{^{2k+1} ^{2k−1}} (4.22)

für n = 4k + 1, wobei J^{(n)} ∈ Γ_{n} jene Matrix ist, deren Elemente alle 1 sind. Für n = 4k + 3, k ∈ N_{0}, konnte Wang keine Antwort auf das zur Diskussion stehende Problem geben (ausgenommen n = 3). Mittlerweile ist es aber gelungen, für spezielle n von dieser Bauart ein Teilresultat zu erzielen.

Satz 4.9 (Simion-Schmidt [62, p. 107]; Kräuter-Seifter [29, p. 59]). Es sei n = 2^{k} − 1 für k ∈ N. Dann gilt für alle Matrizen A ∈ Γ_{n}

|per A| > 0. (4.23)

Der erste offene Fall wäre demnach n = 11. Satz 4.9 legt unmittelbar die Frage nach dem Minimum von |per A| für die dort betrachteten n nahe. Eine allgemeine Antwort ist noch ausständig, doch gestatten die bisher untersuchten Fälle k = 1, 2, 3 die (unveröffentlichte)

Vermutung. Es sei n = 2^{k} − 1 für k ∈ N. Dann gilt

(4.24)  min_{A∈Γ_{n}} |per A| = 2^{n−[log_{2} n]−1}.

5. Obere Schranken für Permanenten

5.1. (0,1)-Matrizen.

Satz 5.1 (Minc [42, p. 790]). Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann gilt

per A ≤ ∏_{i=1}^{n} \frac{r_{i} + 1}{2}. (5.1)

Gleichheit gilt in (5.1) genau dann, wenn A eine Permutationsmatrix ist.

Minc äußerte überdies eine Vermutung, deren Beweis zehn Jahre später von Brėgman erbracht wurde und welche wir aus diesem Grund gleich als Satz formulieren:

Satz 5.2 (Brėgman [8, p. 30]). Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann gilt

per A ≤ ∏_{i=1}^{n} (r_{i}!)^{1/r_{i}}. (5.2)

Gleichheit tritt in (5.2) genau dann ein, wenn es n × n-Permutationsmatrizen P und Q gibt, so daß P AQ direkte Summe von Matrizen J^{(ν_{k})} (k = 1, …, t; ν_{1} + … + ν_{t} = n) ist.

Die Verschärfung gegenüber (5.1) folgt aus der Ungleichung für das arithmetische und geometrische Mittel für die ersten r_{i} natürlichen Zahlen. Auch in diesem Unterabschnitt wollen wir einen Blick auf die Menge Λ_{n}^{k} werfen. Aus Satz 5.2 folgt für A ∈ Λ_{kt}^{k} unmittelbar

per A ≤ (k!)^{t}. (5.3)

Damit ist auch eine Vermutung von Ryser [57, p. 458] gezeigt. In den Fällen n ≢ 0 (mod k) konnte eine Verschärfung von (5.2) für k = 2 und k = 3 erzielt werden.

Satz 5.3 (Merriell [41, passim]). Für alle A ∈ Λ_{2t+1}^{2} gilt

per A ≤ 2^{t} (5.4)

und für alle A ∈ Λ_{3t+i}^{3} gilt

(5.5)  per A ≤ \{ \begin{matrix}6^{t−1} · 9,  falls & i = 1, \\ [6^{t−2} · 9^{2}] , falls & i = 2. \end{matrix}

Die in Satz 5.3 angegebenen Schranken sind bestmöglich. Ist nämlich J^{(n)} die n×n-Matrix, deren Elemente sämtlich 1 sind, und ist K_{n} wie in (1.7) erklärt, dann gilt Gleichheit in (5.4) und (5.5) für die Matrizen J^{(2)}⊕…⊕J^{(2)}⊕K_{3} (J^{(2)} (t−1)- mal) beziehungsweise J^{(3)} ⊕ … ⊕ J^{(3)} ⊕ K_{4} (J^{(3)} (t − 1)-mal) beziehungsweise J^{(3)} ⊕ … ⊕ J^{(3)} ⊕ K_{4} ⊕ K_{4} (J^{(3)} (t − 2)-mal). Für n > 3 gibt es lediglich vermutete Schranken.

5.2. Beliebige nichtnegative Matrizen. In Abschnitt 3 wurde das Minimum der Permanente auf der Menge der doppeltstochastischen Matrizen bestimmt. Im Gegensatz zu diesem läßt sich das Maximum sehr leicht bestimmen.

Satz 5.4 (Marcus-Newman [37, pp. 61 - 62]). Für alle A ∈ Ω_{n} gilt

per A ≤ 1. (5.6)

Gleichheit tritt in (5.6) genau dann auf, wenn A eine Permutationsmatrix ist.

Eine Verallgemeinerung auf beliebige nichtnegative Matrizen bietet das folgende Analogon zu Satz 4.7.

Satz 5.5 (Jurkat-Ryser [22, p. 26]; Minc [44, p. 234]). Es sei A = (a_{ij}) eine nichtnegative n × n-Matrix. Dann gilt

per A ≤ ∏_{i=1}^{n} ∑_{t=1}^{i} a_{it}^{∗}. (5.7)

Ist A positiv, dann besteht in (5.7) Gleichheit genau dann, wenn die ersten n − 1 Zeilen von A kollinear zum Vektor (1, …, 1) sind.

Mit der gleichen Begründung wie in der Bemerkung nach Satz 4.7 kann man die rechte Seite von (5.7) ersetzen durch das Minimum dieser Ausdrücke über alle Permutationen der Zeilenindizes. Es sei A = (a_{ij}) wiederum eine nichtnegative n×n-Matrix mit den Zeilensummen r_{1}, …, r_{n} und den Spaltensummen s_{1}, …, s_{n}. Dann gilt

per A ≤ ∏_{i=1}^{n} r_{i} (5.8)

und

per A ≤ ∏_{i=1}^{n} s_{i}, (5.9)

da auf der rechten Seite von (5.8) und (5.9) im allgemeinen überflüssige Terme auftreten. Aus diesen Ungleichungen folgt schließlich

per A ≤ min (∏_{i=1}^{n} r_{i}, ∏_{i=1}^{n} s_{i}) , (5.10)

was sich in folgender Weise verbessern läßt:

Satz 5.6 (Jurkat-Ryser [23, p. 354]). Es sei A eine nichtnegative n × n-Matrix mit den Zeilensummen r_{1}, …, r_{n} und den Spaltensummen s_{1}, …, s_{n}. Dann gilt

per A ≤ ∏_{i=1}^{n} min (r′_{i}, s′_{i}). (5.11)

Diese Abschätzung ist bestmöglich: Es sei A = (a_{ij}) eine Matrix, die den Voraussetzungen von Satz 5.6 genügt. Ferner enthalte jede (rechteckige) Untermatrix von A eine Zeile oder Spalte mit höchstens einem positiven Element und es gelte a_{ii} = min (r′_{i}, s′_{i}) für i = 1, …, n. Dann tritt in (5.11) Gleichheit auf.

5.3. (1,–1)-Matrizen. Auf der Menge Γ_{n} der n × n-(1, −1)-Matrizen ist das Maximum des Absolutbetrages der Permanente klarerweise durch n! gegeben; diese Schranke wird beispielsweise für die Matrix J^{(n)} erreicht. Wang [68, p. 360] stellte unter anderem die Frage nach scharfen oberen Schranken für den Fall, daß die betrachteten Matrizen in Γ_{n} nichtsingulär sind. Diesem Problem werden wir uns nun widmen. Dabei spielen drei spezielle Matrizen aus Γ_{n} eine wichtige Rolle:

D_{n} = [ \begin{matrix}−1 & 1 & … & 1 \\ 1 & ... & ... & ⋮ \\ ⋮ & ... & ... & 1 \\ 1 & … & 1 & −1 \end{matrix} ] , (5.12)

C_{n} = [ \begin{matrix}1 & 1 & … & 1 \\ 1 & −1 & ... & ⋮ \\ ⋮ & ... & ... & 1 \\ 1 & … & 1 & −1 \end{matrix} ] , (5.13)

S_{n} = [ \begin{matrix}1 & −1 & … & −1 \\ ⋮ & ... & ... & ⋮ \\ ⋮ & & ... & −1 \\ 1 & … & … & 1 \end{matrix} ] . (5.14)

Satz 5.7.

ω_{n} := per D_{n} = ∑_{k=0}^{n} \frac{n!}{k!} (−2)^{k}. (5.15)

ϑ_{n} := per C_{n} = (n + 2) ∑_{k=0}^{n−1} \frac{(n − 1)!}{k!} (−2)^{k} + (−2)^{n}. (5.16)

Die Beziehungen (5.15) und (5.16) folgen unmittelbar aus einem Satz von Perfect [54, p. 236] über die Anzahl positiver Diagonalprodukte in Matrizen der zur Diskussion stehenden Gestalt.

Satz 5.8 (Kräuter-Seifter [29, p. 57]).

\{ \begin{matrix}per S_{2n−1} & = & 2^{2n−1}(2^{n} − 1)B_{2n}/n, \\ per S_{2n} & = & 0, \end{matrix} (5.17)

wobei B_{n} die n-te Bernoulli-Zahl bezeichnet.

Die Herleitung dieses Ergebnisses erfordert die Kenntnis des Hit-Polynoms (Riordan [56, p. 165]) und der exponentiell erzeugenden Funktion für Euler-Polynome (Abramowitz-Stegun [1, p. 804]). Bemerkenswert ist, daß die Folge ⟨τ_{n}⟩ mit τ_{n} = |per S_{n}| gerade die Tangensfunktion als exponentiell erzeugende Funktion besitzt, das heißt

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

wenn man noch τ_{0} = 0 definiert (Abramowitz-Stegun [1, p. 75]). Die τ_{n} werden aufgrund dieses Zusammenhangs in der einschlägigen Literatur Tangens-Zahlen genannt (Comtet [12, p. 259]). Zwei Matrizen A, B ∈ Γ_{n} mögen zueinander äquivalent heißen (A ∼ B), falls B aus A durch Hintereinanderausführung von Transformationen der folgenden Art hervorgeht:

(a) Vertauschen von Zeilen und Spalten;

(b) Transponieren;

(c) Multiplizieren von Zeilen oder Spalten mit dem Faktor −1. Insbesondere gilt für zwei zueinander äquivalente Matrizen A, B ∈ Γ_{n}

|per A| = |per B|. (5.19)

Eine detaillierte Betrachtung der eingangs erwähnten Fragestellung für n ≤ 5 liefert zunächst die Beziehung

|per A| ≤ ϑ_{5} = 24 (5.20)

für alle nichtsingulären A ∈ Γ_{5}. Gleichheit tritt in (5.20) genau dann auf, wenn A ∼ C_{5} gilt. Ferner haben wir

|per A| ≤ ω_{5} = 8 (5.21)

für alle nichtsingulären A ∈ Γ_{5} mit A ≁ C_{5} und A ≁ S_{5}. Entgegen

16 = τ_{5} > ω_{5} = 8 (5.22)

kann mithilfe von Satz 5.8 gezeigt werden, daß für alle n ≥ 6

τ_{n} < ω_{n} (5.23)

gilt, sodaß die für n = 5 erforderliche Zusatzbedingung A ≁ S_{5} für den Nachweis der Gültigkeit von (5.21) entfallen kann. Schließlich gelangt man zu zwei Vermutungen (Kräuter-Seifter [30]).

Vermutung 1. Es sei A ∈ Γ_{n} nichtsingulär, n ≥ 5. Dann gilt

|per A| ≤ ϑ_{n}, (5.24)

wobei das Gleichheitszeichen genau dann zutrifft, wenn A ∼ C_{n} gilt.

Vermutung 2. Es sei A ∈ Γ_{n} nichtsingulär mit A ≁ C_{n}, n ≥ 6. Dann gilt

|per A| ≤ ω_{n}. (5.25)

Eine Charakterisierung des Gleichheitsfalles in (5.25) ist nicht bekannt. Ein allgemeiner Beweis dieser Vermutungen dürfte ziemlich schwierig sein, da die Nichtsingularität (eine über die Determinante definierte Eigenschaft!) zuwenig Informationen über die Struktur der Matrix liefert, deren Permanente berechnet werden soll. Im Rahmen eines allgemeinen Satzes konnte aber folgendes gezeigt werden:

Satz 5.9 (Kräuter-Seifter [30]). Die Vermutungen 1 und 2 sind richtig für alle in Frage kommenden Matrizen mit höchstens zwei negativen Elementen je Zeile und Spalte sowie für alle dazu äquivalenten Matrizen.

6. Andere Problemkreise

In diesem Abschnitt werden neuere Ergebnisse der Permanententheorie besprochen, welche sich nicht unmittelbar in die bereits behandelten Themen einordnen lassen.

In [46, p. 155] führt Minc als älteste unbewiesene Permanenten-Vermutung jene von Scott [61] aus dem Jahr 1881 an. Nach rund einhundert Jahren haben drei Autoren unabhängig voneinander einen Beweis dafür gefunden.

Satz 6.1 (Minc [48, p. 145]; Kittappa [24, p. 75]; Svrtan [63, p. 204]). Es sei A = (a_{ij}) eine n × n-Matrix mit a_{ij} = (x_{i} − y_{j})^{−1}, wobei x_{1}, …, x_{n} und y_{1}, …, y_{n} die verschiedenen Lösungen der Gleichungen x^{n}−1 = 0 beziehungsweise y^{n} + 1 = 0 sind. Dann gilt

(6.1) |per A| = \{ \begin{matrix}n · 2^{−n}[1 · 3 · 5 · . . . · (n − 2)]^{2} & für ungerades n, \\ 0 & für gerades n. \end{matrix}

Die entscheidende Grundlage aller drei Beweise ist der

Satz 6.2 (Borchardt [7, p. 194]). Es sei A = (a_{ij}) eine n × n-Matrix mit a_{ij} = (x_{i} − y_{j})^{−1}, wobei x_{1}, …, x_{n}, y_{1}, …, y_{n} komplexe Zahlen bezeichnen. Dann gilt

(6.2) det A per A = det (A ∗ A),

wobei ∗ das Hadamard-Produkt zweier Matrizen bezeichnet.

Den kürzesten Beweis erbrachte Svrtan. Da er zudem den Vorteil besitzt, mit elementaren algebraischen Hilfsmitteln auszukommen, soll er hier skizziert werden. Es seien G und H die Mengen der n-ten Wurzeln von +1 beziehungsweise −1 und es sei ε ∈ H beliebig, aber fest gewählt. Aufgrund der vollständigen Symmetrie der Permanente in den Zeilen und Spalten des Arguments darf man annehmen, daß die Elemente aus G aund H von der Gestalt

\{ \begin{matrix}x_{i} & = & α^{i} & (i = 1, …, n), \\ y_{j} & = & εα^{j} & (j = 1, …, n) \end{matrix} (6.3)

sind, wobei α eine beliebige primitive n-te Einheitswurzel ist. Führt man nun die Bezeichnungen D_{1} = det A und D_{2} = det (A ∗ A) ein, dann kann man unter Betrachtung spezieller, aus den Termen (1 − εα^{k})^{−ν} zusammengesetzter zirkulanter Matrizen zeigen, daß

D_{ν} = (−1)^{(n−1)ν} ∏_{k=1}^{n} f_{ν}(x_{k}) (6.4)

mit

f_{ν}(x_{k}) = ε^{−k} ∑_{h∈H} ∑_{j=0}^{k} (−1)^{j}\binom{k}{j}(1 − h)^{j−ν} (6.5)

für ν = 1 und ν = 2 gilt. Spaltet man die innere Summe in (6.5) entsprechend j ≤ ν − 1 und j ≥ ν in zwei Teile auf und berücksichtigt man die Tatsache, daß

∑_{h∈H} h^{t} = \{ \begin{matrix}n & für t = 0, \\ 0 & für 0 < t < n \end{matrix} (6.6)

ist, dann erhält man aus (6.5)

f_{ν}(x_{k}) = ε^{−k} ∑_{j=0}^{ν−1} (−1)^{j}\binom{k}{j} \{ ∑_{h∈H} (1 − h)^{j−ν} − n\} . (6.7)

Damit sowie mit

∑_{h∈H} (1 − h)^{−1} = \frac{n}{2},  ∑_{h∈H} (1 − h)^{−2} = \frac{n(2 − n)}{4} (6.8)

folgt über (6.4) die Darstellung

D_{ν} = \{ \begin{matrix}−(\frac{n}{2})^{n} ∏_{k=1}^{n} ε^{−k} & für ν = 1, \\ (−\frac{n}{4})^{n} ∏_{k=1}^{n} ε^{−k}(n − 2k + 2) & für ν = 2. \end{matrix} (6.9)

Wegen D_{1} ≠ 0 folgt schließlich aus Satz 6.2 (D_{1} per A = D_{2})

per A = (−1)^{n−1}2^{−n} ∏_{k=1}^{n} (n − 2k + 2) (6.10)

und daraus (6.1).

1967 äußerten Marcus und Minc [40, p. 306] die folgende

Vermutung. Es sei n ≥ 2. Dann gilt für alle S ∈ Ω_{n}

per S ≥ per (\frac{nJ_{n} − S}{n − 1} ) . (6.11)

Ist n ≥ 4, dann gilt in (6.11) das Gleichheitszeichen genau dann, wenn S = J_{n} gilt.^{1}

Wie die erwähnten Autoren zeigten, folgt aus dieser Vermutung jene von van der Waerden. Während letztere mittlerweile bewiesen werden konnte (siehe Abschnitt 3), konnten in bezug auf die obige Behauptung bisher nur Teilresultate hergeleitet werden. Marcus und Minc [40, pp. 307 - 308] gaben Beweise für hinreichend nahe bei J_{n} liegende sowie für positiv semidefinite symmetrische S ∈ Ω_{n}, Wang [69, p. 147] für n = 3 und Foregger [16, p. 125] für n = 4. In seiner vor kurzem erschienenen Arbeit [11] wies Chang die Gültigkeit von (6.11) im Komplement einer Umgebung von J_{n} nach.

Satz 6.3 (Chang [11, p. 116]). Es sei f(S) = per ((nJ_{n} − S)/(n − 1)) für S ∈ Ω_{n} und es sei k_{n} = d_{n}(n − 1)^{−n}, wobei d_{n} die n-te Dérangement-Zahl bezeichnet. Dann gilt

max_{S∈Ω_{n}} (f(S)) = f(I) = k_{n}. (6.12)

Ist n ≥ 2 und ist per S ≥ k_{n} für S ∈ Ω_{n}, dann gilt (6.11).

Nach Satz 6.3 ist h_{n} := min_{S∈Ω_{n}}(per S) = n! n^{−n}; die Gültigkeit der Vermutung ist also nur mehr für h_{n} ≤ per S < k_{n} ungeklärt. Diese Lücke wird für wachsendes n stets kleiner: aus (1.11) folgt nämlich d_{n} ∼ n!/e und damit |k_{n} − h_{n}| → 0 für n → ∞. Es sei U = (nJ_{n} − I)/(n − 1); dann gilt für alle S ∈ Ω_{n} (nJ_{n} − S)/(n − 1) = SU und (6.11) läßt sich schreiben in der Form

per S ≥ per SU. (6.13)

Chang verwendet im Beweis von Satz 6.3 eine wahrscheinlichkeitstheoretische Interpretation der Permanente einer doppeltstochastischen Matrix nach H. L. Harper (siehe Wilf [70, pp. 249 - 250]): Wir betrachten n Kugeln und n Schachteln. Der Vektor (r_{1}, …, r_{n}) bezeichne das Ereignis, daß sich in der Schachtel m_{j} gerade r_{j} Kugeln befinden (j = 1, …, n), wobei (m_{1}, …, m_{n}) eine Permutation von (1, …, n) ist. Bezeichnet man bei einem simultanen Übergang T_{A} aller n Kugeln die Wahrscheinlichkeit, daß eine Kugel von der Schachtel i zur Schachtel j wechselt, mit a_{ij}, dann ist A = (a_{ij}) eine doppeltstochastische Matrix. Ist nun p_{A}(r_{1}, …, r_{n}) die Wahrscheinlichkeit, daß das Ereignis (r_{1}, …, r_{n}) nach dem Übergang T_{A} auftritt, wobei der Anfangszustand (1, …, 1) war, dann gilt

1Die in [40] ursprünglich für n ≥ 3 formulierte Gleichheitsbedingung wurde für n = 3 von Wang [69] als falsch erkannt.

p_{A}(1, …, 1) = per A. (6.14)

Bezeichnet ferner q_{A}(r_{1}, …, r_{n}) die Wahrscheinlichkeit, daß das Ereignis (1, …, 1) nach dem Übergang T_{A} auftritt, wobei der Anfangszustand (r_{1}, …, r_{n}) war, dann erhält man mithilfe wahrscheinlichkeitstheoretischer Überlegungen bei Summation über alle möglichen Zustände (r_{1}, …, r_{n})

per SU = ∑ p_{S}(r_{1}, …, r_{n}) q_{U}(r_{1}, …, r_{n}) (6.15)

und

q_{U}(r_{1}, …, r_{n}) ≤ q_{U}(1, …, 1) = k_{n}, (6.16)

woraus

per SU ≤ q_{U}(1, …, 1) ∑ p_{S}(r_{1}, …, r_{n}) = k_{n} (6.17)

folgt. Damit ergibt sich wegen per SU = f(S)

f(S) ≤ k_{n} = f(I). (6.18)

Für per S ≥ k_{n} folgt aus (6.13) und (6.18) sofort (6.11).

Abgesehen von verschiedenen Verallgemeinerungen der Vermutung von van der Waerden (siehe auch Satz 3.8) und den Bemühungen, sie zu beweisen, bietet das Studium der Permanente auf der Menge Ω_{n} auch anderweitig ein interessantes Betätigungsfeld (siehe [50, pp. 237 - 239]), aus welchem hier ein Teilaspekt herausgegriffen werden soll. Der Satz von Birkhoff [6, p. 147] besagt, daß Ω_{n} ein konvexes Polyeder bildet, dessen n! Ecken die n × n-Permutationsmatrizen sind. Es liegt nahe zu fragen, ob die Permanente eine konvexe Funktion auf Ω_{n} ist. Für n = 2 kann man in der Tat direkt zeigen, daß

(6.19) per (αB + (1 − α) A) ≤ α per B + (1 − α) per A für alle A, B ∈ Ω_{2} und für alle α, 0 ≤ α ≤ 1, gilt. Für n = 3 hingegen konnte Marcus ein Gegenbeispiel angeben (siehe auch Perfect [53]). In der Folge wurde versucht, entsprechende Aussagen durch geeignete Einschränkungen von B zu bekommen. Perfect [53] bewies (6.19) für B = I und α = \frac{1}{2} sowie für beliebiges A ∈ Ω_{n}. Eine Verbesserung erzielten Brualdi und Newman [9] für B = I und alle α mit 0 ≤ α ≤ 1 sowie für beliebiges A ∈ Ω_{n}. Angeregt durch ein weiteres Resultat dieser Autoren beschäftigten sich Lih und Wang [33] mit der folgenden

Vermutung. Für alle A ∈ Ω_{n} und für alle α mit \frac{1}{2} ≤ α ≤ 1 gilt

(6.20) per (αJ_{n} + (1 − α)A) ≤ α per J_{n} + (1 − α) per A.

Ein Beweis von (6.20) ist bisher nur für n = 3 geglückt; im Fall n = 4 hat man bereits mit erheblichen Schwierigkeiten zu rechnen.

Satz 6.4 (Lih-Wang [33]). Obige Vermutung ist richtig für n = 3. Das Gleichheitszeichen tritt genau dann auf, wenn entweder α = 1 ist oder A = J_{3} oder α = \frac{1}{2} und A = \frac{1}{2} (3J_{3} − I) bis auf Zeilen- oder Spaltenvertauschungen.

Da nach Satz 3.6 per B ≥ per J_{3} für alle B ∈ Ω_{3} gilt, erhält man aus Satz 6.4 unmittelbar die Beziehung

(6.21) per J_{3} ≤ per (αJ_{3} + (1 − α)A) ≤ per A

für alle A ∈ Ω_{3} und für alle α mit \frac{1}{2} ≤ α ≤ 1.

Von hermiteschen Matrizen handelt eine auf Marcus [46, p. 156] zurückgehende

Vermutung. Es sei A eine positiv semidefinite hermitesche nk × nk-Matrix, zusammengesetzt aus k^{2} Blöcken A_{ij}, welche n×n-Matrizen sind. Ferner sei B = (b_{ij}) die k × k-Matrix mit b_{ij} = per A_{ij} (i, j = 1, …, k). Dann gilt

per A ≥ per B. (6.22)

Sind alle A_{ii} positiv definit, dann gilt in (6.22) Gleichheit genau dann, wenn A die Form A = A_{11} ⊕ … ⊕ A_{kk} besitzt.

Lieb [32] bestätigte diese Vermutung für k = 2. Vor kurzem gelang es dann Pate, für symmetrische Matrizen und für hinreichend große n (bei beliebigem k) eine Ungleichung zu beweisen, welche (6.22) verschärft.

Satz 6.5 (Pate [52, p. 14]). Es sei A eine positiv semidefinite symmetrische nk × nk-Matrix von der in der obigen Vermutung angegebenen Struktur. Ferner sei C = (c_{ij}) die k × k-Matrix mit c_{ij} = |per A_{ij}| (i, j = 1, …, k). Dann gibt es für jedes k eine natürliche Zahl n_{k}, so daß für alle n ≥ n_{k} gilt:

per A ≥ per C. (6.23)

Im Beweis dieses Satzes benützt Pate die Tatsache, daß eine positiv semidefinite symmetrische m × m-Matrix stets darstellbar ist als Gramsche Matrix ((x_{i}, x_{j})) geeigneter Vektoren x_{1}, … x_{m} aus dem R^{m}, wobei (.,.) das innere Produkt im R^{m} bezeichnet. Aufgrund eines von Marcus und Newman [39, pp. 48 - 49] entdeckten fundamentalen Zusammenhangs läßt sich die Permanente einer Gramschen Matrix zurückführen auf ein inneres Produkt in der Symmetrieklasse der vollständig symmetrischen Tensoren. Auf die ziemlich komplizierten Details soll hier nicht eingegangen werden.

Wir schließen mit einigen Betrachtungen über zirkulante Matrizen. Solche Matrizen treten beispielsweise bei der Behandlung klassischer kombinatorischer Fragestellungen, wie etwa beim problème des rencontres oder beim problème des ménages, auf. P_{n} bezeichne die n × n-Permutationsmatrix mit Einsen an den Stellen (1, 2), (2, 3), …, (n − 1, n), (n, 1). Dann nennen wir eine Matrix der Form

Z = ∑_{i=0}^{n−1} λ_{i}P_{n}^{i} (6.24)

mit λ_{i} ∈ {0, 1} (i = 0, 1, …, n − 1) und P_{n}^{0} = I eine zirkulante (0, 1)-Matrix oder (wie im folgenden stets bezeichnet) Zirkulante. Der Übersicht in Minc [46, pp. 44 - 48] kann man entnehmen, daß bis vor kurzem lediglich Zirkulanten mit λ_{0} = … = λ_{k−1} = 1 und λ_{k} = … = λ_{n−1} = 0 betrachtet worden sind. Eades, Praeger und Seberry [13] haben sich mit Zirkulanten allgemeinerer Bauart beschäftigt, wobei vor allem die verschiedenen Methoden, die zur Berechnung ihrer Permanente herangezogen wurden, Beachtung verdienen. Um die Notation einfacher zu gestalten, genügt es, eine Zirkulante mit den Positionen der Einsen in ihrer ersten Zeile zu identifizieren. Ist also A = (a_{ij}) (i, j = 0, 1, …, n − 1) und gilt a_{0j_{0}} = … = a_{0j_{r}} = 1 (0 ≤ r ≤ n − 1), dann schreiben wir A = (j_{0}, …, j_{r}). Zwei Zirkulanten A = (a_{ij}) und B = (b_{ij}) mögen zueinander äquivalent heißen, wenn es Zahlen x, y ∈ {0, 1, …, n − 1} gibt, so daß ggT(x, n) = 1 und für jedes j ∈ {0, 1, …, n − 1} a_{0,xj+y} = b_{0j} gilt. Es sei A = (a_{ij}) eine n × n-Matrix und B eine k × k-Matrix. Unter dem Kronecker-Produkt A ⊗ B von A und B verstehen wir die nk × nk-Matrix, die aus den n^{2} Blöcken a_{ij}B (i, j = 0, 1, …, n − 1) zusammengesetzt ist.

Satz 6.6 (Eades-Praeger-Seberry [13, pp. 148 - 149]). Es sei A eine beliebige (0, 1)-Matrix und es bezeichne I_{ν} die ν × ν-Einheitsmatrix. Dann gilt

per (A ⊗ I_{k}) = (per A)^{k} (6.25)

und

per ((I_{k} + P_{k}) ⊗ J^{(m)}) = (m!)^{k} ∑_{j=0}^{m} \binom{m}{j}^{k}. (6.26)

Während man (6.25) unmittelbar durch geeignete Zeilen- und Spaltenvertauschungen erhält, ist für die Herleitung von (6.26) explizites Abzählen der positiven Diagonalprodukte erforderlich. Natürlich sind die in Satz 6.6 betrachteten Matrizen im allgemeinen keine Zirkulanten, doch kann man mit den dortigen Formeln folgendes herleiten. Wir betrachten eine n × n-Zirkulante mit zwei positiven Elementen je Zeile, also eine Matrix (a, b). Ist dann ggT(n, a − b) = g, dann sind (a, b) und (0, g) zueinander äquivalent und wegen (0, g) = (I_{n/g} + P_{n/g}) ⊗ I_{g} folgt

per (a, b) = (per (I_{n/g} + P_{n/g}))^{g} = 2^{g}. (6.27)

Auf ähnliche Weise erhält man für die 2k × 2k-Zirkulanten (0, 1, k, k + 1) sowie für die 3k × 3k-Zirkulanten (0, 1, k, k + 1, 2k, 2k + 1)

\{ \begin{matrix}per (0, 1, k, k + 1) & = & 2^{k+1} + 2^{2k}, \\ per (0, 1, k, k + 1, 2k, 2k + 1) & = & 2^{k+1}3^{k}(1 + 3^{k}). \end{matrix} (6.28)

Neben dem in Satz 6.6 benützten Beweisverfahren und neben der Herleitung von Rekursionsformeln für schwach besetzte Zirkulanten mithilfe des Laplaceschen Entwicklungssatzes wird noch die Methode der sogenannten komplementären Entwicklung vorgestellt, bei welcher es sich um eine besonders einfache Variante des Inklusions-Exklusions-Prinzips handelt. Es sei A = (a_{ij}) eine (0, 1)-Matrix mit a_{km} = 1; die Matrizen B und C mögen aus A hervorgehen, indem man a_{km} = 0 setzt beziehungsweise die k-te Zeile und m-te Spalte von A streicht. Aufgrund der Multilinearität der Permanente folgt dann per A = per B + per C. Damit wurden beispielsweise die Dérangement-Zahlen d_{n} = per (1, 2, …, n − 1) in Abschnitt 1 berechnet. Auf ähnliche Weise gelangt man zu den n-ten Ménage-Zahlen M_{n} = per (2, 3, …, n − 1) (siehe Ryser [58, p. 32]).

Satz 6.7 (Eades-Praeger-Seberry [13, p. 157]). Es sei n gerade und es bezeichne R_{n} die Zirkulante (1, 3, 4, …, n − 1). Dann gilt 30 a. r. kräuter

per R_{n} = M_{n} + 2. (6.29)

Aus dem im Anschluß an Satz 6.6 Gesagten folgt für ggT(n, x) = 2

per (0, 1, 2, …, x − 1, x + 1, …, n − 1) = M_{n} + 2. (6.30)

literatur^{2}

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

[2] Aleksandr Danilovič Aleksandrov, K teorii smešannych ob-emov vypuklych tel IV. Smešannye diskriminanty i smešannye ob-emy. [Zur Theorie der gemischten Volumina konvexer Körper IV. Gemischte Diskriminanten und gemischte Volumina.] Matematičeskij Sbornik (N. S.) 3, 227 - 251 (1938).

[3] Thøger Bang, On matrix-functions giving a good approximation to the v. d. Waerden permanent conjecture. Preprint, Københavns Universitet, 1979.

[4] Natália Bebiano, On the evaluation of permanents. Pacific Journal of Mathematics 101, 1 - 9 (1982).

[5] Jacques Binet, Mémoire sur un système de formules analytiques, et leur application à des considérations géométriques. Journal de l’École Polytechnique 9, Cah. 16, 280 - 354 (1813).

[6] Garrett Birkhoff, Tres observaciones sobre el algebra lineal. Revista de la Universidad Nacional de Tucumán (A) 5, 147 - 151 (1946).

[7] Carl Wilhelm Borchardt, Bestimmung der symmetrischen Verbindungen vermittelst ihrer erzeugenden Function. Journal für die reine und angewandte Mathematik 53, 193 - 198 (1855).

[8] L. M. Brėgman, Nekotorye svojstva neotricatel’nych matric i ich permanentov. [Einige Eigenschaften nichtnegativer Matrizen und ihrer Permanenten.] Doklady Akademii Nauk SSSR 211, 27 - 30 (1973). Englische Übersetzung in: Soviet Mathematics Doklady 14, 945 - 949 (1973).

[9] Richard Anthony Brualdi and Morris Newman, Inequalities for permanents and permanental minors. Proceedings of the Cambridge Philosophical Society 61, 741 - 746 (1965).

[10] Augustin Louis Cauchy, Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment. Journal de l’École Polytechnique 10, Cah. 17, 29 - 112 (1815).

[11] Derek K. Chang, A note on a conjecture of M. Marcus and H. Minc. Linear and Multilinear Algebra 13, 115 - 117 (1983).

2Hier ist nur die zitierte Literatur angegeben. Ausführliche Bibliographien, versehen mit Kurzreferaten (!), findet man in Minc [46, pp. 161 - 199], [50, pp. 250 - 262].

permanenten 31

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

[13] 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).

[14] Grigorij Petrovič Egoryčev, Dokazatel’stvo gipotezy van der Vardena dlja permanentov. [Beweis der Vermutung von van der Waerden für Permanenten.] Sibirskij Matematičeskij Žurnal 22, Nom. 6, 65 - 71 (1981). Englische Übersetzung in: Advances in Mathematics 42, 299 - 305 (1981).

[15] D. I. Falikman, Dokazatel’stvo gipotezy van der Vardena o permanente dvaždy stochastičeskoj matricy. [Beweis der Vermutung von van der Waerden über die Permanente einer doppeltstochastischen Matrix.] Matematičeskie Zametki 29, 931 - 938 (1981). Englische Übersetzung in: Mathematical Notes of the Academy of Sciences of the USSR 29, 475 - 479 (1981).

[16] Thomas Hustad Foregger, Remarks on a conjecture of M. Marcus and H. Minc. Linear and Multilinear Algebra 7, 123 - 126 (1979).

[17] Shmuel Friedland, A lower bound for the permanent of a doubly stochastic matrix. Annals of Mathematics (2) 110, 167 - 176 (1979).

[18] Shmuel Friedland, A proof of a generalized van der Waerden conjecture on permanents. Linear and Multilinear Algebra 11, 107 - 120 (1982).

[19] Georg Frobenius, Über zerlegbare Determinanten. Sitzungsberichte der Königlich-Preußischen Akademie der Wissenschaften zu Berlin, Physikalisch-Mathematische Klasse 1917, 274 - 277 (1917).

[20] Peter Murray Gibson, Conversion of the permanent into the determinant. Proceedings of the American Mathematical Society 27, 471 - 476 (1971).

[21] Marshall Hall, jr., Distinct representatives of subsets. Bulletin of the American Mathematical Society 54, 922 - 926 (1948).

[22] Wolfgang B. Jurkat and Herbert John Ryser, Matrix factorizations of determinants and permanents. Journal of Algebra 3, 1 - 27 (1966).

[23] Wolfgang B. Jurkat and Herbert John Ryser, Term ranks and permanents of nonnegative matrices. Journal of Algebra 5, 342 - 357 (1967).

[24] Rethinasamy Kittappa, Proof of a conjecture of 1881 on permanents. Linear and Multilinear Algebra 10, 75 - 82 (1981).

[25] Donald Ervin Knuth, A permanent inequality. The American Mathematical Monthly 88, 731 - 740 (1981).

[26] Dénes Kőnig, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77, 453 - 465 (1916).

[27] Dénes Kőnig, Über trennende Knotenpunkte in Graphen (nebst Anwendungen auf Determinanten und Matrizen). Acta Litterarum ac Scientiarum Szeged 6, 155 - 179 (1933).

[28] Arnold Richard Kräuter and Norbert Seifter, On convertible (0,1)-matrices. Linear and Multilinear Algebra 13, 311 - 322 (1983).

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

32 a. r. kräuter

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

[31] Jeffrey Clark Lagarias, The van der Waerden conjecture: Two Soviet solutions. Notices of the American Mathematical Society 29, 130 - 133 (1982).

[32] Elliott Hershel Lieb, Proofs of some conjectures on permanents. Journal of Mathematics and Mechanics 16, 127 - 134 (1966).

[33] Ko-Wei Lih and Edward Tzu-Hsia Wang, A convexity inequality on the permanent of doubly stochastic matrices. Congressus Numerantium 36, 189 - 198 (1982).

[34] Jacobus Hendricus van Lint, Notes on Egoritsjev’s proof of the van der Waerden conjecture. Linear Algebra and Its Applications 39, 1 - 8 (1981).

[35] Jacobus Hendricus van Lint, The van der Waerden conjecture: Two proofs in one year. The Mathematical Intelligencer 4, 72 - 77 (1982).

[36] David London, Some notes on the van der Waerden conjecture. Linear Algebra and Its Applications 4, 155 - 160 (1971).

[37] Marvin Marcus and Morris Newman, On the minimum of the permanent of a doubly stochastic matrix. Duke Mathematical Journal 26, 61 - 72 (1959).

[38] Marvin Marcus and Henryk Minc, On the relation between the determinant and the permanent. Illinois Journal of Mathematics 5, 376 - 381 (1961).

[39] Marvin Marcus and Morris Newman, Inequalities for the permanent function. Annals of Mathematics (2) 75, 47 - 62 (1962).

[40] Marvin Marcus and Henryk Minc, On a conjecture of B. L. van der Waerden. Proceedings of the Cambridge Philosophical Society 63, 305 - 309 (1967).

[41] David Merriell, The maximum permanent in Λ_{n}^{k}. Linear and Multilinear Algebra 9, 81 - 91 (1980).

[42] Henryk Minc, Upper bounds for permanents of (0,1)-matrices. Bulletin of the American Mathematical Society 69, 789 - 791 (1963).

[43] Henryk Minc, A lower bound for permanents of (0,1)-matrices. Proceedings of the American Mathematical Society 18, 1128 - 1132 (1967).

[44] Henryk Minc, Bounds for permanents of nonnegative matrices. Proceedings of the Edinburgh Mathematical Society (2) 16, 233 - 237 (1969).

[45] Henryk Minc, Rearrangements. Transactions of the American Mathematical Society 159, 497 - 504 (1971).

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

[47] Henryk Minc, Evaluation of permanents. Proceedings of the Edinburgh Mathematical Society (2) 22, 27 - 32 (1979).

[48] Henryk Minc, On a conjecture of R. F. Scott (1881). Linear Algebra and Its Applications 28, 141 - 153 (1979).

[49] Henryk Minc, The van der Waerden permanent conjecture; pp. 23 - 40 in: General Inequalities 3, edited by E. F. Beckenbach and W. Walter. International Series of Numerical Mathematics, Volume 64. Basel: Birkhäuser, 1983.

permanenten 33

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

[51] Thomas Muir, On a class of permanent symmetric functions. Proceedings of the Royal Society of Edinburgh 11, 409 - 418 (1882).

[52] Thomas Head Pate, Inequalities relating groups of diagonal products in a Gram matrix. Linear and Multilinear Algebra 11, 1 - 17 (1982).

[53] Hazel Perfect, An inequality for the permanent function. Proceedings of the Cambridge Philosophical Society 60, 1030 - 1031 (1964).

[54] Hazel Perfect, Positive diagonals of ±1-matrices. Monatshefte für Mathematik 77, 225 - 240 (1973).

[55] Győrgy Pólya, Aufgabe 424. Archiv der Mathematik und Physik (3) 20, 271 (1913).

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

[57] Herbert John Ryser, Matrices of zeros and ones. Bulletin of the American Mathematical Society 66, 442 - 464 (1960).

[58] Herbert John Ryser, Combinatorial Mathematics. The Carus Mathematical Monographs, Volume 14. Washington: The Mathematical Association of America, 1963.

[59] Alexander Schrijver and W. G. Valiant, On lower bounds for permanents. Indagationes Mathematicae 42, 425 - 427 (1980).

[60] Alexander Schrijver, Bounds on permanents, and the number of 1-factors and 1factorizations of bipartite graphs; pp. 107 - 134 in: Surveys in Combinatorics, edited by E. K. Lloyd. London Mathematical Society Lecture Note Series, Volume 82. Cambridge: Cambridge University Press, 1983.

[61] Robert Forsyth Scott, Mathematical notes. The Messenger of Mathematics (N. S.) 10, 142 - 149 (1881).

[62] Rodica Simion and Frank W. Schmidt, On (+1, −1)-matrices with vanishing permanent. Discrete Mathematics 46, 107 - 108 (1983).

[63] Dragutin Svrtan, Proof of Scott’s conjecture. Proceedings of the American Mathematical Society 87, 203 - 207 (1983).

[64] Gábor Szegő, Lösung zu Aufgabe 424. Archiv der Mathematik und Physik (3) 21, 291 - 292 (1913).

[65] Helge Tverberg, On the permanent of a bistochastic matrix. Mathematica Scandinavica 12, 25 - 35 (1963).

[66] Marc Voorhoeve, A lower bound for the permanents of certain (0,1)-matrices. Indagationes Mathematicae 41, 83 - 86 (1979).

[67] Bartel Leendert van der Waerden, Aufgabe 45. Jahresbericht der Deutschen Mathematiker-Vereinigung 35, 117 (1926).

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

[69] Edward Tzu-Hsia Wang, On a conjecture of M. Marcus and H. Minc. Linear and Multilinear Algebra 5, 145 - 148 (1977).

[70] Herbert S. Wilf, A mechanical counting method and combinatorial applications. Journal of Combinatorial Theory 4, 246 - 258 (1968).

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