\documentstyle[a4,german,12pt,twoside,leqno]{report}
\topmargin0.8cm
\textheight21.4cm
\pagestyle{myheadings}
\markboth{\hfill {\sc a.~r.~kr\"auter} \hfill}{\hfill {\sc l\"osungen der gleichung ${\rm 
per}(zI-A)=0$} \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, B16b (1987), 10 pp.
\newline [Formerly: Publ.~I.~R.~M.~A.~Strasbourg, 1988, 341/S-16, p. 87 - 98.]}

\vspace{39pt}

\setlength{\baselineskip}{15pt}

\begin{center}
{\bf EINIGE BEMERKUNGEN \"UBER DIE L\"OSUNGEN DER GLEICHUNG \, per(zI -- A) = 0}

\vspace{9pt}

{\sc von

\vspace{9pt}

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

\vspace{21pt}

\setlength{\baselineskip}{12pt}

{\footnotesize {\sc Zusammenfassung.} \quad Im Mittelpunkt der vorliegenden Note stehen 
Absch\"atzungen f\"ur den Maximalabstand zweier Nullstellen des Permanentenpolynoms der 
Matrix $A, \; {\rm per}(zI-A).$ Der Motivation f\"ur diese Untersuchungen dient ein 
kurzgefa"ster \"Uberblick \"uber dieses Polynom und seine Anwendungen auf Fragestellungen 
der Graphentheorie.

\vspace{6pt}

{\sc Abstract.} \quad This note focuses on bounds for the maximal distance of two zeros of 
the permanental polynomial of a matrix $A, \; {\rm 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.}

\vspace{6pt}

\setlength{\baselineskip}{15pt}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 1. Das Permanentenpolynom}
\end{center}

Die {\it Permanente} einer $n \times n$-Matrix $A = (a_{ij})$ \"uber einem beliebigen 
kom\-mu\-ta\-ti\-ven Ring ist definiert durch

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

\noindent wobei $S_n$ die symmetrische Gruppe der Ordnung $n$ bezeichnet. Ist $z$ eine
komplexe Ver\"anderliche und bezeichnet $I$ die $n \times n$-Einheitsmatrix, dann nennen wir 
${\rm per}(zI-A)$ das {\it Permanentenpolynom} von $A.$ Einen ausf\"uhrlichen \"Uberblick 
\"uber dieses Polynom findet man bei Merris-Rebman-Watkins [14]; erg\"anzend dazu sei die 
neuere Arbeit [5] von Cvetkovi\'c und Doob (siehe insbesondere pp. 171 - 174) angef\"uhrt. 
\\
F\"ur $k \leq n$ bezeichne $Q_{k,n}$ die Menge

\begin{equation}
Q_{k,n} = \left\{ \alpha = (\alpha_1, ..., \alpha_k) \in {\bf N}^k: \, 1 \leq \alpha_1 < ... 
< \alpha_k \leq n\right\}.
\end{equation}
\stepcounter{zaehler}

\noindent F\"ur eine $n \times n$-Matrix $A$ und einen Vektor $\alpha \in Q_{k,n}$ sei 
$A[\alpha]$ jene Hauptuntermatrix von $A,$ welche durch Streichen der Zeilen und Spalten mit 
den Indizes $\alpha$ entsteht. In der Darstellung

\begin{equation}
{\rm per}(zI-A) = \sum_{k=0}^n (-1)^k \, c_k \, z^{n-k}
\end{equation}
\stepcounter{zaehler}

\noindent haben die $c_k$ folgende Form (siehe Turner [22, p. 522]):

\begin{equation}
\left\{ \begin{array}{l}
        c_k = \sum_{\alpha \in Q_{k,n}} {\rm per}(A[\alpha]), \qquad 
        k = 1, ..., n, \\
        c_0 = 1. \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Insbesondere ist $c_1 = {\rm tr}(A)$ und $c_n = {\rm per}(A).$ \\
Eine wichtige Eigenschaft des Permanentenpolynoms ist seine Invarianz gegen\-\"uber der 
$P$-{\it \"Ahnlichkeit,} das hei"st f\"ur jede $n \times n$-Permutationsmatrix $P$ gilt

\begin{equation}
\left\{ \begin{array}{l@{\quad=\quad}l}
        {\rm per}(zI-P^{-1}AP) & {\rm per}[P^{-1}(zI-A)P] \; = \\
        & {\rm per}(zI-A). \\
\end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Dies folgt aus der Tatsache, da"s beliebige Zeilen- und Spaltenvertauschungen im 
Argument den Wert der Permanentenfunktion unver\"andert lassen (siehe Minc [17, p. 16]). \\
Um auf Probleme eingehen zu k\"onnen, in welchen das Permanentenpolynom von Bedeutung ist, 
sind einige vorbereitende und motivierende Bemerkungen er\-for\-der\-lich. \\
Es sei $G = (V,E)$ ein endlicher, ungerichteter Graph ohne Schlingen oder mehrfache Kanten, 
wobei $V = \left\{ v_1,...,v_n \right\}$ die Knotenmenge von $G$ und $E$ die Kantenmenge von 
$G$ bezeichnet. Die {\it Adjazenzmatrix} von $G, \; A(G) = (a_{ij}),$ ist eine $n \times 
n$-Matrix, definiert durch

\begin{equation}
a_{ij} = \left\{ \begin{array}{l}
                 1, \quad \mbox{falls} \quad (v_i,v_j) \in E, \\
                 0 \quad \mbox{sonst}, \\
                 \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent wobei $(v_i, v_j)$ die (ungerichtete) Kante bezeichnet, welche $v_i, v_j \in
V$ miteinander verbindet. \\
$A(G)$ h\"angt von $G$ sowie von der Numerierung der Knoten von $G$ ab. Es ist bekannt, da"s 
Adjazenzmatrizen bez\"uglich zweier verschiedener Numerierungen der Knoten desselben Graphen 
$P$-\"ahnlich sind. Ferner sind zwei Graphen $G_1$ und $G_2$ genau dann {\it isomorph,} 
falls $A(G_1)$ und $A(G_2)$ $P$-\"ahnlich sind. Somit ist jede gegen\"uber der 
$P$-\"Ahnlichkeit invariante Funktion von $A(G)$ eigentlich eine Funktion des 
zugrundeliegenden Graphen $G.$ Aus (1.5) folgt, da"s ${\rm per}(zI-A(G))$ eine solche 
Funktion darstellt. {\it Das Permanentenpolynom scheint also ein nat\"urliches
Hilfs\-mit\-tel 
beim Studium von Graphen zu sein} (Merris-Rebman-Watkins [14, p. 276]). \\
Man wei"s, da"s die Adjazenzmatrizen isomorpher Graphen das gleiche
Per\-ma\-nen\-ten\-po\-ly\-nom 
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"s 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"s auch das {\it cha\-rak\-te\-ris\-ti\-sche 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"s daf\"ur, anstelle der 
Adjazenzmatrix $A(G)$ die damit zusammenh\"angenden Matrizen

\begin{equation}
B(G) = D(G) + A(G)
\end{equation}
\stepcounter{zaehler}

\noindent und

\begin{equation}
L(G) = D(G) - A(G)
\end{equation}
\stepcounter{zaehler}

\noindent zu betrachten. Dabei ist

\begin{equation}
D(G) = {\rm diag}(d_1, ..., d_n),
\end{equation}
\stepcounter{zaehler}

\noindent worin $d_i$ den Grad des Knotens $v_i \;\; (1 \leq i \leq n)$ bezeichnet. In der 
Literatur ist $L(G)$ unter dem Namen {\it Admittanzmatrix} [4, p. 27], {\it Laplace-Matrix} 
[14, p. 279] oder {\it Kirchhoff-Matrix} [3, p. 182] bekannt (siehe auch [10, p. 345]). Die 
Hoffnung, das Isomorphieproblem bei Graphen mithilfe des Permanentenpolynoms der 
Laplace-Matrix l\"osen zu k\"onnen, hat sich bisher nicht erf\"ullt. Allerdings ist zur Zeit 
kein Paar nichtisomorpher Graphen $G_1$ und $G_2$ bekannt, f\"ur welches ${\rm per}(zI-
L(G_1)) = {\rm per}(zI-L(G_2))$ gilt [14, p. 282]. (F\"ur jenen Fall, in dem die Permanente 
durch eine andere Matrizenfunktion, die {\it zweite Immanante,} ersetzt wird, verweisen wir 
auf die j\"ungsten 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 \"uberraschende Beziehung zwischen dem 
Permanentenpolynom von $B(G)$ und dem Sterngrad von $G$ pr\"asentiert. \\
Unter einem {\it h\"angenden Stern} $S$ eines Graphen $G$ verstehen wir den maximalen 
Untergraphen von $G,$ welcher von allen h\"angenden Kanten gebildet wird, die mit demselben 
Knoten ("`Zentrum von $S$"') inzidieren. Bezeichnet $\nu(S)$ die Anzahl h\"angender Kanten 
in $S,$ dann definiert man als {\it Grad} von $S$ die Differenz $\nu(S) - 1.$ Der {\it 
Sterngrad} von $G$ ist erkl\"art als Summe der Grade aller h\"angenden Sterne von $G.$ 
(Falls es keinen h\"angenden Stern in $G$ gibt, ist der Sterngrad definitionsgem\"a"s Null.)

\bigskip

{\sc Satz 1.1} \, (Faria [7, p. 256]). \quad {\it Der Sterngrad eines Graphen} $G$ {\it ist 
gleich der Vielfachheit der Nullstelle} 1 {\it von} ${\rm per}(zI-B(G)).$

\bigskip

Satz 1.1 wird falsch, wenn man das Permanentenpolynom durch das
cha\-rak\-te\-ris\-ti\-sche Polynom 
ersetzt. Schlie"slich konnte Faria zeigen, da"s f\"ur ungerichtete paare
Gra\-phen $G$ die 
Beziehung ${\rm per}(zI-B(G)) = {\rm per}(zI-L(G))$ gilt [7, p. 262]. Hier kann also in Satz 
1.1 $B(G)$ durch $L(G)$ ersetzt werden.

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 2. Permanentenwurzeln}
\end{center}

Satz 1.1 legt die Betrachtung der Wurzeln der Gleichung 

\begin{equation}
{\rm per}(zI-A) = 0
\end{equation}
\stepcounter{zaehler}

\noindent f\"ur eine komplexe quadratische Matrix $A$ nahe. Eine komplexe Zahl $z = \omega,$ 
welche der Beziehung (2.1) gen\"ugt, wollen wir {\it Permanentenwurzel} von $A$ nennen. \\
Da die explizite Bestimmung von Permanentenwurzeln im allgemeinen
\"au\-"serst\break 
schwie\-rig 
ist, ist man sehr an Absch\"atzungen daf\"ur interessiert.

\bigskip

{\sc Satz 2.1} \, (Brenner-Brualdi [1, p. 586]). \quad {\it Es sei} $A$ {\it eine 
nichtnegative qua\-dra\-ti\-sche Matrix mit dem Spektralradius} $\varrho.$ {\it Dann gilt f\"ur 
jede Permanentenwurzel} $\omega$ {\it von} $A$

\begin{equation}
|\omega| \leq \varrho.
\end{equation}
\stepcounter{zaehler}

{\sc Satz 2.2} \, (Merris [13, p. 156]). \quad {\it Es sei} $A$ {\it eine normale} $n \times 
n$-{\it Matrix mit dem Spektralradius} $\varrho.$ {\it Dann gilt f\"ur jede 
Permanentenwurzel} $\omega$ {\it von} $A$

\begin{equation}
|\omega| \leq c \, \varrho
\end{equation}
\stepcounter{zaehler}

\noindent {\it mit}

\begin{equation}
c = \left\{ 1 + \left(\displaystyle\frac{2n}{\pi}\right)^2\right\}^{1/2}.
\end{equation}
\stepcounter{zaehler}

Die Konstante $c$ in (2.3) kann im allgemeinen nicht durch 1 ersetzt werden. \\
In Analogie zu entsprechenden Ergebnissen \"uber Eigenwerte sind auch {\it 
Ein\-schlie\-"sungs\-s\"at\-ze} f\"ur Permanentenwurzeln hergeleitet worden.

\bigskip

{\sc Satz 2.3} \, (Oliveira [20, p. 192]). \quad {\it Jede Permanentenwurzel einer 
qua\-dra\-ti\-schen Matrix} $A$ {\it liegt in der Vereinigung der Ger\v{s}gorin-Kreise von} $A.$

\bigskip

{\sc Satz 2.4} \, (Gibson [9, p. 20]). \quad {\it Jede
Per\-ma\-nen\-ten\-wur\-zel einer quadratischen 
Matrix} $A$ {\it liegt in der Vereinigung der Cassini-Ovale von} $A.$

\bigskip

Verwandt mit der Frage nach (m\"oglichst kleinen) Bereichen, welche alle
Per\-ma\-nen\-ten\-wur\-zeln 
einer gegebenen Matrix enthalten, ist jene nach dem Maximalabstand zweier 
Per\-ma\-nen\-ten\-wur\-zeln. (F\"ur Eigenwerte stammen diesbez\"ugliche
Un\-ter\-su\-chun\-gen in erster 
Linie von Mirsky [18], [19]; siehe auch [12, pp. 167 - 168].) Dieses Problem soll im 
folgenden ausf\"uhrlicher behandelt werden (siehe Kr\"auter [11]). \\
Es sei $A$ eine komplexe $n \times n$-Matrix mit den Permanentenwurzeln $\omega_1,..., 
\omega_n$ (ent\-spre\-chend ihrer Vielfachheit gez\"ahlt). Wir definieren

\begin{equation}
s_p (A) := \max_{i,j} |\omega_i - \omega_j|,
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,R} (A) := \max_{i,j} |{\rm Re} \, \omega_i - {\rm Re} \, \omega_j|,
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,I} (A) := \max_{i,j} |{\rm Im} \, \omega_i - {\rm Im} \, \omega_j|.
\end{equation}
\stepcounter{zaehler}

\noindent Unsere Aufgabe besteht nun darin, f\"ur diese Ausdr\"ucke 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\"ur gewisse Matrizenklassen gegl\"uckt. \\
Eine quadratische Matrix $A = (a_{ij})$ hei"st {\it untere Hessenberg-Matrix} (oder {\it 
untere Fastdreiecksmatrix}), falls

\begin{equation}
a_{ij} = 0 \quad \mbox{f\"ur} \quad i \leq j-2
\end{equation}
\stepcounter{zaehler}

\noindent gilt. $A$ hei"st {\it obere Hessenberg-Matrix,} falls $A^T$ untere
Hessenberg-Matrix ist. \\
$A$ hei"st {\it Jacobi-Matrix} (oder {\it Tridiagonalmatrix}), wenn $A$ sowohl obere als 
auch untere Hessenberg-Matrix ist. \\
Zwei untere Hessenberg-Matrizen $A = (a_{ij})$ und $B = (b_{ij})$ hei"sen {\it verwandt,} 
falls

\begin{equation}
b_{ij} = \left\{ \begin{array}{l@{\quad\mbox{f\"ur}\quad}l}
                 -a_{ij} & i < j, \\
                 +a_{ij} & i \geq j \\
                 \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent gilt. Zwei obere Hessenberg-Matrizen hei"sen verwandt, wenn ihre Transponierten 
verwandt im vorhin erkl\"arten Sinn sind. Bezeichnen $A$ und $B$ verwandte (entweder beide 
untere oder beide obere) Hessenberg-Matrizen, so schreiben wir $B = \tilde{A}.$ Die Matrix 
$\tilde{A}$ 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\"art, wenn
die Per\-ma\-nen\-ten\-wur\-zeln durch die Eigenwerte von $A$ ersetzt werden. \\
Mit diesen Vorbereitungen sind wir nun in der Lage, den folgenden wichtigen
Hilfs\-satz zu 
formulieren:

\bigskip

{\sc Hilfssatz 2.1} \, (Kr\"auter [11, p. 42]). \quad {\it F\"ur eine Hessenberg-Matrix} $A$ 
{\it gilt}

\begin{equation}
s_p (A) = s_d (\tilde{A}),
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,R} (A) = s_{d,R} (\tilde{A}),
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,I} (A) = s_{d,I} (\tilde{A}).
\end{equation}
\stepcounter{zaehler}

Ehe wir eine erste Absch\"atzung behandeln, ben\"otigen wir eine weitere
Be\-zeich\-nung. \\
$n \geq 2$ komplexe Zahlen $z_1,...,z_n$ hei"sen {\it streckenhalbierende
Punk\-te,} falls sie 
die folgende Eigenschaft besitzen: \\
(1) im Fall $n = 2$ k\"onnen $z_1$ und $z_2$ beliebig sein; \\
(2) im Fall $n > 2$ sind $z_1,...,z_n$ derart beschaffen, da"s $n-2$ von ihnen gleich dem 
arithmetischen Mittel der \"ubrigen zwei sind.

\bigskip

{\sc Hilfssatz 2.2} \, (Mirsky [18, p. 128]). \quad {\it Es seien} $z_1,...,z_n, \;\; n \geq 
2,$ {\it komplexe Zahlen und es sei} $s = \max_{i,j} |z_i - z_j|.$ {\it Dann gilt}

\begin{equation}
\displaystyle\frac{1}{2} \, n s^2 \leq \sum_{1 \leq i<j \leq n} |z_i - z_j|^2.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Das Gleichheitszeichen tritt genau dann auf, wenn} $z_1,...,z_n$ {\it 
streckenhalbierende\break Punk\-te sind.}

\bigskip

{\sc Satz 2.5} \, (Kr\"auter [11, pp. 43 - 44]). \quad {\it F\"ur eine} $n \times n$-{\it 
Hessenberg-Matrix} $A \;\; (n \geq 2)$ {\it gilt}

\begin{equation}
s_p (A) \leq \left\{ 2 \, \| A \| ^2 - \displaystyle\frac{2}{n} \, |{\rm tr} (A) |^2 
\right\}^{1/2}.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Gleichheit tritt in} (2.14) {\it genau dann auf, wenn} $\tilde{A}$ {\it 
normal ist und wenn die Per\-ma\-nen\-ten\-wur\-zeln von} $A$ {\it streckenhalbierende Punkte sind.}

\smallskip

{\it Beweis:} F\"ur die Eigenwerte $\lambda_1,...,\lambda_n$ von $A$ gilt nach Schur [21, 
pp. 492 - 493]

\begin{equation}
\sum_{i=1}^n  |\lambda_i|^2 \leq \| A \| ^2,
\end{equation}
\stepcounter{zaehler}

\noindent wobei das Gleichheitszeichen genau dann auftritt, wenn $A$ normal ist. Mit etwas 
Rechnung erh\"alt man

\begin{equation}
\sum_{1 \leq i<j \leq n} |\lambda_i - \lambda_j|^2 = n \, \sum_{i=1}^n |\lambda_i|^2 - |{\rm 
tr} (A)|^2,
\end{equation}
\stepcounter{zaehler}

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

\begin{equation}
\displaystyle\frac{1}{2} \, n \, [s_d (A)]^2 \leq \sum_{1 \leq i<j \leq n} |\lambda_i - 
\lambda_j|^2 \leq n \, \| A \| ^2 - |{\rm tr} (A)|^2,
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_d (A) \leq \left\{ \displaystyle\frac{2}{n} \, \sum_{1 \leq i<j \leq n} |\lambda_i - 
\lambda_j|^2 \right\}^{1/2} \leq \left\{ 2 \, \| A \| ^2 - \displaystyle\frac{2}{n} \, |{\rm 
tr} (A)|^2 \right\}^{1/2}.
\end{equation}
\stepcounter{zaehler}

Ersetzt man in (2.18) $A$ durch $\tilde{A},$ so erh\"alt man (2.14) mit Hilfssatz 2.1 und 
aufgrund der Tatsache, da"s $\| \tilde{A} \| = \| A \|$ sowie ${\rm tr} (\tilde{A}) = {\rm 
tr} (A)$ gilt. Die Gleich\-heits\-be\-din\-gung folgt aus dem oben zitierten Satz von Schur sowie 
Hilfssatz 2.2. $\Box$

\bigskip

Die Anwendung einer Ungleichung von Deutsch [6] f\"ur Eigenwerte liefert
un\-mit\-tel\-bar eine 
weitere obere Schranke f\"ur $s_p (A),$ welche in manchen F\"allen eine Versch\"arfung von 
(2.14) darstellt.

\bigskip

{\sc Satz 2.6} \, (Kr\"auter [11, p. 44]). \quad {\it F\"ur eine} $n \times 
n$-{\it Hessenberg-Matrix} $A = (a_{ij}) \; \; (n \geq 3)$ {\it gilt}

\begin{equation}
s_p (A) \leq \sum_{1 \leq i,j \leq n} |a_{ij}|.
\end{equation}
\stepcounter{zaehler}

Beispielsweise erh\"alt man f\"ur die Matrix

\[
A = \left[ \begin{array}{ccc}
           2 & 1 & 0 \\
           1 & 2 & 1 \\
           1 & 1 & 101 \\
           \end{array} \right]
\]

\noindent mit (2.14) $s_p (A) \leq 114,36,$ mit (2.19) jedoch $s_p (A) \leq 104.$ (Es ist 
$s_p (A) \approx 98,99.$) \\
Absch\"atzungen f\"ur die Real- und Imagin\"arteile der Permanentenwurzeln von 
Jacobi-Matrizen durch Gibson [8] dienten als Motivation f\"ur die Herleitung oberer 
Schran\-ken f\"ur $s_{p,R} (A)$ beziehungsweise $s_{p,I} (A).$

\bigskip

{\sc Satz 2.7} \, (Kr\"auter [11, p. 46]). \quad {\it Es sei} $A = (a_{ij})$ {\it eine} $n 
\times n$-{\it Hessenberg-Matrix} $(n \geq 2)$, {\it soda"s} ${\rm Re} \, (a_{i,i+1} \, 
a_{i+1,i}) \geq 0$ {\it f\"ur} $i = 1,...,n-1$ {\it ist. Dann gilt}

\begin{equation}
s_{p,R} (A) \leq \left\{ \| A \| ^2 + {\rm Re} \, [{\rm tr} (A^2)] - 
\displaystyle\frac{2}{n} \, [{\rm Re} \, ({\rm tr} (A))]^2 \right\}^{1/2}.
\end{equation}
\stepcounter{zaehler}

\noindent {\it Gleichheit tritt in} (2.20) {\it genau dann auf, wenn} $\tilde{A}$ {\it 
normal ist,} ${\rm Re} \, (a_{i,i+1} \, a_{i+1,i}) = 0$ {\it f\"ur alle} $i = 1,...,n-1,$ 
{\it und wenn die Realteile aller Permanentenwurzeln von} $A$ {\it streckenhalbierende 
Punkte sind.}

\bigskip

Ein analoger Satz gilt f\"ur $s_{p,I} (A).$ Abschlie"send seien noch {\it untere} Schranken 
f\"ur die Gr\"o"sen (2.5) - (2.7) angef\"uhrt.

\bigskip

{\sc Satz 2.8} \, (Kr\"auter [11, p. 48]). \quad {\it Es sei} $A = (a_{ij})$ {\it eine} $n 
\times n$-{\it Hessenberg-Matrix} $(n \geq 2),$ {\it soda"s} $\tilde{A}$ {\it normal ist. 
Dann gilt}

\begin{equation}
s_p (A) \geq \sqrt{3} \, \max_{i \not= j} |a_{ij}|,
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,R} (A) \geq \max_{1 \leq i \leq n} \left\{ |a_{i,i+1} - 
\overline{a_{i+1,i}}|, \; \max_{j \not= i,i+1} |a_{ij} + \overline{a_{ji}}| 
\right\},
\end{equation}
\stepcounter{zaehler}
\begin{equation}
s_{p,I} (A) \geq \max_{1 \leq i \leq n} \left\{ |a_{i,i+1} +
\overline{a_{i+1,i}}|, \; \max_{j \not= i,i+1} |a_{ij} - \overline{a_{ji}}|
\right\}.
\end{equation}
\stepcounter{zaehler}

Man beachte, da"s die Absch\"atzung (2.21) bestm\"oglich ist. Dazu sei

\[
A = \left[ \begin{array}{ccc}
            0 & -a & 0 \\
            0 & 0 & -a \\
            a & 0 & 0 \\
            \end{array} \right] \oplus O_{n-3},
\]

\noindent wobei $a > 0$ ist und $O_{n-3}$ die $(n-3) \times (n-3)$-Nullmatrix bezeichnet.
$A$ besitzt die Permanentenwurzeln $\omega_i = a \, \zeta^{i-1}, \;\; i = 1, 2, 3,$ wobei 
$\zeta$ eine fest gew\"ahlte dritte Einheitswurzel ist, und $\omega_4 = ... = \omega_n = 0.$ 
Somit ist $s_p (A) = a \, \sqrt{3}$ und wegen $\max_{i \not= j} |a_{ij}| = a$ haben wir 
Gleichheit in (2.21). \\
Es soll nicht unerw\"ahnt bleiben, da"s die S\"atze 2.5 - 2.8 f\"ur umfangreichere 
Ma\-tri\-zen\-klas\-sen als die dort angegebenen g\"ultig sind. Dieser Umstand sowie weitere 
Ergebnisse, deren detaillierte Behandlung den Rahmen dieser Note sprengen w\"urde, werden 
ebenfalls in der Arbeit [11] behandelt.

\bigskip

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

\begin{footnotesize}
\begin{enumerate}

\item Joel Lee {\sc Brenner} and Richard Anthony {\sc Brualdi,} Eigenschaften
der Permanentefunktion. {\it Archiv der Mathematik} {\bf 18,} 585 - 586 
(1967).
\item Lothar {\sc Collatz} und Ulrich {\sc Sinogowitz,} Spektren endlicher
Grafen. {\it Abhandlungen aus dem Mathematischen Seminar der Universit\"at
Hamburg} {\bf 21,} 63 - 77 (1957).
\item Gregory M. {\sc Constantine,} Schur convex functions on the spectra of
graphs. {\it Discrete Mathematics} {\bf 45,} 181 - 188 (1983).
\item Drago\v{s} M. {\sc Cvetkovi\'c,} Michael {\sc Doob,} and Horst
{\sc Sachs,} {\it Spectra of Graphs. Theory and Applications.} New York:
Academic Press, 1980.
\item Drago\v{s} M. {\sc Cvetkovi\'c} and Michael {\sc Doob,} Developments
in the theory of graph spectra. {\it Linear and Multilinear Algebra} {\bf
18,} 153 - 181 (1985).
\item Emeric {\sc Deutsch,} On the spread of matrices and polynomials.
{\it Linear Algebra and Its Applications} {\bf 22,} 49 - 55 (1978).
\item Isabel {\sc Faria,} Permanental roots and the star degree of a graph.
{\it Linear Algebra and Its Applications} {\bf 64,} 255 - 265 (1985).
\item Peter Murray {\sc Gibson,} Eigenvalues of complex tridiagonal matrices.
{\it Proceedings of the Edinburgh Mathematical Society (2)} {\bf 17,} 317 -
319 (1971).
\item Peter Murray {\sc Gibson,} Localization of the zeros of the permanent
of a characteristic matrix. {\it Proceedings of the American Mathematical
Society} {\bf 31,} 18 - 20 (1972).
\item Mohammad {\sc Ishaq,} Russell {\sc Merris,} and Elaine {\sc Zaslawsky,}
Problems concerning per\-ma\-nen\-tal polynomials of graphs. {\it Linear and
Multilinear Algebra} {\bf 15,} 345 - 350 (1984).
\item Arnold Richard {\sc Kr\"auter,} On the greatest distance between two
permanental roots of a matrix. {\it Linear Algebra and Its
Ap\-pli\-ca\-tions}
{\bf 93,} 39 - 55 (1987).
\item Marvin {\sc Marcus} and Henryk {\sc Minc,} {\it A Survey of Matrix
Theory and Matrix Inequalities.} Boston: Allyn \& Bacon, 1964.
\item Russell {\sc Merris,} Two problems involving Schur functions. {\it 
Linear Algebra and Its Ap\-pli\-ca\-tions} {\bf 10,} 155 - 162 (1975).
\item Russell {\sc Merris,} Kenneth Ralph {\sc Rebman,} and William
{\sc Watkins,} Permanental po\-ly\-no\-mials of graphs. {\it Linear Algebra and
Its Applications} {\bf 38,} 273 - 288 (1981).
\item Russell {\sc Merris,} The Laplacian permanental polynomial for trees.
{\it Czechoslovak Ma\-the\-ma\-ti\-cal Journal} {\bf 32,} 397 - 403 (1982).
\item Russell {\sc Merris,} The second immanantal polynomial and the centroid
of a graph. {\it SIAM Journal on Algebraic and Discrete Methods} {\bf 7,}
484 - 503 (1986).
\item Henryk {\sc Minc,} {\it Permanents.} Encyclopedia of Mathematics and
Its Applications, Volume 6. Reading: Addison-Wesley, 1978.
\item Leon {\sc Mirsky,} The spread of a matrix. {\it Mathematika} {\bf 3,}
127 - 130 (1956).
\item Leon {\sc Mirsky,} Inequalities for normal and Hermitian matrices.
{\it Duke Mathematical Journal} {\bf 24,} 591 - 599 (1957).
\item Graciano Neves de {\sc Oliveira,} On the multiplicative inverse
eigenvalue problem. {\it Canadian Mathematical Bulletin} {\bf 15,}
189 - 193 (1972).
\item Issai {\sc Schur,} \"Uber die charakteristischen Wurzeln einer linearen
Substitution mit einer Anwendung auf die Theorie der Integralgleichungen.
{\it Mathematische Annalen} {\bf 66,} 488 - 510 (1909).
\item James {\sc Turner,} Generalized matrix functions and the graph
isomorphism problem. {\it SIAM Journal on Applied Mathematics} {\bf 16,}
520 - 526 (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}
