Séminaire Lotharingien de Combinatoire, B20f (1988), 7 pp. [Formerly: Publ. I. R. M. A. Strasbourg, 1988, 372/S-20, p. 121 - 129.]

MAXIMALE PERMANENTEN VON (1,–1)-MATRIZEN MIT BELIEBIGEM RANG

von

Arnold Richard KRÄUTER

Zusammenfassung. Die vorliegende Note bringt einen Überblick über den derzeitigen Stand der Forschung bei der Bestimmung bestmöglicher oberer Schranken für den Betrag der Permanente einer (1, −1)-Matrix.

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

Unter der Permanente einer n × n-Matrix A = (a_{ij}) über einem beliebigen kommutativen Ring verstehen wir den Ausdruck

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

wobei 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änzungsbeiträgen [9] und [10]. Eine (1, −1)-Matrix besteht ausschließlich aus den Elementen +1 und −1. Die Menge aller n × n-(1, −1)-Matrizen werde mit Ω_{n} bezeichnet; die Teilmenge der nichtsingulären Matrizen in Ω_{n} wird mit Ω̃_{n} abgekürzt. Schließlich sei J_{n} ∈ Ω_{n} jene Matrix, deren Elemente sämtlich den Wert +1 haben. Die bekannteste Klasse von (1, −1)-Matrizen stellen die Hadamard-Matrizen dar. Dabei heißt H ∈ Ω_{n} Hadamard-Matrix der Ordnung n, wenn sie der Beziehung

HH^{T} = nI_{n} (2)

genügt, wobei I_{n} die n × n-Einheitsmatrix bezeichnet. Das ursprüngliche Interesse an der Permanente von (1, −1)-Matrizen entstammt der Hoffnung, mithilfe der Permanentenfunktion nichtäquivalente Hadamard-Matrizen charakterisieren zu können. Dieses Problem ist übrigens noch ungelöst. Wir wollen uns hier jedoch mit einer anderen Frage befassen, nämlich mit dem Studium (möglichst scharfer) oberer Schranken für den Betrag der Permanente auf der Menge Ω_{n}. Aufgrund der oben gemachten Bemerkung über die Bedeutung der Hadamard-Matrizen ist es nicht besonders überraschend, daß das erste uns hier interessierende Ergebnis für derartige Matrizen hergeleitet worden ist.

Satz 1 (Marcus-Newman [7, p. 58]). Für jede Hadamard-Matrix H gilt die Ungleichung

|per(H)| ≤ | det(H)|. (3)

Für den Beweis von (3) verwendet man eine Darstellung der Permanentenfunktion als inneres Produkt auf der Symmetrieklasse der vollständig symmetrischen Tensoren. Die Anwendung der Cauchy-Schwarzschen Ungleichung liefert in weiterer Folge für zwei n × n-Matrizen A und B die Beziehung

(4) |per(AB)|^{2} ≤ per(AA^{∗})per(B^{∗}B),

wobei A^{∗} die konjugiert-transponierte Matrix von A bezeichnet. Setzt man nun in (4) A = H und B = I_{n}, dann folgt

|per(H)|^{2} ≤ n^{n}

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äher eingehe, möchte ich noch eine Äquivalenzrelation auf der Menge Ω_{n} einführen. Zwei Matrizen A, B ∈ Ω_{n} mögen zueinander äquivalent heißen (in Zeichen A ∼ B), falls B aus A durch Hintereinanderausführung 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ß ∼ tatsächlich eine Äquivalenzrelation auf Ω_{n} darstellt. Auf die Schwierigkeiten bei der Konstruktion geeigneter Normalformen bezüglich ∼ gehe ich an dieser Stelle nicht ein (siehe [1, pp. 54 - 55]). Erwähnen möchte ich aber die folgende wichtige Tatsache: für alle A, B ∈ Ω_{n} mit A ∼ B gilt

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

Mit anderen Worten: es genügt, sich bei der Betrachtung von |per(A)| für A ∈ Ω_{n} auf Repräsentanten modulo ∼ zu beschränken.

