Séminaire Lotharingien de Combinatoire, B16b (1987), 10 pp. [Formerly: Publ. I. R. M. A. Strasbourg, 1988, 341/S-16, p. 87 - 98.]

EINIGE BEMERKUNGEN ÜBER DIE LÖSUNGEN DER GLEICHUNG per(zI – A) = 0

von

Arnold Richard KRÄUTER

Zusammenfassung. Im Mittelpunkt der vorliegenden Note stehen Abschätzungen für den Maximalabstand zweier Nullstellen des Permanentenpolynoms der Matrix A, per(zI − A). Der Motivation für diese Untersuchungen dient ein kurzgefaßter Überblick über dieses Polynom und seine Anwendungen auf Fragestellungen der Graphentheorie.

Abstract. This note focuses on bounds for the maximal distance of two zeros of the permanental polynomial of a matrix A, per(zI − A). In order to motivate these investigations, we present a short survey of this polynomial and its applications to problems arising in graph theory.

1. Das Permanentenpolynom

Die Permanente einer n × n-Matrix A = (a_{ij}) über einem beliebigen kommutativen Ring ist definiert durch

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

wobei S_{n} die symmetrische Gruppe der Ordnung n bezeichnet. Ist z eine komplexe Veränderliche und bezeichnet I die n × n-Einheitsmatrix, dann nennen wir per(zI −A) das Permanentenpolynom von A. Einen ausführlichen Überblick über dieses Polynom findet man bei Merris-Rebman-Watkins [14]; ergänzend dazu sei die neuere Arbeit [5] von Cvetković und Doob (siehe insbesondere pp. 171 - 174) angeführt. Für k ≤ n bezeichne Q_{k,n} die Menge

Q_{k,n} = {α = (α_{1}, ..., α_{k}) ∈ N^{k} : 1 ≤ α_{1} < ... < α_{k} ≤ n} . (1.2)

Für eine n × n-Matrix A und einen Vektor α ∈ Q_{k,n} sei A[α] jene Hauptuntermatrix von A, welche durch Streichen der Zeilen und Spalten mit den Indizes α entsteht. In der Darstellung

per(zI − A) = ∑_{k=0}^{n}(−1)^{k} c_{k} z^{n−k} (1.3)

haben die c_{k} folgende Form (siehe Turner [22, p. 522]):

