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

\setlength{\baselineskip}{12pt}

\noindent {\footnotesize S\'eminaire Lotharingien de Combinatoire, B20f (1988), 7 pp.
\newline [Formerly: Publ.~I.~R.~M.~A.~Strasbourg, 1988, 372/S-20, p. 121 - 129.]}

\vspace{39pt}

\setlength{\baselineskip}{15pt}

\begin{center}
{\bf MAXIMALE PERMANENTEN VON (1,--1)-MATRIZEN MIT BELIEBIGEM RANG}

\vspace{9pt}

{\sc von

\vspace{9pt}

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

\vspace{21pt}

\setlength{\baselineskip}{12pt}

{\footnotesize {\sc Zusammenfassung.} \quad Die vorliegende Note bringt einen \"Uberblick 
\"uber den derzeitigen Stand der Forschung bei der Bestimmung bestm\"oglicher oberer 
Schranken f\"ur den Betrag der Permanente einer $(1,-1)$-Matrix.

\vspace{6pt}

{\sc Abstract.} \quad This note presents a survey on the current status of the 
investigations on best possible upper bounds for the modulus of the permanent of a $(1,-1)$ 
matrix.}

\vspace{15pt}

\setlength{\baselineskip}{15pt}

Unter der {\it Permanente} einer $n \times n$-Matrix $A = (a_{ij})$ \"uber einem beliebigen 
kommutativen Ring verstehen wir den Ausdruck

\begin{equation}
{\rm per}(A) = \sum_{\sigma \in {\cal S}_n} a_{1\sigma(1)} \cdot ... \cdot a_{n\sigma(n)},
\end{equation}

\noindent wobei ${\cal S}_n$ die symmetrische Gruppe der Ordnung $n$ bezeichnet. Eine 
umfassende Darstellung dieser Matrizenfunktion findet man in der Monografie [8] von Minc 
sowie in den Erg\"anzungsbeitr\"agen [9] und [10]. \\
Eine $(1,-1)$-Matrix besteht ausschlie"slich aus den Elementen $+1$ und $-1.$ Die Menge 
aller $n \times n$-$(1,-1)$-Matrizen werde mit $\Omega_n$ bezeichnet; die Teilmenge der 
nichtsingul\"aren Matrizen in $\Omega_n$ wird mit $\tilde\Omega_n$ abgek\"urzt. Schlie"slich 
sei $J_n \in \Omega_n$ jene Matrix, deren Elemente s\"amtlich den Wert $+1$ haben. \\
Die bekannteste Klasse von $(1,-1)$-Matrizen stellen die Hadamard-Matrizen dar. Dabei hei"st 
$H \in \Omega_n$ {\it Hadamard-Matrix} der Ordnung $n,$ wenn sie der Beziehung

\begin{equation}
H H^T = n I_n
\end{equation}

\noindent gen\"ugt, wobei $I_n$ die $n \times n$-Einheitsmatrix bezeichnet. \\
Das urspr\"ungliche Interesse an der Permanente von $(1,-1)$-Matrizen entstammt der 
Hoffnung, mithilfe der Permanentenfunktion nicht\"aquivalente Hadamard-Matrizen 
charakterisieren zu k\"onnen. Dieses Problem ist \"ubrigens noch ungel\"ost. Wir wollen uns 
hier jedoch mit einer anderen Frage befassen, n\"amlich mit dem Studium
(m\"o\-glichst 
scharfer) oberer Schranken f\"ur den Betrag der Permanente auf der Menge $\Omega_n.$ 
Aufgrund der oben gemachten Bemerkung \"uber die Bedeutung der Hadamard-Matrizen ist es 
nicht besonders \"uberraschend, da"s das erste uns hier interessierende Ergebnis f\"ur 
derartige Matrizen hergeleitet worden ist.

\bigskip

{\sc Satz 1} \, (Marcus-Newman [7, p. 58]). \quad {\it F\"ur jede Hadamard-Matrix} $H$ {\it 
gilt die Ungleichung}

\begin{equation}
|{\rm per}(H)| \leq |\det (H)|.
\end{equation}

F\"ur den Beweis von (3) verwendet man eine Darstellung der
Per\-ma\-nen\-ten\-funk\-tion als inneres 
Produkt auf der Symmetrieklasse der vollst\"andig symmetrischen
Ten\-so\-ren. Die Anwendung der 
Cauchy-Schwarzschen Ungleichung liefert in weiterer Folge f\"ur zwei $n \times n$-Matrizen 
$A$ und $B$ die Beziehung

\begin{equation}
|{\rm per}(AB)|^2 \leq {\rm per}(AA^*) {\rm per}(B^*B),
\end{equation}

\noindent wobei $A^*$ die konjugiert-transponierte Matrix von $A$ bezeichnet. Setzt man
nun in (4) $A = H$ und $B = I_n,$ dann folgt 

\[
|{\rm per}(H)|^2 \leq n^n
\]

\noindent oder wegen $|\det (H)| = n^{n/2}$ die Behauptung von Satz 1. \\
Die erste systematische Untersuchung der Permanente beliebiger $(1,-1)$-Matri\-zen und damit 
auch oberer Schranken dieser Funktion stammt von Wang [13]. Ehe ich auf diese Arbeit n\"aher 
eingehe, m\"ochte ich noch eine \"Aquivalenzrelation auf der Menge $\Omega_n$ einf\"uhren. 
\\
Zwei Matrizen $A, B \in \Omega_n$ m\"ogen zueinander {\it \"aquivalent} hei"sen (in Zeichen 
$A \sim B$), falls $B$ aus $A$ durch Hintereinanderausf\"uhrung von Operationen der 
folgenden drei Typen hervorgeht: \\
(1) Vertauschen zweier Zeilen (Spalten) von $A;$ \\
(2) Transponieren von $A;$ \\
(3) Multiplizieren einer Zeile (Spalte) von $A$ mit dem Faktor $-1.$ \\
Man weist unmittelbar nach, da"s $\sim$ tats\"achlich eine \"Aquivalenzrelation auf 
$\Omega_n$ darstellt. Auf die Schwierigkeiten bei der Konstruktion geeigneter Normalformen 
bez\"uglich $\sim$ gehe ich an dieser Stelle nicht ein (siehe [1, pp. 54 - 55]). Erw\"ahnen 
m\"ochte ich aber die folgende wichtige Tatsache: f\"ur alle $A, B \in \Omega_n$ mit $A \sim 
B$ gilt

\[
|{\rm per}(A)| = |{\rm per}(B)|.
\]

\noindent Mit anderen Worten: es gen\"ugt, sich bei der Betrachtung von $|{\rm per}(A)|$
f\"ur $A \in \Omega_n$ auf Repr\"asentanten modulo $\sim$ zu beschr\"anken.

\bigskip

{\sc Satz 2} \, (Wang [13, pp. 355 - 356). \quad (a) {\it F\"ur alle} $A \in \Omega_n$ {\it 
gilt}

\begin{equation}
|{\rm per}(A)| \leq n!
\end{equation}

\noindent {\it und Gleichheit tritt genau dann auf, wenn} $A \sim J_n$ {\it gilt.} \\
(b) {\it F\"ur alle} $A \in \Omega_n, \; n \geq 2,$ {\it mit} $|{\rm per}(A)| \not= n!$ {\it 
gilt}

\begin{equation}
|{\rm per}(A)| \leq (n-2)(n-1)!
\end{equation}

\noindent {\it und Gleichheit tritt genau dann auf, wenn f\"ur} $n \not= 3$

\begin{equation}
A \sim \left[ \begin{array}{ccccc}
              -1 & 1 & \cdots & \cdots & 1 \\
              1 & 1 & \ddots & & \vdots \\
              \vdots & \ddots & \ddots & \ddots & \vdots \\
              \vdots & & \ddots & \ddots & 1 \\
              1 & \cdots & \cdots & 1 & 1 \\
              \end{array} \right]
\end{equation}

\noindent
{\it gilt und f\"ur} $n = 3$

\begin{equation}
A \sim \left[ \begin{array}{ccc}
              -1 & 1 & 1 \\
              1 & -1 & 1 \\
              1 & 1 & 1 \\
              \end{array} \right].
\end{equation}

Die Arbeit Wangs enth\"alt zwar keine weiteren Resultate zu unserem
Pro\-blem\-kreis, wohl aber 
die folgende interessante Fragestellung: wie sehen scharfe obere Schranken f\"ur $|{\rm 
per}(A)|$ aus, falls $A \in \tilde\Omega_n,$ also $A$ nichtsingul\"ar ist? \\
Vor einigen Jahren konnten Teilantworten auf dieses Problem gegeben werden, 
wel\-che im 
folgenden besprochen werden sollen. Dabei spielen zwei Matrizenklassen eine ausgezeichnete 
Rolle. F\"ur $m \leq n$ sei

\begin{equation}
\mbox{$ C(n,m) = \mbox{$ \begin{array}{r}
                        \rule{0mm}{20mm} \\
                        {\scriptstyle m} \left\{ \rule[-8.5mm]{0mm}{18mm}
                        \right. \\
                        \end{array} $}
                        \!\!\!
                        \left[ \begin{array}{cccccc}
                        1 & 1 & \cdots & \cdots & \cdots & 1 \\
                        1 & \ddots & \ddots & & & \vdots \\
                        \vdots & \ddots & 1 & \ddots & & \vdots \\
                        \vdots & & \ddots & -1 & \ddots & \vdots \\ 
                        \vdots & & & \ddots & \ddots & 1 \\
                        1 & \cdots & \cdots & \cdots & 1 & -1 \\
                        \end{array} \right] $}
\end{equation}

\noindent beziehungsweise

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

\noindent Die Permanenten dieser Matrizen bezeichnen wir mit

\begin{equation}
{\rm per}(C(n,m)) =: \omega_{n,m},
\end{equation}

\noindent speziell

\begin{equation}
\omega_{n,n-1} =: \theta_n,
\end{equation}
\begin{equation}
\omega_{n,n} =: \omega_n,
\end{equation}

\noindent beziehungsweise

\begin{equation}
{\rm per}(S_n) =: \phi_n.
\end{equation}

\noindent Die Betrachtung der obigen Fragestellung f\"ur kleine Werte von $n$ f\"uhrt
schlie"slich auf die folgende

\bigskip

{\sc Vermutung 1} \, (Kr\"auter-Seifter [2, p. 216]). \quad (a) {\it F\"ur alle} $A \in 
\tilde\Omega_n, \; n \geq 5,$ {\it gilt}

\begin{equation}
|{\rm per}(A)| \leq \theta_n
\end{equation}

\noindent {\it und Gleichheit tritt genau dann auf, wenn} $A \sim C(n,n-1)$ {\it gilt.} \\
(b) {\it F\"ur alle} $A \in \tilde\Omega_n, \; n \geq 6, $ {\it mit} $ |{\rm per}(A)| \not= 
\theta_n,$ 
{\it gilt}

\begin{equation}
|{\rm per}(A)| \leq \omega_n.
\end{equation}

\noindent {\it Diese Absch\"atzung ist bestm\"oglich.}

\bigskip

Ehe ich das angek\"undigte Teilergebnis formuliere, m\"ochte ich einige
Be\-mer\-kun\-gen zu 
Vermutung 1 machen. Die Gleichheitsbedingung in (a) hat zur Folge, da"s aufgrund $\omega_n < 
\theta_n$ f\"ur $n \geq 5$ (siehe [2, p. 209]) der Maximalwert $\theta_n$ modulo $\sim$ 
f\"ur genau eine Matrix, n\"amlich $C(n,n-1),$ angenommen wird. In (b) ist eine 
Charakterisierung des Gleichheitsfalles nicht bekannt; vielmehr gibt es Matrizen $M \in 
\tilde\Omega_n$ mit $M \not\sim C(n,n),$ jedoch $|{\rm per}(M)| = \omega_n.$ Die 
Einschr\"ankung $n \geq 6$ in (b) r\"uhrt daher, da"s erst f\"ur solche $n$ die Beziehung 
$|\phi_n| < \omega_n$ gilt (siehe [2, p. 215]), w\"ahrend man f\"ur $n = 5$ zus\"atzlich $A 
\not\sim S_5$ fordern m\"u"ste, um die Behauptung zu erhalten. Diese \"Uberlegung erfordert 
einerseits die explizite Bestimmung der Zahlen $\omega_n$ und $\phi_n$ (auf welche wir 
weiter unten noch eingehen werden), andererseits die Anwendung einiger Absch\"atzungen f\"ur 
die Bernoulli-Zahlen. \\
Als Folgeprodukt eines allgemeineren, sehr langwierig zu beweisenden Satzes konnte nun die 
folgende teilweise Best\"atigung von Vermutung 1 erzielt werden.

\bigskip

{\sc Satz 3} \, (Kr\"auter-Seifter [2, p. 218]). \quad {\it Vermutung 1 ist richtig f\"ur 
alle Matrizen mit h\"ochstens zwei negativen Elementen je Zeile und Spalte sowie f\"ur alle 
dazu \"aquivalenten Matrizen.}

\bigskip

Der Zusatz betrifft solche Matrizen, welche aus den in Frage kommenden
Ma\-tri\-zen mit 
h\"ochstens zwei negativen Elementen je Zeile und Spalte durch die Operation (3) in der 
Definition von $\sim$ hervorgehen, also im allgemeinen mehr als zwei negative Elemente je 
Zeile und Spalte enthalten. Somit wird Vermutung 1 durch Satz 3 f\"ur eine hinreichend 
gro"se Klasse von Matrizen positiv beantwortet. \\
Angesichts der S\"atze 2 und 3 ist die allgemeinere Frage naheliegend, ob sich bei Vorgabe 
des Ranges pr\"azisere Angaben \"uber (gute) obere Schranken f\"ur $|{\rm per}(A)|$ auf 
$\Omega_n$ machen lassen. Dazu die

\bigskip

{\sc Vermutung 2} \, (Kr\"auter [5, pp. 13 - 14]). \quad {\it F\"ur alle} $A \in \Omega_n, 
\; n \geq 5,$ {\it mit} ${\rm rg}(A) = m+1, \; 0 \leq m \leq n-1,$ {\it gilt}

\begin{equation}
|{\rm per}(A)| \leq \omega_{n,m}
\end{equation}

\noindent {\it und Gleichheit tritt genau dann auf, wenn} $A \sim C(n,m)$ {\it gilt.}

\bigskip

F\"ur $m = n-1$ erh\"alt man aus Vermutung 2 Vermutung 1. Teilweise
Be\-st\"a\-ti\-gun\-gen von 
Vermutung 2 sind die S\"atze 2 und 3 (${\rm rg}(A) \geq 1$ beziehungsweise ${\rm rg}(A) \geq 
2$ beziehungsweise ${\rm rg}(A) = n$). Bei seinen Bem\"uhungen, Vermutung 1 f\"ur eine 
andere Matrizenklasse als die in Satz 3 angegebene zu beweisen, hat Seifter auch eine 
Teilantwort auf Vermutung 2 gegeben; aufgrund der technischen Details verzichte ich hier auf 
ein ausf\"uhrliches Zitat und verweise auf die Originalarbeit [12]. \\
Weshalb man sich zur Zeit mit Teilergebnissen zu unserer Fragestellung begn\"ugen mu"s, 
h\"angt meines Erachtens mit der Tatsache zusammen, da"s der Rang einer Matrix (also eine 
Eigenschaft, welche \"uber {\it Unterdeterminanten} erkl\"art wird)
zu\-we\-nig Informationen 
\"uber die Struktur der Matrix liefert, deren Permanente berechnet werden soll. \\
Abschlie"send m\"ochte ich noch einige Bemerkungen \"uber die weiter oben definierten Zahlen 
$\omega_{n,m}, \; \theta_n, \; \omega_n$ und $\phi_n$ machen, ohne auf die zum Teil 
tiefliegenden Hilfsmittel aus der kombinatorischen Analysis (siehe etwa das Buch [11] von 
Riordan) ein\-zu\-ge\-hen. Einige dieser Zahlen lassen sich mit Methoden berechnen, wie ich sie 
bereits vor vier Jahren auf dem 11. Treffen des S\'eminaire Lotharingien de Combinatoire
in Mitwitz [4] pr\"asentiert habe.

\bigskip

{\sc Satz 4} \, (Kr\"auter [6, {\it passim}]). \quad (a) {\it F\"ur alle} $n \in {\bf N}$ 
{\it und f\"ur alle} $m$ {\it mit} $0 \leq m \leq n$ {\it gilt}

\begin{equation}
\omega_{n,m} = \sum_{k=0}^m (-2)^k {m \choose k} (n-k)!.
\end{equation}

\noindent (b) {\it F\"ur alle} $n \geq 2$ {\it gelten die eingliedrigen inhomogenen
Rekursionen}

\begin{equation}
\left\{ \begin{array}{l}
        \theta_1 = 1, \\
        \theta_n = \displaystyle\frac{(n+2)(n-1)}{n+1} \, \theta_{n-1} -
        \displaystyle\frac{(-2)^n}{n+1} \\
        \end{array} \right.
\end{equation}

\noindent {\it und}

\begin{equation}
\left\{ \begin{array}{l}
        \omega_1 = -1, \\
        \omega_n = n \, \omega_{n-1} + (-2)^n. \\
        \end{array} \right.
\end{equation}

\noindent (c) {\it F\"ur alle} $n \geq 3$ {\it gelten die zweigliedrigen homogenen 
Rekursionen}

\begin{equation}
\left\{ \begin{array}{l}
        \theta_1 = 1, \\
        \theta_2 = 0, \\
        \theta_n = (n-2) \, \theta_{n-1} + 2(n-2) \, \theta_{n-2} \\
        \end{array} \right.
\end{equation}

\noindent {\it und}

\begin{equation}
\left\{ \begin{array}{l}
        \omega_1 = -1, \\
        \omega_2 = 2, \\
        \omega_n = (n-2) \, \omega_{n-1} + 2(n-1) \, \omega_{n-2}. \\
        \end{array} \right.
\end{equation}

\noindent (d) {\it F\"ur} $n \rightarrow \infty$ {\it gelten die asymptotischen
Absch\"atzungen}

\begin{equation}
\theta_n \sim e^{-2} \, n!,
\end{equation}
\begin{equation}
\omega_n \sim e^{-2} \, n!.
\end{equation}

\bigskip

{\sc Satz 5} \, (Kr\"auter [3, p. 66], [5, p. 21]). \quad {\it F\"ur alle} $n \in {\bf 
N}$ {\it gilt}

\begin{equation}
\phi_n = (-1)^{(n+1)/2} \, \tau_n,
\end{equation}

\noindent {\it wobei} $\tau_n$ {\it die} $n$-{\it te Tangenszahl ist.}

\bigskip

Wegen $\tau_{2k} = 0$ f\"ur alle $k \in {\bf N}$ gilt auch $\phi_{2k} = 0.$ Die $\phi_n$ 
besitzen \"ubrigens die exponentiell erzeugende Funktion

\begin{equation}
\sum_{n=0}^{\infty} \phi_n \, \displaystyle\frac{x^n}{n!} = 
\displaystyle\frac{2}{1 + \exp(2x)}.
\end{equation}

\noindent Tabellen mit den Werten von $\omega_n, \; \theta_n$ und $\phi_n$ f\"ur $n \leq
15$ findet man in [6, p. 57].

\bigskip

\begin{center}
{\sc Literatur}
\end{center}
         
\setlength{\baselineskip}{12pt}

\begin{footnotesize}
\begin{enumerate}

\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 Arnold Richard {\sc Kr\"auter,} Permanenten - Ein kurzer \"Uberblick. {\it 
Publications de l'Insti\-tut de Recherche Ma\-th\'e\-ma\-tique Avanc\'ee Strasbourg} {\bf 230,} 39 
- 83 (1984).
\item Arnold Richard {\sc Kr\"auter,} \"Uber die Permanente gewisser zirkulanter Matrizen 
und damit zusammenh\"angender Toeplitz-Matrizen. {\it Publications de l'Institut de 
Recherche Ma\-th\'e\-ma\-tique Avanc\'ee Strasbourg} {\bf 266,} 82 - 94 (1985).
\item Arnold Richard {\sc Kr\"auter,} Recent results on permanents of $(1,-1)$ matrices. 
{\it Berichte der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum 
Graz} {\bf 249,} 1 - 25 (1985).
\item Arnold Richard {\sc Kr\"auter,} Permanenten von $(1,-1)$-Matrizen. {\it Berichte der 
Ma\-the\-ma\-tisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum Graz} {\bf 
273,} 1 - 103 (1987).
\item Marvin {\sc Marcus} and Morris {\sc Newman,} Inequalities for the permanent function. 
{\it Annals of Mathematics (2)} {\bf 75,} 47 - 62 (1962).
\item Henryk {\sc Minc,} {\it Permanents.} Encyclopedia of Mathematics and Its Applications, 
Volume 6. Reading: Addison-Wesley, 1978.
\item Henryk {\sc Minc,} Theory of permanents 1978 - 1981. {\it Linear and Multilinear 
Algebra} {\bf 12,} 227 - 263 (1983).
\item Henryk {\sc Minc,} Theory of permanents 1982 - 1985. {\it Linear and Multilinear 
Algebra} {\bf 21,} 109 - 148 (1987).
\item John {\sc Riordan,} {\it An Introduction to Combinatorial Analysis.} Fourth printing. 
New York: Wiley, 1967.
\item Norbert {\sc Seifter,} Upper bounds for permanents of $(1,-1)$-matrices. {\it Israel 
Journal of Mathematics} {\bf 48,} 69 - 78 (1984).
\item Edward Tzu-Hsia {\sc Wang,} On permanents of $(1,-1)$-matrices. {\it Israel Journal of 
Mathematics} {\bf 18,} 353 - 361 (1974).

\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}
