Séminaire Lotharingien de Combinatoire B36z (10pp.)

EIN VERGLEICH ZWEIER OBERER SCHRANKEN

FÜR DIE PERMANENTE VON (0, 1)-MATRIZEN

von

Suk-Geun HWANG und Arnold Richard KRÄUTER

Zusammenfassung. In dieser Note werden hinreichende Bedingungen dafür angegeben, welche der Permanentenabschätzungen von Minc-Brėgman (1973) und Donald et al. (1984) für eine gegebene Matrix schärfer ist.

Abstract. In this note we present sufficient conditions such that one can predict immediately which one of the permanental bounds by Minc-Brėgman (1973) and Donald et al. (1984) gives the better estimation for a given matrix.

1. Einleitung. Es sei A = (a_{ij}) eine n × n-Matrix über C. Die Permanente von A ist definiert durch

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

wobei S_{n} die symmetrische Gruppe der Ordnung n bezeichnet.

Eine Matrix A = (a_{ij}) heißt (0, 1)-Matrix falls a_{ij} ∈ {0, 1} ist für alle i und j.

Eine n × n-Matrix A heißt vollständig unzerlegbar, falls es keine n × n-Permutationsmatrizen P und Q gibt mit

P AQ = [ \begin{matrix}X & O \\ Z & Y \end{matrix} ] ,

wobei die Diagonalblöcke X und Y quadratisch sind. Anderenfalls heißt A teilweise zerlegbar.

Ausgangspunkt unserer Untersuchungen sind die folgenden zwei Ungleichungen für Permanenten:

Satz A (vermutet von H. Minc [6], bewiesen von L. M. Brėgman [1], neu bewiesen von A. Schrijver [8]). Es sei A eine n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Dann gilt

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

Gleichheit tritt in (1) genau dann auf, wenn A permutationsäquivalent zu einer direkten Summe quadratischer Blöcke ist, deren Elemente sämtlich 1 sind.

Satz B (J. Donald, J. Elwin, R. Hager & P. Salamon [2], neu bewiesen von S.-G. Hwang & A. R. Kräuter [4]). Es sei A eine vollständig unzerlegbare n × n-Matrix mit nichtnegativen ganzzahligen Elementen und den Zeilensummen r_{1}, …, r_{n}. Dann gilt

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

Auf die Wiedergabe der in [3] angegebenen Gleichheitsbedingung wird hier wegen der zahlreichen technischen Details verzichtet.

Bemerkungen.

(a) Die Schranke in (1) gilt für alle (0, 1)-Matrizen, ob sie nun vollständig unzerlegbar oder teilweise zerlegbar sind. Die Schranke in (2) hingegen gilt für alle vollständig unzerlegbaren nichtnegativen ganzzahligen Matrizen, ob sie nun bloß Nullen und Einsen oder auch andere ganze Zahlen enthalten.

(b) Selbst dann, wenn wir uns auf vollständig unzerlegbare (0, 1)-Matrizen beschränken, sind die Schranken in (1) und (2) nicht vergleichbar, da (1) schärfer ist als (2), falls viele Zeilensummen größer als 2 sind, und da (2) schärfer ist als (1), falls viele Zeilensummen gleich 2 sind und die anderen Zeilensummen nicht besonders groß (H. Minc [7]).

Problem. Im folgenden bezeichne A stets eine vollständig unzerlegbare n × n-(0,1)-Matrix mit den Zeilensummen r_{1}, …, r_{n}. Aus Bemerkung (b) folgt, daß die Anzahl der Zeilen von A mit genau zwei Einsen von maßgeblicher Bedeutung dafür ist, welche der beiden zur Diskussion stehenden Ungleichungen die schärfere Schranke liefert. Wir führen deshalb diese Anzahl als zusätzlichen Parameter ein und leiten ein Kriterium dafür her, welche der Schranken (1) und (2) für eine gegebene Matrix A die bessere ist.

2. Eigenschaften einer mit der Gamma-Funktion zusammenhängenden Funktion. Um die Herleitung des angekündigten Kriteriums zu ermöglichen, benötigen wir einige vorbereitende Betrachtungen über eine mit der Gamma-Funktion zusammenhängende Funktion. Dazu sei

Φ(x) := Γ(x + 1)^{1/x}, x > 0, (3)