Satz 2 (Wang [13, pp. 355 - 356). (a) Für alle A ∈ Ω_{n} gilt

|per(A)| ≤ n! (5)

und Gleichheit tritt genau dann auf, wenn A ∼ J_{n} gilt.

(b) Für alle A ∈ Ω_{n}, n ≥ 2, mit |per(A)| ≠ n! gilt

|per(A)| ≤ (n − 2)(n − 1)! (6)

und Gleichheit tritt genau dann auf, wenn für n ≠ 3

A ∼ [ \begin{matrix}−1 & 1 & ⋯ & ⋯ & 1 \\ 1 & 1 & ... & & ⋮ \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & & ... & ... & 1 \\ 1 & ⋯ & ⋯ & 1 & 1 \end{matrix} ] (7)

gilt und für n = 3

A ∼ [ \begin{matrix}−1 & 1 & 1 \\ 1 & −1 & 1 \\ 1 & 1 & 1 \end{matrix} ] . (8)

Die Arbeit Wangs enthält zwar keine weiteren Resultate zu unserem Problemkreis, wohl aber die folgende interessante Fragestellung: wie sehen scharfe obere Schranken für |per(A)| aus, falls A ∈ Ω̃_{n}, also A nichtsingulär ist? Vor einigen Jahren konnten Teilantworten auf dieses Problem gegeben werden, welche im folgenden besprochen werden sollen. Dabei spielen zwei Matrizenklassen eine ausgezeichnete Rolle. Für m ≤ n sei

C(n, m) = m \{ [ \begin{matrix}1 & 1 & ⋯ & ⋯ & ⋯ & 1 \\ 1 & ... & ... & & & ⋮ \\ ⋮ & ... & 1 & ... & & ⋮ \\ ⋮ & & ... & −1 & ... & ⋮ \\ ⋮ & & & ... & ... & 1 \\ 1 & ⋯ & ⋯ & ⋯ & 1 & −1 \end{matrix} ] (9)

beziehungsweise

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

Die Permanenten dieser Matrizen bezeichnen wir mit

per(C(n, m)) =: ω_{n,m}, (11)

speziell

ω_{n,n−1} =: θ_{n}, (12)

ω_{n,n} =: ω_{n}, (13)

beziehungsweise

per(S_{n}) =: ϕ_{n}. (14)

Die Betrachtung der obigen Fragestellung für kleine Werte von n führt schließlich auf die folgende

Vermutung 1 (Kräuter-Seifter [2, p. 216]). (a) Für alle A ∈ Ω̃_{n}, n ≥ 5, gilt

|per(A)| ≤ θ_{n} (15)

und Gleichheit tritt genau dann auf, wenn A ∼ C(n, n − 1) gilt.

(b) Für alle A ∈ Ω̃_{n}, n ≥ 6, mit |per(A)| ≠ θ_{n}, gilt

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

Diese Abschätzung ist bestmöglich.

Ehe ich das angekündigte Teilergebnis formuliere, möchte ich einige Bemerkungen zu Vermutung 1 machen. Die Gleichheitsbedingung in (a) hat zur Folge, daß aufgrund ω_{n} < θ_{n} für n ≥ 5 (siehe [2, p. 209]) der Maximalwert θ_{n} modulo ∼ für genau eine Matrix, nämlich C(n, n − 1), angenommen wird. In (b) ist eine Charakterisierung des Gleichheitsfalles nicht bekannt; vielmehr gibt es Matrizen M ∈ Ω̃_{n} mit M ≁ C(n, n), jedoch |per(M)| = ω_{n}. Die Einschränkung n ≥ 6 in (b) rührt daher, daß erst für solche n die Beziehung |ϕ_{n}| < ω_{n} gilt (siehe [2, p. 215]), während man für n = 5 zusätzlich A ≁ S_{5} fordern müßte, um die Behauptung zu erhalten. Diese Überlegung erfordert einerseits die explizite Bestimmung der Zahlen ω_{n} und ϕ_{n} (auf welche wir weiter unten noch eingehen werden), andererseits die Anwendung einiger Abschätzungen für die Bernoulli-Zahlen. Als Folgeprodukt eines allgemeineren, sehr langwierig zu beweisenden Satzes konnte nun die folgende teilweise Bestätigung von Vermutung 1 erzielt werden.

Satz 3 (Kräuter-Seifter [2, p. 218]). Vermutung 1 ist richtig für alle Matrizen mit höchstens zwei negativen Elementen je Zeile und Spalte sowie für alle dazu äquivalenten Matrizen.

Der Zusatz betrifft solche Matrizen, welche aus den in Frage kommenden Matrizen mit höchstens zwei negativen Elementen je Zeile und Spalte durch die Operation (3) in der Definition von ∼ hervorgehen, also im allgemeinen mehr als zwei negative Elemente je Zeile und Spalte enthalten. Somit wird Vermutung 1 durch Satz 3 für eine hinreichend große Klasse von Matrizen positiv beantwortet. Angesichts der Sätze 2 und 3 ist die allgemeinere Frage naheliegend, ob sich bei Vorgabe des Ranges präzisere Angaben über (gute) obere Schranken für |per(A)| auf Ω_{n} machen lassen. Dazu die

Vermutung 2 (Kräuter [5, pp. 13 - 14]). Für alle A ∈ Ω_{n}, n ≥ 5, mit rg(A) = m + 1, 0 ≤ m ≤ n − 1, gilt

|per(A)| ≤ ω_{n,m} (17)

und Gleichheit tritt genau dann auf, wenn A ∼ C(n, m) gilt.

Für m = n − 1 erhält man aus Vermutung 2 Vermutung 1. Teilweise Bestätigungen von Vermutung 2 sind die Sätze 2 und 3 (rg(A) ≥ 1 beziehungsweise rg(A) ≥ 2 beziehungsweise rg(A) = n). Bei seinen Bemühungen, Vermutung 1 für 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ührliches Zitat und verweise auf die Originalarbeit [12]. Weshalb man sich zur Zeit mit Teilergebnissen zu unserer Fragestellung begnügen muß, hängt meines Erachtens mit der Tatsache zusammen, daß der Rang einer Matrix (also eine Eigenschaft, welche über Unterdeterminanten erklärt wird) zuwenig Informationen über die Struktur der Matrix liefert, deren Permanente berechnet werden soll. Abschließend möchte ich noch einige Bemerkungen über die weiter oben definierten Zahlen ω_{n,m}, θ_{n}, ω_{n} und ϕ_{n} machen, ohne auf die zum Teil tiefliegenden Hilfsmittel aus der kombinatorischen Analysis (siehe etwa das Buch [11] von Riordan) einzugehen. Einige dieser Zahlen lassen sich mit Methoden berechnen, wie ich sie bereits vor vier Jahren auf dem 11. Treffen des Séminaire Lotharingien de Combinatoire in Mitwitz [4] präsentiert habe.

Satz 4 (Kräuter [6, passim]). (a) Für alle n ∈ N und für alle m mit 0 ≤ m ≤ n gilt

ω_{n,m} = ∑_{k=0}^{m}(−2)^{k}\binom{m}{k}(n − k)!. (18)

(b) Für alle n ≥ 2 gelten die eingliedrigen inhomogenen Rekursionen

\{ \begin{matrix}θ_{1} = 1, \\ θ_{n} = \frac{(n + 2)(n − 1)}{n + 1} θ_{n−1} − \frac{(−2)^{n}}{n + 1} \end{matrix} (19)

und

\{ \begin{matrix}ω_{1} = −1, \\ ω_{n} = n ω_{n−1} + (−2)^{n}. \end{matrix} (20)

(c) Für alle n ≥ 3 gelten die zweigliedrigen homogenen Rekursionen

\{ \begin{matrix}θ_{1} = 1, \\ θ_{2} = 0, \\ θ_{n} = (n − 2) θ_{n−1} + 2(n − 2) θ_{n−2} \end{matrix} (21)

und

\{ \begin{matrix}ω_{1} = −1, \\ ω_{2} = 2, \\ ω_{n} = (n − 2) ω_{n−1} + 2(n − 1) ω_{n−2}. \end{matrix} (22)

(d) Für n → ∞ gelten die asymptotischen Abschätzungen

θ_{n} ∼ e^{−2} n!, (23)

ω_{n} ∼ e^{−2} n!. (24)

Satz 5 (Kräuter [3, p. 66], [5, p. 21]). Für alle n ∈ N gilt

ϕ_{n} = (−1)^{(n+1)/2} τ_{n}, (25)

wobei τ_{n} die n-te Tangenszahl ist.

Wegen τ_{2k} = 0 für alle k ∈ N gilt auch ϕ_{2k} = 0. Die ϕ_{n} besitzen übrigens die exponentiell erzeugende Funktion

∑_{n=0}^{∞} ϕ_{n} \frac{x^{n}}{n!} = \frac{2}{1 + exp(2x)}. (26)

Tabellen mit den Werten von ω_{n}, θ_{n} und ϕ_{n} für n ≤ 15 findet man in [6, p. 57]. maximale permanenten 7

Literatur

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

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

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

4. Arnold Richard Kräuter, Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen. Publications de l’Institut de Recherche Mathématique Avancée Strasbourg 266, 82 - 94 (1985).

5. Arnold Richard Kräuter, Recent results on permanents of (1, −1) matrices. Berichte der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum Graz 249, 1 - 25 (1985).

6. Arnold Richard Kräuter, Permanenten von (1, −1)-Matrizen. Berichte der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum Graz 273, 1 - 103 (1987).

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

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

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

10. Henryk Minc, Theory of permanents 1982 - 1985. Linear and Multilinear Algebra 21, 109 - 148 (1987).

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

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

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

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