\documentclass[10pt,twoside,final]{siamltex}
\usepackage{amsfonts,epsfig}

\usepackage[ansinew]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
%\usepackage{amsfonts}
\newtheorem{examp}[theorem]{Example}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}


% Text dimensions
\setlength{\textheight}{190mm} 
\setlength{\textwidth}{130mm}
\topmargin = 20mm

% Box for end of proof outside environment
\def\cvd{~\vbox{\hrule\hbox{%
     \vrule height1.3ex\hskip0.8ex\vrule}\hrule } }

\def\nref#1{{\rm (\ref{#1})}}
\newcommand{\R}{{\mathbb{R}}} 
\newcommand{\Z}{{\mathbb{Z}}} 

% Common extra environments
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{algorithm}[theorem]{Algorithm}
%\newtheorem{example}[theorem]{Example}


% Symbols for real and complex numbers
%\newcommand{\reals}{\mathbb{R}}
%\newcommand{\complex}{\mathbb{C}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\input{elaheader-vol13-13.tex}
\setcounter{page}{162}

\bibliographystyle{plain}

\title{Subdirect sums of nonsingular 
$M$-matrices and of their inverses\thanks{Received by the editors 
16 February 2005. Accepted for
publication 22 June 2005. Handling Editor: Michael Neumann.}}

\author{Rafael Bru\thanks{%
Institut de Matem\`{a}tica Multidisciplinar, 
Universitat Polit\`{e}cnica de Val\`{e}ncia. 
Cam\'{\i} de Vera s/n. 46022 Val\`{e}ncia. Spain (rbru@mat.upv.es, 
pedroche@mat.upv.es). Supported by Spanish DGI and FEDER grant
MTM2004-02998 and by the
Oficina de Ci\'{e}cia i Tecnologia de la Presid\'{e}cia de La Generalitat Valenciana
under project GRUPOS03/062.} 
\and Francisco Pedroche\footnotemark[2] 
\and Daniel B. Szyld\thanks{%
Department of Mathematics, Temple University, Philadelphia, 
PA 19122-6094, U.S.A.  (szyld@math.temple.edu).
Supported in part by the 
U.S.\ National Science Foundation under grant DMS-0207525.} }


\pagestyle{myheadings} \markboth{R. Bru, F. Pedroche, and D.B. Szyld}
{Subdirect Sums of Nonsingular $M$-matrices and of Their Inverses} 
\maketitle

\begin{abstract}
The question of when the subdirect sum of two nonsingular
$M$-matrices is a nonsingular $M$-matrix is studied. 
Sufficient conditions are given.
The case of inverses of $M$-matrices is also studied.
In particular, 
it is shown that the subdirect sum of overlapping principal
submatrices of a nonsingular $M$-matrix is
a nonsingular $M$-matrix.
Some examples illustrating
the conditions presented are also given.
\end{abstract}

\begin{AMS} 15A48.
\end{AMS}

\begin{keywords} Subdirect sum, $M$-matrices, Inverse of $M$-matrix, 
Overlapping blocks.
\end{keywords}

\section{Introduction}
Subdirect sum of matrices are generalizations of the usual
sum of matrices (a $k$-subdirect sum is formally
defined below in Section \ref{ksums_sec}). They were
introduced by Fallat and Johnson in \cite{FaJo}, 
where many of their properties were analyzed.
For example, they showed that the subdirect sum of
positive definite matrices, or of symmetric $M$-matrices,
are positive definite or symmetric $M$-matrices, respectively. 
They also showed that this is not the case for $M$-matrices:
the sum of two $M$-matrices may not be an $M$-matrix.
%Regarding the $k$-subdirect sum, it is known that
%for the case $k=0$ (called {\em direct sum}) the sum of 
%$M$-matrices is again an $M$-matrix and this is also
%the case when $k=1$. Nevertheless, when $k>1$, 
%the $k$-subdirect sum of $M$-matrices may not be an $M$-matrix
%and this is what we are concerned about.
One goal of the present paper is to
give sufficient conditions so that the subdirect sum 
of nonsingular $M$-matrices is a nonsingular \mbox{$M$-matrix.}
%, which was an open question left in \cite{FaJo}. 
We also treat the case of the subdirect sum
of inverses of $M$-matrices.

Subdirect sums of two overlapping principal
submatrices of a nonsingular $M$-matrix 
appear naturally when analyzing additive Schwarz methods for
Markov chains or other matrices \cite{BrPeSzR04}, \cite{FrSz}.
In this paper we show that
the subdirect sum of two overlapping principal
submatrices of a nonsingular $M$-matrix 
is a nonsingular $M$-matrix.


The paper is structured as follows. 
In Section \ref{ksums_sec} we focus on 
the nonsingularity of the subdirect sum
of any pair of nonsingular matrices, giving an explicit expression
for the inverse. 
In Section \ref{M_mat:sec} we  study
the $k$-subdirect sum  of two
nonsingular $M$-matrices and
in particular,  the case of
subdirect sums of overlapping blocks of nonsingular $M$-matrices.
In Section \ref{p:sec} we extend some results 
to the subdirect sum of more than two nonsingular $M$-matrices. 
In Section \ref{inverse:sec} we analyze the subdirect sum of two
inverses.
Finally, 
in Section \ref{P_mat:sec} we mention some open questions on
subdirect sums of $P$-matrices.
Throughout the paper we give 
examples which help illustrate
the theoretical results.



\section{Subdirect sums of nonsingular matrices} \label{ksums_sec}


Let  $A$ and $B$ be two square matrices of
order $n_1$ and $n_2$, respectively, and
let $k$ be an integer such that $1 \leq k \leq \min(n_1,n_2)$. 
%\in \mathbb{R}^{n_1 \times n_1}$ and $B  \in \mathbb{R}^{n_2 \times n_2}$  
Let $A$ and $B$ be partitioned into $2 \times 2$ blocks as follows:
\begin{equation}
A = 
\left [
\begin{array}{c c }
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{array}
\right ], \quad
B =\left [
\begin{array}{c c }
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{array}
\right ],
\label{AiB}
\end{equation}
\noindent where  $A_{22}$ and  $B_{11}$ 
are square matrices of order $k$.
Following \cite{FaJo},
we call the following square matrix of order
$n=n_1+n_2-k$,
\begin{equation}\label{laC}
C = 
\left [
\begin{array}{c c c}
A_{11} & A_{12} & 0 \\
A_{21} & A_{22}+B_{11} & B_{12} \\
     0  & B_{21} & B_{22} 
\end{array}
\right ]
\end{equation}
the $k$-subdirect sum of $A$ and $B$ and denote
it by  $C=A \oplus_{k} B$.


We are interested  in the case when $A$ and $B$ 
are nonsingular matrices.
We partition the inverses of $A$ and $B$ conformably
to \nref{AiB}  and denote its blocks as follows:
\begin{equation}
A^{-1} = 
\left [
\begin{array}{c c }
\hat{A}_{11} & \hat{A}_{12} \\
\hat{A}_{21} & \hat{A}_{22}
\end{array}
\right ], \quad
B^{-1} =\left [
\begin{array}{c c }
\hat{B}_{11} & \hat{B}_{12} \\
\hat{B}_{21} & \hat{B}_{22}
\end{array}
\right ],
\label{AiBinv}
\end{equation}
where, as before, 
$\hat{A}_{22}$ and
$\hat{B}_{11}$
are square of order $k$.  

In the following result we show that nonsingularity of matrix
$\hat{A}_{22} + \hat{B}_{11}$ 
is a necessary and sufficient condition for the $k$-subdirect sum
$C$ to be nonsingular. 
The proof
is based on the use of the relation $n=n_1+n_2-k$ to properly 
partition the indicated matrices.

\begin{theorem}\label{teo:cg}
Let  $A$ and $B$  be nonsingular matrices 
of order $n_1$ and $n_2$, respectively, and
let $k$ be an integer such that $1 \leq k \leq \min(n_1,n_2)$. 
Let  $A$ and $B$ be partitioned as in 
\nref{AiB} and their inverses be partitioned as in
\nref{AiBinv}. Let  $C=A \oplus_{k} B$.
%\nref{laC}. 
Then 
$C$ is nonsingular if and only if $\hat{H}=\hat{A}_{22} + \hat{B}_{11}$
is nonsingular.
\end{theorem}

%\begin{proof}
{\em Proof.} 
Let $I_m$ be the identity matrix of order $m$. The
theorem follows from the following relation:
%
\begin{equation}\label{fac}
\left [
\begin{array}{c c }
A^{-1} & O \\
O & I_{n-n_1}
\end{array}
\right ] C
\left [
\begin{array}{c c }
I_{n-n_2} & O \\
O & B^{-1}
\end{array}
\right ]  =  
\left [
\begin{array}{c c c}
I_{n-n_2} & \hat{A}_{12}  & O  \\
O & \hat{H}   &  \hat{B}_{12} \\
O  &  O    &  I_{n-n_1}
\end{array}
\right ] . ~~ \cvd 
\end{equation}
%\end{proof} 


\subsection{ Nonsingular $M$-matrices} \label{M_mat:sec}

Given 
$A=\{a_{ij} \} \in \R^{m \times n}$,
we write $A > O$ ($A \geq O$), 
%where $O$ denotes the zero matrix, 
to indicate
$a_{ij} > 0$  ($a_{ij} \geq 0$), for $i=1,\ldots,m$, $j=1,\ldots,n$,
and such matrices are called positive (nonnegative). 
Similarly,
$A \geq B$ when $A-B \geq O$.
% We call $Z^{n \times n}$ the set of $n \times n$ matrices
Square matrices
which have nonpositive off-diagonal entries are called
$Z$-matrices.
%, i.e., $Z^{n \times n}$ 
%$= \{ M=(m_{ij}) \in \R^{n \times n} : \ m_{ij} \leq 0, i \neq j\}$.
We call  a $Z$-matrix $M$
%$M \in Z^{n \times n}$ 
a nonsingular $M$-matrix if $M^{-1} \geq O$. 
We recall some properties of these matrices; see \cite{BePl}, \cite{varga}:
\\
(i)  The diagonal of a nonsingular $M$-matrix is positive.
\\
(ii) If $B$ is a $Z$-matrix and $M$ is a nonsingular $M$-matrix,
and $M \leq B$, then $B$ is also a nonsingular $M$-matrix.
In particular, any matrix 
obtained from a nonsingular $M$-matrix 
by setting certain off-diagonal entries
to zero is also a nonsingular $M$-matrix. %varga, pag 91
\\
(iii) A matrix $M$ is a nonsingular $M$-matrix 
if and only if each principal submatrix of $M$ is 
a nonsingular $M$-matrix. 
\\ (iv)
%If $M \in Z^{n \times n}$ then
A $Z$-matrix
$M$ is a 
nonsingular $M$-matrix if and only if 
there exists a positive vector $x > 0$ such that $Mx >0$.

We first consider
the $k$-subdirect sum  of 
nonsingular $Z$-matrices.
% to be a nonsingular $M$-matrix can be given as follows.  
>From \nref{fac}
we can explicitly write
%
\[
C^{-1} = 
\left [
\begin{array}{c c }
I_{n-n_2} & O \\
O & B^{-1}
\end{array}
\right ] 
\left [
\begin{array}{c c c}
I_{n-n_2} & -\hat{A}_{12}\hat{H}^{-1} & \hat{A}_{12}\hat{H}^{-1} \hat{B}_{12} \\
O & \hat{H}^{-1}   &  - \hat{H}^{-1} \hat{B}_{12} \\
O  &  O    &  I_{n-n_1}
\end{array}
\right ]
\left [
\begin{array}{c c }
A^{-1}  & O \\
O & I_{n-n_1}
\end{array}
\right ] 
\]
%
from which we obtain
%
\begin{equation}\label{cinv}
C^{-1} = 
\left [
\begin{array}{c c c}
\hat{A}_{11}- \hat{A}_{12} \hat{H}^{-1} \hat{A}_{21} & \hat{A}_{12}-\hat{A}_{12}\hat{H}^{-1}\hat{A}_{22} & \hat{A}_{12}\hat{H}^{-1} \hat{B}_{12} \\
\hat{B}_{11} \hat{H}^{-1}\hat{A}_{21}  & \hat{B}_{11} \hat{H}^{-1} \hat{A}_{22}  &  - \hat{B}_{11} \hat{H}^{-1} \hat{B}_{12} + \hat{B}_{12} \\
\hat{B}_{21}\hat{H}^{-1}\hat{A}_{21}  & \hat{B}_{21}\hat{H}^{-1}\hat{A}_{22}     &  - \hat{B}_{21} \hat{H}^{-1} \hat{B}_{12} + \hat{B}_{22}
\end{array}
\right ]
\end{equation}
%\noindent
and therefore we can state the following immediate result.

\begin{theorem}\label{coro:cg}
\noindent
Let  $A$ and $B$  be nonsingular $Z$-matrices 
of order $n_1$ and $n_2$, respectively, and
let $k$ be an integer such that $1 \leq k \leq \min(n_1,n_2)$.
Let  $A$ and $B$ be partitioned as in
\nref{AiB} and their inverses be partitioned as in
\nref{AiBinv}. Let  $C=A \oplus_{k} B$.
% given by \nref{laC} and 
Let $\hat{H}=\hat{A}_{22} + \hat{B}_{11}$ be nonsingular. 
Then $C$ is a nonsingular $M$-matrix if and only if 
each of the nine blocks of $C^{-1}$ in \nref{cinv} is nonnegative.
\end{theorem}

%\begin{proof} Follows from  \nref{cinv} and the discussion above on
%the definition of nonsingular $M$-matrix. 
%\end{proof}

We  consider now the case where $A$ and $B$ are nonsingular $M$-matrices. 
%We can give a more practical 
It was shown in \cite{FaJo} that even if
$H=A_{22} + B_{11}$ is a nonsingular $M$-matrix,
this does not guarantee that
$C=A \oplus_{k} B$ is a nonsingular $M$-matrix.  
We point out that this matrix $H$ is not the matrix
$\hat{H}$ obtained from $A^{-1}$ and $B^{-1}$ and
used in Theorem \ref{teo:cg}. 
The fact that $H$ is a nonsingular $M$-matrix is a 
necessary but not a sufficient condition for $C$ to be a nonsingular
$M$-matrix. Sufficient conditions are presented in the following result.


%\pagebreak

\begin{theorem}\label{teo:nonov}
Let $A$ and $B$ be nonsingular $M$-matrices 
partitioned as in \nref{AiB}. Let 
$x_1 > 0 \in \R^{(n_1-k) \times 1}$,
$y_1 > 0  \in \R^{k \times 1}$, $x_2 >0 \in \R^{k \times 1}$ and
$y_2 > 0 \in \R^{(n_2-k) \times 1}$ be such that
%
\begin{equation}\label{deteo}
A \left [
\begin{array}{c}
x_1 \\
y_1 \\
\end{array}
\right ] > 0,  \quad
B \left [
\begin{array}{c}
x_2 \\
y_2 \\
\end{array}
\right ] > 0.
\end{equation}
%
Let $H=A_{22} + B_{11}$ be a nonsingular $M$-matrix and let 
%
\begin{equation}\label{lay}
y = H^{-1} \left ( A_{22} y_1 + B_{11} x_2 \right ). 
\end{equation}
%
Then if $y \leq y_1$ and $y \leq x_2$ 
the $k$-subdirect sum 
$C=A \oplus_{k} B$ is a nonsingular $M$-matrix.
\end{theorem}


\begin{proof}
We will show that there exists $u > 0$ such that $Cu>0$.
We first note that from \nref{deteo} we get
%
\begin{equation}\label{leseq}
\left. 
\begin{array}{c c c}
A_{11} x_1 +A_{12} y_1 & >  & 0  \\
A_{21} x_1 + A_{22} y_1  & > & 0  \\
\end{array}
\right \}, \quad 
\left. 
\begin{array}{c c c}
B_{11} x_2 + B_{12} y_2 &  >  & 0  \\
B_{21} x_2 + B_{22} y_2 &  > & 0  \\
\end{array}
\right \}.
\end{equation}
%
Taking $u = \left[\begin{array}{c}x_1\\ y\\ y_2 \end{array} \right] $ 
and partitioning 
$C$ as in \nref{laC} we obtain
%
\vspace*{-5mm}
%
\begin{equation}\label{leseq2}
C u = 
\left [ 
\begin{array}{c}
A_{11} x_1 +A_{12} y    \\
A_{21} x_1 + (A_{22} + B_{11}) y + B_{12} y_2  \\
B_{21} y + B_{22} y_2 
\end{array}
\right ] .
\end{equation}
%
Since $A_{21} \leq O$ and $B_{12} \leq O$, 
from \nref{leseq} it follows that $A_{22}y_1 >0$ and $B_{11}x_2 >0$.
Since $H^{-1} \geq O$, from  \nref{lay}
we have that $y$ is positive,
and consequently, so is $u$, i.e., $u>0$. 
%Therefore we also have $u>0$. 
We will show that $Cu >0$ one block of rows in \nref{leseq2} at a time.
If $y \leq y_1$, as $A_{12} \leq 0$, we have that
$A_{12} y \geq  A_{12} y_1$
and again using \nref{leseq} we obtain that the first block of rows of $Cu$
is positive.
In a similar way, the condition  $y \leq x_2$  together
with the last equation of \nref{leseq} allows to conclude
that the third block of rows of $Cu$ is positive. Finally,
substituting $y$ given by \nref{lay} in the second row of $Cu$
and considering \nref{leseq} we conclude that the second block of rows
of $Cu$ is also positive.
\end{proof}

Note that $A$ and $B$ are nonsingular $M$-matrices 
and therefore the positive 
vectors $(x_1,y_1)$ and $(x_2,y_2)$ 
of \nref{deteo}
always exist.
This theorem gives sufficient but not
necessary conditions for $C=A \oplus_{k} B$ to
be a nonsingular $M$-matrix, as illustrated in Example \ref{exf3}
further below.

%cercant2.m
\begin{examp}{\rm 
The matrices 
%
\[
A=
\left[ 
\begin{array}{c| c c}
    3&   -2&   -1\\
\hline
 -1/2&    2&   -3\\
   -1&   -1&    4\\
\end{array}
\right] \mbox{\rm ~~ and ~~}
B=
\left[ 
\begin{array}{c c| c}
    1&   -2& -1/3\\
   -3&    9&    0\\
\hline
   -2& -1/2&    6\\
\end{array}
\right], 
\]
%\noindent
and the vectors
%
\[
\left [
\begin{array}{c}
x_1 \\
\hline
y_1 \\
\end{array}
\right ]  = 
\left [
\begin{array}{c}
1.8 \\
\hline
2 \\
1 \\
\end{array}
\right ] \mbox{\rm ~~ and ~~}
\left [
\begin{array}{c}
x_2 \\
\hline
y_2 \\
\end{array}
\right ]  = 
\left [
\begin{array}{c}
2.5 \\
1 \\
\hline
1 \\
\end{array}
\right ] 
\]
%\noindent
satisfy the inequalities \nref{deteo}, and computing the vector $y$ from
\nref{lay} we get  $y \approx (1.95, 0.87)^{T}$,
which satisfy $y \leq y_1$ and $y \leq x_2$.
Therefore the $2$-subdirect sum
%
\[
C=\left[ 
\begin{array}{c |c c |c}
    3&   -2&   -1&    0\\
\hline
 -1/2&    3&   -5& -1/3\\
   -1&   -4&   13&    0\\
\hline
    0&   -2& -1/2&    6\\
\end{array}
\right]
\]
%\noindent
is a nonsingular $M$-matrix in accordance with Theorem \ref{teo:nonov}.
}
\end{examp}


%fallat3.m
\begin{examp}\label{exf3}{\rm 
The matrices 
%
\[
A=
\left[ 
\begin{array}{c| c c}
    5&   -1/2&   -1/3\\
\hline
 -1&    4&   -2\\
   -1&   -6&    10\\
\end{array}
\right] \mbox{\rm ~~ and ~~} 
B=
\left[ 
\begin{array}{c c| c}
    1&   -2& -1/3\\
   -3&    9&    0\\
\hline
   -2& -1/2&    6\\
\end{array}
\right]
\]
%\noindent
and the vectors 
%
\[
\left [
\begin{array}{c}
x_1 \\
\hline
y_1 \\
\end{array}
\right ]  = 
\left [
\begin{array}{c}
1 \\
\hline
1 \\
1 \\
\end{array}
\right ] \mbox{\rm ~~ and ~~} 
\left [
\begin{array}{c}
x_2 \\
\hline
y_2 \\
\end{array}
\right ]  = 
\left [
\begin{array}{c}
2.5 \\
1 \\
\hline
1 \\
\end{array}
\right ] 
\]
%\noindent
satisfy the inequalities \nref{deteo}, but computing vector $y$ from
\nref{lay} we obtain
%\linebreak

$y \approx (1.18, 0.85)^{T}$,
which does not satisfy the conditions of Theorem~\ref{teo:nonov}. 
Nevertheless the $2$-subdirect sum 
%
\[
C= A \oplus_2 B =
\left[ 
\begin{array}{c| c c| c}
    5&   -1/2&   -1/3 & 0\\
\hline
 -1&    5&   -4 & -1/3\\
   -1&   -9&    19 & 0\\
\hline
0 &   -2& -1/2&    6\\
\end{array}
\right]
\]
%\noindent
is a nonsingular $M$-matrix.
}
\end{examp}

In the special case of $A$ and $B$ block lower and upper
triangular nonsingular $M$-matrices, respectively, the results of
Theorems~\ref{coro:cg} and \ref{teo:nonov} are easy to establish.
%More specifically, 
Let
%
\begin{equation}
A = 
\left [
\begin{array}{c c }
A_{11} & 0 \\
A_{21} & A_{22}
\end{array}
\right ], \quad
B =\left [
\begin{array}{c c }
B_{11} & B_{12} \\
0 & B_{22}
\end{array}
\right ] ,
\label{AiBtr}
\end{equation}
%\noindent
with $A_{22}$ and $B_{11}$ square matrices
of order $k$.

\begin{theorem}\label{teo:ciginv} 
Let $A$ and $B$ be nonsingular lower and upper block triangular 
nonsingular $M$-matrices, respectively, 
partitioned as in \nref{AiBtr}.
Then $C=A \oplus_{k} B$ is a nonsingular $M$-matrix.
\end{theorem}

\begin{proof}
We can repeat the same argument as
in the proof of Theorem~\ref{teo:nonov} with the advantage of having
$A_{12}=O$ and $B_{21}=O$. 
Note that
conditions $y \leq y_1$ and $y \leq x_2$ are not necessary here
because the first and last block of rows of 
$Cu$ in \nref{leseq2} are automatically positive in this case. 
\end{proof}

\begin{remark}{\rm 
The expression 
of $C^{-1}$ is given by \nref{cinv}. In this 
particular case of block triangular matrices
we have $\hat{A}_{12}=O$, 
$\hat{B}_{21}=O$, $\hat{A}_{22}=A_{22}^{-1}$, 
$\hat{B}_{11}=B_{11}^{-1}$, from which 
$\hat{H}=A_{22}^{-1}+B_{11}^{-1}$.
If, in addition, $A_{22}=B_{11}$, then
we obtain 
%
\[ % \begin{align}
C^{-1} = 
 \left [
\begin{array}{c c c}
A_{11}^{-1}  &  O   & O  \\
- \frac{1}{2} A_{22}^{-1} A_{21} A_{11}^{-1}  & \frac{1}{2} A_{22}^{-1}  
      &   -\frac{1}{2} A_{22}^{-1} B_{12} B_{22}^{-1} \\
O  & O    &  B_{22}^{-1}
\end{array}
\right ]   \geq O  . 
\] % \end{align}
}
\end{remark}

%nfallat2.m
\begin{examp}\label{ex:nf2}{\rm 
The matrices  
%
\[
A=
\left[ 
\begin{array}{c| c c}
     3    & 0  &   0 \\
\hline
    -1  &    5  &  -1 \\
    -1  &  -9  &   5 \\
\end{array}
\right] \mbox{\rm ~~ and ~~}  
B=
\left[ 
\begin{array}{c c| c}
     6   & -2   & -1\\
    -4   &  3   & -3 \\
\hline
     0   &  0    & 2\\
\end{array}
\right]
\]
%\noindent
satisfy the hypotheses of Theorem~\ref{teo:ciginv}.
The matrices $C=A \oplus_{2} B$ and $C^{-1}$ are 
% 
\[
C=
\left[ 
\begin{array}{c | c c| c}
     3   &  0 &    0  &   0\\
\hline
    -1  &  11  &  -3  &  -1\\
    -1  & -13  &  8  &  -3\\
\hline
     0  &   0   &  0  &   2\\
\end{array}
\right],  \quad
C^{-1} =
\left[ 
\begin{array}{c | c c| c}
   1/3&    0&    0&    0\\
\hline
 11/147&   8/49&   3/49&  17/98\\
   8/49&  13/49&  11/49&  23/49\\
\hline
    0&    0&    0&  1/2\\
\end{array}
\right]
\]
%\noindent
and therefore $C$ is a nonsingular $M$-matrix as expected.
}
\end{examp}

In some applications, 
such as in domain decomposition \cite{smith-book}, \cite{toselli-widlund},
matrices $A$ and $B$ partitioned as in \nref{AiB}
arise with a  common block,
i.e., 
$A_{22} = B_{11}$. In the next example we 
show
that even if $A$ and $B$ are nonsingular $M$-matrices,
and so is the common block,
we can not ensure that $C= A \oplus_k B$ is
a nonsingular $M$-matrix.

%trobat3.m
\begin{examp}\label{ex:trob3}{\rm 
The matrices
%
\[
A =\left [
\begin{array}{c|c c}
370& -342& -318 \\
\hline
 -448&  737& -107\\
  -46& -190&  444\\
\end{array}
\right ], \quad
B =\left [
\begin{array}{c c| c}
  737& -107& -134\\
 -190&  444& -440\\
\hline
 -885& -182&  603\\
\end{array}
\right ]
\]
% \noindent
are nonsingular $M$-matrices with
$A_{22}=B_{11}$ an $M$-matrix, but  $C =A \oplus_{2} B$ is not
an $M$-matrix, since we have
% 
\[
C =
\left [
\begin{array}{c |c c| c}
  370& -342& -318&    0\\
\hline
 -448& 1474& -214& -134\\
  -46& -380&  888& -440\\
\hline
    0& -885& -182&  603\\
\end{array}
\right ]
\]
%
\[
\mbox{\rm ~~ and ~~ ~}
C^{-1} \approx
\left [
\begin{array}{c |c c| c}
   -0.0291  &  -0.0242 &  -0.0204 &  -0.0203\\
\hline
   -0.0145  & -0.0109  & -0.0098  & -0.0096\\
   -0.0214  & -0.0163  & -0.0132  & -0.0133\\
\hline
   -0.0277  & -0.0210  & -0.0183  & -0.0164\\
\end{array}
\right ].
\] 
}
\end{examp}

In the next section we shall see that
when $A$ and $B$ share a block and 
they are submatrices of a given 
nonsingular $M$-matrix, the resulting $k$-subdirect sum is in fact
a nonsingular $M$-matrix.

\subsection{Overlapping $M$-matrices} \label{overlap:sec}

In this section we restrict
%$A \in \mathbb{R}^{n_1 \times n_1}$ and $B  \in \mathbb{R}^{n_2 \times n_2}$ 
$A$ and $B$
to be principal submatrices of a given nonsingular $M$-matrix
and such that they have a common block. 
%
Let
\begin{equation}\label{laM}
M = 
\left [
\begin{array}{c c c}
M_{11} & M_{12} & M_{13}\\
M_{21} & M_{22} & M_{23} \\
M_{31} & M_{32} & M_{33} 
\end{array}
\right ]
\end{equation}
be a nonsingular $M$-matrix
with $M_{22}$ square matrix of order $k \geq 1$ and  let
\begin{equation}
A = 
\left [
\begin{array}{c c }
M_{11} & M_{12} \\
M_{21} & M_{22}
\end{array}
\right ] {\rm ~~ and ~~ }
B =\left [
\begin{array}{c c }
M_{22} & M_{23} \\
M_{32} & M_{33}
\end{array}
\right ]
\label{AiBdeM}
\end{equation}
%  \noindent
%
be of order $n_1$ and $n_2$, respectively.
%  \noindent
%Therefore
The
$k$-subdirect sum of $A$ and $B$ is thus given by
% 
\begin{equation}\label{Cdelt}
C = A \oplus_{k} B =
\left [
\begin{array}{c c c}
M_{11} & M_{12} & O \\
M_{21} & 2M_{22} & M_{23} \\
O & M_{32} & M_{33} 
\end{array}
\right ].
\end{equation} 

In the following theorem we show that $C$ is
a nonsingular $M$-matrix.
%We recall that if $M \leq B$ with $B$ a $Z$-matrix,
%and $M$ is a  nonsingular $M$-matrix then
%$B$ is a nonsingular $M$-matrix as well (see, for example, \cite{Sch}).

\begin{theorem}\label{teo:gene}
Let $M$ be a nonsingular $M$-matrix partitioned as in \nref{laM},  and
let $A$ and $B$ be two overlapping principal submatrices given
by \nref{AiBdeM}.
Then the $k$-subdirect sum 
$C=A \oplus_{k} B$ is a nonsingular $M$-matrix.
\end{theorem}

\begin{proof}
Let us construct an $n \times n$ $Z$-matrix $T$
as follows:
%
\begin{equation}\label{laX}
T = 
\left [
\begin{array}{c c c}
M_{11} & 2M_{12} & M_{13} \\
M_{21} & 2M_{22} & M_{23} \\
M_{31} & 2M_{32} & M_{33} 
\end{array}
\right ] .
\end{equation}
%
Then $T=M \diag(I,2I,I)$ and we get
$T^{-1} = \diag(I,(1/2)I,I) M^{-1} \geq O$. 
Then $T$ is a nonsingular $M$-matrix.
Finally since $C$ is a $Z$-matrix and $C \geq T$ 
we conclude that $C$ is a nonsingular $M$-matrix.
\end{proof}

%suma6v3 usant la matriu Q_total per definir A
\begin{examp}\label{exteoge}{\rm 
The following nonsingular $M$-matrix is partitioned as in
\nref{laM}: 
%
\begin{equation}
M =\left [
\begin{array}{c c |c c  c| c}
  13/14&   -4/23&   -3/20&   -1/42& -19/186&   -3/46\\
    -3/7&   21/23&    -1/5&   -1/21&   -1/93&   -6/23\\
\hline
    -1/7&   -7/46&   17/20&   -1/14&  -1/186&   -2/23\\
   -4/21&  -27/92&   -1/15&     4/7&  -58/93&  -27/92\\
   -1/14&   -9/46&   -3/10&    -1/7&   53/62&   -9/46\\
\hline
   -2/21&   -9/92&   -2/15&    -2/7&   -7/62&   83/92\\
\end{array}
\right ].
\end{equation}
%
Taking overlapping submatrices $A$ and $B$ as in \nref{AiBdeM}
the 
$3$-subdirect sum $C=A \oplus_{3} B$ is
given by
%
\[
C =\left [
\begin{array}{c c |c c  c| c}
   13/14&   -4/23&   -3/20&   -1/42& -19/186&       0\\
    -3/7&   21/23&    -1/5&   -1/21&   -1/93&       0\\
\hline
    -1/7&   -7/46&   17/10&    -1/7&   -1/93&   -2/23\\
   -4/21&  -27/92&   -2/15&     8/7& -116/93&  -27/92\\
   -1/14&   -9/46&    -3/5&    -2/7&   53/31&   -9/46\\
\hline
       0&       0&   -2/15&    -2/7&   -7/62&   83/92\\
\end{array}
\right ]
\]
%   \noindent
and it is a nonsingular $M$-matrix according to 
Theorem~\ref{teo:gene}. In fact, we have that
\[
C^{-1} \approx \left [
\begin{array}{c c |c c  c| c}
    1.3500   & 0.3977 &   0.2624 &   0.1609  &  0.2103 &   0.1232 \\
    0.7628   & 1.4108 &   0.3383 &   0.2085  &  0.2185 &   0.1478 \\
\hline
    0.3007   & 0.2845 &   0.7422 &   0.2006  &  0.1824 &   0.1763 \\
    1.1024   & 1.1571 &   0.8927 &   1.6092  &  1.3118 &   0.8940 \\
    0.4854   & 0.5256 &   0.5116 &   0.4379  &  0.9664 &   0.4013 \\
\hline
    0.4543   & 0.4743 &   0.4564 &   0.5941  &  0.5634 &   1.4679 \\
\end{array}
\right ].
\]
%
}
\end{examp}

\subsection{$k$-subdirect sum of $p$ $M$-matrices} \label{p:sec}

In this section we extend Theorems~\ref{teo:nonov} and 
\ref{teo:gene}
to the subdirect sum of several nonsingular $M$-matrices. 
Example~\ref{exul} later in the section illustrates the notation
used in the proofs.

\begin{theorem}\label{teo:pM}
Let $A_i \in \R^{n_i \times n_i}$, $i=1,\ldots p$,
be nonsingular $M$-matrices partitioned as
%
\begin{equation}\label{lesai}
A_i = 
\left [
\begin{array}{c c }
A_{i,11} & A_{i,12} \\
A_{i,21} & A_{i,22}
\end{array}
\right ]
\end{equation}
% \noindent
with $A_{i,11}$ a square matrix of order $k_{i-1} \geq 1$
and $A_{i,22}$  a square matrix of order $k_{i} \geq 1$, i.e.,
$n_i=k_{i-1}+k_i$.  Since $A_i$ are nonsingular $M$-matrices
we have that there exist
$x_{i} > 0 \in \R^{(n_i-k_i) \times 1}$ and 
$y_{i} > 0  \in \R^{k_i \times 1}$ such that
%
\begin{equation}
A_i \left [
\begin{array}{c}
x_{i} \\
y_{i} \\
\end{array}
\right ] > 0, \quad i=1,\ldots, p.
\end{equation}
% 
Let $C_0=A_1$ and 
define the following $p-1$ $k_i$-subdirect sums:
%
\begin{equation}\label{ci}
C_i= C_{i-1} \oplus_{k_i} A_{i+1}, \quad i=1, \ldots, p-1,
\end{equation}
i.e.,
% Explicitly 
\[
\begin{array}{c c l}
C_1 & = & A_1 \oplus_{k_1} A_2, \\
C_2  & =  &(A_1 \oplus_{k_1} A_2) \oplus_{k_2} A_3 = C_1 \oplus_{k_2} A_{3}, \\
     &   \vdots  & \\
C_{p-1} & = & \left(A_1 \oplus_{k_1} A_2 \oplus_{k_2} \cdots  
\oplus_{k_{p-2}} A_{p-1} \right) \oplus_{k_{p-1}} A_{p} = C_{p-2}   
\oplus_{k_p-1} A_{p}. \\
\end{array}
\] 
Each subdirect sum $C_i$ is of order 
$m_i$, such that $m_0=n_1$ and
%
\[
m_i = m_{i-1} + n_{i+1} - k_i = m_{i-1} + k_{i+1},  \quad i=1,\ldots,p-1 .
\]
% 
Let us partition $C_i$ in the form
%
\begin{equation}\label{lesci}
C_i = 
\left [
\begin{array}{c c }
C_{i,11} & C_{i,12} \\
C_{i,21} & C_{i,22}
\end{array}
\right ],  \quad i=1,\ldots,p-1,
\end{equation}
% \noindent
with 
$C_{i,22}$  a square matrix of order $k_{i+1}$.
%and obviously 
%$C_{i,11}$ a square matrix of order $m_i-k_{i+1}$
%
Let 
%
\[
H_i = C_{i-1,22} + A_{i+1,11}, \quad i=1, \ldots p-1,
\]
% \noindent
be nonsingular $M$-matrices and let 
%
\[
z_i = H_i^{-1} (C_{i-1,22} y_{i} + A_{i+1,11} x_{i+1}),  \quad i=1, \ldots p-1.
\]
% 
Then, if $z_i \leq y_i$ and $z_i \leq x_{i+1}$, the 
subdirect sums $C_i$ given by 
\nref{ci} are nonsingular $M$-matrices for $i=1,\ldots,p-1$.
%
\end{theorem}

\begin{proof}
It is easy to see that applying Theorem \ref{teo:nonov} to 
each consecutive pair of matrices $C_i$ we have that
$C_1$, $C_2$, \ldots, $C_{p-1}$ are nonsingular $M$-matrices.
This can be shown by induction.
\end{proof}

We now  extend Theorem~\ref{teo:gene} to the 
sub-direct sum of $p$ submatrices of a given nonsingular $M$-matrix 
$M$. To that end, we first define 
$M(S)$ a principal submatrix of $M$ with rows and columns
with indices in the set of indices $S=\{ i,i+1,i+2, \ldots, j \}$. 
In \cite{BrPeSzR04} we call these
{\em consecutive principal submatrices}.
For example, matrices
$A$ and $B$ given by \nref{AiBdeM} can be expressed as a submatrices
of $M$ given by \nref{laM} as
$A=M(S_1)$, $B=M(S_2)$ with $S_1=\{1,2\}$ and 
$S_2=\{2,3\}$.


\begin{theorem}\label{teo:gen2}
Let $M$ be a nonsingular $M$-matrix. 
Let $A_i=M(S_i)$, $i=1, \ldots, p$, be principal consecutive submatrices
of $M$ and consider the $p-1$  $k_i$-subdirect
sums given by 
%
\begin{equation}\label{cibis}
C_i= C_{i-1} \oplus_{k_i} A_{i+1}, \quad i=1, \ldots, p-1,
\end{equation}
% \noindent
in which $C_0=A_1$.
%are properly defined. 
Then each of the $k_i$-subdirect
sums $C_i$ is a nonsingular $M$-matrix. 
\end{theorem}


\begin{proof}
It is easy to relate the structure of each $C_i$ to that
of the submatrices $A_i$ involved. We consider 
that $A_i$ are overlapping principal submatrices of the 
form \nref{AiBdeM} but allowing that each
$A_i$ has different number of blocks.
Let $M$ be partitioned as
%
\begin{equation}\label{laM5}
M = 
\left [
\begin{array}{c c c c c}
M_{11} & M_{12} & M_{13}  & \cdots & M_{1n}  \\
M_{21} & M_{22} & M_{23}  & \cdots & M_{2n}  \\
M_{31} & M_{32} & M_{33}  & \cdots & M_{3n}  \\
\vdots &\vdots  &\vdots   & \ddots & \vdots  \\
M_{n1} & M_{n2} & M_{n3} & \cdots & M_{nn}  \\
\end{array}
\right ]
\end{equation}
% \noindent 
according with the size of the principal
submatrices $A_i$.
Each block  $M_{ij}$ may be a submatrix of more than one $A_{m}$,
$m =1, \ldots, p$. Let $b^{(l)}_{ij} \geq 0$ be the number of matrices
$A_{m}$ such that $M_{ij}$ is a submatrix of $A_{m}$,
for $m =1, \ldots, l+1$. Of course we can have $b^{(l)}_{ij}=0$.
Let us consider the $l$th subdirect sum
$C_{l}$, $1 \leq l \leq p-1$, which is of the form 
%
\begin{equation}\label{laC5}
C_{l}= 
\left [
\begin{array}{c c c c c}
b^{(l)}_{11} M_{11} & b^{(l)}_{12} M_{12} &  b^{(l)}_{13} M_{13} & \cdots & b^{(l)}_{1l} M_{1l}\\
b^{(l)}_{21} M_{21} & b^{(l)}_{22} M_{22} & b^{(l)}_{23} M_{23}   &  \cdots & b^{(l)}_{2l} M_{2l}\\
b^{(l)}_{31}M_{31} & b^{(l)}_{32}M_{32} & b^{(l)}_{33} M_{33} &    \cdots & b^{(l)}_{3l} M_{3l}\\
\vdots &\vdots  &\vdots  & \ddots & \vdots  \\
b^{(l)}_{l1}M_{l1} & b^{(l)}_{l2}M_{l2} & b^{(l)}_{l3}M_{l3}  & \cdots & b^{(l)}_{ll}M_{ll}  \\
\end{array}\right ].
\end{equation}
% \noindent
% in which $b^{(l)}_{ij} \geq 0$ denotes the number of 
% submatrices $A_i$ in which the block 
% $M_{ij}$ is within.
% Therefore $b^{(l)}_{ij}=0$ if and only if $M_{ij}$ does not belong to any
% $A_i$, $i=1, \ldots, l+1$. 
Observe 
that $C_l$ is a $Z$-matrix and that $b^{(l)}_{ii} > 0$. 
%as the $C_i$ are properly defined
%(i.e., they match the definition of $k$-subdirect sum
%given by \nref{AiB} and  \nref{laC}).
Furthermore, for each column it holds that
$b^{(l)}_{ii} \geq b^{(l)}_{ji}, j=1, \ldots, l$.

The proof proceeds in a manner
similar to that of Theorem~\ref{teo:gene}.
%We have that $C_{l}$ is a $Z$-matrix. 
Consider the $Z$-matrix (partitioned in the same manner as $M$) 
%
\[
T_l = M_l 
\diag (b^{(l)}_{11} I, b^{(l)}_{22} I, b^{(l)}_{33} I, \ldots, b^{(l)}_{ll}I),
\]
% \noindent
where $M_l$ is the principal submatrix of \nref{laM5}
with  row and column blocks from $1$~to~$l$.
It follows that
$T_l^{-1} \geq O$
and therefore $T_l$ is a nonsingular $M$-matrix.
Finally, 
since $C_{l} \geq  T_l$, we conclude that $C_{l}$ is a
nonsingular $M$-matrix, $l=1,\ldots,p$.  
\end{proof}

%exultim.m
\begin{examp}\label{exul}{\rm 
Given the nonsingular 
$M$-matrix $M$ of Example \ref{exteoge}, let us 
consider the following overlapping blocks
%
\[
A_1= M(\{1,2,3\}) =
\left [
\begin{array}{c c c}
 13/14& -4/23& -3/20\\
  -3/7& 21/23&  -1/5\\
  -1/7& -7/46& 17/20\\
\end{array}
\right ],
\]
%
\[
A_2= M(\{2,3,4,5\}) =
\left [
\begin{array}{c c c c}
 21/23&   -1/5&  -1/21&  -1/93\\
  -7/46&  17/20&  -1/14& -1/186\\
 -27/92&  -1/15&    4/7& -58/93\\
  -9/46&  -3/10&   -1/7&  53/62\\
\end{array}
\right ],
\]
%
\[
A_3= M(\{3,4,5,6\}) =
\left [
\begin{array}{c c c c}
  17/20&  -1/14& -1/186&  -2/23\\
  -1/15&    4/7& -58/93& -27/92\\
  -3/10&   -1/7&  53/62&  -9/46\\
  -2/15&   -2/7&  -7/62&  83/92\\
\end{array}
\right ].
\]
% 
Then we have the $2$-subdirect sum
%
\[
C_1 = A_1 \oplus_{2} A_2 = 
\left [
\begin{array}{c c c c c}
  13/14&  -4/23&  -3/20&      0&      0\\
   -3/7&  42/23&   -2/5&  -1/21&  -1/93\\
   -1/7&  -7/23&  17/10&  -1/14& -1/186\\
      0& -27/92&  -1/15&    4/7& -58/93\\
      0&  -9/46&  -3/10&   -1/7&  53/62\\
\end{array}
\right ],
\]
% \noindent
which is a nonsingular $M$-matrix, and 
the $3$-subdirect sum
%
\[
C_2 = C_1 \oplus_{3} A_3 = 
\left [
\begin{array}{c c c c c c}
   13/14&   -4/23&   -3/20&       0&       0&       0\\
    -3/7&   42/23&    -2/5&   -1/21&   -1/93&       0\\
    -1/7&   -7/23&   51/20&    -1/7&   -1/93&   -2/23\\
       0&  -27/92&   -2/15&     8/7& -116/93&  -27/92\\
       0&   -9/46&    -3/5&    -2/7&   53/31&   -9/46\\
       0&       0&   -2/15&    -2/7&   -7/62&   83/92\\

\end{array}
\right ],
\]
% \noindent 
which is also a nonsingular $M$-matrix in accordance with Theorem
\ref{teo:gen2}. Observe that in this example we have 
$k_1=2$ and $k_2=3$. Note also that, for example, we have
$b^{(1)}_{22} =2$, $b^{(1)}_{33} = 2$, $b^{(1)}_{14}=0$, $b^{(2)}_{22} =2$, $b^{(3)}_{22} =2$,
$b^{(2)}_{33} = 3$, $b^{(2)}_{14}=0$. %, with the notation
%of the proof of Theorem \ref{teo:gen2}.
%
}
\end{examp} 

\section{Subdirect sums of inverses} \label{inverse:sec}
Let $A$ and $B$ be nonsingular matrices 
partitioned as in \nref{AiB}. 
In this section we consider
the $k$-subdirect sum of their inverses. 
We will establish counterparts to some of results in the previous sections.
%the $k$-subdirect sum of $A^{-1}$ and $B^{-1}$.
Let us denote by
$G= A^{-1} \oplus_{k} B^{-1}$, with $A^{-1}$ and 
$B^{-1}$ partitioned as in \nref{AiBinv}, i.e.,
%
\begin{equation}\label{laG}
G =  
\left [
\begin{array}{c c c}
\hat{A}_{11} & \hat{A}_{12} & 0 \\
\hat{A}_{21} & \hat{A}_{22}+\hat{B}_{11} & \hat{B}_{12} \\
     0  & \hat{B}_{21} & \hat{B}_{22} 
\end{array}
\right ].
\end{equation}

As a corollary to, and in analogy to Theorem~\ref{teo:cg},
the next statement indicates that the nonsingularity 
of $A_{22} + B_{11}$ is a necessary condition to obtain $G$ nonsingular. 

\begin{theorem}\label{teo:cg2}
\noindent
Let  $A$ and $B$  be nonsingular matrices 
partitioned as in \nref{AiB} and let their inverses be partitioned as in
\nref{AiBinv}. Let $G= A^{-1} \oplus_{k} B^{-1}$ partitioned as in
\nref{laG} with $k \geq 1$. 
Then $G$ is nonsingular if and only if $H=A_{22} + B_{11}$
is nonsingular.
\end{theorem}

%\begin{proof}
%It is similar to that of Theorem \ref{teo:cg}, 
%replacing $C$ by $G$, $A^{-1}$ by $A$,
%$B^{-1}$ by $B$, $\hat{A}_{12}$ by $A_{12}$,
%$\hat{B}_{12}$ by $B_{12}$ and $\hat{H}$ by $H$.
%\end{proof}

%\noindent
% REMARK. 
We remark that in analogy to the expression \nref{cinv} of 
$C^{-1}$,
the explicit form of $G^{-1}$ is
% 
\begin{equation}\label{ginv}
G^{-1} = 
\left [
\begin{array}{c c c}
A_{11}- A_{12} H^{-1} A_{21} & A_{12}-A_{12}H^{-1}A_{22} & A_{12}H^{-1} B_{12} \\
B_{11} H^{-1}A_{21}  & B_{11} H^{-1} A_{22}  &  - B_{11} H^{-1} B_{12} + B_{12} \\
B_{21}H^{-1}A_{21}  & B_{21}H^{-1}A_{22}     &  - B_{21} H^{-1} B_{12} + B_{22}
\end{array}
\right ].
\end{equation}

\begin{coro}\label{coro:un}
When $A$ and $B$ are nonsingular $M$-matrices with the common block
$A_{22} = B_{11}$ a square matrix of order $k$,
i.e., of the form
%
\begin{equation}
A = 
\left [
\begin{array}{c c }
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{array}
\right ], \quad
B =\left [
\begin{array}{c c }
A_{22} & B_{12} \\
B_{21} & B_{22}
\end{array}
\right ],
\label{AiBcb}
\end{equation}
% \noindent
then $H=2A_{22}$ is nonsingular and therefore $G=A^{-1} \oplus_k B^{-1}$ is nonsingular.
\end{coro}

We note that this is the case when $A$ and $B$ are overlapping
submatrices of an $M$-matrix, i.e., of the form
\nref{AiBdeM} and \nref{laM} considered in Section \ref{overlap:sec}, 
where we were
interested in the subdirect sum of $A$ and $B$. Here
we conclude that the subdirect sum of their inverses is always
nonsingular.

%suma6v3 usant la matriu Q_total per definir A
\begin{examp}\label{trenca}{\rm 
Let $A$ and $B$ be the matrices of Example~\ref{exteoge}, then according
to Corollary~\ref{coro:un}, 
the $3$-subdirect sum of the inverses
%
\[
G =A^{-1} \oplus_3 B^{-1} \approx \left [
\begin{array}{c c |c c  c| c}
    1.5033  &  0.5513  &  0.5547  &  0.2757  &  0.3912    &     0 \\
    0.9540  &  1.5996  &  0.7158  &  0.3635  &  0.4038    &     0 \\
\hline
    0.6004  &  0.5636  &  2.9750  &  0.8144  &  0.7407    &0.3708 \\
    2.0383  &  2.1242  &  3.5729  &  6.5498  &  5.3372    &2.0139 \\
    0.8953  &  0.9650  &  2.0470  &   1.8025 &   3.9062   & 0.9048 \\
\hline
         0  &       0  &  0.8551  &  1.3803  &  1.2652    &1.9143 \\
\end{array}
\right ]
\]
% \noindent
is a nonsingular matrix.
}
\end{examp}

In the above example a 
direct computation shows that
$G^{-1}$ is not an $M$-matrix:
%
\[
G^{-1} \approx \left [
\begin{array}{c c |c c  c| c}
    0.8900&   -0.2337&   -0.0750&   -0.0119&   -0.0511&    0.0512\\
   -0.4682&    0.8566&   -0.1000&   -0.0238&   -0.0054&    0.0470\\
\hline
   -0.0714&   -0.0761&    0.4250&   -0.0357&   -0.0027&   -0.0435\\
   -0.0952&   -0.1467&   -0.0333&    0.2857&   -0.3118&   -0.1467\\
   -0.0357&   -0.0978&   -0.1500&   -0.0714&    0.4274&   -0.0978\\
\hline
    0.1242&    0.2045&   -0.0667&   -0.1429&   -0.0565&    0.7123\\
\end{array}
\right ]
\]
%
which is not a $Z$-matrix.
Note that when $A$ and $B$ are $M$-matrices
we have from \nref{laG} 
that $G=A^{-1} \oplus B^{-1}$ is nonnegative.
Therefore assuming that $G^{-1}$ exists we have 
$(G^{-1})^{-1} \geq O$. Then it is a natural question 
to seek
conditions so that $G^{-1}$ is a nonsingular $M$-matrix.
% , being $G= A^{-1} \oplus B^{-1}$.
We study this question next.

%\subsection{Subdirect sums of inverses of $M$-matrices} \label{inverseM:sec}

The expressions \nref{laG} of $G$ and \nref{ginv} of $G^{-1}$,
Theorem~\ref{teo:cg2}, and the observation that for
nonsingular $M$-matrices we have $(G^{-1})^{-1} \geq O$, 
imply the following result.

\begin{theorem}\label{coro:cg2}
Let  $A$ and $B$  be nonsingular $M$-matrices 
partitioned as in \nref{AiB} and their inverses partitioned 
as in \nref{AiBinv}. Let $G= A^{-1} \oplus_{k} B^{-1}$ 
% partitioned as in \nref{laG}, 
with $k \geq 1$, and let $H=A_{22} + B_{11}$ be
nonsingular. Then $G^{-1}$
is a nonsingular $M$-matrix if and only if 
$G^{-1}$ is a $Z$-matrix. \end{theorem}

%\begin{proof} Follows from Theorem
%\ref{teo:cg2}, the
%definition of nonsingular $M$-matrix and the fact 
%that from \nref{laG} we have
%$(G^{-1})^{-1} \geq O$. 
%\end{proof}

\begin{coro}\label{coro:z}
Let $A$ and $B$ 
be lower and upper block triangular nonsingular $M$-matrices,
respectively, partitioned as in \nref{AiBtr}
with $A_{22}$ and $B_{11}$ square matrices of order $k$ and
$H=A_{22} + B_{11}$ nonsingular. Then
$G^{-1}=  (A^{-1} \oplus_{k} B^{-1})^{-1}$ 
is a nonsingular  $M$-matrix if and only if the following 
conditions hold:
%
\begin{itemize}
\item[{\rm i)}] $B_{11} H^{-1}A_{21} \leq O$.
\item[{\rm ii)}] $B_{11} H^{-1} A_{22}$ is a $Z$-matrix.
\item[{\rm iii)}] $- B_{11} H^{-1} B_{12} + B_{12} \leq O$.
\end{itemize}
% 
\end{coro}

\begin{proof}
>From \nref{ginv} and 
\nref{AiBtr}
we have that
\begin{equation}\label{ginvpc}
G^{-1} = 
\left [
\begin{array}{c c c}
A_{11} & 0 & 0 \\
B_{11} H^{-1}A_{21}  & B_{11} H^{-1} A_{22}  &  - B_{11} H^{-1} B_{12} + B_{12} \\
0  & 0     &   B_{22}
\end{array}
\right ]
\end{equation}
%\noindent
and therefore $G^{-1}$ is a  $Z$-matrix if and only if the conditions
i), ii) and iii) hold.
%
\end{proof}


Conditions i), ii) and iii) in the corollary are not
as stringent as they may appear. For example, 
let $A$ and $B$ 
be block triangular nonsingular $M$-matrices partitioned as in
\nref{AiBtr} with a common block
$A_{22}=B_{11}$,
a square matrix of order $k$, i.e.,
%
\begin{equation}
A = 
\left [
\begin{array}{c c }
A_{11} & 0 \\
A_{21} & A_{22}
\end{array} \right] 
 \mbox{\rm  ~~ and ~~}
B =\left [
\begin{array}{c c }
A_{22} & B_{12} \\
0 & B_{22}
\end{array}
\right ] .
\label{AiB0}
\end{equation}
% \noindent
Then $G^{-1}=  (A^{-1} \oplus_{k} B^{-1})^{-1}$ 
is a nonsingular  $M$-matrix, since we have from
\nref{ginvpc}  that
% 
\[
G^{-1} 
=
\left [
\begin{array}{c c c}
A_{11}  &  O   & O  \\
 \frac{1}{2}  A_{21}  & \frac{1}{2} A_{22}  &   \frac{1}{2} B_{12} \\
O  & O    &  B_{22}
\end{array}
\right ],
\]
% \noindent
and therefore  $G^{-1}$ is a $Z$-matrix. 
In fact, in this case, we have
% 
\[
G =  
\left [
\begin{array}{c c c}
A_{11}^{-1}  &  O   & O  \\
-A_{22}^{-1}A_{21}A_{11}^{-1}  & 2 A_{22}^{-1}  &   -A_{22}^{-1} B_{12} B_{22}^{-1}  \\
O  & O    &  B_{22}^{-1} 
\end{array}
\right ] \geq O .
\]
% 
The next example illustrates this situation. 


%nfallat2.m
\begin{examp}
{\rm 
Let $A$ and $B$ be the matrices of Example~\ref{ex:nf2}, then
%
\[
G=A^{-1} \oplus_{2} B^{-1}=
\left[ 
\begin{array}{c | c c| c}
    1/3&    0&    0&    0\\
\hline
   1/8& 49/80& 21/80&  9/20\\
  7/24& 77/80& 73/80& 11/10\\
\hline
    0&    0&    0&  1/2 \\
\end{array}
\right] ,
\]
% \noindent
and % $G^{-1}$ given by
% 
\[
G^{-1} = 
\left[ 
\begin{array}{c | c c| c}
     3&    0&    0&    0\\
\hline
 -18/49& 146/49&   -6/7& -39/49\\
   -4/7&  -22/7&      2&  -11/7\\
\hline
 0&    0&    0&    2 \\
\end{array}
\right]
\]
% \noindent
is a nonsingular $M$-matrix in accordance with Corollary~\ref{coro:z}.
}
\end{examp}


Note that if the hypotheses of Corollary~\ref{coro:z}
are satisfied,
and recalling Theorem~\ref{teo:ciginv},
we have that each of the matrices  
$C=A \oplus_k B$ and $G^{-1} = (A^{-1} \oplus_k B^{-1})^{-1}$
are both nonsingular $M$-matrices.

%\pagebreak


\section{$P$-matrices} \label{P_mat:sec}

A square matrix is a $P$-matrix if all its principal
minors are positive. As a consequence we have that
all the diagonal entries of a $P$-matrix are positive.
It is also follows that a nonsingular $M$-matrix is a $P$-matrix.
It can also be shown that if
$A$ is a nonsingular $M$-matrix, then $A^{-1}$ is a $P$-matrix;
see, e.g., \cite{HoJo}. 

%HoJo pag 21

In \cite{FaJo} it is shown that the 
$k$-subdirect sum (with $k>1$) of two $P$-matrices 
is not necessarily a $P$-matrix.
Our results in Sections \ref{M_mat:sec} and \ref{inverse:sec} hold for
nonsingular $M$-matrices and inverses of 
$M$-matrices, respectively. As these two classes of matrices are subsets
of $P$-matrices, it is natural to ask if similar sufficient 
conditions can be found so that the $k$-subdirect sum 
of $P$-matrices is a $P$-matrix. 
The following example indicates that the answer may not be easy to obtain,
since even in the simplest case
of diagonal submatrices 
the $k$-subdirect sum may not be a $P$-matrix.

%resultsumap.m
\begin{examp}\label{pmat}{\rm 
Given the $P$-matrices 
%
\[
A=
\left[ 
\begin{array}{c| c c}
    543 &  388 &   322 \\
\hline
    69 &   160  & 0\\
   368 & 0 &  375\\
\end{array}
\right], \quad
B=
\left[ 
\begin{array}{c c| c}
    136  & 0   & 219 \\
     0   & 225  & 159\\
\hline
   61  & 177   & 230\\
\end{array}
\right]
\]
% \noindent
we have that the $2$-subdirect sum 
%
\[
C=A \oplus_{2} B = 
\left[ 
\begin{array}{c | c  c| c}
 543 &  388 &   322     &  0\\
\hline
    69  & 296 &  0   & 219 \\
   368   & 0 &  600  & 159\\
\hline
 0&    61  & 177   & 230 \\
\end{array}
\right]
\]
% \noindent
is not a $P$-matrix, since $\det(C)<0$.
%
}
\end{examp}

\medskip\noindent
{\bf Acknowledgment.} 
We thank the referee for a very careful
reading of the manuscript and for his comments.

\begin{thebibliography}{10}

\bibitem{BePl} A.~Berman and R.J.~Plemmons.
{\em Nonnegative Matrices in the Mathematical Sciences},
Academic Press, New York, 1979. Reprinted and updated, SIAM, 
Philadelphia, 1994.

\bibitem{BrPeSzR04} R.~Bru, F.~Pedroche, and D.B.~Szyld.
 Additive Schwarz Iterations for Markov Chains, 
{\em SIAM J. Matrix Anal. Appl.}, to appear.

\bibitem{FaJo} S.M.~Fallat and C.R.~Johnson.
Sub-direct sums and positivity classes of matrices. 
{\em Linear Algebra Appl.}, 288:149--173, 1999.

\bibitem{FrSz}
A.~Frommer and D.B.~Szyld.
Weighted Max Norms, Splittings,and Overlapping Additive Schwarz
Iterations, {\em Numerische Mathematik}, 83:259--278, 1999.

\bibitem{HoJo} R.A.~Horn and C.R.~Johnson.
{\em Matrix Analysis}. Cambridge University Press, New York, 
1985.

\bibitem{smith-book}
B.F.~Smith, P.E.~Bj{\o}rstad, and W.D.~Gropp.
{\em Domain decomposition: Parallel multilevel methods for elliptic
partial differential equations}.
Cambridge University Press, Cambridge, 1996.

\bibitem{toselli-widlund}
A.~Toselli and O.B.~Widlund.
{\em Domain Decomposition: Algorithms and Theory}.
\newblock
Springer Series in Computational Mathematics, vol.~34.
\newblock Springer, New York, 2005.

\bibitem{varga}
R.S.~Varga.
{\em Matrix Iterative Analysis}.
\newblock Prentice-Hall, Englewood Cliffs, New Jersey, 1962.
Second Edition, revised and expanded, Springer, New York, 2000.

\end{thebibliography}


\end{document}