wobei Γ die Gamma-Funktion bezeichnet. Es ist bemerkenswert, daß für alle positiven ganzen Zahlen n gilt:

Φ(n) = n!^{1/n}.

Ferner definieren wir

g_{a,b}(x) := ln \frac{ax + b}{Φ(x)}, x > − \frac{b}{a} > 1, (4)

wobei a und b reelle Konstanten bezeichnen.

Satz 1 (S.-G. Hwang & A. R. Kräuter [5]). g_{a,b}(x) ist streng monoton wachsend und konkav. Ferner gilt

lim_{x→∞} g_{a,b}(x) = 1 + ln a. (5)

(Der Beweis beruht im Wesentlichen auf der Stirlingschen Formel für die Gamma-Funktion,

Γ(x) = \sqrt{2π}x^{x− \frac{1}{2}} e^{−x+μ(x)}, x > 0, (6)

und verwendet einige Eigenschaften von μ(x).)

Wir definieren

λ(x) := g_{1,−1}(x) = ln \frac{x − 1}{Φ(x)}, x > 1. (7)

Korollar 1.

(a) λ(x) ist streng monoton wachsend und konkav. Überdies gilt die Beziehung

lim_{x→∞} λ(x) = 1. (8)

(b) Es gelten die folgenden Ungleichungen:

Φ(x) > x − 1 für 0 < x < x_{0}, (9)

Φ(x) < x − 1 für x_{0} < x < ∞, (10)

wobei x_{0} = 2, 695142 … die eindeutig bestimmte Nullstelle von λ(x) für x > 1 ist.

(c) Die Funktion \frac{x−1}{Φ(x)} ist streng monoton wachsend für x > 1.

3. Ein Vergleich der Abschätzungen (1) und (2) für vollständig unzerlegbare (0, 1)-Matrizen. Gemäß Korollar 1, (b) ist die Schranke (1) besser (bzw. schlechter) als die Schranke (2), falls r_{i} ≥ 3 (bzw. r_{i} = 2 ) für alle i gilt. Für weiterreichende Aussagen benötigen wir einige zusätzliche Bezeichnungen. Es seien r_{1}, …, r_{n} ganze Zahlen ≥ 2, ferner sei r = (r_{1}, …, r_{n}). Wir definieren

μ(r) := ∏_{i=1}^{n} Φ(r_{i}), (11)

δ(r) := 1 + ∏_{i=1}^{n}(r_{i} − 1). (12)

Für ganze Zahlen n und k mit 0 ≤ k ≤ n sei

S(n, k) := {r = (r_{1}, …, r_{n}) : k der r_{i} sind gleich 2, 3 ≤ r_{i} ≤ n sonst}.

Im folgenden bestimmen wir die Mengen

K_{n} := {k : 0 ≤ k ≤ n, μ(r) < δ(r) für alle r ∈ S(n, k)},

L_{n} := {k : 0 ≤ k ≤ n, μ(r) > δ(r) für alle r ∈ S(n, k)}

und zeigen, daß

K_{n} = {0, 1, 2, …, k_{1}(n)},
L_{n} = {k_{2}(n), k_{2}(n) + 1, …, n − 1, n}

gilt, wobei k_{1}(n) und k_{2}(n) extremal in dem Sinne sind, daß k_{1}(n) + 1 ∉ K_{n} und k_{2}(n) − 1 ∉ L_{n}. Nun sind wir in der Lage, das folgende wichtige Hilfsresultat zu formulieren.

Lemma 1. Es sei x_{k} = (2, …, 2, 3, …, 3) ∈ S(n, k) und y_{k} = (2, …, 2, n, …, n) ∈ S(n, k). Dann gilt für alle r ∈ S(n, k)

δ(x_{k}) − μ(x_{k}) ≤ δ(r) − μ(r) ≤ δ(y_{k}) − μ(y_{k}). (13)

Zur Bestimmung von K_{n} definieren wir

c := \frac{ln(2\sqrt{2}/ ^{3} \sqrt{6})}{ln(2/ ^{3} \sqrt{6})} = 4, 614131 …, (14)

und, für ganze Zahlen n und k mit 0 ≤ k ≤ n,