\{ \begin{matrix}c_{k} = ∑_{α∈Q_{k,n}} per(A[α]), k = 1, ..., n, \\ c_{0} = 1. \end{matrix} (1.4)

Insbesondere ist c_{1} = tr(A) und c_{n} = per(A). Eine wichtige Eigenschaft des Permanentenpolynoms ist seine Invarianz gegenüber der P -Ähnlichkeit, das heißt für jede n × n-Permutationsmatrix P gilt

\{ \begin{matrix}per(zI − P^{−1}AP) = & per[P^{−1}(zI − A)P] = \\ = & per(zI − A). \end{matrix} (1.5)

Dies folgt aus der Tatsache, daß beliebige Zeilen- und Spaltenvertauschungen im Argument den Wert der Permanentenfunktion unverändert lassen (siehe Minc [17, p. 16]). Um auf Probleme eingehen zu können, in welchen das Permanentenpolynom von Bedeutung ist, sind einige vorbereitende und motivierende Bemerkungen erforderlich. Es sei G = (V, E) ein endlicher, ungerichteter Graph ohne Schlingen oder mehrfache Kanten, wobei V = {v_{1}, ..., v_{n}} die Knotenmenge von G und E die Kantenmenge von G bezeichnet. Die Adjazenzmatrix von G, A(G) = (a_{ij}), ist eine n × n-Matrix, definiert durch

(1.6) a_{ij} = \{ \begin{matrix}1, falls (v_{i}, v_{j}) ∈ E, \\ 0 sonst, \end{matrix}

wobei (v_{i}, v_{j}) die (ungerichtete) Kante bezeichnet, welche v_{i}, v_{j} ∈ V miteinander verbindet. A(G) hängt von G sowie von der Numerierung der Knoten von G ab. Es ist bekannt, daß Adjazenzmatrizen bezüglich zweier verschiedener Numerierungen der Knoten desselben Graphen P -ähnlich sind. Ferner sind zwei Graphen G_{1} und G_{2} genau dann isomorph, falls A(G_{1}) und A(G_{2}) P -ähnlich sind. Somit ist jede gegenüber der P -Ähnlichkeit invariante Funktion von A(G) eigentlich eine Funktion des zugrundeliegenden Graphen G. Aus (1.5) folgt, daß per(zI − A(G)) eine solche Funktion darstellt. Das Permanentenpolynom scheint also ein natürliches Hilfsmittel beim Studium von Graphen zu sein (Merris-Rebman-Watkins [14, p. 276]).

lösungen der gleichung per(zI − A) = 0 3

Man weiß, daß die Adjazenzmatrizen isomorpher Graphen das gleiche Permanentenpolynom besitzen (Turner [22, p. 521]). Es erhebt sich nun die Frage, ob umgekehrt von der Gleichheit der Permanentenpolynome auf die Isomorphie der jeweiligen Graphen geschlossen werden darf. Daß dies im allgemeinen nicht der Fall ist, zeigte Turner anhand eines einfachen Gegenbeispiels [22, pp. 524 - 525]. Es sei an dieser Stelle daran erinnert, daß auch das charakteristische Polynom isomorphe Graphen nicht zu charakteristieren vermag; dieser Sachverhalt findet sich bereits 1957 in der Arbeit [2] von Collatz und Sinogowitz (siehe auch [4, p. 156]; man vergleiche dazu auch die einleitenden Bemerkungen bei Merris [15, p. 397].) Diese negativen Befunde waren der Anlaß dafür, anstelle der Adjazenzmatrix A(G) die damit zusammenhängenden Matrizen

B(G) = D(G) + A(G) (1.7)

und

L(G) = D(G) − A(G) (1.8)

zu betrachten. Dabei ist

D(G) = diag(d_{1}, ..., d_{n}), (1.9)

worin d_{i} den Grad des Knotens v_{i} (1 ≤ i ≤ n) bezeichnet. In der Literatur ist L(G) unter dem Namen Admittanzmatrix [4, p. 27], Laplace-Matrix [14, p. 279] oder Kirchhoff-Matrix [3, p. 182] bekannt (siehe auch [10, p. 345]). Die Hoffnung, das Isomorphieproblem bei Graphen mithilfe des Permanentenpolynoms der Laplace-Matrix lösen zu können, hat sich bisher nicht erfüllt. Allerdings ist zur Zeit kein Paar nichtisomorpher Graphen G_{1} und G_{2} bekannt, für welches per(zI − L(G_{1})) = per(zI − L(G_{2})) gilt [14, p. 282]. (Für jenen Fall, in dem die Permanente durch eine andere Matrizenfunktion, die zweite Immanante, ersetzt wird, verweisen wir auf die jüngsten Untersuchungen von Merris [16].) Im Zusammenhang mit dem Studium der Matrizen B(G) und L(G) verdient die Arbeit [7] von Faria besondere Beachtung, welche unter anderem eine überraschende Beziehung zwischen dem Permanentenpolynom von B(G) und dem Sterngrad von G präsentiert. Unter einem hängenden Stern S eines Graphen G verstehen wir den maximalen Untergraphen von G, welcher von allen hängenden Kanten gebildet wird, die mit demselben Knoten (”Zentrum von S“) inzidieren. Bezeichnet ν(S) die Anzahl hängender Kanten in S, dann definiert man als Grad von S die Differenz ν(S) − 1. Der Sterngrad von G ist erklärt als Summe der Grade aller hängenden Sterne von G. (Falls es keinen hängenden Stern in G gibt, ist der Sterngrad definitionsgemäß Null.)

Satz 1.1 (Faria [7, p. 256]). Der Sterngrad eines Graphen G ist gleich der Vielfachheit der Nullstelle 1 von per(zI − B(G)).

Satz 1.1 wird falsch, wenn man das Permanentenpolynom durch das charakteristische Polynom ersetzt. Schließlich konnte Faria zeigen, daß für ungerichtete paare Graphen G die Beziehung per(zI −B(G)) = per(zI −L(G)) gilt [7, p. 262]. Hier kann also in Satz 1.1 B(G) durch L(G) ersetzt werden.

2. Permanentenwurzeln

Satz 1.1 legt die Betrachtung der Wurzeln der Gleichung

per(zI − A) = 0 (2.1)

für eine komplexe quadratische Matrix A nahe. Eine komplexe Zahl z = ω, welche der Beziehung (2.1) genügt, wollen wir Permanentenwurzel von A nennen. Da die explizite Bestimmung von Permanentenwurzeln im allgemeinen äußerst schwierig ist, ist man sehr an Abschätzungen dafür interessiert.

Satz 2.1 (Brenner-Brualdi [1, p. 586]). Es sei A eine nichtnegative quadratische Matrix mit dem Spektralradius ϱ. Dann gilt für jede Permanentenwurzel ω von A

|ω| ≤ ϱ. (2.2)

Satz 2.2 (Merris [13, p. 156]). Es sei A eine normale n × n-Matrix mit dem Spektralradius ϱ. Dann gilt für jede Permanentenwurzel ω von A

|ω| ≤ c ϱ (2.3)

mit

c = \{1 + (\frac{2n}{π})^{2}\}^{1/2} . (2.4)

Die Konstante c in (2.3) kann im allgemeinen nicht durch 1 ersetzt werden. In Analogie zu entsprechenden Ergebnissen über Eigenwerte sind auch Einschließungssätze für Permanentenwurzeln hergeleitet worden.

Satz 2.3 (Oliveira [20, p. 192]). Jede Permanentenwurzel einer quadratischen Matrix A liegt in der Vereinigung der Geršgorin-Kreise von A.

Satz 2.4 (Gibson [9, p. 20]). Jede Permanentenwurzel einer quadratischen Matrix A liegt in der Vereinigung der Cassini-Ovale von A.

Verwandt mit der Frage nach (möglichst kleinen) Bereichen, welche alle Permanentenwurzeln einer gegebenen Matrix enthalten, ist jene nach dem Maximalabstand zweier Permanentenwurzeln. (Für Eigenwerte stammen diesbezügliche Untersuchungen in erster Linie von Mirsky [18], [19]; siehe auch [12, pp. 167 - 168].) Dieses Problem soll im folgenden ausführlicher behandelt werden (siehe Kräuter [11]). Es sei A eine komplexe n × n-Matrix mit den Permanentenwurzeln ω_{1}, ..., ω_{n} (entsprechend ihrer Vielfachheit gezählt). Wir definieren

s_{p}(A) := max_{i,j} |ω_{i} − ω_{j}|, (2.5)

s_{p,R}(A) := max_{i,j} |Re ω_{i} − Re ω_{j}|, (2.6)

s_{p,I}(A) := max_{i,j} |Im ω_{i} − Im ω_{j}|. (2.7)

Unsere Aufgabe besteht nun darin, für diese Ausdrücke obere und untere Schranken anzugeben, welche sich als einfach zu berechnende Funktionen der Elemente von A darstellen lassen. Die Herleitung derartiger Schranken ist aufgrund technischer Schwierigkeiten bisher lediglich für gewisse Matrizenklassen geglückt. Eine quadratische Matrix A = (a_{ij}) heißt untere Hessenberg-Matrix (oder untere Fastdreiecksmatrix), falls

a_{ij} = 0 für i ≤ j − 2 (2.8)

gilt. A heißt obere Hessenberg-Matrix, falls A^{T} untere Hessenberg-Matrix ist. A heißt Jacobi-Matrix (oder Tridiagonalmatrix), wenn A sowohl obere als auch untere Hessenberg-Matrix ist. Zwei untere Hessenberg-Matrizen A = (a_{ij}) und B = (b_{ij}) heißen verwandt, falls

b_{ij} = \{ \begin{matrix}−a_{ij} für & i < j, \\ +a_{ij} für & i ≥ j \end{matrix} (2.9)

gilt. Zwei obere Hessenberg-Matrizen heißen verwandt, wenn ihre Transponierten verwandt im vorhin erklärten Sinn sind. Bezeichnen A und B verwandte (entweder beide untere oder beide obere) Hessenberg-Matrizen, so schreiben wir B = Ã. Die Matrix Ã ist aufgrund der Beziehung (2.9) eindeutig bestimmt. Analog zu (2.5) - (2.7) seien s_{d}(A), s_{d,R}(A) und s_{d,I}(A) erklärt, wenn die Permanentenwurzeln durch die Eigenwerte von A ersetzt werden. Mit diesen Vorbereitungen sind wir nun in der Lage, den folgenden wichtigen Hilfssatz zu formulieren:

Hilfssatz 2.1 (Kräuter [11, p. 42]). Für eine Hessenberg-Matrix A gilt

s_{p}(A) = s_{d}(Ã), (2.10)

s_{p,R}(A) = s_{d,R}(Ã), (2.11)

s_{p,I}(A) = s_{d,I}(Ã). (2.12)

Ehe wir eine erste Abschätzung behandeln, benötigen wir eine weitere Bezeichnung. n ≥ 2 komplexe Zahlen z_{1}, ..., z_{n} heißen streckenhalbierende Punkte, falls sie die folgende Eigenschaft besitzen:

(1) im Fall n = 2 können z_{1} und z_{2} beliebig sein;

(2) im Fall n > 2 sind z_{1}, ..., z_{n} derart beschaffen, daß n − 2 von ihnen gleich dem arithmetischen Mittel der übrigen zwei sind.

Hilfssatz 2.2 (Mirsky [18, p. 128]). Es seien z_{1}, ..., z_{n}, n ≥ 2, komplexe Zahlen und es sei s = max_{i,j} |z_{i} − z_{j}|. Dann gilt

\frac{1}{2} ns^{2} ≤ ∑_{1≤i<j≤n} |z_{i} − z_{j}|^{2}. (2.13)

Das Gleichheitszeichen tritt genau dann auf, wenn z_{1}, ..., z_{n} streckenhalbierende Punkte sind.

Satz 2.5 (Kräuter [11, pp. 43 - 44]). Für eine n × n-Hessenberg-Matrix A (n ≥ 2) gilt

s_{p}(A) ≤ \{2 ∥A∥^{2} − \frac{2}{n} |tr(A)|^{2}\}^{1/2} . (2.14)

Gleichheit tritt in (2.14) genau dann auf, wenn Ã normal ist und wenn die Permanentenwurzeln von A streckenhalbierende Punkte sind.

Beweis: Für die Eigenwerte λ_{1}, ..., λ_{n} von A gilt nach Schur [21, pp. 492 - 493]

∑_{i=1}^{n} |λ_{i}|^{2} ≤ ∥A∥^{2}, (2.15)

wobei das Gleichheitszeichen genau dann auftritt, wenn A normal ist. Mit etwas Rechnung erhält man

∑_{1≤i<j≤n} |λ_{i} − λ_{j}|^{2} = n ∑_{i=1}^{n} |λ_{i}|^{2} − |tr(A)|^{2}, (2.16)

woraus mit Hilfssatz 2.2 und (2.15) nach einigen Umformungen folgt:

\frac{1}{2} n [s_{d}(A)]^{2} ≤ ∑_{1≤i<j≤n} |λ_{i} − λ_{j}|^{2} ≤ n ∥A∥^{2} − |tr(A)|^{2}, (2.17)

s_{d}(A) ≤ \{\frac{2}{n} ∑_{1≤i<j≤n} |λ_{i} − λ_{j}|^{2}\}^{1/2} ≤ \{2 ∥A∥^{2} − \frac{2}{n} |tr(A)|^{2}\}^{1/2} . (2.18)

Ersetzt man in (2.18) A durch Ã, so erhält man (2.14) mit Hilfssatz 2.1 und aufgrund der Tatsache, daß ∥Ã∥ = ∥A∥ sowie tr(Ã) = tr(A) gilt. Die Gleichheitsbedingung folgt aus dem oben zitierten Satz von Schur sowie Hilfssatz 2.2. □

Die Anwendung einer Ungleichung von Deutsch [6] für Eigenwerte liefert unmittelbar eine weitere obere Schranke für s_{p}(A), welche in manchen Fällen eine Verschärfung von (2.14) darstellt.

Satz 2.6 (Kräuter [11, p. 44]). Für eine n × n-Hessenberg-Matrix A = (a_{ij}) (n ≥ 3) gilt

s_{p}(A) ≤ ∑_{1≤i,j≤n} |a_{ij}|. (2.19)

Beispielsweise erhält man für die Matrix

A = [ \begin{matrix}2 & 1 & 0 \\ 1 & 2 & 1 \\ 1 & 1 & 101 \end{matrix} ]

mit (2.14) s_{p}(A) ≤ 114, 36, mit (2.19) jedoch s_{p}(A) ≤ 104. (Es ist s_{p}(A) ≈ 98, 99.) Abschätzungen für die Real- und Imaginärteile der Permanentenwurzeln von Jacobi-Matrizen durch Gibson [8] dienten als Motivation für die Herleitung oberer Schranken für s_{p,R}(A) beziehungsweise s_{p,I}(A).

Satz 2.7 (Kräuter [11, p. 46]). Es sei A = (a_{ij}) eine n × n-Hessenberg-Matrix (n ≥ 2), sodaß Re (a_{i,i+1} a_{i+1,i}) ≥ 0 für i = 1, ..., n − 1 ist. Dann gilt

(2.20) s_{p,R}(A) ≤ \{∥A∥^{2} + Re [tr(A^{2})] − \frac{2}{n} [Re (tr(A))]^{2}\}^{1/2} .

Gleichheit tritt in (2.20) genau dann auf, wenn Ã normal ist, Re (a_{i,i+1} a_{i+1,i}) = 0 für alle i = 1, ..., n − 1, und wenn die Realteile aller Permanentenwurzeln von A streckenhalbierende Punkte sind.

Ein analoger Satz gilt für s_{p,I}(A). Abschließend seien noch untere Schranken für die Größen (2.5) - (2.7) angeführt.

Satz 2.8 (Kräuter [11, p. 48]). Es sei A = (a_{ij}) eine n × n-Hessenberg-Matrix (n ≥ 2), sodaß Ã normal ist. Dann gilt

s_{p}(A) ≥ \sqrt{3} max_{i≠j} |a_{ij}|, (2.21)

s_{p,R}(A) ≥ max_{1≤i≤n} \{|a_{i,i+1} − \overline{a_{i+1,i}}|, max_{j≠i,i+1} |a_{ij} + \overline{a_{ji}}|\} , (2.22)

s_{p,I}(A) ≥ max_{1≤i≤n} \{|a_{i,i+1} + \overline{a_{i+1,i}}|, max_{j≠i,i+1} |a_{ij} − \overline{a_{ji}}|\} . (2.23)

Man beachte, daß die Abschätzung (2.21) bestmöglich ist. Dazu sei

A = [ \begin{matrix}0 & −a & 0 \\ 0 & 0 & −a \\ a & 0 & 0 \end{matrix} ] ⊕ O_{n−3},

wobei a > 0 ist und O_{n−3} die (n − 3) × (n − 3)-Nullmatrix bezeichnet. A besitzt die Permanentenwurzeln ω_{i} = a ζ^{i−1}, i = 1, 2, 3, wobei ζ eine fest gewählte dritte Einheitswurzel ist, und ω_{4} = ... = ω_{n} = 0. Somit ist s_{p}(A) = a \sqrt{3} und wegen max_{i≠j} |a_{ij}| = a haben wir Gleichheit in (2.21). Es soll nicht unerwähnt bleiben, daß die Sätze 2.5 - 2.8 für umfangreichere Matrizenklassen als die dort angegebenen gültig sind. Dieser Umstand sowie weitere Ergebnisse, deren detaillierte Behandlung den Rahmen dieser Note sprengen würde, werden ebenfalls in der Arbeit [11] behandelt.

Literatur

[1] Joel Lee Brenner and Richard Anthony Brualdi, Eigenschaften der Permanentefunktion. Archiv der Mathematik 18, 585 - 586 (1967).

[2] Lothar Collatz und Ulrich Sinogowitz, Spektren endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 21, 63 - 77 (1957).

[3] Gregory M. Constantine, Schur convex functions on the spectra of graphs. Discrete Mathematics 45, 181 - 188 (1983).

[4] Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of Graphs. Theory and Applications. New York: Academic Press, 1980.

[5] Dragoš M. Cvetković and Michael Doob, Developments in the theory of graph spectra. Linear and Multilinear Algebra 18, 153 - 181 (1985).

[6] Emeric Deutsch, On the spread of matrices and polynomials. Linear Algebra and Its Applications 22, 49 - 55 (1978).

[7] Isabel Faria, Permanental roots and the star degree of a graph. Linear Algebra and Its Applications 64, 255 - 265 (1985).

[8] Peter Murray Gibson, Eigenvalues of complex tridiagonal matrices. Proceedings of the Edinburgh Mathematical Society (2) 17, 317 - 319 (1971).

[9] Peter Murray Gibson, Localization of the zeros of the permanent of a characteristic matrix. Proceedings of the American Mathematical Society 31, 18 - 20 (1972).

[10] Mohammad Ishaq, Russell Merris, and Elaine Zaslawsky, Problems concerning permanental polynomials of graphs. Linear and Multilinear Algebra 15, 345 - 350 (1984).

[11] Arnold Richard Kräuter, On the greatest distance between two permanental roots of a matrix. Linear Algebra and Its Applications 93, 39 - 55 (1987).

[12] Marvin Marcus and Henryk Minc, A Survey of Matrix Theory and Matrix Inequalities. Boston: Allyn & Bacon, 1964.

[13] Russell Merris, Two problems involving Schur functions. Linear Algebra and Its Applications 10, 155 - 162 (1975).

[14] Russell Merris, Kenneth Ralph Rebman, and William Watkins, Permanental polynomials of graphs. Linear Algebra and Its Applications 38, 273 - 288 (1981).

[15] Russell Merris, The Laplacian permanental polynomial for trees. Czechoslovak Mathematical Journal 32, 397 - 403 (1982).

[16] Russell Merris, The second immanantal polynomial and the centroid of a graph. SIAM Journal on Algebraic and Discrete Methods 7, 484 - 503 (1986).

10 a. r. kräuter

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

[18] Leon Mirsky, The spread of a matrix. Mathematika 3, 127 - 130 (1956).

[19] Leon Mirsky, Inequalities for normal and Hermitian matrices. Duke Mathematical Journal 24, 591 - 599 (1957).

[20] Graciano Neves de Oliveira, On the multiplicative inverse eigenvalue problem. Canadian Mathematical Bulletin 15, 189 - 193 (1972).

[21] Issai Schur, Über die charakteristischen Wurzeln einer linearen Substitution mit einer Anwendung auf die Theorie der Integralgleichungen. Mathematische Annalen 66, 488 - 510 (1909).

[22] James Turner, Generalized matrix functions and the graph isomorphism problem. SIAM Journal on Applied Mathematics 16, 520 - 526 (1968).

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