\documentstyle[a4,german,12pt,twoside,leqno]{report}
\topmargin0.8cm
\textheight21.4cm
\pagestyle{myheadings}
\markboth{\hfill {\sc a.~r.~kr\"auter} \hfill}{\hfill {\sc permanenten} \hfill}
\begin{document}

\newcounter{abschnitt}
\newcounter{zaehler}[abschnitt]
\renewcommand{\theequation}{\arabic{abschnitt}.\arabic{zaehler}}
\renewcommand{\labelenumi}{[\arabic{enumi}]}

\thispagestyle{empty}

\setlength{\baselineskip}{12pt}

\noindent
{\footnotesize S\'eminaire Lotharingien de Combinatoire, B09b (1983), 34 pp.
\newline [Formerly: Publ.~I.~R.~M.~A.~Strasbourg, 1984, 230/S-09, p. 39 - 83.]}

\vspace{39pt}

\setlength{\baselineskip}{15pt}

\begin{center}
{\bf PERMANENTEN - EIN KURZER \"UBERBLICK}

\vspace{9pt}

{\sc von

\vspace{9pt}

Arnold Richard KR\"AUTER}
\end{center}

\vspace{21pt}

\setlength{\baselineskip}{12pt}

{\footnotesize {\sc Zusammenfassung.} \quad Der vorliegende Artikel bringt eine knappe
\"Ubersicht \"uber 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\"ur Permanenten, deren Pr\"asentation f\"ur
(0,1)-Matrizen, nichtnegative Matrizen und $(1,-1)$-Matrizen erfolgt. Soweit nicht bereits
in den genannten Themenkreisen enthalten, werden abschlie"send neueste Entwicklungen in der
Permanententheorie vorgestellt.

\vspace{6pt}

{\sc Abstract.} \quad 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.}

\vspace{6pt}


\setlength{\baselineskip}{15pt}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 1. Grundlagen}
\end{center}

{\bf 1.1. Definition der Permanente. Einleitende Bemerkungen.} \quad Die {\it Permanente} $ 
{\rm per} \, A $ einer $ n \times n $-Matrix $ A = (a_{ij}) $ mit Elementen aus einem 
beliebigen kommutativen Ring ist definiert durch

\begin{equation}
{\rm per} \, A = \sum_{\sigma \in S_n} \, a_{1 \sigma(1)} 
\cdot \ldots \cdot 
a_{n \sigma(n)} ,
\end{equation}
\stepcounter{zaehler}

\noindent wobei $S_n$ die symmetrische Gruppe der Ordnung $ n $ bezeichnet. F\"ur eine 
beliebige Permutation $ \sigma \in S_n $ hei"se die Folge $ (a_{1 \sigma (1)}, \ldots, a_{n 
\sigma(n)}) $ {\it Diagonale} von $ A $ und das Produkt $ a_{1 \sigma (1)} \cdot \ldots 
\cdot a_{n \sigma(n)} $ {\it Diagonalprodukt} von $ A $. Die Permanente von $ A $ kann also 
aufgefa"st werden als Summe der Diagonalprodukte von $ A $. \\
Der Name {\it Permanente} wird in der heute gebr\"auchlichen Bedeutung 1882 von Muir [51, p. 
410] eingef\"uhrt, doch treten Permanenten sinngem\"a"s bereits 1813/15 in den Arbeiten [5] 
und [10] von Binet und Cauchy auf. Seitdem sind \"uber vierhundert Ver\"offentlichungen zum 
Thema Permanenten erschienen, darunter 1978 die her\-vor\-ra\-gen\-de Monografie [46] von Minc. Die 
Entwicklungen zwischen 1978 und 1981 (unter Einschlu"s des Beweises f\"ur die Vermutung von 
van der Waerden) behandelt Minc im \"Ubersichtsartikel [50]. \\
Die zwei zuletzt genannten Publikationen stellen die wichtigste Grundlage f\"ur
Glie\-de\-rung 
und Auswahl des Stoffes im vorliegenden Aufsatz dar, doch fanden auch neueste Ergebnisse 
Ber\"ucksichtigung (dies gilt insbesondere f\"ur den letzten Ab\-schnitt). Dem 
\"Uberblickscharakter Rechnung tragend wird auf Beweise weitgehend verzichtet und 
diesbez\"uglich auf die zitierte Originalliteratur verwiesen. \"Uberdies wurde in der 
Darstellung weder Vollst\"andigkeit noch gr\"o"ste Allgemeinheit
an\-ge\-strebt. 
An\-wen\-dun\-gen von 
Permanenten auf Probleme der Kombinatorik und an\-de\-rer Be\-rei\-che behandelt der in diesem 
Band enthaltene Aufsatz von Herrn Seifter.

\bigskip