ϵ(n, k) := \frac{1}{ln(2\sqrt{2}/ ^{3} \sqrt{6})} ln (1 + \frac{1}{2^{n−k}} ) . (15)

ϵ besitzt folgende Eigenschaften:

(a) ϵ(n, k) > 0 ;

(b) ϵ(n, k) → 0 für (n − k) → ∞;

(c) ϵ(n, k) < 1 für k ≤ n − 1.

Eine entscheidende Rolle bei der Bestimmung von k_{1}(n) spielt die folgende Ungleichung:

⌊n/c⌋ + 1 − \frac{n}{c} < ϵ(n, ⌊n/c⌋ + 1), (16)

worin ⌊x⌋ den ganzzahligen Anteil von x bezeichnet.

Satz 2 (S.-G. Hwang & A. R. Kräuter [5]). Es sei n ≥ 3 eine ganze Zahl und es sei K_{n} die oben definierte Menge. Dann gilt K_{n} = {0, 1, 2, …, k_{1}(n)}, wobei

k_{1}(n) = \{ \begin{matrix}⌊n/c⌋ + 1, & falls (16) gilt, \\ ⌊n/c⌋ & sonst. \end{matrix}

Beweisskizze. Wir zeigen

K_{n} = {k : 0 ≤ k ≤ ⌊n/c⌋ + a_{n}},

wobei

a_{n} = \{ \begin{matrix}1, & falls (16) gilt, \\ 0 & sonst. \end{matrix}

Für x_{k} = (2, …, 2, 3, …, 3) ∈ S(n, k) folgt aus Lemma 1 sofort

K_{n} = {k : 0 ≤ k ≤ n, μ(x_{k}) < δ(x_{k})}.

Nun ist

μ(x_{k}) = 2^{k/2}Φ(3)^{n−k},

δ(x_{k}) = 2^{n−k} (1 + \frac{1}{2^{n−k}} ) .

Somit gilt μ(x_{k}) < δ(x_{k}) genau dann, wenn

(\frac{2\sqrt{2}}{Φ(3)})^{k} < (\frac{2}{Φ(3)})^{n} (1 + \frac{1}{2^{n−k}} )

gilt oder

k < \frac{n}{c} + ϵ(n, k). (17)

Ist nun k ≤ ⌊n/c⌋, so ist (17) sicher erfüllt und damit {0, 1, 2, …, ⌊n/c⌋} ⊆ K_{n}. k = ⌊n/c⌋ + 1 genügt (17) genau dann, wenn (16) erfüllt ist. Wir haben noch zu zeigen: K_{n} enthält kein k mit ⌊n/c⌋ + 2 ≤ k ≤ n. Wegen n ≥ 3 ist sicher n ∉ K_{n}. Es sei also ⌊n/c⌋ + 2 ≤ k ≤ n − 1. Dann ist aber ϵ(n, k) < 1 und somit

k ≥ (⌊n/c⌋ + 1) + 1 > \frac{n}{c} + ϵ(n, k).

□

Zur Bestimmung von L_{n} definieren wir

β_{n} := 1 + \frac{ln \sqrt{2}}{λ(n)} (18)

und

ζ(n, k) := \frac{1}{ln \sqrt{2} + λ(n)} ln (1 + \frac{1}{(n − 1)^{n−k}} ) . (19)

β_{n} und ζ besitzen folgende Eigenschaften:

(a) β_{n} ↘ 1 + ln \sqrt{2} für n → ∞;

(b) ζ(n, k) → 0 für n → ∞;

(c) ζ(n, k) < 1, falls k < n. Die ”Testungleichung“ bei der Bestimmung von k_{2}(n) lautet

⌊n/β_{n}⌋ + 1 − \frac{n}{β_{n}} > ζ(n, ⌊n/β_{n}⌋ + 1). (20)

Satz 3 (S.-G. Hwang & A. R. Kräuter [5]). Es sei n ≥ 3 eine ganze Zahl und L_{n} wie oben definiert. Dann gilt L_{n} = {k_{2}(n), k_{2}(n)+1, …, n−1, n}, wobei

k_{2}(n) = \{ \begin{matrix}⌊n/β_{n}⌋ + 1, & falls (20) gilt, \\ ⌊n/β_{n}⌋ + 2, & sonst. \end{matrix}

Für n ≤ 10 sind die Werte von k_{1}(n) und k_{2}(n) in Tabelle 1 angeführt.

\begin{matrix}n & k_{1}(n) & k_{2}(n) \\ 3 & 1 & 2 \\ 4 & 1 & 3 \\ 5 & 1 & 3 \\ 6 & 1 & 4 \\ 7 & 1 & 5 \\ 8 & 2 & 6 \\ 9 & 2 & 6 \\ 10 & 2 & 7 \end{matrix}

Tabelle 1.

Bemerkung. Aufgrund von Satz 2 könnte man erwarten, daß β_{n} aus Satz 3, welches ja von n abhängt, durch eine Konstante β ersetzt werden kann. Mit kleinen Einschränkungen ist dies tatsächlich möglich, wie der folgende Satz zeigt.

Satz 4 (S.-G. Hwang & A. R. Kräuter [5]). Es seien n ≥ 4 und k ≤ n ganze Zahlen. Falls k > n/(1 + ln \sqrt{2}) gilt, dann ist k ∈ L_{n}.

Bemerkungen.

(a) Es sei β = 1 + ln \sqrt{2}. Satz 4 hat den Vorteil, daß nun die unhandliche Beziehung (20) nicht mehr erforderlich ist. Ein Nachteil von Satz 4 besteht darin, daß nunmehr im allgemeinen wegen k ≥ ⌊n/β⌋ + 1 k > k_{2}(n) ist.

(b) Aufgrund der Größe der ”Skalierungsfaktoren“ c und β_{n} tritt eine Lücke zwischen k_{1}(n) und k_{2}(n) auf, das heißt für k_{1}(n) < k < k_{2}(n) ist keine einheitliche Vorhersage möglich, ob μ(r) < δ(r) oder μ(r) > δ(r) gilt für r ∈ S(n, k).

Beispiel. Es sei n = 4 und k = 2. Dann ist nach Satz 2 und Satz 3 k_{1}(4) < 2 < k_{2}(4). Hier gibt es folgende drei Möglichkeiten:

(a) r = (2, 2, 3, 3). Dann gilt

6, 603 … = μ(r) > δ(r) = 5

für die Matrizen

[ \begin{matrix}1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{matrix} ] .

(b) r = (2, 2, 3, 4). Dann gilt

8, 043 … = μ(r) > δ(r) = 7

für die Matrizen

[ \begin{matrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{matrix} ] .

(c) r = (2, 2, 4, 4). Dann gilt

9, 797 … = μ(r) < δ(r) = 10

für die Matrizen

[ \begin{matrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] , [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] .

zitierte literatur

1. L. M. Brėgman, Some properties of nonnegative matrices and their permanents [Russian], Dokl. Akad. Nauk SSSR 211 (1973), 27 - 30. English translation in Sov. Math. Dokl. 14 (1973), 945 - 949.

2. J. Donald, J. Elwin, R. Hager, and P. Salamon, A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I, Linear Algebra Appl. 61 (1984), 187 - 198.

10 s.-g. hwang und a. r. kräuter

3. J. Donald, J. Elwin, R. Hager, and P. Salamon, A graph theoretic upper bound on the permanent of a nonnegative integer matrix II. The extremal case. Linear Algebra Appl. 61 (1984), 199 - 218.

4. S. G. Hwang and A. R. Kräuter, A matrix theoretical proof of an upper bound for the permanent of a nonnegative integral matrix. Preprint, Montanuniversität Leoben, 1996.

5. S. G. Hwang and A. R. Kräuter, Comparison of permanental bounds of (0,1)- matrices. Preprint, Montanuniversität Leoben, 1996.

6. H. Minc, Upper bounds for permanents of (0,1)-matrices. Bull. Amer. Math. Soc. 69 (1963), 789 - 791.

7. H. Minc, Theory of permanents 1982 - 1985. Linear Multilinear Algebra 21 (1987), 109 - 148.

8. A. Schrijver, A short proof of Minc’s conjecture. J. Comb. Theory Ser. A 25 (1978), 80 - 83.

Suk-Geun Hwang

Department of Mathematics Education Teachers College Kyungpook National University Taegu 702-701, Republik Korea E-mail: sghwang@bh.kyungpook.ac.kr

und

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