%unipathic.tex %edited june 8,1994 by judi and michael \documentstyle[12pt,leqno]{article} \newtheorem{cor}{Corollary}[section] \newtheorem{thm}[cor]{Theorem} \newtheorem{lem}[cor]{Lemma} \newtheorem{rem}[cor]{Remark} \newtheorem{defi}[cor]{Definition} \newtheorem{nota}[cor]{Notation} \newtheorem{exa}[cor]{Example} \newtheorem{oq}[cor]{Open Question} \newtheorem{claim}[cor]{Claim} \newtheorem{obs}[cor]{Observation} \renewcommand{\theequation}{\thecor} \newcommand{\el}{\ell} \newcommand{\RE}{\rm I\mskip-4mu R} \renewcommand{\l}{\langle} \newcommand{\r}{\rangle} \newcommand{\vd}{\vdots} \newcommand{\ld}{\ldots} \newcommand{\dd}{\ddots} \newcommand{\ac}{\leadsto} \newcommand{\nac}{\not\leadsto} \newcommand{\ed}{\rightarrow} \newcommand{\ned}{\not\rightarrow} \newcommand{\g}{\Gamma} \newcommand{\D}{{\cal D}} \begin{document} \bibliographystyle{plain} \title{INVERSES OF UNIPATHIC M--MATRICES} \author{J. J. McDonald \thanks{Work supported by NSERC grant 6-53120} \\ Department of Mathematics and Statistics \\University of Regina\\ Regina, Saskatchewan S4S 0A2 \and M. Neumann\thanks{Work supported by NSF Grant DMS-8901860 and NSF Grant DMS-9306357.}\\Department of Mathematics \\University of Connecticut\\ Storrs, Connecticut 06269--3009 \and H. Schneider\thanks{Work supported by NSF Grant DMS-9123318.}\\Department of Mathematics\\University of Wisconsin\\ Madison, Wisconsin 53706 \and M. J. Tsatsomeros \thanks{Work supported by NSERC grant 6-53121} \\ Department of Mathematics and Statistics \\University of Regina \\Regina, Saskatchewan S4S 0A2} %\date \maketitle \newpage \begin{center} {\bf Abstract} \end{center} \medskip %We continue our investigation on the inverse M--matrix problem %begun in \cite{MNST}. This time In this paper, we characterize all nonnegative matrices whose inverses are M--matrices with unipathic digraphs. A digraph is called unipathic if there is at most one simple path from any vertex $j$ to any other vertex $k$. The set of unipathic digraphs on $n$ vertices includes the simple $n$--cycle and all digraphs whose underlying undirected graphs are trees (or forests). We show that any unipathic nonsingular M--matrix is permutation similar to an LU--decomposition into unipathic M--matrices. Our results facilitate the construction of nonnegative matrices whose inverses a M--matrices with unipathic digraphs. We highlight this procedure for inverses of tridiagonal M--matrices and of M--matrices whose digraph is the simple $n$--cycle with loops. \newpage %************************************************************** \section{Introduction} In the present article we contribute toward the inverse M--matrix problem by providing necessary and sufficient conditions for an (entrywise) nonnegative matrix $C$ to be the inverse of an M--matrix whose digraph is unipathic. A digraph is called unipathic if there is at most one simple path from any vertex $j$ to any other vertex $k$. \medskip Unipathic graphs were introduced by Harary, Norman, and Cartwright \cite{HNC}, and they were proposed as a new direction of research in combinatorial matrix analysis by Maybee \cite{M}. It is pointed out in \cite{M} that unipathic digraphs can serve as a generalization and a theoretic unification of digraphs whose underlying undirected graphs are trees (or forests) and of directed simple cycles. \medskip The conditions we obtain for a nonnegative matrix to be an inverse of an M--matrix whose digraph is unipathic involve positivity of the diagonal entries and certain $2\times 2$ principal minors as well as the zeroness of particular off--diagonal entries and $2\times 2$ almost principal minors (see Theorem \ref{main}). Our proof is based on properties of unipathic graphs (see Lemmas \ref{path} and \ref{indeg}) and on a key observation in \cite{MNST} that connects zero $2\times 2$ almost principal minors of an inverse M--matrix to the digraph of the M--matrix (see Theorem \ref{thmi}). \medskip In Section 4, we show that a nonsingular M--matrix whose digraph is unipathic admits, up to a permutation similarity, an LU--decomposition into lower and upper triangular M--matrices whose graphs are unipathic (see Theorem \ref{ulu}). A stronger result holds when the digraph of the M--matrix is a forest (see Theorem \ref{flu}). \medskip Our results facilitate the construction of nonnegative matrices whose inverses a M--matrices with unipathic digraphs. We illustrate this procedure for inverses of tridiagonal M--matrices and of M--matrices whose digraph is a simple cycle with loops (see Section 5). \medskip For definitions, references and background on M--matrices and the inverse M--matrix problem the reader is referred to Berman and Plemmons \cite{BP} and Johnson \cite{J}. \medskip In the following section we introduce the notation necessary to describe our results, summarize the properties of unipathic digraphs, and present some definitions and auxiliary results. %************************************************************** \section{Notation and Preliminaries} Throughout the paper we let $\l n\r=\{1,2,\ld,n\}$ and $\g=(V,E)$ be a digraph with vertex set $V=\l n\r$ and directed edge set $E=\{(i,j) \ | \ i,j\in V\}$. A {\it path} from $j$ to $k$ in $\Gamma$ is a sequence of vertices $j=r_1,r_2,...,r_t=k$, with $(r_i,r_{i+1})\in E$, for $i=1,...,t-1$. A path is {\em simple} if $r_1, r_2,\ldots, r_t$ are distinct. A path from any vertex to itself is called a {\em cycle}. It is called a {\em simple cycle} if the intermediate vertices are distinct. \medskip A digraph is called {\em unipathic} if there is at most one simple path from any vertex $j$ to any other vertex $k$. \medskip We adopt the following notation to be used within proofs and in commentary: \medskip $j\ac_\g k$ : if there is a path from $j$ to $k$ in $\g$ (``$j$ has access to $k$ in $\g$''). $j\nac_\g k$ : if there is no path from $j$ to $k$ in $\g$. $j\ed_\g k$ : if $(j,k)\in\ E$. $j\ned_\g k$ : if $(j,k)\not\in\ E$. \medskip We denote by $\g_i$ the digraph obtained from $\g$ when vertex $i$ and any associated edges are removed (i.e., the subgraph of $\g$ induced by $\l n\r\setminus i$). We denote by $\g^i$ the digraph obtained from $\g_i$ by adding an edge from a vertex $j$ to a vertex $k$ whenever $j\ed_\g i$ and $i\ed_\g k$. The {\em transitive closure} of $\g$, denoted by $\overline{\g}$, is obtained from $\Gamma$ by adding an edge $(i,j)$ whenever $i\ac_\g j$. If $\g=(V,E)$ and $\g'=(V,E')$ are two digraphs, we let $\g\cup\g'=(V,E\cup E')$. \medskip The {\it digraph of a matrix} $A=(a_{ij})\in\RE^{nn}$ is denoted by ${\cal D}(A)=(V,E)$, with $V=\langle n\rangle$ and $E= \{(i,j) \ | \ a_{ij}\ne 0\}$. We say that $A$ is {\em irreducible} if $j\ac_{{\cal D}(A)} k$ for all $j,k\in V$. The matrix $A$ is called {\em unipathic} if ${\cal D}(A)$ is a unipathic digraph. \medskip The {\em underlying undirected graph} of $\g$ is obtained by removing the loops and the directions from the edges of $\g$. An undirected graph with no cycles is called a {\em forest}. A connected forest is called a {\em tree}. A vertex of a tree incident to exactly one edge is called {\em pendant}. \medskip We continue with a summary of the characteristics of unipathic digraphs. Clearly in any digraph, if there is a path from $j$ to $k$, then there is a simple path from $j$ to $k$. By definition, if $\g$ is unipathic, then there may be several paths from $j$ to $k$, but there can only be one simple path. More precisely we have the following lemma. \begin{lem} \label{path} Let $\g$ be a unipathic digraph. Let $i,\ j,\ k$ be distinct vertices such that $j\ac_\g k$. Then the following are equivalent: \begin{description} \item[(i)] The vertex $j$ does not have access to $k$ in $\g_i$. \item[(ii)] Every path in $\g$ from $j$ to $k$ goes through $i$. \item[(iii)] The simple path from $j$ to $k$ in $\g$ goes through $i$. \end{description} \end{lem} \noindent \underline{Proof}: \medskip\noindent (i) implies (ii): If $j\nac_{\g_i} k$, then every path from $j$ to $k$ must go through $i$. \medskip\noindent (ii) implies (iii): If every path in $\g$ from $j$ to $k$ goes through $i$, then the simple path from $j$ to $k$ in $\g$ goes through $i$. \medskip\noindent (iii) implies (i): Let $i$ be any vertex in the simple path from $j$ to $k$. Suppose $j\ac_{\g_i} k$. Then there is a simple path from $j$ to $k$ in $\g_i$. But then we would have two different simple paths from $j$ to $k$ in $\g$. Contradiction. Hence $j\nac_{\g_i} k$. $\hfill \Box$ \medskip A unipathic digraph may have loops on its vertices and, unlike a digraph whose underlying undirected graph is a tree, may have cycles of length greater than 2. However, no two cycles can have a common edge. As it is explained in \cite{M}, every strongly connected unipathic digraph can be constructed from a tree (by adjoining chords and orienting the resulting cycles, and by replacing edges with directed simple paths). Notice that if the digraph of a combinatorially symmetric matrix $A=(a_{ij})$ (i.e., $a_{ij}\neq 0$ implies $a_{ji}\neq 0$) is strongly connected and unipathic, then its underlying undirected graph must be a tree. \medskip An important property of unipathic digraphs is given next. The {\em indegree} (resp. {\em outdegree}) of a vertex $i$ of a digraph is the number of edges entering (resp. issuing from) vertex $i$. \begin{lem} \label{indeg} Let $\g=(V,E)$ be a unipathic digraph. Then there is a vertex with indegree at most 1, and a vertex with outdegree at most 1. \end{lem} \noindent \underline{Proof}: \medskip\noindent If there is not a vertex with indegree 0, let $r_1,r_2,...,r_t\in V$ and $(r_i,r_{i+1})\in E$, $i=1,...,t-1$, be a simple path in $\g$ of maximal length. Then $r_1$ has indegree at most 1, otherwise (by maximality of the path) for some $i,j\in\l t \r$ with $i0$ for all $1\leq i \leq n$, $C+\alpha I$ is invertible for all $\alpha \geq 0$, ${\cal D}(C)=\overline{{\cal D}(C)}$, and \addtocounter{cor}{1} \begin{equation} \label{eq.2} {\cal D}((C+\alpha I)^{-1}) \ = \ {\cal D}(C), \ \ \mbox{for all} \ \ \alpha>0. \end{equation} \end{thm} \noindent \underline{Proof}: \medskip\noindent Assume first that $C$ is the inverse of an M--matrix. Then it is well known that $c_{ii}>0$, $i=1,\ldots,n$, $C+\alpha I$ is invertible for all $\alpha \geq 0$, and ${\cal D}(C)=\overline{{\cal D}(C)}$. Now put $A=C^{-1}$ and observe that \addtocounter{cor}{1} \begin{equation} \label{eq.3} (C+\alpha I)^{-1} \ = \ \beta A( A +\beta I )^{-1}, \end{equation} where $\beta:=1/\alpha$. Since $A$ is a nonsingular M--matrix, there exists $P\geq 0$ such that $A=sI-P$ and such that $s>\rho(P)$ (the spectral radius of $P$). But then, by the Neumann expansion, \addtocounter{cor}{1} \begin{equation} \label{eq.4} C \ = \ \frac{1}{s}I + \frac{1}{s}\sum_{j=1}^{\infty} \frac{P^j}{s^j}. \end{equation} The validity of (\ref{eq.2}) now follows by comparing, for $\alpha>0$, the expansion for the matrix on the right--hand--side of (\ref{eq.3}) which can be obtained via (\ref{eq.1}) and the expansion in (\ref{eq.4}). \medskip\noindent Conversely, suppose that the equality in (\ref{eq.2}) holds for all $\alpha>0$. If $((C+\alpha I)^{-1})_{ij}=0$ for some $\alpha>0$, then by (\ref{eq.2}) it must hold for all $\alpha>0$ and hence, by continuity arguments, $(C^{-1})_{ij}=0$. Similarly, if $((C+\alpha I)^{-1})_{ij}<0$ then, again by (\ref{eq.2}), this entry must be negative for all $\alpha>0$ so that $(C^{-1})_{ij}\leq 0$. Suppose now that $((C+\alpha I )^{-1})_{ij}>0$, $i\neq j$, for some $\alpha>0$ so that this entry is positive for all $\alpha>0$. Then, for sufficiently large $\alpha>0$, the Neumann expansion gives us that: \begin{displaymath} ((C+\alpha I )^{-1})_{ij} \ = \ \frac{1}{\alpha} \left(\left(I +\frac{C}{\alpha} \right)^{-1} \right)_{ij} \ = \ \frac{1}{\alpha}\left(I - \frac{C}{\alpha}+ \frac{C^2}{\alpha^2}- \ldots \right)_{ij}. \end{displaymath} In particular we see that as $\alpha$ increases, it will attain a value such that beyond this value the $(i,j)$--th entry of $(C+\alpha I)^{-1}$ will become negative, contradicting the constancy of the sign implied by (\ref{eq.2}). Hence there cannot be a value of $\alpha>0$ for which $(C+\alpha I)^{-1})_{ij}>0$ and our proof is done. \hfill $\Box$ \medskip Our theorem has the following two corollaries. \begin{cor} \label{corollary.1} Let $C=(c_{ij})\in\RE^{nn}$ be nonnegative. Then a necessary and sufficient condition for $C$ to be the inverse of an M--matrix is that $c_{ii}>0$, the matrix $C+\alpha I$ is invertible for all $\alpha >0$, ${\cal D}(C) = \overline{{\cal D}(C)}$, and that for each pair $(i,j)$ the minor of $C+\alpha I$ obtained after deleting the $i$--th row and $j$--th column, has a constant sign as a function of $\alpha>0$. \end{cor} \begin{cor} If $A\in\RE^{nn}$ is a nonsingular M--matrix, then for any $\alpha >0$, ${\cal D}(A^{-1}+\alpha I)^{-1}=\overline{{\cal D}(A)}$. \end{cor} \medskip The last corollary has the following implication. Suppose that $A\in\RE^{nn}$ is a nonsingular irreducible M--matrix, but which has some off--diagonal entries equal to zero. Invert $A$ to obtain the positive matrix $C$. Now invert $C+\alpha I$. Then $(C+\alpha I)^{-1}$ has all its entries nonzero. %************************************************************** \section{The Inverse of a Unipathic M--matrix} We begin with a theorem on nonsingular M--matrices proved in McDonald, Neumann, Schneider, and Tsatsomeros \cite{MNST}. It represents a graph--theoretical refinement and generalization of a condition found in Willoughby \cite{Wi} that is necessary for a matrix to be an inverse M--matrix. \begin{thm} \label{thmi} Let $A\in\RE^{nn}$ be a nonsingular M--matrix and $\g={\cal D}(A)$. Let also $C=A^{-1}$ and $\{i,j,k\}\subseteq\l n\r$ be distinct. Then: \begin{description} \item[(i)] $c_{jk}=\frac{c_{ji}c_{ik}}{c_{ii}}$, whenever $j$ does not have access to $k$ in $\g_i$, \item[(ii)] $c_{jk}>\frac{c_{ji}c_{ik}}{c_{ii}}$, whenever $j$ has access to $k$ in $\g_i$. \end{description} \end{thm} Notice that Theorem \ref{thmi} refers to the value (zero or positive) of the almost principal minors of $C$ formed from rows $i,\ j$ and columns $i, \ k$. In the next theorem, our main result, we provide necessary and sufficient conditions for $C\geq 0$ to be the inverse of a unipathic M--matrix with digraph $\g$. It is apparent that these conditions involve the diagonal entries of $C$, some off--diagonal entries and $2\times 2$ principal minors, and some of the almost principal minors of $C$ mentioned in clause (i) of Theorem \ref{thmi}. \begin{thm} \label{main} Let $\g$ be a unipathic graph on $n$ vertices and $C\in\RE^{nn}$. Then the following are equivalent: \begin{description} \item[(i)] $C$ is nonsingular and $C^{-1}$ is a M--matrix such that ${\cal D}(C^{-1})=\g$. \item[(ii)] $C \geq 0$ and satisfies: \begin{description} \item[(a)] $c_{ii}>0$, for all $i\in\l n \r$. \item[(b)] $c_{jj}c_{kk}> c_{jk}c_{kj},$ for all distinct $j$ and $k$ such that there is an edge from $j$ to $k$ in $\g$. \item[(c)] $c_{jk}=0,$ whenever there is no path from $j$ to $k$ in $\g$. \item[(d)] $c_{jk}=\frac{c_{ji} c_{ik}}{c_{ii}},$ for all distinct $i,j,k,$ such that there is a path from $j$ to $k$ in $\g$ and there is no path from $j$ to $k$ in $\g_i$. \end{description} \end{description} \end{thm} \noindent\underline{Proof}: \medskip\noindent (i) implies (ii): Since $C^{-1}$ is an M--matrix, $C\geq 0$ and (ii)(a),(b) follow from well known facts about M--matrices (see e.g., \cite{BP}). Property (ii)(c) follows from the fact that the digraph of an inverse M--matrix is the transitive closure of the digraph of its inverse (see Schneider \cite{S}). Property (ii)(d) follows from Theorem \ref{thmi}. \medskip\noindent (ii) implies (i): We proceed by induction on $n$. For $n=1,$ the result follows trivially. Assume that (ii) implies (i) for all $(n-1)\times (n-1)$ matrices. \medskip Using the inductive hypothesis we will establish three claims which, combined with Lemma \ref{schur}, will allow us to show that $C$ is invertible and that its inverse is a Z--matrix (i.e., it has nonpositive off--diagonal entries) with graph $\g$. \medskip \noindent {\bf Claim 1} \ {\em $c_{jj}c_{kk}>c_{jk}c_{kj}$, for all distinct $j,k\in\l n\r$.} \medskip\noindent\underline{Proof of Claim 1}: If $j\nac_\g k$ or $k\nac_\g j$ then by (c), $c_{jk}c_{kj}=0,$ and the claim follows. Assume $j\ac_\g k$ and $k\ac_\g j$. We induct on the length, $r$, of the simple path from $j$ to $k$. If $r=1$, the claim follows from (b). Assume $r>1$ and that the claim holds for any two vertices connected by a simple path with length less than $r$. Either the simple path from $j$ to $k$ has no vertices, other than $j$ and $k$, in common with the simple path from $k$ to $j$, or there is an additional vertex $i$ which is common to both paths. In the latter case, by (d), Lemma \ref{path}, and the induction hypothesis on the path length, $$\frac{c_{jk}c_{kj}}{c_{jj}c_{kk}}= \frac{c_{ji}c_{ik}c_{ki}c_{ij}}{c_{jj}c_{ii}c_{kk}c_{ii}} =(\frac{c_{ji}c_{ij}}{c_{jj}c_{ii}} ) (\frac{c_{ik}c_{ki}}{c_{kk}c_{ii}})<1.$$ \noindent In the former case, for any $i$ in the simple path from $j$ to $k$, there is a simple path from $i$ to $j$ through $k$. Hence by (d), Lemma \ref{path}, and the induction hypothesis on the path length, $$\frac{c_{jk}c_{kj}}{c_{jj}c_{kk}}= \frac{c_{ji}c_{ik}c_{kj}}{c_{jj}c_{ii}c_{kk}} =\frac{c_{ji}c_{ij}}{c_{jj}c_{ii}}<1.$$ This establishes Claim 1. \medskip \noindent {\bf Claim 2} {\em For any $\el\in\l n \r$ let $S=\l n \r\setminus \el$ and $B=C/C[\el,\el]$. Then $B$ is invertible and $B^{-1}$ is an M--matrix with ${\cal D}(B^{-1})=\g_\el$.} \medskip \noindent \underline{Proof of Claim 2}: By the induction hypothesis, it is enough to show $B$ satisfies (ii) for the graph $\g_\el$. For ease of notation, we will assume that the the indices of the entries of $B$ correspond to those of $C$, i.e., $$b_{jk}=c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}}.$$ First we show that $B$ is nonnegative. \medskip If $b_{jk}$ is nonzero, then either $c_{jk}\neq 0$ or $c_{j\el}c_{\el k}\neq 0 $, hence $j\ac_\g k$. \medskip If $c_{j\el}c_{\el k}=0$, then $b_{jk}=c_{jk}\geq 0$. \medskip If $c_{j\el}c_{\el k}\neq 0$ then by (c) $j\ac_\g \el$ and $\el\ac_\g k$. \begin{description} \item If $j\nac_{\g_\el} k$, \\ then by (d) $$b_{jk}=c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}} =b_{jk}-b_{jk}=0.$$ \item If $j\ac_{\g_\el} k$, \\ then since joining the simple paths from $j$ to $\el$ and $\el$ to $k$ forms a path from $j$ to $k$ which includes $\el$, it cannot be a simple path and hence there must be a least one vertex which is repeated. Let $i$ be the first vertex in the path from $j$ to $\el$ which is also in the path from $\el$ to $k$. Then the subpath from $j$ to $i$ and then $i$ to $k$, forms a simple path from $j$ to $k$. Hence $j\nac_{\g_i} k$, $j\nac_{\g_i} \el$, and $\el\nac_{\g_i} k$. By Lemma \ref{path}, $$b_{jk}=c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}} =c_{jk}-\frac{c_{ji}c_{i\el}c_{\el i}c_{ik}}{c_{ii}c_{ii} c_{\el\el}}$$ $$= c_{jk}-c_{jk}\frac{c_{i\el}c_{\el i}}{c_{ii}c_{\el\el}} =c_{jk}(1-\frac{c_{i\el}c_{\el i}}{c_{ii}c_{\el\el}}) >0 \ \ (\mbox{by Claim 1}).$$ \end{description} We now show that properties (ii)(a)--(d), labeled here as (a')--(d'), also hold for the matrix $B$ with the graph $\g_\el$. \medskip \noindent (a') By Claim 1, $$b_{jj}=c_{jj}-\frac{c_{j\el}c_{\el j}}{c_{\el\el}}>0.$$ \medskip\noindent (b') Suppose $j\ed_{\g_\el} k$. \medskip\noindent If $k\nac_{\g} \el$, then either $k\nac_\g j$ or $j\nac_\g \el$, so by (c), \addtocounter{cor}{1} \begin{equation} \label{e1} c_{k\el}=0=\frac{c_{kj}c_{j\el}}{c_{jj}}. \end{equation} \medskip\noindent Otherwise $k\ac_{\g} \el$ and hence $j\ac_{\g} \el$. Then either $j$ is in the simple path from $k$ to $\el$ in $\g$, or the edge from $j$ to $k$ combined with the simple path from $k$ to $\el$ forms a simple path from $j$ to $\el$ in $\g$ which includes $k$. Hence, by (d) and Lemma \ref{path} either (\ref{e1}) holds or \addtocounter{cor}{1} \begin{equation} \label{e2} c_{j\el}=\frac{c_{jk}c_{k\el}}{c_{kk}}. \end{equation} \medskip\noindent If (\ref{e1}) holds then by replacing $c_{k\el}$ in the following expression we get: $$b_{jj}b_{kk}-b_{jk}b_{kj}= (c_{jj}-\frac{c_{j\el}c_{\el j}}{c_{\el\el}}) (c_{kk}-\frac{c_{k\el}c_{\el k}}{c_{\el\el}})- (c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}}) (c_{kj}-\frac{c_{k\el}c_{\el j}}{c_{\el\el}}) $$ $$ =(c_{jj}c_{kk}-c_{jk}c_{kj})- \frac{c_{jj}c_{kk}c_{j\el}c_{\el j}- c_{jk}c_{kj}c_{j\el}c_{\el j}}{c_{jj}c_{\el\el}} -\frac{c_{kj}c_{j\el}c_{\el k}-c_{kj}c_{j\el}c_{\el k}} {c_{\el\el}} $$ $$ =(c_{jj}c_{kk}-c_{jk}c_{kj}) (1-\frac{c_{j\el}c_{\el j}}{c_{jj}c_{\el\el}})>0 \ \ (\mbox{by Claim 1}).$$ If equation (\ref{e2}) holds, then the above inequality follows in a similar manner. \medskip\noindent (c') If $j\nac_{\g_\el} k$, then by (c) or (d) $$b_{jk}=c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}} =c_{jk}-c_{jk}=0.$$ \medskip\noindent (d') Let $i,j,k \in S$ be distinct. Assume $j\ac_{\g_\el} k$, but $j\nac_{(\g_\el)_i} k$. Then $j\nac_{\g_i} k$, hence by (d) \addtocounter{cor}{1} \begin{equation} \label{e3} c_{jk}=\frac{c_{ji}c_{ik}}{c_{ii}}. \end{equation} \medskip If $j\ac_\g \el$ and $k\ac_\g \el$, then by Lemma \ref{path} either $i$ is in the simple path from $j$ to $\el$, or $i$ is in the simple path from $\el$ to $k$. Hence by (d) and Lemma \ref{path}, \addtocounter{cor}{1} \begin{equation} \label{e4} c_{j\el}=\frac{c_{ji}c_{i\el}}{c_{ii}} \end{equation} or \addtocounter{cor}{1} \begin{equation} \label{e5} c_{\el,k}=\frac{c_{\el i}c_{ik}}{c_{ii}}. \end{equation} \medskip\noindent If $j\nac_\g \el$ then $i\nac_\g \el$, and hence by (c), equation (\ref{e4}) is satisfied. \medskip\noindent If $\el\nac_\g k$ then $\el\nac_\g i$, and hence by (c), equation (\ref{e5}) is satisfied. \medskip\noindent Hence either (\ref{e4}) holds, or (\ref{e5}) holds. \medskip If (\ref{e4}) holds, then using (\ref{e3}) to replace $c_{jk}$ and (\ref{e4}) to replace $c_{j\el}$ in the following expression we get: \[ b_{jk}b_{ii}-b_{ji}b_{ik}= (c_{jk}-\frac{c_{j\el}c_{\el k}}{c_{\el\el}}) (c_{ii}-\frac{c_{i\el}c_{\el i}}{c_{\el\el}}) (c_{ji}-\frac{c_{j\el}c_{\el i}}{c_{\el\el}}) (c_{ik}-\frac{c_{i\el}c_{\el k}}{c_{\el\el}}) \] \[ =(c_{jk}c_{ii}-c_{ji}c_{ik})- (\frac{c_{ji}c_{ik}c_{i\el}c_{\el i}- c_{ji}c_{i\el}c_{\el i}c_{ik}}{c_{ii}c_{\el\el}}) \] \[ -(\frac{c_{ii}c_{ji}c_{i\el}c_{\el k}-c_{ii}c_{i\el}c_{\el k} c_{ji}} {c_{ii}c_{\el\el}}) =0. \] If (\ref{e5}) holds, then the above equality follows in a similar manner. This establishes Claim 2. \medskip By Lemma \ref{indeg}, there is a vertex with indegree at most 1. Without loss of generality, we can assume this vertex is labeled by $n$ (otherwise we can work with a permutation similarity of $C$). Let $T=\langle n-1\rangle$. \medskip\noindent {\bf Claim 3}: {\em The matrix $C[T,T]$ is invertible and its inverse is an M-matrix with graph $\g^n$. Moreover, $C/C[T,T]>0$.} \medskip\noindent \underline{Proof of Claim 3}: Since $i\ac_{\g^n} j$ if and only if $i\ac_{\g} j$, (a), (c) and (d) of (ii) must hold for $C[T,T]$. Also (ii)(b) follows from Claim 1. Hence, by the induction hypothesis, $C[T,T]$ is invertible and its inverse is an M--matrix with graph $\Gamma^n$. To show that $C/C[T,T]>0$, if the indegree of $n$ is one choose $m$ such that $m\ed_\g n$, otherwise choose any $m\in\l n-1\r$. Then by (c) and (d): \addtocounter{cor}{1} \begin{equation} \label{e6} C[T,n]=\left[ \begin{array}{c} c_{1n}\\c_{2n}\\ \vdots \\c_{n-1,n} \end{array} \right] \end{equation} \[ =\left[ \begin{array}{c}\frac{c_{1m}c_{mn}}{c_{mm}} \\ \frac{c_{2m}c_{mn}}{c_{mm}}\\ \vdots \\ \frac{c_{n-1,m}c_{mn}}{c_{mm}} \end{array} \right]= \frac{c_{mn}}{c_{mm}} \left[ \begin{array}{c} c_{1m} \\ c_{2m} \\ \vdots \\ c_{n-1,m} \end{array} \right]= \frac{c_{mn}}{c_{mm}} C[T,m] \] Thus, by (\ref{e6}), $$C/C[S,S]=c_{nn}-C[n,S](C[S,S])^{-1}C[S,n] $$ $$=c_{nn}-\frac{c_{mn}}{c_{mm}}C[n,S](C[S,S])^{-1}C[S,m] =c_{nn}-\frac{c_{mn}}{c_{mm}}C[n,S]e_m $$ $$=c_{nn}-\frac{c_{mn}c_{nm}}{c_{mm}}>0 \ \ (\mbox{by Claim 1}). $$ This establishes Claim 3. \medskip Recall now that, since by Claims 2 and 3 \ $C/C[n,n], \ C[T,T]$, and \ $C/C[T,T]$ \ are invertible, \ $C$ has to be invertible and its inverse is, from Lemma \ref{schur} with $R=n$ and $Q=T$, \[ \left[\matrix{ (C/C[n,n])^{-1} & -(C[T,T])^{-1}C[T,n](C/C[T,T])^{-1} \cr -(C[n,n])^{-1}C[n,T](C/C[n,n])^{-1} & (C/C[T,T])^{-1} \cr} \right]. \] Moreover, by Claim 2, \ $C^{-1}[\el,\el]=(C/C[\el,\el])^{-1}$ \ is an M--matrix with graph $\g_\el$, for all $\el\in\l n\r$. It follows that $C^{-1}$ is a Z--matrix with graph $\g$, whose inverse is a nonnegative matrix. This means that $C^{-1}$ is an M--matrix with graph $\g$. {\hfill $\Box$} \medskip The contents of Claims 2 and 3 within the inductive proof of Theorem \ref{main} can now be stated separately. \begin{cor} \label{cors} Let $C\in\RE^{nn}$ be the inverse of a unipathic M--matrix with digraph $\g$. \begin{description} \item[(i)] For any $\el\in\l n\r$ and $S=\l n \r\setminus \el$, \ $C/C[\el,\el]$ is the inverse of a unipathic M--matrix with digraph $\g_\el$. \item[(ii)] For any $\el\in\l n\r$ of indegree at most 1 and $T=\l n \r\setminus \el$, \ $C[T,T]$ is the inverse of a unipathic M--matrix with digraph $\g^\el$. Moreover, $C/C[T,T]>0$. \end{description} \end{cor} \begin{rem} {\em It is well known that if $C$ is an inverse M--matrix then its diagonal entries and $2\times 2$ principal minors are positive, the $2\times 2$ almost principal minors satisfy Theorem \ref{thmi}, and ${\cal D}(C)=\overline{{\cal D}(C)} =\overline{{\cal D}(C^{-1})}$. These conditions are not in general sufficient for $C\geq 0$ to be an inverse M--matrix. However, as we show in Theorem \ref{main}, a subset of these conditions, dictated by a unipathic digraph, is necessary and sufficient for $C$ to be the inverse of a unipathic M--matrix. } \end{rem} \begin{rem} {\em It follows by Corollary \ref{corollary.1} that if $C$ is a nonnegative matrix that satisfies one and hence both of the equivalent conditions of Theorem \ref{main}, then for each pair $1\leq i,j \leq n$, the minor of $C+\alpha I$ which is obtained by deleting the $i$--th row and $j$--th column has a constant sign as a function of $\alpha>0$. } \end{rem} %&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& \section{LU--decompositions of Unipathic M--matrices} \begin{thm} \label{ulu} Let $A\in\RE^{nn}$ be a nonsingular unipathic M--matrix. Then there is a permutation matrix $P$ such that $P^{-1}AP=LU$, where $L$ and $U$ are unipathic M--matrices with $L$ lower triangular and $U$ upper triangular. \end{thm} \noindent\underline{Proof}: \medskip\noindent By Lemma \ref{indeg}, the digraph of every principal submatrix of $A$ is unipathic and hence has a vertex of indegree one. To obtain the LU--decomposition mentioned in the statement of the theorem, we perform row reduction with respect to a pivot that corresponds to a vertex of indegree one in the digraph of the unreduced part. Symmetric permutations of $A$ may be needed, but for simplicity of notation in the proof, we will assume that the vertices of ${\cal D}(A)$ are ordered appropriately. We proceed by induction on $n$. For $n=1$ the result is trivial. Assume it is true for all $(n-1)\times(n-1)$ unipathic M--matrices. Let $T=\langle n\rangle\setminus \{1\}$. Let $C=A^{-1}$. By Corollary \ref{cors}, $(C[T,T])^{-1}$ is a unipathic M--matrix and hence, by the inductive hypothesis, $(C[T,T])^{-1}=L_1U_1$, where $L_1$ and $U_1$ are unipathic lower and upper triangular M--matrices, respectively. By Lemma \ref{schur} applied to $A$, $(C[T,T])^{-1}=A/A[1,1]$. Hence, row reduction results in the following factorization: %\[ %\left. %\left[ %\begin{array}{l} % \underline{\begin{array}{cc} \ \ \ 1 & \ \ 0 \ldots 0\ % \end{array}} % \vspace{12pt} \\ % \begin{array}{cc} \begin{array}{c} % 0\\ \vdots \\ 0 \\ -\frac{a_{j1}}{a_{11}} \\ 0 % \\ \vdots \\ 0 % \end{array} % & \mbox{\Huge $I$}\end{array} %\end{array} %\right] %\hspace{-.8in}\right| \hspace{.8in} % \ \ %\left. %\left[ %\begin{array}{c} % \underline{\begin{array}{ll} a_{11} & \mbox{\ \ \ \large $A[1,T]$} %\ \ \ \end{array}} % \vspace{12pt} \\ % \begin{array}{lc} \begin{array}{c} % 0\\ \vdots \\ 0 \\ a_{j1} \\ 0 \\ \vdots \\ 0 \end{array} % & \mbox{\ \large $A[T,T]$} \end{array} %\end{array} %\right] %\hspace{-1in}\right| \hspace{1in} %= %\left. %\left[ %\begin{array}{c} % \underline{\begin{array}{cc} a_{11} & \mbox{ \ \ \large $A[1,T]$} %\ \ \ \ \end{array}} % \vspace{12pt} \\ % \begin{array}{lc} \begin{array}{c} % 0 \\ \vdots \\ \\ \vdots \\ \\ \vdots \\ 0 \end{array} % \hspace{.2in} & \mbox{\ \ \Huge $B$}\ \ \end{array} %\end{array} %\right] %\hspace{-1.2in}\right| \hspace{1.2in} %\] %\[ %=\left. %\left[ %\begin{array}{l} % \underline{\begin{array}{cc} \ 1 \ \ \ \ & \ \ \ 0 \ldots 0\ \ \ \ % \end{array}} % \vspace{12pt} \\ % \begin{array}{cc} \begin{array}{c} % 0 \\ \vdots \\ \\ \vdots \\ \\ \vdots \\ 0 \end{array} % \hspace{.2in} & \mbox{\ \ \ \ \Huge $L_1$}\ \ \ \ \end{array} %\end{array} %\right] %\hspace{-1in}\right| \hspace{1in}. %\left. %\left[ %\begin{array}{c} % \underline{\begin{array}{cc} a_{11} & \mbox{ \ \ \large $A[1,T]$} %\ \ \ \ \end{array}} % \vspace{12pt} \\ % \begin{array}{cc} \begin{array}{c} % 0 \\ \vdots \\ \\ \vdots \\ \\ \vdots \\ 0 \end{array} % \hspace{.2in} & \mbox{\ \ \ \ \Huge $U_1$}\ \ \ \ \end{array} %\end{array} %\right] %\hspace{-1.2in}\right| \hspace{1.2in}. %\] \addtocounter{cor}{1} \begin{equation} \label{lu1} A= \left. \left[ \begin{array}{l} \underline{\begin{array}{cc}\ 1 & \ \ \ \ \ \ 0 \ldots 0\ \ \ \ \end{array}} \vspace{12pt} \\ \begin{array}{cc} \begin{array}{c} 0\\ \vdots \\ 0 \\ \frac{a_{j1}}{a_{11}} \\ 0 \\ \vdots \\ 0 \end{array} & \mbox{\ \ \ \ \Huge $L_1$}\ \ \ \ \end{array} \end{array} \right] \hspace{-1.15in}\right| \hspace{1.15in} \left. \left[ \begin{array}{c} \underline{\begin{array}{cc} a_{11} & \mbox{ \ \ \large $A[1,T]$} \ \ \ \ \end{array}} \vspace{12pt} \\ \begin{array}{cc} \begin{array}{c} 0 \\ \vdots \\ \\ \vdots \\ \\ \vdots \\ 0 \end{array} \hspace{.2in} & \mbox{\ \ \ \ \Huge $U_1$}\ \ \ \ \end{array} \end{array} \right] \hspace{-1.2in}\right| \hspace{1.2in}, \end{equation} completing the proof of the theorem. {\hfill $\Box$} \bigskip We note that the unipathic digraphs of $L$ and $U$ are necessarily forests. For an M--matrix $A$ whose digraph is a forest we have, indeed, a stronger result. \begin{thm} \label{flu} Let $A\in\RE^{nn}$ with $\D(A)$ a forest. The following are equivalent: \begin{description} \item[(i)] The matrix $A$ is a nonsingular M--matrix. \item[(ii)] There is a permutation matrix $P$ such that $P^{-1}AP=LU$, where $L$ and $U$ are lower and upper triangular nonsingular M--matrices, respectively, with ${\cal D}(L)\cup{\cal D}(U)={\cal D}(P^{-1}AP)$. \end{description} \end{thm} \noindent\underline{Proof}: \medskip\noindent (i) implies (ii): By Theorem \ref{ulu} we need only show that $\D(L)\cup\D(U)=\D(A)$. We proceed as in the proof of Theorem \ref{ulu}. Since the digraph of $A$ is a forest, we can choose the pivots to correspond to pendant vertices in the digraphs of the ureduced part. Then, letting $B=A/A[1,1]$, by Corollary \ref{cors}, $\D (B)=\D (A)^{1}=\D (A)_1$, and hence $\D (B)$ is also a forest. By induction $B=L_1U_1$, where $L_1$ and $U_1$ are unipathic lower and upper triangular M--matrices, respectively, and $\D(L_1)\cup\D(U_1)=\D(B)$. Combining this with equation (\ref{lu1}) we see that $\D(L)\cup\D(U)=\D(A)$. \medskip\noindent (ii) implies (i): Since $L$ and $U$ are M--matrices, we need only show that $A$ is a Z--matrix. Suppose $a_{jk}> 0$ for some $j\neq k$. Then $$01. $$ Since $\Gamma$ is unipathic, no two simple cycles share a common edge so making the above choices will proceed without overlap. If there is an edge from $j$ to $k$, with $j\neq k$, but this edge is not part of any simple cycle, assign any positive value to $c_{jk}$. If $j$ does not have access to $k$ in $\Gamma$, then set $c_{jk}=0$. The remaining entries of $C$ are uniquely determined by Theorem \ref{main}(ii) (d). \medskip We highlight this procedure for the inverse of a tridiagonal M--matrix and of an M--matrix whose digraph is the simple $n$--cycle with loops. \medskip We begin with the inverse of a tridiagonal M--matrix. Properties (ii)(c), (iii)(c), and (iii)(d) of the following theorem also appear in Barrett \cite{B}, who characterizes inverses of tridiagonal matrices in general. \begin{thm} \label{tri} The following are equivalent for $C\in\RE^{nn}$. \begin{description} \item[(i)] $C$ is nonsingular and $C^{-1}$ is a tridiagonal M--matrix. \item[(ii)] $C\geq 0$ and satisfies \begin{description} \item[(a)] $c_{ii}>0,$ for all $i\in\l n \r.$ \item[(b)] $c_{ii}c_{i+1,i+1}-c_{i+1,i}c_{i,i+1}>0,$ for all $i\in\l n-1 \r.$ \item[(c)] $c_{jk}=\frac{c_{ji} c_{ik}}{c_{ii}},$ for all $j>i>k$ and for all $k>i>j.$ \end{description} \item[(iii)] $C\geq 0$ and satisfies \begin{description} \item[(a)] $c_{ii}>0,$ for all $i\in\l n \r.$ \item[(b)] $c_{ii}c_{i+1,i+1}-c_{i+1,i}c_{i,i+1}>0,$ for all $i\in\l n-1 \r.$ \item[(c)] $c_{ij}=\frac{c_{i,i+1} c_{i+1,i+2}\ldots c_{j-1,j}}{c_{i+1,i+1}c_{i+2,i+2}\ldots c_{j-1,j-1}},$ for all $j>i+1.$ \item[(d)] $c_{ij}=\frac{c_{j,j+1} c_{j+1,j+2}\ldots c_{i-1,i}}{c_{j+1,j+1}c_{j+2,j+2}\ldots c_{i-1,i-1}},$ for all $i>j+1.$ \end{description} \item[(iv)] $C$ is a totally nonnegative nonsingular matrix whose inverse in an M--matrix. \item[(v)] There exists a permutation matrix $P$ such that $P^{-1}CP$ has a UL--decomposition, where $U$ and $L$ are upper and lower triangular matrices, respectively, whose entries satisfy the requirements ascribed to the elements of the matrix $C$ in {\rm (ii)}. \end{description} \end{thm} \noindent \underline{Proof}: \medskip\noindent The equivalence of (i) and (ii) follows directly from Theorem \ref{main} applied to the digraph of a tridiagonal matrix. The equivalence of (ii) and (iii) is also straightforward. The equivalence of (i) and (iv) is a result due to Lewin \cite{L}. The equivalence of (i) and (v) follows by applying Theorem \ref{flu} to $A=C^{-1}$, and then by applying the equivalence of (i) and (ii) to the triangular factors. %We next show the %equivalence of (v) and (i). Suppose that (v) holds. Then, due to the %equivalence of (ii) and (i), both $U^{-1}$ and $L^{-1}$ are tridiagonal %(and triangular) M--matrices. Hence each is a %bidiagonal M--matrix of the appropriate type. As $C^{-1}=L^{-1}U^{-1}$, it %now readily follows by checking that $C^{-1}$ is a tridiagonal M--matrix. %Suppose now that (i) holds. Then, by Fiedler and Ptak \cite{FP}, %$C^{-1}$ has an %LU--factorization into upper and lower triangular M--matrices, say $L'$ %and $U'$, respectively. Being the LU--factors of a tridiagonal %matrix, $L'$ and $U'$ are tridiagonal (actually bidiagonal) themselves. %Hence $C=(U')^{-1}(L')^{-1}$, where by virtue of the equivalence of (i) and %(ii), the elements of these factors satisfy the requirements ascribed to %the elements of the matrix $C$ given in (ii). \hfill $\Box$ \medskip Note that if the entries of the first superdiagonal, first subdiagonal and the diagonal of $C=(c_{ij})$ satisfy (ii)(a) and (ii)(b) of Theorem \ref{tri}, then (ii)(c) (or (iii)(c) and (iii)(d)) uniquely determine the remaining entries of $C$. This is illustrated in the following example. \begin{exa} {\em We construct inverses of tridiagonal M--matrices as follows. Begin by filling in the tridiagonal structure of $C=(c_{ij})$ so that (ii)(a) and (ii)(b) of Theorem \ref{tri} are satisfied. For example let } $$C=\left[ \begin{array}{cccccc} 4&2&*&*&*&*\\2&2&2&*&*&*\\ \ast &1&2&6&*&*\\ \ast &*&0&1&1&*\\ \ast &*&*&1&3&4 \\ \ast &*&*&*&2&4\end{array} \right].$$ {\em Then use (ii)(c) (or (iii)(c) and (iii)(d)) to (uniquely) fill in the *'s, one (sub--) superdiagonal at a time:} $$C=\left[ \begin{array}{cccccc} 4&2&2&6&6&8\\2&2&2&6&6&8\\ 1 &1&2&6&6&8\\ 0 &0&0&1&1&4/3\\ 0 &0&0&1&3&4 \\ 0 &0&0&2/3&2&4\end{array} \right].$$ {\em Then } $$C^{-1}=\left[ \begin{array}{rrrrrr}1/2&- 1/2&0&0&0&0 \\ -1/2&3/2&-1&0&0&0\\0&-1/2&1&-3&0&0\\ 0&0&0&3/2&-1/2&0\\0&0&0&- 1/2&7/6&-1\\ 0&0&0&0&-1/2&3/4 \end{array}\right].$$ \end{exa} \medskip Next we consider the case where the digraph is a simple cycle with loops. \begin{thm} \label{cyc} The following are equivalent for $C\in\RE^{nn}$. \begin{description} \item[(i)] The matrix $C$ is nonsingular and $C^{-1}$ is an M--matrix whose digraph is the simple $n$--cycle $1\ed 2\ed\dots \ed n\ed 1$, with loops. \item[(ii)] $C\gg 0$ and satisfies \begin{description} \item[(a)] $\frac{c_{11}c_{22}\ld c_{nn}}{c_{12}c_{23}\ld c_{n-1,n}c_{n1}}>1,$ \item[(b)] $c_{jk}=\frac{c_{ji} c_{ik}}{c_{ii}},$ for all \ $i>j>k$, \ $k>i>j,$ \ and \ $j>k>i.$ %\item[(c)] $c_{jk}=\frac{c_{ji} c_{ik}}{c_{ii}},$ \ %for all $ k>i>j.$ \end{description} %\item[(iii)] $C\gg 0$ and satisfies %\begin{description} %\item[(a)] $\alpha=\frac{c_{11}c_{22}\ld c_{nn}} %{c_{12}c_{23}\ld %c_{n-1,n}c_{n1}}>1,$ %\item[(b)] $c_{ij}=%\frac{c_{jj}c_{j+1,j+1},\ld c_{ii}} %{\alpha (c_{j,j+1}, c_{j+1,j+2}\ld c_{i-1,i})},$ %for all $i>j$, %\item[(c)] $c_{ij}=\frac{c_{i,i+1} c_{i+1,i+2}\ldots %c_{j-%1,j}}{c_{i+1,i+1}c_{i+2,i+2}\ldots %c_{j-1,j-1}},$ for all $j>i+1.$ %\end{description} \end{description} \end{thm} %\noindent \underline{Proof}: %\medskip\noindent %........ %\hfill $\Box$ \begin{exa} {\em We construct an inverse of an M--matrix whose digraph is a simple cycle with loops as follows. Begin by filling in the cycle of ${\cal D}(C)$ so that Theorem \ref{cyc} (ii)(a) is satisfied. For example let } $$C=\left[ \begin{array}{cccccc} 4&2&*&*&*&*\\ \ast&2&2&*&*&*\\ \ast &*&2&6&*&*\\ \ast &*&*&1&1&*\\ \ast &*&*&*&3&4 \\ 1&*&*&*&*&4\end{array} \right].$$ {\em Then use (ii)(b) to (uniquely) fill in the *'s: } $$C=\left[ \begin{array}{cccccc} 4&2&2&6&6&8\\2&2&2&6&6&8\\ 2 &1&2&6&6&8\\ 1/3 &1/6&1/6&1&1&4/3\\ 1 &1/2&1/2&3/2&3&4 \\ 1 &1/2&1/2&3/2&3/2&4\end{array} \right].$$ {\em Then } $$C^{-1}=\left[ \begin{array}{rrrrrr} 1/2&- 1/2&0&0&0&0 \\ 0&1&-1&0&0&0\\0&0&1&-6&0&0\\ 0&0&0&2&-2/3&0\\0&0&0&0&2/3&- 2/3\\ -1/8&0&0&0&0&1/2 \end{array}\right].$$ \end{exa} \medskip Let $Z$ denote the $n\times n$ simple cycle permutation matrix. We can apply Theorem \ref{cyc} to characterize all nonnegative matrices which are polynomials in $Z$ and which are inverses of M--matrices whose digraph is a simple $n$--cycle with loops. \begin{cor} Let $Z$ be the $n\times n$ simple cycle permutation matrix. Let $k_1,\ldots,k_n$ be nonnegative numbers and consider the matrix \begin{displaymath} C \ = \ p(Z) \ = \ k_1I +k_2Z+\ldots k_n Z^{n-1}. \end{displaymath} Then necessary and sufficient conditions for $C$ to be the inverse of an M--matrix whose digraph is a simple cycle with loops are that: \begin{description} \item[(i)] $k_1 \ > \ k_2$. \item[(ii)] $k_j \ = \ \left( k_2 \right)^{j-1}/ \left(k_1\right )^{j-2}$, \ $j=3,\ldots,n$. \end{description} \end{cor} %************************************************************ \bigskip\bigskip\noindent \underline{ACKNOWLEDGEMENT} \bigskip\noindent The authors would like to thank Professor Bjarne Toft for providing us with the simple proof of Lemma \ref{indeg}. %************************************************************** \newpage \begin{thebibliography}{10} \bibitem{B} Wayne W. Barrett. A Theorem on Inverses of Tridiagonal Matrices. {\it Linear Algebra and its Applications,} 27:211-217, 1979. \bibitem{BP} A. Berman and R. Plemmons. {\it Nonnegative Matrices in the Mathematical Sciences}. Academic Press, New York, 1979. \bibitem{BS} Richard A. Brualdi and Hans Schneider. Determinantal Identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley. {\it Linear Algebra and its Applications,} 52/53:769--791, 1983. %\bibitem{FP} M. Fiedler and Ptak. %On matrices with non--positive off--diagonal elements %and positive principal minors. {\it Czechoslovak Math. J.,} %12:382--400, 1962. %\bibitem{GV} Gene H. Golub and Charles F. Van Loan. {\it Matrix %Computations, Second Edition}. The John Hopkins University Press, %Baltimore, 1989. \bibitem{HNC} Frank Harary, Robert Z. Norman, and Dorwin Cartwright. {\it Structural Models}, Wiley, New York, 1965. %\bibitem{HJ2} %Roger A. Horn and Charles R. Johnson. %{\it Topics in Matrix Analysis}, Cambridge U.P. 1991. \bibitem{J} Charles R. Johnson. Inverse M--matrices {\it Linear Algebra and its Applications,} 47:195--216, 1982. \bibitem{L} M. Lewin. \newblock Totally nonnegative, M--, and Jacobi matrices. \newblock {\it SIAM J. Alg. Disc. Meth.}, 1:419--421, 1980. \bibitem{M} John S. Maybee. Some Possible New Directions for Combinatorial Matrix Analysis. {\it Linear Algebra and its Applications,} 107:23--40, 1988. \bibitem{MNST} J.J. McDonald, M. Neumann, H. Schneider, and M.J. Tsatsomeros. Inverse M--matrix Inequalities and Generalized Ultrametrix Matrices. {\it Linear Algebra and its Applications,} to appear. \bibitem{S} Hans Schneider. Theorems on M--splittings of a singular M--matrix which depend on graph structure. {\it Linear Algebra and its Applications,} 58:407--424, 1984. \bibitem{W} Luck J. Watford, Jr. The Schur Complement of Generalized M--matrices. {\it Linear Algebra and its Applications,} 5:247--255, 1972. \bibitem{Wi} R. A. Willoughby. The Inverse M--Matrix Problem. {\it Linear Algebra and its Applications,} 18:75--94, 1977. \end{thebibliography} \end{document} \medskip\noindent First as $A$ and $A+\beta I$ are nonsingular M--matrices with $A\leq A+\beta I$ for all $\beta \geq 0$, and since $(A+\beta I)^{-1}\geq 0$, we have that $A(A+\beta)^{- 1}\leq I$, namely $A(A+\beta I)^{-1}$ is a Z--matrix. Since $A$ is an M--matrix there exists $x\gg 0$ such that $Ax\gg 0$. Then $A(A+\beta I)^{-1}x\gg 0$ and so $A(A+\beta I)^{-1}$ is a nonsingular M--matrix. \medskip\noindent Now let us compute $A(A+\beta I)^{-1}$: \begin{eqnarray*} A \ (A&+&\beta I)^{-1} = (sI-P)[(s+\beta)I-P]^{-1} \\ & = & \frac{1}{s+\beta}(sI-P)\left(I - \frac{P}{s+\beta} \right)^{-1} \\ & = & \frac{1}{s+\beta}(sI-P)\left[ I + \frac{P}{s+\beta} +\frac{P^2}{(s+\beta)^2}+\ldots \right] \\ & = &\frac{s}{s+\beta}I +\frac{1}{s+\beta} \left\{ \left(\frac{s}{s+\beta}-1\right)P +\left[\frac{s}{(s+\beta)^2}-\frac{1}{(s+\beta)}\right] P^2 \right.\\ & & + \left. \left[ \frac{s}{(s+\beta)^3} - \frac{1}{(s+\beta)^2} \right]P^3 + \ldots \right\} \\ & = & \frac{s}{s+\beta}I + \frac{1}{s+\beta}\left(\frac{s}{s+\beta}-1 \right) \left[P + \frac{P^2}{s+\beta} + \frac{P^3}{(s+\beta)^2} + \ldots \right ] \\ & = & \frac{s}{s+\beta}I + \left(1- \frac{s}{s+\beta} \right) \left[ \frac{P}{s+ \beta} +\frac{P^2}{(s+\beta)^2} +\ldots \right] \\ & = & \frac{s}{s+\beta}I - \frac{\beta}{s+\beta} \sum_{j=1}^{\infty} \frac{P^j}{(s+\beta)^j}. \end{eqnarray*} This completes the proof. \hfill $\Box$ \medskip The above result leads us to the following characterization for a nonnegative matrix to be the inverse of an M--matrix.