{\bf 1.2. Eigenschaften der Permanente. Entwicklungss\"atze.} \quad Der 
be\-que\-me\-ren 
Formulierung halber werden wir uns der folgenden Bezeichnungen bedienen. F\"ur $ r \leq n $ 
sei $ Q_{r,n} $ definiert durch

\begin{equation}
Q_{r,n} = \left\{(\omega_1, \ldots, \omega_r) \in {\bf N}^r: 
1 \leq \omega_1 <
 \ldots < \omega_r \leq n \right\} .
\end{equation}
\stepcounter{zaehler}

\noindent F\"ur eine $ n \times n $-Matrix $ A = (a_{ij}) $ sowie f\"ur Vektoren $ \alpha =
(\alpha_1, \ldots, \alpha_r) \in Q_{r,n} $ und $ \beta = (\beta_1, \ldots, \beta_r) \in 
Q_{r,n} $ bezeichne $ A[\alpha|\beta] $ jene $ r \times r $-Untermatrix von $ A $, deren $ 
(i,j) $-tes Element $ a_{\alpha_i \beta_j} $ ist. Ferner bezeichne $ A(\alpha|\beta) $ die 
zu $ A[\alpha|\beta] $ komplement\"are $ (n - r) \times (n - r) $-Untermatrix von $ A $. 
(Man erh\"alt also $ A(\alpha|\beta) $ durch Streichung der Zeilen mit den Indizes $ 
\alpha_1, \ldots, \alpha_r $ und der Spalten mit den Indizes $ \beta_1, \ldots, \beta_r $ 
von $ A $.)

\bigskip

{\sc Satz 1.1.} \quad {\it Es sei} $ A = (a_{ij}) $ {\it eine} $ n \times n $-{\it Matrix.} 
\\
(a) {\it Die Funktion} $ {\rm per} \, A $ {\it ist multilinear in den Zeilen und Spalten 
von} $ A $. \\
(b) {\it F\"ur} $ n \times n $-{\it Permutationsmatrizen} $ P $ {\it und} $ Q $ {\it gilt}

\begin{equation}
{\rm per} \, PAQ = {\rm per} \, A.
\end{equation}
\stepcounter{zaehler}

\noindent (c) {\it F\"ur die transponierte Matrix} $ A^T $ {\it von} $ A $ {\it gilt}

\begin{equation}
{\rm per} \, A^T = {\rm per} \, A.
\end{equation}
\stepcounter{zaehler}

\noindent (d) {\it F\"ur einen beliebigen Vektor} $ \alpha \in Q_{r,n} $ {\it gilt}

\begin{equation}
{\rm per} \, A = \sum_{\omega \in Q_{r,n}} {\rm per} \, A [\alpha|\omega] \; {\rm per} \, A 
(\alpha|\omega)
\end{equation}
\stepcounter{zaehler}

\noindent {\it (Laplacescher Entwicklungssatz f\"ur die Entwicklung der Permanente nach den 
Zeilen mit den Indizes} $ \alpha_1, \ldots, \alpha_r) $. {\it Insbesondere gilt f\"ur} $ r = 
1 $

\begin{equation}
{\rm per} \, A = \sum_{j = 1}^n a_{ij} \, {\rm per} \, A 
(i|j).
\end{equation}
\stepcounter{zaehler}

\noindent {\it (Analoge Formeln gelten f\"ur die Entwicklung nach Spalten.)}

\bigskip

Zur Illustration von Satz 1.1 wollen wir die Permanente der Matrix

\begin{equation}
K_n = \left[
\begin{array}{cccc}
0 & 1 & \ldots &  1 \\
1 & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & 1 \\
1      &  \ldots & 1 & 0
\end{array} \right] 
\end{equation}
\stepcounter{zaehler}

\noindent berechnen. (1.6) liefert f\"ur $ i = 1 $

\begin{equation}
{\rm per} \, K_n = \sum_{j=2}^n {\rm per} \, K_n (1|j).
\end{equation}
\stepcounter{zaehler}

\noindent Da jede der $ (n - 1) \times (n - 1) $-Matrizen $ K_n(1|j) $ insgesamt $ n - 2 $ 
Nullen enth\"alt, welche in paarweise verschiedenen Zeilen und Spalten stehen, gilt ferner 
bei Verwendung von (1.3) sowie der Multilinearit\"at  in der ersten Spalte 

\begin{equation}
{\rm per} \, K_n (1|j) = {\rm per} \, K_{n-1} + {\rm per} \, 
K_{n-2} ,
\end{equation}
\stepcounter{zaehler}

\noindent woraus mit (1.8)

\begin{equation}
{\rm per} \, K_n = (n - 1) ({\rm per} \, K_{n-1} + {\rm per} 
\, K_{n-2}) 
\end{equation}
\stepcounter{zaehler}

\noindent folgt und weiter induktiv

\begin{equation}
{\rm per} \, K_n = n! \sum_{k=0}^n {\frac{1}{k!}} \; (-1)^k .
\end{equation}
\stepcounter{zaehler}

\noindent Dies ist die $ n $-te {\it D\'erangement-Zahl} $ d_n $ (siehe etwa Comtet [12, p. 
180]) aus dem bekannten {\it probl\`eme des rencontres}. Wie die Matrix $ K_n $ mit diesem 
Problem zu\-sam\-men\-h\"angt, geht aus den Bemerkungen \"uber Inzidenzmatrizen im bereits 
erw\"ahnten Aufsatz von Herrn Seifter hervor, weshalb wir hier auf Details nicht eingehen. 
\\
Im Anschlu"s an Satz 1.1 ist zu bemerken, da"s zwei f\"ur das Rechnen mit 
De\-ter\-mi\-nan\-ten 
au"serordentlich wichtige Eigenschaften auf die Permanente bedauerlicherweise nicht 
zutreffen: \\
(a) {\it Die Permanentenfunktion ist nicht invariant gegen\"uber beliebigen elementaren 
Zeilen- und Spaltenoperationen}. \\
(b) {\it F\"ur Permanenten gibt es kein Analogon zum Determinanten-Produktsatz.} \\
Die erste dieser Bemerkungen hat zur Folge, da"s die Berechnung der Permanente mithilfe 
einer derart effizienten Methode, wie sie der Gau"ssche Algorithmus f\"ur Determinanten 
darstellt, unm\"oglich ist. Andererseits w\"urde man bei Verwendung des Laplaceschen 
Entwicklungssatzes $ n!(n - 1) $ Multiplikationen ben\"otigen. Es ist daher naheliegend, 
nach 
Methoden zu suchen, welche erheblich weniger
Mul\-ti\-pli\-ka\-ti\-o\-nen erfordern. Dies ist der Fall 
bei den folgenden zwei Entwicklungss\"atzen, welche urspr\"unglich f\"ur beliebige $ m 
\times n $-Matrizen, $ m \leq n $, formuliert worden sind.

\bigskip

{\sc Satz 1.2} \, (Ryser [58, p. 26]). \quad {\it Es sei} $ A $ {\it eine} $ n \times 
n $-{\it Matrix, es sei} $ \Lambda_k $ {\it die Menge aller} $ n \times k $-{\it 
Untermatrizen} $ X $ {\it von} $ A $ {\it und es bezeichne} $ r_i (X) $ {\it die} $ 
i $-{\it te Zeilensumme von} $ X \; (i = 1, \ldots, n) $. {\it Dann gilt} 

\begin{equation}
{\rm per} \, A = \sum_{t=0}^{n-1}(-1)^t  \sum_{X \in 
\Lambda_{n-t}}
r_1(X) \cdot \ldots \cdot r_n(X).
\end{equation}
\stepcounter{zaehler}

\bigskip

Es sei $ A = (a_{ij}) $ eine $ n \times n $-Matrix. $ r_{i_1 \ast \ldots \ast i_s} $ 
bezeichne die Summe der Elemente im Hadamard-Produkt der Zeilen mit den Indizes $ i_1, 
\ldots, i_s $ von $ A $, das hei"st 
 
\begin{equation}
r_{i_1 \ast \ldots \ast i_s} \; = \sum_{j=1}^n a_{i_1j} \cdot 
\ldots
\cdot a_{i_sj} .
\end{equation}
\stepcounter{zaehler}

\noindent Weiters bezeichne $ D(n) $ die Menge

\begin{equation}
\begin{array}{cc}
D(n) \, = & \left\{ (\omega_1, \ldots, \omega_k) \in {\bf 
N}^k: \; 1 \leq 
\omega_1 \leq \ldots \leq \omega_k \leq n; \right. \\
& \left. \omega_1 + \ldots + \omega_k = n; \, k = 1, \ldots, 
n \right\} \\
\end{array} 
\end{equation}
\stepcounter{zaehler}

\noindent und $ R(\omega) $ f\"ur $ \omega = (\omega_1, \ldots, \omega_k) \in D(n) $
die symmetrisierte Summe aller verschiedenen Produkte der $ r_{i_1 \ast \ldots \ast i_s} \; 
(s = \omega_1, \ldots, \omega_k) $, so da"s in jedem Produkt die Folgen 
$ (i_1, \ldots, i_s) \break
\in Q_{s,n} \; (s = \omega_1, \ldots, \omega_k) $ eine Partition der Menge $ \{1, \ldots, 
n\} $ bilden.

\bigskip

{\sc Satz 1.3} \, (Minc [47, p. 31]). \quad {\it Es sei} $ A $ {\it eine} $ n \times 
n $-{\it Matrix. Dann gilt}

\begin{equation}
{\rm per} \, A = \sum_{\omega \in D(n)} \, (-1)^{n+k} \prod_{i=1}^k (\omega_i - 1)! \, 
R(\omega).
\end{equation}
\stepcounter{zaehler} 

W\"ahrend 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\"ur die Entwicklung von Permanenten. 
Abschlie"send sei noch die vor kurzem erschienene Arbeit [4] von Bebiano erw\"ahnt, die 
mithilfe einer Identit\"at, in welcher Permanenten als Koeffizienten von Polynomen 
auftreten, die Formeln (1.12) und (1.15) gewinnt.

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 2. Permanenten und Determinanten}
\end{center}

{\bf 2.1. Das Problem von P\'olya.} \quad Wir haben im vorigen Abschnitt bemerkt, da"s die 
Berechnung der Permanente gegen\"uber der Determinante sehr schwierig ist. Die \"Ahnlichkeit 
der Definitionen beider Funktionen legt jedoch den Gedanken nahe, Permanenten mithilfe 
linearer Transformationen des Arguments auf Determinanten zur\"uckzuf\"uhren. Pr\"azise 
formuliert lautet das Problem: Gibt es zu einer beliebigen Menge $ S $ von $ n \times 
n $-Matrizen stets eine lineare Abbildung $ T $, so da"s 

\begin{equation}
{\rm per} \, A = \det \, T(A)
\end{equation}
\stepcounter{zaehler} 

\noindent f\"ur alle $ A \in S $ gilt? W\"ahlt man beispielsweise f\"ur $ S $ die Menge 
aller $ 2 \times 2 $-Matrizen 

\begin{equation}
A = \left[
\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{array} \right]
\end{equation}
\stepcounter{zaehler} 

\noindent und f\"ur $ T $ die Abbildung

\begin{equation}
T(A) = \left[
\begin{array}{cc}
a_{11} & -a_{12} \\
a_{21} &  a_{22}
\end{array} \right],
\end{equation}
\stepcounter{zaehler} 

\noindent dann gilt (2.1) tats\"achlich f\"ur alle $ A \in S $. Dies ist f\"ur $ n \geq 3 $
nicht mehr der Fall. 1913 stellte n\"amlich P\'olya [55] die folgende, von Szeg\H{o} [64] 
gel\"oste Aufgabe: {\it Es sei} $ S $ {\it die Menge aller} $ n \times n $-{\it Matrizen. 
Man 
zeige, da"s es f\"ur} $ n \geq 3 $ {\it im allgemeinen keine Abbildung} $ T $ {\it gibt, 
welche in ihrem Argument einen einheitlichen Vorzeichenwechsel bewirkt, so da"s} (2.1) {\it 
f\"ur alle} $ A \in S $ {\it gilt}. \\
Rund f\"unfzig Jahre sp\"ater wurde dieses Problem wieder aufgegriffen. Dabei konnte die 
folgende wesentliche Verbesserung erzielt werden:

\bigskip

{\sc Satz 2.1} \, (Marcus-Minc [38, p. 381]). \quad {\it Es sei} $ S $ {\it die Menge aller} 
$ n \times n $-{\it Matrizen}, $ n \geq 3 $. {\it Dann gibt es im allgemeinen keine lineare 
Abbildung} $ T $, {\it so da"s} (2.1) {\it f\"ur alle} $ A \in S $ {\it gilt}.

\bigskip

Mit diesem Ergebnis war nun endg\"ultig klar, da"s es keine allgemeine M\"oglichkeit gibt, 
Permanenten auf Determinanten zur\"uckzuf\"uhren.

\bigskip

{\bf 2.2. Konvertible Matrizen}. \quad Im Anschlu"s an Satz 2.1 haben einige Forscher 
versucht, hinreichende Bedingungen f\"ur Matrizen herzuleiten, so da"s (2.1) gilt. Wir 
wollen Matrizen mit dieser Eigenschaft {\it konvertibel} nennen. Wir vereinbaren
\"uberdies, da"s alle folgenden Abbildungen $ T $ lediglich Vorzeichen\"anderungen
in ihrem Argument bewirken m\"ogen. $ \nu (A) $ bezeichne die Anzahl der Nullen in $ A $, $ 
\mu(T(A)) $ bezeichne die Anzahl der von $ T $ in $ A $ hervorgerufenen Vorzeichenwechsel 
und $ N_n $ sei die Zahl 

\begin{equation}
N _n = \frac{1}{2} (n^2 - 3n + 2).
\end{equation}
\stepcounter{zaehler}

{\sc Satz 2.2} \, (Gibson [20, p. 474]). \quad {\it Es sei} $ A $ {\it eine konvertible} $ n 
\times n$-(0,1)-{\it Matrix mit positiver Permanente. Dann gilt}

\begin{equation}
\nu (A) \geq N _n .
\end{equation}
\stepcounter{zaehler}

\noindent {\it Das Gleichheitszeichen gilt in} (2.5) {\it genau dann, wenn} $ A $ {\it durch 
Zeilen- oder Spal\-ten\-ver\-tau\-schun\-gen auf die Gestalt}

\begin{equation}
T_n = \left[ \begin{array}{ccccc}
             1 & 1 & 0 &\ldots &  0 \\
             \vdots & \ddots & \ddots & \ddots & \vdots \\
             \vdots & & \ddots & \ddots & 0 \\
             \vdots & & & \ddots & 1 \\
             1 & \ldots & \ldots & \ldots & 1
             \end{array} \right].
\end{equation}
\stepcounter{zaehler}

\noindent {\it gebracht werden kann.}

\bigskip

Die Charakterisierung der Matrizen $ A $ mit $ \nu (A) = N _n $ gestattet es, f\"ur diese 
Klasse detaillierte Aussagen \"uber die Abbildungen $ T $ zu machen, so da"s (2.1) gilt.

\bigskip

{\sc Satz 2.3} \, (Kr\"auter-Seifter [28, {\it passim}]). \quad {\it Es sei} $ A $ {\it 
eine} $ n \times n$-(0,1)-{\it Matrix mit positiver Permanente, ferner sei} $ \nu(A) = N_n, 
\;\; n \geq 4, $ {\it und es gelte} $ {\rm per} \, A = \det \,T(A) $. {\it Dann gilt 

\begin{equation}
n - 1 \leq \mu(T(A)) \leq {n + 1 \choose 2} ,
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei jeder ganzzahlige Wert in diesem Intervall f\"ur ein geeignetes} $ T $ 
tats\"ach\-lich angenommen wird. Auf der linken beziehungsweise rechten Seite von} (2.7) 
{\it gilt das Gleichheitszeichen genau dann, wenn die Matrix} $ T(A) $ {\it bis auf Zeilen- 
oder Spaltenvertauschungen mit der Matrix}

\[
U_n = \left[ \begin{array}{ccccc}
             1 & -1 & 0 & \ldots &  0 \\
             \vdots & \ddots & \ddots & \ddots & \vdots \\
             \vdots & & \ddots & \ddots & 0 \\
             \vdots & & & \ddots & -1 \\
             1 & \ldots & \ldots & \ldots & 1
             \end{array} \right]
\]

\noindent {\it beziehungsweise} $ -U_n $ {\it \"ubereinstimmt.}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 3. Die Vermutung von van der Waerden}
\end{center}

{\bf 3.1. Von Marcus und Newman bis Friedland und Bang.} \quad 1926 stellte van der Waerden 
[67] (in moderner Terminologie formuliert) die folgende Frage: {\it Wie gro"s ist 
das Minimum der Permanente auf der Menge} $ \Omega_n $ {\it aller doppeltstochastischen} $ n 
\times n $-{\it Matrizen}? (Eine quadratische Matrix hei"st {\it doppeltstochastisch}, wenn 
ihre Elemente nichtnegativ sind und \"uberdies ihre Zeilen- und Spaltensummen $ 1 $ sind.) 
Die Anregung zu dieser Aufgabe geht zur\"uck auf den

\bigskip        

{\sc Satz 3.1} \, (K\H{o}nig [26, p. 458]). \quad {\it Es sei} $ A $ {\it eine 
nichtnegative} $ n \times n $-{\it Matrix, deren Zeilen- und Spaltensummen denselben 
positiven Wert besitzen. Dann gilt}

\begin{equation}
{\rm per} \, A > 0.
\end{equation}
\stepcounter{zaehler}

Marcus und Newman sind die ersten Autoren, die sich mit dem genannten Problem besch\"aftigt 
haben. Ihre Arbeit [37] stellt ein sorgf\"altiges Studium der Eigenschaften von Matrizen aus 
$ \Omega_n $ mit minimaler Permanente dar mit dem Ziel nachzuweisen, da"s all diese 
Eigenschaften von genau einer Matrix erf\"ullt werden, n\"amlich 

\begin{equation}
J_n = \left[ \begin{array}{ccc}
             \frac{1}{n} & \ldots & \frac{1}{n} \\
             \vdots & \ddots & \vdots \\
             \frac{1}{n} & \ldots & \frac{1}{n} 
             \end{array} \right].
\end{equation}
\stepcounter{zaehler}

\noindent Dieses (von den erw\"ahnten Autoren nur teilweise erreichte) Ziel ist der Inhalt 
der "`Vermutung von van der Waerden"': {\it F\"ur alle} $ A \in \Omega_n $ {\it gilt}

\begin{equation}
{\rm per} \, A \geq \frac{n!}{n^n}.
\end{equation}
\stepcounter{zaehler}

\noindent Die versch\"arfte Fassung enth\"alt \"uberdies folgende Charakterisierung des 
Gleich\-heits\-fal\-les: {\it In} (3.3) {\it tritt Gleichheit genau dann ein, wenn} $ A = J_n $ 
{\it ist}. \\
Der Arbeit von Marcus und Newman kommt das gro"se Verdienst zu, mit ihrer Vermutung und mit 
ihren Ergebnissen das innerhalb der darauffolgenden zwei\-ein\-halb Jahrzehnte stark gestiegene 
Interesse an der Permanententheorie geweckt und wich\-ti\-ge Ideen zur vollst\"andigen L\"osung 
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\"ulle von Teilresultaten, welche vor dem Beweis von (3.3) erschienen sind, sollen 
lediglich zwei angef\"uhrt werden (beide sind 1979 erschienen):

\bigskip
 
{\sc Satz 3.2} \, (Friedland [17, p. 175]). \quad {\it F\"ur alle} $ A \in \Omega_n $ {\it 
gilt}

\begin{equation}
{\rm per} \, A \geq e^{-n}.
\end{equation}
\stepcounter{zaehler}

{\sc Satz 3.3} \, (Bang [3, p. 3]). \quad {\it F\"ur alle} $ A \in \Omega_n $ {\it gilt}

\begin{equation}
{\rm per} \, A \geq e^{1-n}.
\end{equation}
\stepcounter{zaehler}

Man beachte, da"s die Schranken in (3.3), (3.4) und (3.5) von nahezu gleicher 
Gr\"o"senordnung sind; es folgt n\"amlich aus der Stirlingschen Formel

\begin{equation}
\frac{n!}{n^n} \approx \sqrt{2 \pi n} \, e^{-n} .
\end{equation}
\stepcounter{zaehler}

\bigskip

{\bf 3.2. Falikman und Egory\v{c}ev.} \quad Nach zahlreichen vergeblichen Versuchen mehrerer 
Mathematiker gelang es schlie"slich den sowjetischen Forschern Falikman [15] und 
Egory\v{c}ev [14], unabh\"angig voneinander den Nachweis f\"ur die Richtigkeit der Vermutung 
von van der Waerden zu erbringen. (Falikman reichte seinen Beweis 1979 ein, Egory\v{c}ev 
1980.) Beide erhielten f\"ur ihre Leistung den Fulkerson-Preis 1982. Beide Beweise beruhen 
im Grunde genommen auf einem Spezialfall einer Ungleichung f\"ur gemischte Diskriminanten 
quadratischer Formen von Aleksandrov [2, pp. 231 - 232], welche in der hier ben\"otigten 
Form folgenderma"sen lautet:

\bigskip

{\sc Satz 3.4.} \quad {\it Es sei} $ A $ {\it eine nichtnegative} $ n \times 
(n - 2) $-{\it Matrix, es seien} $ x $ {\it und} $ y $ {\it Spaltenvektoren mit} $ n $ {\it 
Komponenten und es sei \"uberdies} $ x $ {\it nichtnegativ. Dann gilt}

\begin{equation}
[{\rm per} \, (A,x,y)]^2 \geq {\rm per} \, (A,x,x) \; {\rm per} \, (A,y,y).
\end{equation}
\stepcounter{zaehler}

\noindent {\it Sind} $A$ {\it und} $ x $  {\it positiv, dann gilt in} (3.7) {\it das 
Gleichheitszeichen genau dann, wenn} $ x $ {\it und} $ y $ {\it kollinear sind}.

\bigskip

Ein expliziter Beweis dieses Satzes findet sich bei Knuth [25, p. 735] und van Lint [34, pp. 
3 - 4]. (Egory\v{c}ev hat die Ungleichung von Aleksandrov unmittelbar verwendet und konnte 
daher auf einen Beweis verzichten. Falikman hingegen bewies (3.7) f\"ur den Fall $ {\rm per} 
\, (A,x,y) = 0 $.) W\"ahrend Falikman keine weiteren Hilfsmittel ben\"otigt, ben\"utzt  
Egory\v{c}ev \"uberdies den

\bigskip

{\sc Satz 3.5} \, (London [36, p. 156]). \quad {\it Es sei} $ A = (a_{ij}) \in \Omega_n $ 
{\it eine Matrix mit minimaler Permanente. Dann gilt f\"ur alle} $ i $ {\it und} $ j $ 

\begin{equation}
{\rm per} \, A(i|j) \geq {\rm per} \, A.
\end{equation}
\stepcounter{zaehler}

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

\bigskip

Eine Gegen\"uberstellung beider Beweise enthalten die sch\"onen \"Ubersichtsartikel von 
Lagarias [31], van Lint [35] und Minc [49]. Wir begn\"ugen uns hier mit einer modifizierten 
Fassung des Beweises von Egory\v{c}ev (siehe Schrijver [60, pp. 117 - 118]).

\bigskip

{\sc Satz 3.6} \, (Falikman [15, p. 932]; Egory\v{c}ev [14, p. 66]). \quad {\it F\"ur alle} 
$ A \in \Omega_n $ {\it gilt}

\begin{equation}
{\rm per} \, A \geq \frac{n!}{n^n}.
\end{equation}
\stepcounter{zaehler}

{\it Beweis:} Es sei im folgenden $ A = (B,x,y) \in \Omega_n $ stets eine Matrix mit 
minimaler Permanente, wobei $ B $ eine $ n \times (n - 2) $-Matrix ist und $ x = (x_1, 
\ldots, x_n)^T $ sowie $ y = ( y_1, \ldots, y_n)^T $ Spaltenvektoren sind. Entwickelt man 
${\rm per} \, (B,x,x) $ nach der letzten Spalte, dann erh\"alt man mit Satz 3.5

\[
\begin{array}{ccl}
{\rm per} \, (B,x,x) & = & \sum_{i=1}^n \, x_i \,{\rm per} \, (B,x,e^{(i)}) \geq \\
                     & \geq & \sum_{i=1}^n \, x_i \, {\rm per} \, (B,x,y) = \\
                     & = & {\rm per} \, (B,x,y) \\
\end{array} 
\]

\noindent aufgrund der Doppeltstochastizit\"at, wobei $ e^{(i)} = (0, \ldots,1, \ldots,0)^T 
$ ist mit $ 1 $ an der $ i $-ten Stelle. Analog erh\"alt man

\[
{\rm per} \, (B,y,y) \geq {\rm per} \, (B,x,y) ,
\]

\noindent also

\begin{equation}
[{\rm per} \, (B,x,y)]^2 \leq {\rm per} \; (B,x,x) \,{\rm per} \, (B,y,y) .
\end{equation}
\stepcounter{zaehler}

\noindent Andererseits folgt aus Satz 3.4 

\begin{equation}
[{\rm per} \, (B,x,y)]^2 \geq {\rm per} \, (B,x,x) \; {\rm per} \, (B,y,y). 
\end{equation}
\stepcounter{zaehler}

\noindent Nach Satz 3.1 ist nun $ {\rm per} \, (B,x,y) > 0, $ und somit folgt aus (3.10) und 
(3.11)

\begin{equation}
{\rm per} \, (B,x,x) = {\rm per} \, (B,y,y) = {\rm per} \, (B,x,y).
\end{equation}
\stepcounter{zaehler}

\noindent Daraus folgt wiederum

\begin{equation} 
\left\{ \begin{array}{lll}
        {\rm per} \, (B, \frac{x+y}{2}, \frac{x+y}{2}) & = & \frac{1}{4} \, {\rm per} \,                                
        (B,x,x) + \frac{1}{2} \, {\rm per} \, (B,x,y) \; + \\                                                                                                                                            
        & & + \; \frac{1}{4} \, {\rm per} \, (B,y,y) \; = \\
        & = & {\rm per} \, (B,x,y). \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Da die Matrix $ (B, \frac{x+y}{2}, \frac{x+y}{2}) $ doppeltstochastisch ist, 
besitzt sie somit ebenfalls mi\-ni\-ma\-le Permanente. Es sei nun die Matrix $ A = (a_{ij}) $ so 
gew\"ahlt, da"s 

\[
\Phi (A) = \sum_{i,j} \, a^2_{ij} 
\]

\noindent m\"oglichst klein ist. (Dies ist stets m\"oglich, da die Menge $ \Omega_n $ 
aufgrund des Satzes von Birkhoff [6, p. 147] kompakt ist.) Angenommen, es sei $ A \neq J_n 
$. Dann sind ohne Beschr\"ankung 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 $ \tilde A = (B, \frac{x+y}{2}, \frac{x+y}{2}) $ der Fall, jedoch gilt
(wie man leicht nachpr\"uft) wegen $ x \not= y \quad \Phi (\tilde A) < \Phi (A) $ im 
Widerspruch zur Minimalit\"at von $ \Phi (A) $. Somit ist $ A = J_n $ und $ {\rm per} \, (A) 
= \frac{n!}{n^n}. \hfill \Box $

\bigskip

Egory\v{c}ev konnte dar\"uber hinaus die Eindeutigkeit der Matrix $ J_n $ zeigen:

\bigskip

{\sc Satz 3.7} \, (Egory\v{c}ev [14, p. 66]). \quad {\it In} (3.9) {\it gilt das 
Gleichheitszeichen genau dann, wenn} $ A = J_n $ {\it ist.}

\smallskip

{\it Beweis:} Es gen\"ugt zu zeigen, da"s die Bedingung notwendig ist. Wir nehmen an, es 
g\"abe eine Matrix $ A \in \Omega_n $ mit $ {\rm per} \, (A) = n! \, n^{-n} $, jedoch $ A 
\not= J_n $. Ferner sei $ A $ so gew\"ahlt, da"s die Anzahl der verschwindenden 
Matrizenelemente von $ A $ m\"oglichst klein ist. Sind mindestens $ n - 1 $ Spalten von $ A 
$ positiv, dann d\"urfen wir ohne Beschr\"ankung der Allgemeinheit annehmen, da"s $ A = 
(B,x,y) $ mit $ B $ und $ x $ positiv und $ x \not= y $ ist. Dann folgt aus (3.12) die 
Gleichheit in (3.7). Nach der Gleichheitsbedingung in Satz 3.4 ist dies \"aquivalent dazu, 
da"s $ y = \lambda x $ f\"ur ein geeignetes $ \lambda $ gilt. Aufgrund der 
Doppeltstochastizit\"at von $ A $ mu"s $ \lambda = 1 $ gelten, also $ x = y $ sein im 
Widerspruch zur Annahme. Somit ist $ A = J_n $. \\
Besitzt $ A $ h\"ochstens $ n - 2 $ positive Spalten, dann d\"urfen wir $ A $ in der Gestalt 
$ A = (B, x, y) $ annehmen, so da"s nicht alle Spalten von $ B $ positiv sind und ferner $ y 
$ mindestens eine verschwindende Komponente besitzt, wo die entsprechende 
Kom\-po\-nen\-te von $ x 
$ positiv ist. Gem\"a"s (3.13) ist $ (B, \frac{x+y}{2}, \frac{x+y}{2}) $ wiederum eine 
Matrix mit mi\-ni\-ma\-ler Permanente, welche zwar von $ J_n $ verschieden ist, aber mindestens 
eine Null weniger enth\"alt als $ A $ , womit wiederum ein Widerspruch vorliegt. Also ist 
auch hier $ A = J_n. \hfill \Box$

\bigskip

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

\bigskip

{\sc Satz 3.8} \, (Friedland [18, p. 120]). \quad {\it Es sei} $ A \in \Omega_n $ {\it und 
es bezeichne} $ \sigma_k (A) $ {\it die Summe aller} $ k $-{\it reihigen Unterpermanenten 
von} $ A $. {\it Dann gilt f\"ur alle} $ 2 \leq k \leq n $ {\it und} $ A \not= J_n $

\begin{equation}
\sigma_k (A) > \sigma _k (J_n).
\end{equation}
\stepcounter{zaehler}

Dies best\"atigt eine Vermutung von Tverberg [65, p. 26] (Tverberg bewies (3.14) f\"ur $ k = 
2 $ und $ k = 3). $ Offensichtlich handelt es sich dabei um eine Verallgemeinerung der 
Vermutung von van der Waerden, welche man f\"ur $ k = n $ erh\"alt.

\bigskip

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 4. Untere Schranken f\"ur Permanenten}
\end{center}

Es wurde bereits erw\"ahnt, da"s die explizite Berechnung von Permanenten im allgemeinen ein 
schwieriges Problem darstellt. Daher sind Schranken f\"ur
Per\-ma\-nen\-ten, ausgedr\"uckt durch 
leicht zu berechnende Funktionen (beispielsweise Zei\-len\-sum\-men), von gro"ser Wichtigkeit. Da 
f\"ur beliebige Matrizen keine scharfen Absch\"atzungen zu erwarten sind, werden wir uns 
hier auf einige wichtige Klassen von Matrizen beschr\"anken. Im vorliegenden Abschnitt soll 
die Frage nach unteren Schranken f\"ur Permanenten dieser Matrizen behandelt werden.

\bigskip

{\bf 4.1. (0,1)-Matrizen}. \quad Die gro"se kombinatorische Bedeutung von
Per\-ma\-nen\-ten auf 
der Menge der $ (0,1) $-Matrizen wird in der Arbeit von Herrn Seifter geb\"uhrend 
herausgestellt. Wir beginnen mit dem

\bigskip

{\sc Satz 4.1} \, (Hall [21, p. 923]). \quad {\it Es sei} $ A $ {\it eine} $n \times 
n$-(0,1)-{\it Matrix mit mindestens} $ k \leq n $ {\it Einsen je Zeile und es sei} $ {\rm 
per} \, A > 0 $. {\it Dann gilt}

\begin{equation}
{\rm per} \, A \geq k!.
\end{equation}
\stepcounter{zaehler}

Man beachte in Satz 4.1 die Zusatzbedingung  $ {\rm per} \, A > 0 $. Ohne sie blieben die 
unteren Schranken unscharf, da der Wert der Permanente wesentlich von der Anordnung der 
Nullen abh\"angt und erst in zweiter Linie von der Anzahl der Einsen je Zeile. In der Tat 
kann die Permanente einer $ n \times n$-(0,1)-Matrix mit $ n(n - 1) $ positiven Elementen 
verschwinden (Vorliegen einer Nullspalte). \\
F\"ur die Behandlung weiterer Ergebnisse ist es n\"utzlich, folgende Bezeichnungen 
einzuf\"uhren. Es sei $ \alpha = (\alpha_1, \ldots, \alpha_n) $ ein $ n $-Tupel reeller 
Zahlen. Dann bezeichne $ \alpha^{\ast} = (\alpha_1^{\ast}, \ldots, \alpha_n^{\ast}) $ jenes 
$ n $-Tupel, welches man durch Anordnung der Komponenten von $ \alpha $ in der 
Rei\-hen\-fol\-ge
$ \alpha_1^{\ast} \geq \ldots \geq \alpha_n^{\ast} $ erh\"alt, und es bezeichne $ \alpha' = 
(\alpha'_1, \ldots, \alpha'_n) $ jenes $ n $-Tupel, welches man durch Anordnung der 
Komponenten von $ \alpha $ in der Rei\-hen\-fol\-ge $ \alpha'_1 \leq \ldots \leq \alpha'_n $ 
erh\"alt. Es sei $ A $ eine $ n \times n$-(0,1)-Matrix mit den Zeilensummen $ r_1, \ldots, 
r_n $. Dann bezeichne $ \overline {A} $ jene $ n \times n$-(0,1)-Matrix, in deren $ i $-ter 
Zeile die ersten $r_i$ Elemente 1 sind und die restlichen $ n - r_i $ Elemente $ 0 \quad (i 
= 1, \ldots,n) $. Beispielsweise hat f\"ur 

\begin{equation}
A = \left[ \begin{array}{ccccc}
           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{array} \right].
\end{equation}
\stepcounter{zaehler}

\noindent $ \overline {A} $ die Gestalt

\begin{equation}
\overline {A} = \left[ \begin{array}{ccccc}
                       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{array} \right].
\end{equation}
\stepcounter{zaehler}

\bigskip

{\sc Satz 4.2} \, (Jurkat-Ryser [22, p. 26]; Minc [43, pp. 1129 - 1130]). \quad {\it Es sei} 
$ A $ eine $ n \times n$-(0,1)-{\it Matrix mit den Zeilensummen} $ r_1, \ldots, r_n $. {\it 
Dann gilt}

\begin{equation}
{\rm per} \, A \geq \prod_{i=1}^n \, {\rm max} \, (0, r_i + i - n).
\end{equation}
\stepcounter{zaehler}

\noindent {\it F\"ur} $ {\rm per} \, A > 0 $ {\it tritt Gleichheit in} (4.4) {\it genau dann 
auf, wenn es eine} $ n \times n$-(0,1)-{\it Permutationsmatrix} $ P $ {\it gibt mit} $ AP = 
\overline {A} $.

\bigskip

Leider liefert Satz 4.2 keine guten Schranken. Treten n\"amlich 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 \"Uberlegung m\"oglich. Da die Permanentenfunktion unver\"andert gegen\"uber 
Zeilenvertauschungen bleibt, kann man diese gerade so vornehmen, da"s die Zeilensummen in 
nichtaufsteigender Reihenfolge angeordnet sind.

\bigskip

{\sc Satz 4.3} \, (Minc [45, p. 503]). \quad {\it Es sei} $ A $ {\it eine} $ n \times 
n$-(0,1)-{\it Matrix mit den Zeilensummen} $ r_1, \ldots, r_n $. {\it Dann gilt}

\begin{equation}
{\rm per} \, A \geq \prod_{i=1}^n \, {\rm max} (0, r_i^{\ast} + i - n).
\end{equation}
\stepcounter{zaehler}

\noindent {\it (Gleichheitsbedingung wie in Satz 4.2.)}

\bigskip

Da"s die Absch\"atzung (4.5) besser als (4.4) ist, geht hervor aus dem folgenden

\bigskip

{\sc Hilfssatz} \, (Minc [45, p. 503]). \quad {\it Es seien} $ r_1, \ldots, r_n $  {\it 
nichtnegative ganze Zahlen} $ \leq n $. {\it Dann gilt}
 
\begin{equation}
\prod^n_{i=1} {\rm max} \, (0,r^{\ast}_i + i - n) \geq \prod^n_{i=1} {\rm max} \, (0,r_i + i 
- n).
\end{equation}
\stepcounter{zaehler}

\noindent {\it In} (4.6) {\it tritt Gleichheit genau dann auf, wenn entweder die linke Seite 
verschwindet oder} $ r^{\ast}_i = r_i $ {\it f\"ur alle} $ i = 1, \ldots, n $ {\it gilt}.

\bigskip

Jene $ n \times n$-(0,1)-Matrizen, welche genau $ k $ Einsen je Zeile und Spalte besitzen, 
verdienen besonderes Interesse; wir bezeichnen die Menge dieser Matrizen mit $ \Lambda_n^k 
$. F\"ur $ A \in \Lambda_n^k $ ist offenbar $ \frac{1}{k} A \in \Omega_n $; somit gilt nach 
Satz 3.6

\begin{equation}
{\rm per} \, A \geq n! \, \left(\frac{k}{n}\right)^n
\end{equation}
\stepcounter{zaehler}

\noindent aufgrund der Multilinearit\"at der Permanente. Da die Matrizen in $ \Lambda_n^k $ 
in jeder Zeile und Spalte $ n - k $ Nullen enthalten, ist eine Verbesserung der 
Absch\"atzung (4.7) zu erwarten. In der Tat folgt aus Minc [46, p. 72, Problem 19] f\"ur 
alle $ A \in \Lambda_n^2 $

\begin{equation}
{\rm per} \, A \geq 2.
\end{equation}
\stepcounter{zaehler}

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

\bigskip

{\sc Satz 4.4} \, (Voorhoeve [66, p. 85]). \quad {\it F\"ur alle} $ A \in \Lambda_n^3 $ {\it 
gilt}

\begin{equation} 
{\rm per} \, A \geq 6 \cdot \left(\frac{4}{3}\right)^{n-3}.
\end{equation}
\stepcounter{zaehler}

Leider l\"a"st sich die von Voorhoeve ben\"utzte Beweismethode nicht auf $ n > 3 $ 
ausdehnen. Wir definieren nun $ \mu_k(n) $ durch

\begin{equation}
\mu_k (n) = \min_{A \in \Lambda_n^k}({\rm per} \, A).
\end{equation}
\stepcounter{zaehler}

\bigskip

{\sc Satz 4.5} \, (Schrijver-Valiant [59, p. 426]).

\begin{equation}
\mu_k (n) \leq k^{2n} {nk \choose n}^{-1} .
\end{equation}
\stepcounter{zaehler}

Eine Folgerung aus diesem Satz betrifft die bei der Behandlung des $ 
n $-di\-men\-si\-o\-na\-len Dimerenproblems wichtige Gr\"o"se

\begin{equation}
\theta_k = \lim_{n \to \infty} \, \sqrt[n] {\mu_k (n)}.
\end{equation}
\stepcounter{zaehler}
\noindent

\noindent Mithilfe der Stirlingschen Formel erh\"alt man aus (4.11) unmittelbar

\begin{equation}
\theta_k \leq \frac{(k - 1)^{k-1}}{k^{k-2}} .
\end{equation}
\stepcounter{zaehler}

\noindent Die Tatsache, da"s f\"ur $ k = 1,2,3 $ (in letzterem Fall unter Verwendung von
Satz 4.4) die Gleichheit in (4.13) bewiesen werden kann, veranla"ste Schrijver und Valiant 
zu der folgenden 

\bigskip

{\sc Vermutung.} 

\begin{equation}
\theta_k = \frac{(k - 1)^{k-1}}{k^{k-2}} .
\end{equation}
\stepcounter{zaehler}

{\bf 4.2. Beliebige nichtnegative Matrizen}. \quad Von grundlegender Bedeutung
f\"ur die kombinatorische Matrizentheorie ist der 

\bigskip

{\sc Satz 4.6} \, (Frobenius [19, p. 274]; K\H{o}nig [27, p. 169]). \quad {\it Es sei} $ A $ 
{\it eine nichtnegative} $ n \times n $-{\it Matrix. Dann gilt}

\begin{equation}
{\rm per} \, A > 0
\end{equation}
\stepcounter{zaehler}

\noindent {\it genau dann, wenn} $ A $ {\it keine} $ s \times (n - s + 1) $-{\it 
Null-Untermatrix enth\"alt} $ (s= 1, \ldots, n - 1)$.

\bigskip

N\"ahere Informationen \"uber die Matrix $ A $ erlauben es, Verbesserungen von (4.15) 
anzugeben. F\"ur eine positive $ n \times n $-Matrix $ A = (a_{ij}) $ definieren wir $ a = 
{\rm min}_{i,j} (a_{ij}) $. Wegen $ a_{ij} > 0 $ f\"ur alle $ i $ und $ j $ ist dann $ a > 0 
$ und es gilt offensichtlich

\begin{equation}
{\rm per} \, A \geq n! \, a^n .
\end{equation}
\stepcounter{zaehler}

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

\begin{equation}
{\rm per} \, A \geq n! \, \prod_{i=1}^n \, a_{in}^\ast .
\end{equation}
\stepcounter{zaehler}

\noindent Gleichheit gilt in (4.17) genau dann, wenn alle Zeilen kollinear zum Vektor
$ (1, \ldots, 1) $ sind. Eine weitere, wesentliche Verbesserung von (4.17) enth\"alt der

\bigskip

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

\begin{equation}
{\rm per} \, A \geq \prod_{i=1}^n \, \sum_{t=1}^i \, a_{it}'.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Ist} $ A $ {\it positiv, dann tritt in} (4.18) {\it Gleichheit genau 
dann auf, wenn die ersten} $ n - 1 $ {\it Zeilen von} $ A $ {\it kollinear zum Vektor} $(1, 
\ldots, 1) $ {\it sind}.

\bigskip

Satz 4.7 besagt also, da"s $ {\rm per} \, A $ nicht \"ubertroffen 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\"uber 
Zeilenvertauschungen zunutze, dann kann man die rechte Seite von (4.18) ersetzen durch das 
Maximum dieser Ausdr\"ucke \"uber alle Permutationen der
Zei\-len\-in\-di\-zes. Auf die Erw\"ahnung 
weiterer m\"oglicher Versch\"arfungen sei hier verzichtet. Wir verweisen diesbez\"uglich auf 
Minc [44].

\bigskip

{\bf 4.3. (1,-1)-Matrizen}. \quad Als einzige Klasse von Matrizen, in welchen auch negative 
Elemente auftreten k\"onnen, wollen wir jene der $ n \times n$-$(1,-1)$-Matrizen n\"aher 
betrachten. Die Menge dieser Matrizen werde mit $ \Gamma_n $ bezeichnet. Eine wichtige 
Teilmenge von $ \Gamma_n $ bilden die Hadamard-Matrizen $H \; (HH^T = nI) $. Beim Studium 
von Permanenten auf $ \Gamma_n $ kann man sich auf den Absolutbetrag beschr\"anken. Ist 
n\"amlich die Permanente einer Matrix $ A \in \Gamma_n $ negativ, dann erh\"alt man durch 
Multiplikation einer Zeile von $ A $ mit dem Faktor $ -1 $ eine Matrix $ A' \in \Gamma_n $ 
mit

\begin{equation}
{\rm per} \, A'= {\rm -per} \, A > 0
\end{equation}
\stepcounter{zaehler}

\noindent aufgrund  der Multilinearit\"at. Als erster befa"ste sich Wang [68] mit der Frage, 
wann $ |{\rm per} \, A| $ f\"ur $ A \in \Gamma_n $ den Minimalwert $ 0 $ tats\"achlich 
annimmt.

\bigskip

{\sc Satz 4.8} \, (Wang [68, p. 257]). \quad {\it Es sei} $ n \geq 2 $ {\it von der Form} $ 
n = 2k $ {\it oder} $ n = 4k + 1 $ {\it f\"ur} $ k \in {\bf N} $. {\it Dann gibt es stets 
eine Matrix} $ A \in \Gamma_n $ {\it mit}

\begin{equation}
{\rm per} \, A = 0.
\end{equation}
\stepcounter{zaehler}

Wang konstruiert in seinem Beweis folgende Beispiele:

\begin{equation}
A = \left[ \begin{array}{c|ccccc}
           1 & -1 & 1 &  \ldots & 1 & -1 \\ \hline
           1 & & & & & \\
           \vdots & & & & & \\
           \vdots & & & J^{(n-1)} & & \\
           \vdots & & & & & \\
           1 & & & & & \\
           \end{array} \right]
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur $ n = 2k $ und

\begin{equation} \begin{array}{r} \mbox{$ \overbrace{\rule{20mm}{0mm}}^{2k+1}                                                    
                 \overbrace{\rule{28mm}{0mm}}^{2k-1} \rule{4mm}{0mm} $} \\
                 \mbox{$ A = \mbox{$ \begin{array}{r} \rule{0mm}{4mm} \\
                 {\scriptstyle k} \left\{ \rule[-7.25mm]{0mm}{16.5mm} \right. \\
                 {\scriptstyle 3k} \left\{ \rule[-7.25mm]{0mm}{16.5mm} \right. \\
                 \end{array} $} \!\!\!\! \left[ \begin{array}{c|cccccc}
                                                1 & 1 & \ldots & 1 & -1 & \ldots & -1 \\                                                 
\hline
                                                1 & & & & & & \\
                                                \vdots & & & & & & \\
                                                1 & & & & & & \\
                                                -1 & & & & J^{(n-1)} & & \\
                                                \vdots & & & & & & \\
                                                -1 & & & & & & \\
                                                \end{array} \right] $}
                 \end{array}
\end{equation}
\stepcounter{zaehler}

\noindent
f\"ur $ n = 4k + 1 $, wobei $ J^{(n)} \in \Gamma_n $ jene Matrix ist, deren Elemente alle $ 
1 $ sind. F\"ur $ n = 4k + 3, \,  k \in {\bf{N}}_0 $, konnte Wang keine Antwort auf das zur 
Diskussion stehende Problem geben (ausgenommen $ n = 3$). Mittlerweile ist es aber gelungen, 
f\"ur spezielle $n $ von dieser Bauart ein Teilresultat zu erzielen.

\bigskip

{\sc Satz 4.9} \, (Simion-Schmidt [62, p. 107]; Kr\"auter-Seifter [29, p. 59]). \quad {\it 
Es sei} $ n = 2^k - 1 $ {\it f\"ur} $ k \in {\bf{N}}$. {\it Dann gilt f\"ur alle Matrizen} $ 
A \in \Gamma_n $

\begin{equation}
|{\rm per} \, A| > 0.
\end{equation}
\stepcounter{zaehler}

Der erste offene Fall w\"are demnach $ n = 11 $. Satz 4.9 legt unmittelbar die Frage nach 
dem Minimum von $ |{\rm per} \, A| $ f\"ur die dort betrachteten $ n $ nahe. Eine allgemeine 
Antwort ist noch ausst\"andig, doch gestatten die bisher untersuchten F\"alle $ k = 1,2,3 $ 
die (unver\"offentlichte)

\bigskip

{\sc Vermutung}. \quad {\it Es sei} $ n = 2^k - 1 $ {\it f\"ur} $ k \in {\bf{N}} $. {\it 
Dann gilt}

\begin{equation}
\min_{A \in \Gamma_n} |{\rm per} \, A| = 2^{n-[\log_2n]-1}.
\end{equation}
\stepcounter{zaehler}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 5. Obere Schranken f\"ur Permanenten}
\end{center}

{\bf 5.1. (0,1)-Matrizen.}

\bigskip

{\sc Satz 5.1} \, (Minc [42, p. 790]). \quad {\it Es sei} $ A $ {\it eine} $ n \times 
n$-(0,1)-{\it Matrix mit den Zeilensummen} $ r_1, \ldots, r_n $. {\it Dann gilt}

\begin{equation}
{\rm per} \, A \leq \prod_{i = 1}^{n} \, \frac{r_i + 1}{2}.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Gleichheit gilt in} (5.1) {\it genau dann, wenn} $ A $ {\it eine 
Permutationsmatrix ist.}

\bigskip

Minc \"au"serte \"uberdies eine Vermutung, deren Beweis zehn Jahre sp\"ater von Br\.egman 
erbracht wurde und welche wir aus diesem Grund gleich als Satz
for\-mu\-lie\-ren:

\bigskip

{\sc Satz 5.2} \, (Br\.egman [8, p. 30]). \quad {\it Es sei} $ A $ {\it eine} $ n \times 
n$-(0,1)-{\it Matrix mit den Zeilensummen} $ r_1, \ldots, r_n $. {\it Dann gilt}

\begin{equation}
{\rm per} \, A \leq \prod_{i = 1}^{n} \, (r_i!)^{1/r_i}.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Gleichheit tritt in} (5.2) {\it genau dann ein, wenn es} \, $ n \times 
n $-{\it Permutationsmatrizen} $ P $ {\it und} $ Q $ {\it gibt, so da"s} $ PAQ $ {\it 
direkte Summe von Ma\-tri\-zen} \, $ J^{(\nu_k)} \;\; (k = 1, \ldots, t; \; \nu_1 + \ldots + 
\nu_t = n) $ {\it ist}.

\bigskip

Die Versch\"arfung gegen\"uber (5.1) folgt aus der Ungleichung f\"ur das arithmetische und 
geometrische Mittel f\"ur die ersten $ r_i $ nat\"urlichen Zahlen. \\
Auch in diesem Unterabschnitt wollen wir einen Blick auf die Menge $ \Lambda_n^k $ werfen. 
Aus Satz 5.2 folgt f\"ur $ A \in \Lambda^k_{kt} $ unmittelbar 

\begin{equation}
{\rm per} \, A \leq (k!)^t.
\end{equation}
\stepcounter{zaehler}

\noindent Damit ist auch eine Vermutung von Ryser [57, p. 458] gezeigt. In den F\"allen
$ n \not\equiv 0 \; ({\rm mod} \, k) $ konnte eine Versch\"arfung von (5.2) f\"ur $ k = 2$ 
und $k = 3 $ erzielt werden.

\bigskip

{\sc Satz 5.3} \, (Merriell [41, {\it passim}]). \quad {\it F\"ur alle} $ A \in 
\Lambda_{2t+1}^2 $ {\it gilt}

\begin{equation} 
{\rm per} \, A \leq 2^t
\end{equation}
\stepcounter{zaehler}

\noindent {\it und f\"ur alle} $ A \in \Lambda_{3t+i}^3 $ {\it gilt}

\begin{equation}
{\rm per} \, A \leq \left\{ \begin{array}{l@{\quad{\it falls}\quad}l}
                            6^{t-1} \cdot 9, & i = 1, \\
                            \left[ 6^{t-2} \cdot 9^2 \right], & i = 2. \\
                            \end{array} \right.
\end{equation}
\stepcounter{zaehler}

Die in Satz 5.3 angegebenen Schranken sind bestm\"oglich. Ist n\"amlich $ J^{(n)} $ die $ n 
\times n $-Matrix, deren Elemente s\"amtlich $ 1 $ sind, und ist $ K_n $ wie in (1.7) 
erkl\"art, dann gilt Gleichheit in (5.4) und (5.5) f\"ur die Matrizen $ J^{(2)} \oplus 
\ldots \oplus J^{(2)} \oplus K_3 \;\; (J^{(2)} \;\; (t - 1) $-mal) beziehungsweise $ J^{(3)} 
\oplus \ldots \oplus J^{(3)} \oplus K_4 \;\; (J^{(3)} \;\; (t - 1) $-mal) beziehungsweise $ 
J^{(3)} \oplus \ldots \oplus J^{(3)} \oplus K_4 \oplus K_4 \;\; (J^{(3)} \;\; 
(t - 2) $-mal). F\"ur $ n > 3 $ gibt es lediglich vermutete Schranken.

\bigskip

{\bf 5.2. Beliebige nichtnegative Matrizen.} \quad In Abschnitt 3 wurde das 
Mi\-ni\-mum der 
Permanente auf der Menge der doppeltstochastischen Matrizen bestimmt. Im Gegensatz zu diesem 
l\"a"st sich das Maximum sehr leicht bestimmen.

\bigskip

{\sc Satz 5.4} \, (Marcus-Newman [37, pp. 61 - 62]). \quad {\it F\"ur alle} $ A \in \Omega_n 
$ {\it gilt}

\begin{equation}
{\rm per} \, A \leq 1.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Gleichheit tritt in} (5.6) {\it genau dann auf, wenn} $ A $ {\it eine
Permutationsmatrix ist.}

\bigskip

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

\bigskip

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

\begin{equation}
{\rm per} \, A \leq \prod_{i=1}^n \, \sum_{t=1}^i \, a_{it}^{\ast}.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Ist} $ A $ {\it positiv, dann besteht in} (5.7) {\it Gleichheit genau dann, 
wenn die ersten} $ n - 1 $ {\it Zeilen von} $ A $ {\it kollinear zum Vektor} $ (1, \ldots, 
1) $ {\it sind}.

\bigskip

Mit der gleichen Begr\"undung wie in der Bemerkung nach Satz 4.7 kann man die rechte Seite 
von (5.7) ersetzen durch das Minimum dieser Ausdr\"ucke \"uber alle Permutationen der 
Zeilenindizes. \\
Es sei $ A = (a_{ij}) $ wiederum eine nichtnegative $ n \times n $-Matrix mit den 
Zeilensummen $ r_1, \ldots, r_n $ und den Spaltensummen $ s_1, \ldots, s_n $. Dann gilt

\begin{equation}
{\rm per} \, A \leq \prod_{i=1}^n r_i
\end{equation}
\stepcounter{zaehler}

\noindent und

\begin{equation}
{\rm per} \, A \leq \prod_{i=1}^n s_i,
\end{equation}
\stepcounter{zaehler}

\noindent da auf der rechten Seite von (5.8) und (5.9) im allgemeinen \"uberfl\"ussige
Terme auftreten. Aus diesen Ungleichungen folgt schlie"slich

\begin{equation}
{\rm per} \, A \leq {\rm min} \left( \prod_{i=1}^n \, r_i, \prod_{i=1}^n \, s_i \right),
\end{equation}
\stepcounter{zaehler}

\noindent was sich in folgender Weise verbessern l\"a"st:

\bigskip

{\sc Satz 5.6} \, (Jurkat-Ryser [23, p. 354]). \quad {\it Es sei} $ A $ {\it eine 
nichtnegative} $ n \times n $-{\it Matrix mit den Zeilensummen} $ r_1, \ldots, r_n $ {\it 
und den Spaltensummen} $ s_1, \ldots, s_n $. {\it Dann gilt}

\begin{equation}
{\rm per} \, A \leq \prod_{i=1}^n \, {\rm min} \, (r'_i, s'_i).
\end{equation}
\stepcounter{zaehler}

\bigskip

Diese Absch\"atzung ist bestm\"oglich: Es sei $ A = (a_{ij}) $ eine Matrix, die den 
Voraussetzungen von Satz 5.6 gen\"ugt. Ferner enthalte jede (rechteckige) 
Un\-ter\-ma\-trix von $ 
A $ eine Zeile oder Spalte mit h\"ochstens einem positiven Element und es gelte $ a_{ii} = 
{\rm min} \, (r'_i, s'_i) $ f\"ur $ i = 1, \ldots, n$. Dann tritt in (5.11) Gleichheit auf.

\bigskip

{\bf 5.3. (1,--1)-Matrizen.} \quad Auf der Menge $ \Gamma_n $ der $ n \times 
n$-$ (1,-1) $-Matrizen ist das Maximum des Absolutbetrages der Permanente klarerweise durch 
$ n $! gegeben; diese Schranke wird beispielsweise f\"ur die Matrix $ J^{(n)} $ erreicht. 
Wang [68, p. 360] stellte unter anderem die Frage nach scharfen oberen Schranken f\"ur den 
Fall, da"s die betrachteten Matrizen in $ \Gamma_n $ nichtsingul\"ar sind. Diesem Problem
werden wir uns nun widmen. Dabei spielen drei spezielle Matrizen aus $ \Gamma_n $ eine 
wichtige Rolle:

\begin{equation}
D_n = \left[ \begin{array}{cccc}
             -1 & 1 & \ldots &  1 \\
             1 & \ddots & \ddots & \vdots \\
             \vdots & \ddots & \ddots & 1 \\
             1 & \ldots & 1 & - 1
             \end{array} \right],
\end{equation}
\stepcounter{zaehler}

\begin{equation}
C_n = \left[ \begin{array}{cccc}
             1 & 1 & \ldots &  1 \\
             1 & -1 & \ddots & \vdots \\
             \vdots & \ddots & \ddots & 1 \\
             1 & \ldots  & 1 & - 1 \\
             \end{array} \right],
\end{equation}
\stepcounter{zaehler}

\begin{equation}
S_n = \left[ \begin{array}{cccc}
             1 & -1 & \ldots & -1 \\
             \vdots & \ddots & \ddots & \vdots \\
             \vdots & & \ddots & -1 \\
             1 & \ldots  & \ldots & 1
             \end{array} \right].
\end{equation}
\stepcounter{zaehler}

\newpage

{\sc Satz 5.7.}

\begin{equation}
\omega_n := {\rm per} \, D_n = \sum_{k=0}^n \frac{n!}{k!} \, (-2)^k .
\end{equation}
\stepcounter{zaehler}

\begin{equation}
\vartheta_n := {\rm per} \, C_n = (n + 2) \sum_{k=0}^{n-1} \frac{(n-1)!}{k!} \, (-2)^k + (-
2)^n .
\end{equation}
\stepcounter{zaehler}

Die Beziehungen (5.15) und (5.16) folgen unmittelbar aus einem Satz von Perfect [54, p. 236] 
\"uber die Anzahl positiver Diagonalprodukte in Matrizen der zur 
Dis\-kus\-si\-on stehenden 
Gestalt.

\bigskip

{\sc Satz 5.8} \, (Kr\"auter-Seifter [29, p. 57]). 
 
\begin{equation}
\left\{ \begin{array}{lll}
        {\rm per} \, S_{2n-1}  & = & 2^{2n-1} (2^n - 1) B_{2n}/n , \\
        {\rm per} \, S_{2n} & = & 0 , \\
        \end{array} \right. 
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $ B_n $ {\it die} $ n $-{\it te Bernoulli-Zahl bezeichnet.}

\bigskip
Die Herleitung dieses Ergebnisses erfordert die Kenntnis des {\it Hit-Po\-ly\-noms}
(Ri\-or\-dan 
[56, p. 165]) und der exponentiell erzeugenden Funktion f\"ur Euler-Polynome 
(Ab\-ra\-mo\-witz-Stegun [1, p. 804]). Bemerkenswert ist, da"s die Folge $ \langle \tau_n \rangle 
$ mit $ \tau_n = |{\rm per} \, S_n| $ gerade die Tangensfunktion als exponentiell erzeugende 
Funktion besitzt, das hei"st 

\begin{equation}
\sum_{n=0}^{\infty} \, \tau_n \, \frac{x^n}{n!} = \tan \, x ,
\end{equation}
\stepcounter{zaehler}

\noindent wenn man noch $ \tau_0 = 0 $ definiert (Abramowitz-Stegun [1, p. 75]). Die $ 
\tau_n $ werden aufgrund dieses Zusammenhangs in der einschl\"agigen Literatur {\it 
Tangens-Zahlen} ge\-nannt (Comtet [12, p. 259]). \\
Zwei Matrizen $ A, B \in \Gamma_n $ m\"ogen zueinander {\it \"aquivalent} hei"sen $ (A \sim 
B) $, falls $ B $ aus $ A $ durch Hintereinanderausf\"uhrung 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\"ur zwei zueinander \"aquivalente Matrizen $ A, B \in \Gamma_n $

\begin{equation}
|{\rm per} \, A| = |{\rm per} \, B|.
\end{equation}
\stepcounter{zaehler}

\noindent Eine detaillierte Betrachtung der eingangs erw\"ahnten Fragestellung f\"ur $ n 
\leq 5 $ liefert zun\"achst die Beziehung

\begin{equation}
|{\rm per} \, A| \leq \vartheta_5 = 24
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur alle nichtsingul\"aren $ A \in \Gamma_5 $. Gleichheit tritt in (5.20) genau 
dann auf, wenn $ A \sim C_5 $ gilt. Ferner haben wir 

\begin{equation}
|{\rm per} \, A| \leq \omega_5 = 8
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur alle nichtsingul\"aren $ A \in \Gamma_5 $ mit $ A \not\sim C_5 $ und $ A 
\not\sim S_5 $. Entgegen

\begin{equation}
16 = \tau_5 > \omega_5 = 8
\end{equation}
\stepcounter{zaehler}

\noindent kann mithilfe von Satz 5.8 gezeigt werden, da"s f\"ur alle $ n \geq 6 $

\begin{equation}
\tau_n < \omega_n
\end{equation}
\stepcounter{zaehler}

\noindent gilt, soda"s die f\"ur $ n = 5 $ erforderliche Zusatzbedingung $ A \not\sim S_5 $
f\"ur den Nachweis der G\"ultigkeit von (5.21) entfallen kann. Schlie"slich gelangt man zu 
zwei Vermutungen (Kr\"auter-Seifter [30]).

\bigskip

{\sc Vermutung 1.} \quad {\it Es sei} $ A \in \Gamma_n $ {\it nichtsingul\"ar,} $ n \geq 5 
$. {\it Dann gilt}

\begin{equation}
|{\rm per} \, A| \leq \vartheta_n,
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei das Gleichheitszeichen genau dann zutrifft, wenn $ A \sim C_n $ gilt.}

\bigskip

{\sc Vermutung 2.} \quad {\it Es sei} $ A \in \Gamma_n $ {\it nichtsingul\"ar mit} $ A 
\not\sim C_n, n \geq 6 $. {\it Dann gilt}

\begin{equation}
|{\rm per} \, A| \leq \omega_n.
\end{equation}
\stepcounter{zaehler}

Eine Charakterisierung des Gleichheitsfalles in (5.25) ist nicht bekannt. Ein allgemeiner 
Beweis dieser Vermutungen d\"urfte ziemlich schwierig sein, da die 
Nicht\-sin\-gu\-la\-ri\-t\"at (eine 
\"uber die Determinante definierte Eigenschaft!) zuwenig
In\-for\-ma\-ti\-o\-nen \"uber die Struktur 
der Matrix liefert, deren Permanente berechnet werden soll. Im Rahmen eines allgemeinen 
Satzes konnte aber folgendes gezeigt werden:

\bigskip

{\sc Satz 5.9} \, (Kr\"auter-Seifter [30]). \quad {\it Die Vermutungen 1 und 2 sind richtig 
f\"ur alle in Frage kommenden Matrizen mit h\"ochstens zwei negativen Elementen je Zeile und 
Spalte sowie f\"ur alle dazu \"aquivalenten Matrizen.}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 6. Andere Problemkreise}
\end{center}

In diesem Abschnitt werden neuere Ergebnisse der Permanententheorie 
be\-spro\-chen, welche sich 
nicht unmittelbar in die bereits behandelten Themen einordnen lassen. 

\bigskip

In [46, p. 155] f\"uhrt Minc als \"alteste unbewiesene Permanenten-Ver\-mu\-tung jene von 
Scott [61] aus dem Jahr 1881 an. Nach rund einhundert Jahren haben drei Autoren unabh\"angig 
voneinander einen Beweis daf\"ur gefunden.

\bigskip

{\sc Satz 6.1} \, (Minc [48, p. 145]; Kittappa [24, p. 75]; Svrtan [63, p. 204]). \quad {\it 
Es sei} $ A = (a_{ij}) $ {\it eine} $ n \times n $-{\it Matrix mit} $ a_{ij} = (x_i - y_j 
)^{-1} $, {\it wobei} $ x_1, \ldots, x_n $ {\it und} $ y_1, \ldots, y_n $ {\it die 
verschiedenen L\"osungen der Gleichungen} $ x^n - 1 = 0 $  {\it beziehungsweise} $ y^n + 1 = 
0 $ {\it sind. Dann gilt}

\begin{equation}
|{\rm per} \, A| = \left\{ \begin{array}{ll}
                           n \cdot 2^{-n} [1 \cdot 3 \cdot 5 \cdot \ldots \cdot (n - 2)]^2 &
                           \mbox{\it f\"ur ungerades} \quad n, \\
                           0 & \mbox{\it f\"ur gerades} \quad n. \\ 
                           \end{array} \right.
\end{equation}
\stepcounter{zaehler}

Die entscheidende Grundlage aller drei Beweise ist der 

\bigskip

{\sc Satz 6.2} \, (Borchardt [7, p. 194]). \quad  {\it Es sei} $ A = (a_{ij}) $ {\it eine} $ 
n \times n $-{\it Matrix mit} $ a_{ij} = (x_i - y_j)^{-1} $, {\it wobei} $ x_1, \ldots, 
x_n, y_1, \ldots, y_n $ {\it komplexe Zahlen bezeichnen. Dann gilt}

\begin{equation}
\det \, A \; {\rm per} \, A = \det \, (A \ast A),
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $ \ast $ {\it das Hadamard-Produkt zweier Matrizen bezeichnet}.

\bigskip

Den k\"urzesten 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 $ 
\varepsilon \in H $ beliebig, aber fest gew\"ahlt. Aufgrund der vollst\"andigen Symmetrie 
der Permanente in den Zeilen und Spalten des Arguments darf man annehmen, da"s die Elemente 
aus $ G $ aund $ H $  von der Gestalt

\begin{equation}
\left\{ \begin{array}{cccc}
        x_i & = & \alpha^i & \,\, (i = 1, \ldots, n), \\
        y_j & = & \varepsilon \alpha^j & \,\, (j = 1, \ldots, n) \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent sind, wobei $ \alpha $ eine beliebige primitive $ n $-te Einheitswurzel ist. 
F\"uhrt man nun die Bezeichnungen $ D_1 = \det \, A $ und $ D_2 = \det \, (A \ast A) $ ein, 
dann kann man unter Betrachtung spezieller, aus den Termen $(1 - \varepsilon 
\alpha^k)^{-\nu} $ zusammengesetzter zirkulanter Matrizen zeigen, da"s

\begin{equation}
D_{\nu} = (-1)^{(n-1)\nu} \, \prod^n_{k=1} \, f_{\nu} (x_k)
\end{equation}
\stepcounter{zaehler}

\noindent mit 

\begin{equation}
f_{\nu} (x_k) = \varepsilon^{-k} \sum_{h \in H} \, \sum^k_{j=0} \, (-1)^j {k \choose j} (1 - 
h)^{j-\nu}
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur $ \nu = 1 $ und $\nu = 2 $ gilt. Spaltet man die innere Summe in (6.5) 
entsprechend $ j \leq \nu - 1 $ und $ j \geq \nu $ in zwei Teile auf und ber\"ucksichtigt 
man die Tatsache, da"s 

\begin{equation}
\sum _{h \in H} \, h^t = \left\{ \begin{array}{ll}
                                 n & \mbox{f\"ur} \quad t = 0, \\
                                 0 & \mbox{f\"ur} \quad 0 < t < n \\
                                 \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent ist, dann erh\"alt man aus (6.5)

\begin{equation}
f_{\nu} (x_k) = \varepsilon^{-k} \, \sum_{j=0}^{\nu-1} \, (-1)^j {k \choose j} \left\{ 
\sum_{h \in H} \, (1 - h)^{j-\nu} - n \right\} .
\end{equation}
\stepcounter{zaehler}

\noindent Damit sowie mit

\begin{equation}
\sum_{h \in H} \, (1 - h)^{-1} = \frac{n}{2}, \qquad \sum_{h \in H} \, (1 - h)^{-2} = 
\frac{n(2-n)}{4}
\end{equation}
\stepcounter{zaehler}

\noindent folgt \"uber (6.4) die Darstellung

\begin{equation}
D_{\nu} = \left\{ \begin{array}{ll}
                  -(\frac{n}{2})^n \, \prod_{k=1}^n \, \varepsilon^{-k} & \mbox{f\"ur} \quad                                                                      
                  \nu = 1,\\
                  & \\
                  (-\frac{n}{4})^n \, \prod_{k=1}^n \,  \varepsilon^{-k} (n - 2k + 2) & 
                  \mbox{f\"ur} \quad \nu = 2. \\
                  \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Wegen $ D_1 \not= 0 $ folgt schlie"slich aus Satz 6.2  $ \; (D_1 \, {\rm per} \, A 
= D_2) $

\begin{equation}
{\rm per} \, A = (-1)^{n-1} 2^{-n} \, \prod_{k=1}^n \, (n - 2k + 2)
\end{equation}
\stepcounter{zaehler}

\noindent und daraus (6.1).

\bigskip

1967 \"au"serten Marcus und Minc [40, p. 306] die folgende

\bigskip

{\sc Vermutung}. \quad {\it Es sei} $ n \geq 2 $. {\it Dann gilt f\"ur alle} $ S \in \Omega 
_n $

\begin{equation}
{\rm per} \, S \geq {\rm per} \, \left(\frac{nJ_n - S}{n - 1}\right).
\end{equation}
\stepcounter{zaehler}

\noindent {\it Ist} $ n \geq 4 $, {\it dann gilt in} (6.11) {\it das Gleichheitszeichen
genau dann, wenn} $ S = J_n $ {\it gilt.}\footnote{Die in [40] urspr\"unglich f\"ur $ n \geq 
3 $ formulierte Gleichheitsbedingung wurde f\"ur $ n = 3 $ von Wang [69] als falsch 
erkannt.}

\bigskip

Wie die erw\"ahnten Autoren zeigten, folgt aus dieser Vermutung jene von van der Waerden. 
W\"ahrend 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\"ur hinreichend nahe bei $ J_n $ liegende sowie f\"ur positiv 
semidefinite symmetrische $ S \in \Omega_n $, Wang [69, p. 147] f\"ur $ n = 3 $ und Foregger 
[16, p. 125] f\"ur $ n = 4 $. In seiner vor kurzem erschienenen Arbeit [11] wies Chang die 
G\"ultigkeit von (6.11) im Komplement einer Umgebung von $ J_n $ nach.

\bigskip

{\sc Satz 6.3} \, (Chang [11, p. 116]). \quad {\it Es sei} $ f(S) = {\rm per} \, \left( 
(nJ_n - S)/(n-1) \right) $ {\it f\"ur} $ S \in \Omega_n $ {\it und es sei }$ k_n = d_n(n - 
1)^{-n} $, {\it wobei} $ d_n $ {\it die} $ n $-{\it te D\'erangement-Zahl bezeichnet. Dann 
gilt}

\begin{equation}
\max_{S \in \Omega_n} \, (f(S)) = f(I) = k_n .
\end{equation}
\stepcounter{zaehler}

\noindent {\it Ist} $ n \geq 2 $ {\it und ist} $ {\rm per} \, S \geq k_n $ {\it f\"ur} $ S 
\in \Omega_n $, {\it dann gilt} (6.11).

\bigskip

Nach Satz 6.3 ist $ h_n := {\rm min}_{S \in \Omega_n} ({\rm per} \, S) = n! \, n^{-n} $;
die G\"ultigkeit der Vermutung ist also nur mehr f\"ur $ h_n \leq {\rm per} \, S < k_n $ 
ungekl\"art. Diese L\"ucke wird f\"ur wachsendes $ n $ stets kleiner: aus (1.11) folgt 
n\"amlich $ d_n \sim n!/e $ und damit $ |k_n - h_n| \to 0 $ f\"ur $ n \to \infty $. Es sei $ 
U = (nJ_n - I)/(n-1) $; dann gilt f\"ur alle $ S \in \Omega_n \quad (nJ_n -S)/(n-1) = SU $
und (6.11) l\"a"st sich schreiben in der Form

\begin{equation}
{\rm per} \, S \geq {\rm per} \, SU.
\end{equation}
\stepcounter{zaehler}

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, \ldots, r_n) $ bezeichne das Ereignis, da"s sich in der Schachtel $ m_j $ gerade $ r_j 
$ Kugeln befinden $ (j = 1, \ldots, n) $, wobei $ (m_1, \ldots, m_n) $ eine Permutation von
$ (1, \ldots, n) $ ist. Bezeichnet man bei einem simultanen \"Ubergang $ T_A $ aller $ n $ 
Kugeln die Wahr\-schein\-lich\-keit, da"s 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, \ldots, r_n) $ die Wahrscheinlichkeit, da"s das Ereignis $ (r_1, \ldots, r_n) $ 
nach dem \"Ubergang $ T_A $ auftritt, wobei der An\-fangs\-zu\-stand $ (1, \ldots, 1) $ war, dann 
gilt

\begin{equation}
p_A (1, \ldots, 1) = {\rm per} \, A.
\end{equation}
\stepcounter{zaehler}

\noindent Bezeichnet ferner $ q_A (r_1, \ldots, r_n) $ die Wahrscheinlichkeit, da"s das 
Ereignis \\
$ (1, \ldots, 1) $ nach dem \"Ubergang $ T_A $ auftritt, wobei der Anfangszustand \\
$ (r_1, \ldots, r_n) $ war, dann erh\"alt man mithilfe wahrscheinlichkeitstheoretischer 
\"Uber\-le\-gun\-gen bei Summation \"uber alle m\"oglichen Zust\"ande $ (r_1, \ldots, r_n) $

\begin{equation}
{\rm per} \, SU = \sum p_S (r_1, \ldots, r_n) \; q_U (r_1, \ldots, r_n)
\end{equation}
\stepcounter{zaehler}

\noindent und

\begin{equation}
q_U (r_1, \ldots, r_n) \leq q_U (1, \ldots, 1) = k_n,
\end{equation}
\stepcounter{zaehler}

\noindent woraus

\begin{equation}
{\rm per} \, SU \leq q_U (1, \ldots, 1) \sum p_S (r_1, \ldots, r_n) = k_n
\end{equation}
\stepcounter{zaehler}

\noindent folgt. Damit ergibt sich wegen $ {\rm per} \, SU = f(S) $

\begin{equation}
f(S) \leq k_n = f(I).
\end{equation}
\stepcounter{zaehler}

\noindent F\"ur $ {\rm per} \, S \geq k_n $ folgt aus (6.13) und (6.18) sofort (6.11). 

\bigskip

Abgesehen von verschiedenen Verallgemeinerungen der Vermutung von van der Waerden (siehe 
auch Satz 3.8) und den Bem\"uhungen, sie zu beweisen, bietet das Studium der Permanente auf 
der Menge $ \Omega_n $ auch anderweitig ein interessantes Bet\"atigungsfeld (siehe [50, pp. 
237 - 239]), aus welchem hier ein Teilaspekt heraus\-ge\-grif\-fen werden soll. \\
Der Satz von Birkhoff [6, p. 147] besagt, da"s $ \Omega_n $ ein konvexes Polyeder bildet, 
dessen $ n! $ Ecken die $ n \times n $-Permutationsmatrizen sind. Es liegt nahe zu fragen, 
ob die Permanente eine konvexe Funktion auf $ \Omega_n $ ist. F\"ur $ n = 2 $ kann man in 
der Tat direkt zeigen, da"s

\begin{equation}
{\rm per} \, \left(\alpha B + (1 - \alpha) \, A \right) \leq \alpha \, {\rm per} \, B + (1 - 
\alpha) \, {\rm per} \, A
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur alle $ A, B \in \Omega_2 $ und f\"ur alle $ \alpha, \; 0 \leq \alpha \leq 
1 $, gilt. F\"ur $ n = 3 $ hingegen konnte Marcus ein Gegenbeispiel angeben (siehe auch 
Perfect [53]). In der Folge wurde versucht, entsprechende Aussagen durch geeignete 
Einschr\"ankungen von $ B $ zu bekommen. Perfect [53] bewies (6.19) f\"ur $ B = I $ und $ 
\alpha = \frac{1}{2} $ sowie f\"ur beliebiges $ A \in \Omega_n $. Eine Verbesserung 
erzielten Brualdi und Newman [9] f\"ur $ B = I $ und alle $ \alpha $ mit $ 0 \leq \alpha 
\leq 1 $ sowie f\"ur beliebiges $ A \in \Omega_n $. Angeregt durch ein weiteres Resultat
dieser Autoren besch\"aftigten sich Lih und Wang [33] mit der folgenden

\bigskip

{\sc Vermutung}. \quad {\it F\"ur alle} $ A \in \Omega_n $ {\it und f\"ur alle} $ \alpha $ 
{\it mit} $ \frac{1}{2} \leq \alpha \leq 1 $ {\it gilt}

\begin{equation}
{\rm per} \, \left(\alpha J_n + (1 - \alpha) A \right) \leq \, \alpha \; {\rm per} \, J_n + 
(1 - \alpha) \; {\rm per} \, A.
\end{equation}
\stepcounter{zaehler}

Ein Beweis von (6.20) ist bisher nur f\"ur $ n = 3 $ gegl\"uckt; im Fall $ n = 4 $ hat man 
bereits mit erheblichen Schwierigkeiten zu rechnen.

\bigskip

{\sc Satz 6.4} \, (Lih-Wang [33]). \quad {\it Obige Vermutung ist richtig f\"ur} $ n = 3 $. 
{\it Das Gleichheitszeichen tritt genau dann auf, wenn entweder} $ \alpha = 1 $ {\it ist 
oder} $ A = J_3 $ {\it oder} $ \alpha = \frac{1}{2} $ {\it und} $ A = \frac{1}{2} \, (3 J_3 
- I ) $ {\it bis auf Zeilen- oder Spaltenvertauschungen}.

\bigskip

Da nach Satz 3.6 $ {\rm per} \, B \geq {\rm per} \, J_3 $ f\"ur alle $ B \in  \Omega_3 $ 
gilt, erh\"alt man aus Satz 6.4 unmittelbar die Beziehung

\begin{equation}
{\rm per} \, J_3 \leq {\rm per} \, \left(\alpha J_3 + (1 - \alpha) A \right) \leq {\rm per} 
\, A
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur alle $ A \in \Omega_3 $ und f\"ur alle $ \alpha $ mit $ \frac{1}{2} \leq
\alpha \leq 1 $. 

\bigskip

Von hermiteschen Matrizen handelt eine auf Marcus [46, p. 156] zur\"uckgehende

\bigskip

{\sc Vermutung}. \quad {\it Es sei} $ A $ {\it eine positiv semidefinite hermitesche} $ nk 
\times nk $-{\it Matrix, zusammengesetzt aus} $ k^2 $  {\it Bl\"ocken} $ A_{ij} $, {\it 
welche} $ n \times n $-{\it Matrizen sind. Ferner sei} $ B = (b_{ij}) $ {\it die} $ k \times 
k $-{\it Matrix mit} $ b_{ij} = {\rm per} \, A_{ij} \, \, (i,j = 1, \ldots, k). $ {\it Dann 
gilt}

\begin{equation}
{\rm per} \, A \geq {\rm per} \, B .
\end{equation}
\stepcounter{zaehler}

\noindent {\it Sind alle} $ A_{ii} $ {\it positiv definit, dann gilt in} (6.22) {\it 
Gleichheit genau dann, wenn} $ A $ {\it die Form} $ A = A_{11} \oplus \ldots \oplus A_{kk} $ 
{\it besitzt}.

\bigskip

Lieb [32] best\"atigte diese Vermutung f\"ur $ k = 2 $. Vor kurzem gelang es dann Pate, 
f\"ur symmetrische Matrizen und f\"ur hinreichend gro"se $ n $ (bei beliebigem $ k $) eine 
Ungleichung zu beweisen, welche (6.22) versch\"arft.

\bigskip

{\sc Satz 6.5} \, (Pate [52, p. 14]). \quad {\it Es sei} $ A $ {\it eine positiv 
semidefinite symmetrische} $ nk \times nk $-{\it Matrix von der in der obigen Vermutung 
angegebenen Struktur. Ferner sei} $ C = (c_{ij}) $ {\it die} $ k \times k $-{\it Matrix 
mit} $ c_{ij} = |{\rm per} \, A_{ij}| \;\; (i,j = 1, \ldots, k) $. {\it Dann gibt es f\"ur 
jedes} $ k $ {\it eine nat\"urliche Zahl} $ n_k $, {\it so da"s f\"ur alle} $ n \geq n_k $ 
{\it gilt:}

\begin{equation}
{\rm per} \, A \geq {\rm per} \, C.
\end{equation}
\stepcounter{zaehler}

Im Beweis dieses Satzes ben\"utzt Pate die Tatsache, da"s eine positiv semidefinite 
symmetrische $ m \times m $-Matrix stets darstellbar ist als Gramsche Matrix $ ((x_i, x_j)) 
$ geeigneter Vektoren $ x_1, \ldots x_m $ aus dem $ {\bf{R}}^m $, wobei (.,.) das innere 
Produkt im  $ {\bf{R}}^m $ bezeichnet. Aufgrund eines von Marcus und Newman [39, pp. 48 
- 49] entdeckten fundamentalen Zusammenhangs l\"a"st sich die Permanente einer Gramschen 
Matrix zur\"uckf\"uhren auf ein inneres Produkt in der Symmetrieklasse der vollst\"andig 
sym\-me\-tri\-schen Tensoren. Auf die ziemlich komplizierten Details soll hier nicht eingegangen 
werden. 

\bigskip

Wir schlie"sen mit einigen Betrachtungen \"uber zirkulante Matrizen. Solche
Ma\-tri\-zen treten 
beispielsweise bei der Behandlung klassischer kombinatorischer 
Fra\-ge\-stel\-lun\-gen, wie etwa 
beim {\it probl\`eme des rencontres} oder beim {\it probl\`eme des m\'enages,} auf. $ P_n $ 
bezeichne die $ n \times n $-Permutationsmatrix mit Einsen an den Stellen 
$ (1, 2), (2, 3), \break
\ldots, (n - 1, n), (n,1). $ Dann nennen wir eine Matrix der Form

\begin{equation}
Z = \sum^{n-1}_{i=0} \, \lambda_i P^{i}_n
\end{equation}
\stepcounter{zaehler}

\noindent mit $ \lambda_i \in \{0, 1\} \quad (i= 0, 1, \ldots, n - 1) $ und $ P^0_n = I $ 
eine {\it zirkulante} $ (0,1) $-{\it Matrix} oder (wie im folgenden stets bezeichnet) {\it 
Zirkulante}. Der \"Ubersicht in Minc [46, pp. 44 - 48] kann man entnehmen, da"s bis vor 
kurzem lediglich Zirkulanten mit $ \lambda_0 = \ldots = \lambda_{k-1} = 1 $ und $ \lambda_k 
= \ldots = \lambda_{n-1} = 0 $ betrachtet worden sind. Eades, Praeger und Seberry [13] haben 
sich mit Zirkulanten allgemeinerer Bauart besch\"aftigt, wobei vor allem die verschiedenen 
Methoden, die zur Berechnung ihrer Permanente he\-ran\-ge\-zo\-gen wurden, Beachtung verdienen. Um 
die Notation einfacher zu gestalten, gen\"ugt es, eine Zirkulante mit den Positionen der 
Einsen in ihrer ersten Zeile zu identifizieren. Ist also $ A = (a_{ij}) \quad (i, j = 0, 1, 
\ldots, n - 1) $ und gilt $ a_{0j_0} = \ldots = a_{0j_r} = 1 \quad (0 \leq r \leq n-1) $, 
dann schreiben wir $ A =(j_0, \ldots, j_r) $. Zwei Zirkulanten $ A = (a_{ij}) $ 
und $ B = (b_{ij}) $ m\"ogen zueinander {\it \"aquivalent} hei"sen, wenn es Zahlen $ x, y 
\in \{0, 1,\ldots, n - 1\} $ gibt, so da"s $ {\rm ggT} (x, n) = 1 $ und f\"ur jedes $ j \in 
\{0, 1, \ldots, n - 1 \} \;\; a_{0, xj+y} = b_{0j} $ gilt. Es sei $ A = (a_{ij}) $ eine $ n 
\times n $-Matrix und $ B $ eine $ k \times k $-Matrix. Unter dem {\it Kronecker-Produkt} $ 
A \otimes B $ von  $ A $ und $ B $ verstehen wir die $ nk \times nk$-Matrix, die aus den
$ n^2 $ Bl\"ocken $ a_{ij}B \;\; (i, j = 0, 1, \ldots, n - 1) $ zusammengesetzt ist.

\bigskip

{\sc Satz 6.6} \, (Eades-Praeger-Seberry [13, pp. 148 - 149]). \quad {\it Es sei} $ A $ {\it 
eine beliebige} $ (0, 1) $-{\it Matrix und es bezeichne} $ I_{\nu} $ {\it die} $ \nu \times 
\nu $-{\it Einheitsmatrix. Dann gilt}

\begin{equation}
{\rm per} \, (A \otimes I_k) = ({\rm per} \, A)^k
\end{equation}
\stepcounter{zaehler}

\noindent {\it und}

\begin{equation}
{\rm per} \, \left((I_k + P_k) \otimes J^{(m)}\right) = (m!)^k \, \sum_{j=0}^m \, {m \choose 
j}^k .
\end{equation}
\stepcounter{zaehler}

W\"ahrend man (6.25) unmittelbar durch geeignete Zeilen- und
Spal\-ten\-ver\-tau\-schun\-gen erh\"alt, 
ist f\"ur die Herleitung von (6.26) explizites Abz\"ahlen der positiven 
Dia\-go\-nal\-pro\-duk\-te 
erforderlich. Nat\"urlich sind die in Satz 6.6 betrachteten Matrizen im allgemeinen keine 
Zirkulanten, doch kann man mit den dortigen For\-meln fol\-gen\-des herleiten. Wir betrachten eine
$ n \times n $-Zirkulante mit zwei positiven Elementen je Zeile, also eine Matrix $ (a, b) 
$. Ist dann $ {\rm ggT}(n, a - b) = g $, dann sind $ (a, b) $ und $ (0, g) $ zueinander 
\"aquivalent und wegen $ (0, g) = (I_{n/g} + P_{n/g}) \otimes I_g $ folgt

\begin{equation}
{\rm per} \, (a, b) = ({\rm per} \, (I_{n/g} + P_{n/g}))^g = 2^g.
\end{equation}
\stepcounter{zaehler}

\noindent Auf \"ahnliche Weise erh\"alt man f\"ur die $ 2k \times 2k $-Zirkulanten $ (0, 1, 
k, k + 1) $ sowie f\"ur die $ 3k \times 3k $-Zirkulanten $ (0, 1, k, k + 1, 2k, 2k + 1) $

\begin{equation}
\left\{ \begin{array}{lll}
       {\rm per} \, (0, 1, k, k + 1) & = & 2^{k+1} + 2^{2k}, \\
       {\rm per} \, (0, 1, k, k + 1, 2k, 2k + 1) & = & 2^{k+1} 3^k (1 + 3^k). \\
       \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Neben dem in Satz 6.6 ben\"utzten Beweisverfahren und neben der Herleitung von
Rekursionsformeln f\"ur schwach besetzte Zirkulanten mithilfe des Laplaceschen 
Ent\-wicklungs\-satzes wird noch die Methode der sogenannten komplement\"aren 
Ent\-wick\-lung 
vorgestellt, bei welcher es sich um eine besonders einfache Variante des 
In\-klu\-si\-ons-Ex\-klu\-si\-ons-Prin\-zips handelt. Es sei $ A = (a_{ij}) $ eine $ (0, 1) $-Matrix mit $ 
a_{km} = 1 $; die Matrizen $ B $ und $ C $ m\"ogen aus $ A $ hervorgehen, indem man $ a_{km} 
= 0 $ setzt beziehungsweise die $ k $-te Zeile und $ m $-te Spalte von $ A $ streicht. 
Aufgrund der Multilinearit\"at der Permanente folgt dann $ {\rm per} \, A = {\rm per} \, B + 
{\rm per} \, C $. Damit wurden beispielsweise die D\'erangement-Zahlen $ d_n = {\rm per} \, 
(1, 2, \ldots, n - 1) $ in Abschnitt 1 berechnet. Auf \"ahnliche Weise gelangt man zu den $ 
n $-ten {\it M\'enage-Zahlen} $ M_n = {\rm per} \, (2, 3, \ldots, n - 1) $ (siehe Ryser [58, 
p. 32]).

\bigskip

{\sc Satz 6.7} \, (Eades-Praeger-Seberry [13, p. 157]). \quad  {\it Es sei} $ n $ {\it 
gerade und es bezeichne} $ R_n $ {\it die Zirkulante} $ (1, 3, 4, \ldots, n - 1) $. {\it 
Dann gilt}

\begin{equation}
{\rm per} \, R_n = M_n + 2 .
\end{equation}
\stepcounter{zaehler}

Aus dem im Anschlu"s an Satz 6.6 Gesagten folgt f\"ur $ {\rm ggT}(n,x) = 2 $

\begin{equation}
{\rm per} \, (0, 1, 2, \ldots, x - 1, x + 1, \ldots, n - 1) = M_n + 2 .
\end{equation}
\stepcounter{zaehler}


\begin{center}
{\sc literatur}{\footnote {\rm Hier ist nur die zitierte Literatur angegeben. Ausf\"uhrliche
Bibliographien, versehen mit Kurzreferaten (!), findet man in Minc [46, pp. 161 - 199], [50,
pp. 250 - 262].}}
\end{center}

\setlength{\baselineskip}{12pt}

\begin{footnotesize}
\begin{enumerate}

\item Milton {\sc Abramowitz} and Irene A. {\sc Stegun} (editors), {\it Handbook of
Mathematical Functions.} Ninth printing. New York: Dover, 1972.
\item Aleksandr Danilovi\v{c} {\sc Aleksandrov,} K teorii sme\v{s}annych ob-emov vypuklych
tel IV. Sme\-\v{s}an\-nye diskriminanty i sme\v{s}annye ob-emy. [Zur Theorie der gemischten
Volumina konvexer K\"orper IV. Gemischte Diskriminanten und gemischte Volumina.] {\it
Ma\-te\-ma\-ti\-\v{c}es\-kij Sbornik (N. S.)} {\bf 3,} 227 - 251 (1938).
\item Th{\o}ger {\sc Bang,} On matrix-functions giving a good approximation to the v. d.
Waerden permanent conjecture. {\it Preprint, K{\o}benhavns Universitet,} 1979.
\item Nat\'alia {\sc Bebiano,} On the evaluation of permanents. {\it Pacific Journal of
Mathematics} {\bf 101,} 1 - 9 (1982).
\item Jacques {\sc Binet,} M\'emoire sur un syst\`eme de formules analytiques, et leur
application \'a des consid\'erations g\'eom\'etriques. {\it Journal de l'\'Ecole
Polytechnique} {\bf 9,} Cah. 16, 280 - 354 (1813).
\item Garrett {\sc Birkhoff,} Tres observaciones sobre el algebra lineal. {\it Revista de la
Universidad Nacional de Tucum\'an (A)} {\bf 5,} 147 - 151 (1946).
\item Carl Wilhelm {\sc Borchardt,} Bestimmung der symmetrischen Verbindungen vermittelst
ihrer erzeugenden Function. {\it Journal f\"ur die reine und angewandte Mathematik} {\bf
53,} 193 - 198 (1855).
\item L. M. {\sc Br\.egman,} Nekotorye svojstva neotricatel'nych matric i ich permanentov.
[Einige Eigenschaften nichtnegativer Matrizen und ihrer Permanenten.] {\it Doklady Akademii
Nauk SSSR} {\bf 211,} 27 - 30 (1973). $\,$ Englische \"Ubersetzung in: {\it Soviet
Mathematics Doklady} {\bf 14,} 945 - 949 (1973).
\item Richard Anthony {\sc Brualdi} and Morris {\sc Newman,} Inequalities for permanents and
per\-ma\-nen\-tal minors. {\it Proceedings of the Cambridge Philosophical Society} {\bf 61,} 741 -
746 (1965).
\item Augustin Louis {\sc Cauchy,} M\'emoire sur les fonctions qui ne peuvent obtenir que
deux valeurs \'egales et de signes contraires par suite des transpositions op\'er\'ees entre
les variables qu'elles renferment. {\it Journal de l'\'Ecole Polytechnique} {\bf 10,} Cah.
17, 29 - 112 (1815).
\item Derek K. {\sc Chang,} A note on a conjecture of M. Marcus and H. Minc. {\it Linear and
Multilinear Algebra} {\bf 13,} 115 - 117 (1983).
\item Louis {\sc Comtet,} {\it Advanced Combinatorics.} Revised and enlarged edition.
Translated from the French by J. W. {\sc Nienhuys.} Dordrecht: Reidel, 1974.
\item Peter {\sc Eades,} Cheryl Elisabeth {\sc Praeger,} and Jennifer Roma {\sc Seberry,}
Some remarks on the permanents of circulant (0,1) matrices. {\it Utilitas Mathematica} {\bf
23,} 145 - 159 (1983).
\item Grigorij Petrovi\v{c} {\sc Egory\v{c}ev,} Dokazatel'stvo gipotezy van der Vardena dlja
permanentov. [Beweis der Vermutung von van der Waerden f\"ur Permanenten.] {\it Sibirskij
Matemati\v{c}eskij \v{Z}urnal} {\bf 22,} Nom. 6, 65 - 71 (1981). $\,$ Englische
\"Ubersetzung in: {\it Advances in Mathematics} {\bf 42,} 299 - 305 (1981).
\item D. I. {\sc Falikman,} Dokazatel'stvo gipotezy van der Vardena o permanente dva\v{z}dy
sto\-chas\-ti\-\v{c}es\-koj matricy. [Beweis der Vermutung von van der Waerden \"uber die Permanente
einer dop\-pelt\-sto\-chas\-ti\-schen Matrix.] {\it Matemati\v{c}eskie Zametki} {\bf 29,} 931 - 938
(1981). $\,$ Englische \"Ubersetzung in: {\it Mathe\-ma\-ti\-cal Notes of the Academy of Sciences
of the USSR} {\bf 29,} 475 - 479 (1981).
\item Thomas Hustad {\sc Foregger,} Remarks on a conjecture of M. Marcus and H. Minc. {\it
Linear and Multilinear Algebra} {\bf 7,} 123 - 126 (1979).
\item Shmuel {\sc Friedland,} A lower bound for the permanent of a doubly stochastic matrix.
{\it Annals of Mathematics (2)} {\bf 110,} 167 - 176 (1979).
\item Shmuel {\sc Friedland,} A proof of a generalized van der Waerden conjecture on
permanents. {\it Linear and Multilinear Algebra} {\bf 11,} 107 - 120 (1982).
\item Georg {\sc Frobenius,} \"Uber zerlegbare Determinanten. {\it Sitzungsberichte der
K\"o\-nig\-lich-Preu"si\-schen Akademie der Wissenschaften zu Berlin, Physikalisch-Mathematische
Klas\-se} {\bf 1917,} 274 - 277 (1917).
\item Peter Murray {\sc Gibson,} Conversion of the permanent into the determinant. {\it
Proceedings of the American Mathe\-ma\-ti\-cal Society} {\bf 27,} 471 - 476 (1971).
\item Marshall {\sc Hall,} jr., Distinct representatives of subsets. {\it Bulletin of the
American Mathe\-ma\-ti\-cal Society} {\bf 54,} 922 - 926 (1948).
\item Wolfgang B. {\sc Jurkat} and Herbert John {\sc Ryser,} Matrix factorizations of
determinants and permanents. {\it Journal of Algebra} {\bf 3,} 1 - 27 (1966).
\item Wolfgang B. {\sc Jurkat} and Herbert John {\sc Ryser,} Term ranks and permanents of
nonnegative matrices. {\it Journal of Algebra} {\bf 5,} 342 - 357 (1967).
\item Rethinasamy {\sc Kittappa,} Proof of a conjecture of 1881 on permanents. {\it Linear
and Mul\-ti\-li\-near Algebra} {\bf 10,} 75 - 82 (1981).
\item Donald Ervin {\sc Knuth,} A permanent inequality. {\it The American Mathematical
Month\-ly} {\bf 88,} 731 - 740 (1981).
\item D\'enes {\sc K\H{o}nig,} \"Uber Graphen und ihre Anwendung auf Determinantentheorie
und Men\-gen\-leh\-re. {\it Mathematische Annalen} {\bf 77,} 453 - 465 (1916).
\item D\'enes {\sc K\H{o}nig,} \"Uber trennende Knotenpunkte in Graphen (nebst Anwendungen
auf De\-ter\-mi\-nan\-ten und Matrizen). {\it Acta Litterarum ac Scientiarum Szeged} {\bf 6,} 155 -
179 (1933).
\item Arnold Richard {\sc Kr\"auter} and Norbert {\sc Seifter,} On convertible
(0,1)-matrices. {\it Linear and Multilinear Algebra} {\bf 13,} 311 - 322 (1983).
\item Arnold Richard {\sc Kr\"auter} and Norbert {\sc Seifter,} On some questions concerning
permanents of $(1,-1)$-matrices. {\it Israel Journal of Mathematics} {\bf 45,} 53 - 62
(1983).
\item Arnold Richard {\sc Kr\"auter} and Norbert {\sc Seifter,} Some properties of the
permanent of $(1,-1)$-matrices. {\it Linear and Multilinear Algebra} {\bf 15,} 207 - 223
(1984).
\item Jeffrey Clark {\sc Lagarias,} The van der Waerden conjecture: Two Soviet solutions.
{\it Notices of the American Mathematical Society} {\bf 29,} 130 - 133 (1982).
\item Elliott Hershel {\sc Lieb,} Proofs of some conjectures on permanents. {\it Journal of
Mathematics and Mechanics} {\bf 16,} 127 - 134 (1966).
\item Ko-Wei {\sc Lih} and Edward Tzu-Hsia {\sc Wang,} A convexity inequality on the
permanent of doubly stochastic matrices. {\it Congressus Numerantium} {\bf 36,} 189 - 198
(1982).
\item Jacobus Hendricus van {\sc Lint,} Notes on Egoritsjev's proof of the van der Waerden
conjecture. {\it Linear Algebra and Its Applications} {\bf 39,} 1 - 8 (1981).
\item Jacobus Hendricus van {\sc Lint,} The van der Waerden conjecture: Two proofs in one
year. {\it The Mathematical Intelligencer} {\bf 4,} 72 - 77 (1982).
\item David {\sc London,} Some notes on the van der Waerden conjecture. {\it Linear Algebra
and Its Applications} {\bf 4,} 155 - 160 (1971).
\item Marvin {\sc Marcus} and Morris {\sc Newman,} On the minimum of the permanent of a
doubly stochastic matrix. {\it Duke Mathematical Journal} {\bf 26,} 61 - 72 (1959).
\item Marvin {\sc Marcus} and Henryk {\sc Minc,} On the relation between the
determinant and the permanent. {\it Illinois Journal of Mathematics} {\bf 5,} 376 - 381
(1961).
\item Marvin {\sc Marcus} and Morris {\sc Newman,} Inequalities for the permanent function.
{\it Annals of Mathematics (2)} {\bf 75,} 47 - 62 (1962).
\item Marvin {\sc Marcus} and Henryk {\sc Minc,} On a conjecture of B. L. van der Waerden.
{\it Pro\-ceed\-ings of the Cambridge Philosophical Society} {\bf 63,} 305 - 309 (1967).
\item David {\sc Merriell,} The maximum permanent in $ \Lambda_n^k $. {\it Linear and
Multilinear Algebra} {\bf 9,} 81 - 91 (1980).
\item Henryk {\sc Minc,} Upper bounds for permanents of (0,1)-matrices. {\it Bulletin of the
American Mathematical Society} {\bf 69,} 789 - 791 (1963).
\item Henryk {\sc Minc,} A lower bound for permanents of (0,1)-matrices. {\it Proceedings of
the American Mathematical Society} {\bf 18,} 1128 - 1132 (1967).
\item Henryk {\sc Minc,} Bounds for permanents of nonnegative matrices. {\it Proceedings of
the Edin\-burgh Mathematical Society (2)} {\bf 16,} 233 - 237 (1969).
\item Henryk {\sc Minc,} Rearrangements. {\it Transactions of the American Mathematical
Society} {\bf 159,} 497 - 504 (1971).
\item Henryk {\sc Minc,} {\it Permanents.} Encyclopedia of Mathematics and Its Applications,
Volume 6. Reading: Addison-Wesley, 1978.
\item Henryk {\sc Minc,} Evaluation of permanents. {\it Proceedings of the 
Edinburgh Mathematical So\-cie\-ty (2)} {\bf 22,} 27 - 32 (1979).
\item Henryk {\sc Minc,} On a conjecture of R. F. Scott (1881). {\it Linear Algebra and Its
Applications} {\bf 28,} 141 - 153 (1979).
\item Henryk {\sc Minc,} The van der Waerden permanent conjecture; pp. 23 - 40 in: {\it
General Inequalities 3,} edited by E. F. {\sc Beckenbach} and W. {\sc Walter.} International
Series of Numerical Mathematics, Volume 64. Basel: Birkh\"auser, 1983.
\item Henryk {\sc Minc,} Theory of permanents 1978 - 1981. {\it Linear and Multilinear
Algebra} {\bf 12,} 227 - 263 (1983).
\item Thomas {\sc Muir,} On a class of permanent symmetric functions. {\it Proceedings of
the Royal Society of Edinburgh} {\bf 11,} 409 - 418 (1882).
\item Thomas Head {\sc Pate,} Inequalities relating groups of diagonal products in a Gram
matrix. {\it Linear and Multilinear Algebra} {\bf 11,} 1 - 17 (1982).
\item Hazel {\sc Perfect,} An inequality for the permanent function. {\it Proceedings of the
Cambridge Philosophical Society} {\bf 60,} 1030 - 1031 (1964).
\item Hazel {\sc Perfect,} Positive diagonals of $\pm$1-matrices. {\it Monatshefte f\"ur
Mathematik} {\bf 77,} 225 - 240 (1973).
\item Gy\H{o}rgy {\sc P\'olya,} Aufgabe 424. {\it Archiv der Mathematik und Physik (3)} {\bf
20,} 271 (1913).
\item John {\sc Riordan,} {\it An Introduction to Combinatorial Analysis.} Fourth printing.
New York: Wiley, 1967.
\item Herbert John {\sc Ryser,} Matrices of zeros and ones. {\it Bulletin of the American
Mathematical Society} {\bf 66,} 442 - 464 (1960).
\item Herbert John {\sc Ryser,} {\it Combinatorial Mathematics.} The Carus Mathematical
Mo\-no\-graphs, Volume 14. Washington: The Mathematical Association of America, 1963.
\item Alexander {\sc Schrijver} and W. G. {\sc Valiant,} On lower bounds for permanents.
{\it Indagationes Mathematicae} {\bf 42,} 425 - 427 (1980).
\item Alexander {\sc Schrijver,} Bounds on permanents, and the number of 1-factors and
1-fac\-to\-ri\-za\-tions of bipartite graphs; pp. 107 - 134 in: {\it Surveys in Combinatorics,}
edited by E. K. {\sc Lloyd.} London Mathematical Society Lecture Note Series, Volume 82.
Cambridge: Cambridge University Press, 1983.
\item Robert Forsyth {\sc Scott,} Mathematical notes. {\it The Messenger of Mathematics (N.
S.)} {\bf 10,} 142 - 149 (1881).
\item Rodica {\sc Simion} and Frank W. {\sc Schmidt,} On $(+1,-1)$-matrices with vanishing
permanent. {\it Discrete Mathematics} {\bf 46,} 107 - 108 (1983).
\item Dragutin {\sc Svrtan,} Proof of Scott's conjecture. {\it Proceedings of the American
Mathematical Society} {\bf 87,} 203 - 207 (1983).
\item G\'abor {\sc Szeg\H{o},} L\"osung zu Aufgabe 424. {\it Archiv der Mathematik und
Physik (3)} {\bf 21,} 291 - 292 (1913).
\item Helge {\sc Tverberg,} On the permanent of a bistochastic matrix. {\it Mathematica
Scandinavica} {\bf 12,} 25 - 35 (1963).
\item Marc {\sc Voorhoeve,} A lower bound for the permanents of certain (0,1)-matrices. {\it
In\-da\-ga\-tio\-nes Mathematicae} {\bf 41,} 83 - 86 (1979).
\item Bartel Leendert van der {\sc Waerden,} Aufgabe 45. {\it Jahresbericht der Deutschen
Ma\-the\-ma\-ti\-ker-Vereinigung} {\bf 35,} 117 (1926).
\item Edward Tzu-Hsia {\sc Wang,} On permanents of $(1,-1)$-matrices. {\it Israel Journal of
Mathematics} {\bf 18,} 353 - 361 (1974).
\item Edward Tzu-Hsia {\sc Wang,} On a conjecture of M. Marcus and H. Minc. {\it Linear and
Mul\-ti\-li\-near Algebra} {\bf 5,} 145 - 148 (1977).
\item Herbert S. {\sc Wilf,} A mechanical counting method and combinatorial applications.
{\it Journal of Combinatorial Theory} {\bf 4,} 246 - 258 (1968).

\end{enumerate}
\end{footnotesize}

\vspace{36pt}

\begin{tabular}{lp{4.8cm}l}
& & Arnold Richard {\sc Kr\"auter} \\
& & Institut f\"ur Mathematik und \\
& & Angewandte Geometrie \\
& & Montanuniversit\"at Leoben \\
& & Franz-Josef-Stra"se 18 \\
& & A-8700 Leoben, \"Osterreich \\
& & E-mail: {\sf kraeuter@unileoben.ac.at} \\
\end{tabular}

\end{document}