Decay Rates of the Inverse of Nonsymmetric Tridiagonal and Band Matrices.
It is well known that the inverse of an irreducible nonsingular symmetric tridiagonal matrix is given by two sequences of real numbers, {ui} and {vi}, such that similar result holds for nonsymmetric matrices A. There the  inverse can be described by four sequences {ui},{vi}, {xi},$ and {vi} with u xiyi. Here we characterize certain properties of A, i.e., being an M-matrix or positive definite,  in terms of the ui, vi,xi, and yi. We also establish a relation of zero row sums and zero column sums of A and pairwise constant ui,vi, xi, and yi. Moreover, we consider decay rates for the entries of the inverse of tridiagonal and block tridiagonal (banded) matrices. For diagonally dominant matrices we show that the entries of the inverse strictly decay along a row or column. We give a sharp decay result for tridiagonal irreducible M-matrices and tridiagonal positive definite matrices. We also give a decay rate for arbitrary banded M-matrices.
Introduction
In many mathematical problems which gives rise to a linear system of equations the
system matrix is tridiagonal or block tridiagonal. For example the numerical solution
of partial differential equations mostly leads to tridiagonal (one dimensional
problems) and block tridiagonal (higher dimensional problems). Therefore these
classes of matrices have been extensively studied. A review of this topic is given by
Meurant [Meu] for symmetric matrices. One of the most important results is established
by Gantmacher and Krein [GK], who proved that the inverse of a symmetric
irreducible tridiagonal matrix is a so-called Green matrix which is given by two
sequences fu i
and fv i
g of real numbers. A similar result is established by Ikebe.
He proved that the inverse of a nonsymmetric irreducible tridiagonal matrix has a
similar structure as a symmetric one and is given by four sequences fu i
and fy i
g: We call such a matrix a generalized Green matrix.
Considering (block) tridiagonal matrices and their inverses there are different kinds
of problems. On one hand one wants to find explicit formulas for the inverses of
tridiagonal matrices and on the other hand one wants to characterize matrices
whose inverses are (block) tridiagonal. Here we continue considering tridiagonal
matrices and their inverses. We consider generalized Green matrices and show that
the inverse of a generalized Green matrix is tridiagonal. Thus, with Ikebe's result we
obtain a characterization of irreducible nonsingular tridiagonal matrices. Moreover
we characterizes tridiagonal M-matrices and tridiagonal symmetric positive definite
matrices in terms of the fu i
fy i
g. We explain the connection of zero
row sums and zero columns of a tridiagonal matrix and pairwise constant u
and y i .
It has been observed that for large classes of banded matrices the entries of the
inverse tend to zero as ji \Gamma jj becomes larger. The rate of decay is important to construct
sparse approximations of the inverse as preconditioners. In [D] and [DMS] it is
shown that the entries of the inverse of a symmetric positive matrix are bounded in
an exponentially decaying manner along a row or column. For nonsymmetric tridiagonal
M-matrices which are strictly diagonally dominant by rows and by columns
we establish that the entries of the inverse indeed decay along each row and column
away from the diagonal. We also give a bound for this decay. This result generalize
a result by Concus, Golub, and Meurant [CGM] for symmetric matrices.
For arbitrary tridiagonal M-matrices or positive definite matrices the entries of the
inverse do not decay a long a row in general. However, here we establish a sharp
decay rate related to two diagonal entries for the inverses of tridiagonal matrices.
This result can be proved easily and continues the number of elegant results on
tridiagonal matrices. For symmetric matrices the result is related to Vassilevski
[Vas] result for which Cauchy-Bunyakowski-Schwarz constants are used. Therefore
we establish a new proof of Vassilevski's result and obtain a new way to compute
or estimate Cauchy-Bunyakowski-Schwarz constants for tridiagonal matrices. Moreover
3we establish a decay rate for the inverses of banded M-matrices.
2 Inverses of tridiagonal matrices
One of the most important results on symmetric tridiagonal matrices is the result
by Gantmacher and Krein [GK] which describes the structure of the inverse of these
matrices.
Theorem 2.1 Let A 2 IR n;n be symmetric, irreducible and nonsingular. Then A is
tridiagonal if and only if A \Gamma1 is a Green matrix.
A Green matrices
is given by two sequences fu i
of
numbers such that
or
c i;j
Green matrices can be described more elegantly as the Hadamard product (elemen-
twise product) of a so-called type D and a flipped type D matrix, (see [Mar] and
For nonsymmetric tridiagonal matrices A 2 IR n;n with
c n\Gamma2 a
c
(2.
Ikebe [I] proved that the inverse of A has a similar structure as for the symmetric
case.
Theorem 2.2 Let A 2 IR n;n be irreducible and tridiagonal. If A is nonsingular then
there exist four sequences fu i
g, fv i
g, fx i
g, fy i
g such that A \Gamma1 =:
by
c i;j
In the following we discuss inverses of nonsymmetric tridiagonal matrices. Therefore
we define a generalized Green matrix related to Ikebe's result.
Definition 2.3 A matrix
is called a generalized Green matrix if
there exist four sequences fu i
g, fv i
g, fx i
g, fy i
g such that
c i;j
Next we give some properties of generalized Green matrices. For A 2 IR n;n let A ij
denote the (n \Gamma 1) \Theta (n \Gamma 1) matrix obtained from A by deleting the i-th row and
the j-th column. Moreover, for a generalized Green matrix define
d i;j
We then have
Theorem 2.4 Let A 2 IR n;n be a generalized Green matrix. Then
det
det A i;i+1
det A
d i+1;i
det A i+1;i
det A
det A
Proof. We first consider det A. The case obviously true. For
we do Gaussian elimination from the right, i.e. we multiply A from the right with
a b
with
Using the inductive hypothesis we obtain the first equality of (2.4). Gaussian elimination
from the left gives the second equality.
To obtain (2.5) we multiply A i;i+1 from the left with
l s;s
l
for
l
l s;t
we get
det A
det A
d i+1;i
Similarly we obtain det A i+1;i .
Next we first consider A i;j with multiplying A i;j from the right with
l s;s
l
for
l s;t
we get
A i;j
where ~
A 1 is a diagonal matrix whose last diagonal entry is zero. Thus, det A i;j
Similarly we obtain det A i;j
With Ikebe's theorem (Theorem 2.2) and Theorem 2.4 we immediately obtain the
following theorem
Theorem 2.5 Let A 2 IR n;n be irreducible and nonsingular. Then A is tridiagonal
if and only if A \Gamma1 is a generalized Green matrix.
Proof. The sufficient part of Theorem 2.5 is proved by Ikebe [I]. Now assume that
A \Gamma1 is a generalized Green matrix.
a i;j
det A j;i
det A
With Theorem 2.4 we get that A is tridiagonal. 2
Here we should mention that Barrett gives in [B] another characterization of tridiagonal
matrices.
Theorem 2.6 Let
. Then
C \Gamma1 is tridiagonal if and only if C has the triangle property, i.e.
c i;j
c i;k c k;j
c k;k
for all
Note that none of these theorems includes the other. In Theorem 2.5 there is a restriction
on irreducibility while in Theorem 2.6 there is a restriction of the diagonal
entries of the inverse. In [A] Asplund gives a characterization in terms of vanishing
certain minors of the inverse. However the beauty of Ikebe's result and Theorem 2.5
is the explicit form of the inverse which can be used to establish more properties of
the inverse of a tridiagonal matrix.
Next we will characterize nonsingular tridiagonal M-matrices. A matrix
is called a nonsingular M-matrix if a i;j
nonnegative ma-
trix. We characterize nonsingular tridiagonal M-matrices in terms of the sequences
fy i
which gives A \Gamma1 . To do so we define for
Theorem 2.7 Let A 2 IR n;n be irreducible and nonsingular. Then the following are
equivalent:
1. A is a tridiagonal M-matrix,
2. A \Gamma1 is a generalized Green matrix where all have the same sign
and
Proof.
is given by
a
Thus Theorem 2.4 yields to
a i;i+1
a i+1;i
If A is an M-matrix we have
Therefore
Hence ff i
If ff i
Since
for all i, i.e.
we obtain
Therefore
A \Gamma1 is a nonnegative matrix we then obtain that A is an M-matrix. 2
Corollary 2.8 Let A 2 IR n;n be symmetric irreducible and nonsingular. Then the
following are equivalent:
1. A is a tridiagonal M-matrix,
2. A \Gamma1 is a Green matrix given by the sequences fu i
and fv i
g where all
and have the same sign and
In [MNNST] another characterization of tridiagonal M-matrices is given. There it is
used that for each nonsymmetric irreducible tridiagonal M-matrix A there exists a
diagonal matrix D such that DA is symmetric. Here we can avoid this symmetrization

For symmetric positive definite matrices we immediately obtain the following cha-
racterization
Corollary 2.9 Let A 2 IR n;n be a nonsingular symmetric tridiagonal matrix. A is
positive definite if and only if there exists a diagonal matrix
with jd ii
such that
(DAD)
where all u i and v i in (2:8) have the same sign and
These characterizations of tridiagonal M-matrices and tridiagonal positive definite
matrices will be useful in the next section.
3 Decay rates
In this section we consider the decay of the elements of the inverse of tridiagonal and
banded matrices. Several papers already established results on this topic. In [D] and
[DMS] it is shown that the entries of the inverse of a symmetric positive matrix are
bounded in an exponentially decaying manner along a row or column. Here we will
give some sharp decay rates and we will show that the entries of a nonsymmetric
tridiagonal diagonally dominant matrix indeed decay along a row and column.
is diagonally dominant by columns if
j for all i:
If
j for all i:
then B is called diagonally dominant by rows. If the above inequalities are strict
then B is called strictly diagonally dominant by columns or by rows respectively.
For A as in (2.2) being a symmetric tridiagonal M-matrix which is diagonally dominant
by columns (with a 1 ? b 1 and a n ? b Meurant proved in
[CGM] that the sequence fu i
g is strictly increasing while fv i
g is strictly decreasing.
Thus the entries of A \Gamma1 indeed strictly decay along each row or column. Moreover
they proved that
A is diagonally dominant one has ae ! 1.
We will generalize this result to the nonsymmetric case. In the following we also
assume for simplicity that A is a tridiagonal Z-matrix, i.e.
a 1 \Gammab 1
\Gammac 1 a 2 \Gammab 2
\Gammac n\Gamma2
a
\Gammab
\Gammac
0:
The entries of the sequences fu i
and fy i
which give A \Gamma1 , can be computed
as follows
Lemma 3.1 Let A 2 IR n;n be an irreducible tridiagonal Z-matrix. Then
a
c
a i
Proof. Multiplying the i-th row of A with the (i 1)-th column of A \Gamma1 gives the
Multiplying the i-th row of A \Gamma1 with the (i \Gamma 1)-th column of A gives the x i .
Multiplying the i-th row of A with the i-th column of A \Gamma1 gives the v i
. Moreover,
we use that
For the next theorem we defineae 1
a i
a i
Theorem 3.2 Let A 2 IR n;n be an irreducible tridiagonal M-matrix.
If A is diagonally dominant by rows and if a 1 ? b 1 and a n
then fu i
g is
strictly increasing while fy i
g is strictly decreasing. Moreover,
ae (j \Gammai)
If A is diagonally dominant by columns and if a 1 ? c 1 and a n ? b
then fx i
g is
strictly increasing while fv i
g is strictly decreasing. Moreover,
ae (j \Gammai)
Proof. First assume that A is diagonally dominant by rows and a 1
It is clear that . By the induction hypothesis and Lemma 3.1 we get
a
To obtain the disered result for the v i
we have to establish a recursive formula.
Multiplying the i-th row of A \Gamma1 with the i-th column of A gives
a
Multiplying the (i 1)-th row of A \Gamma1 with the i-th column of A gives
\Gammab
Multiplying the (i 1)-th row of A with the (i 1)-th column of A \Gamma1 gives
y i+2
Hence
and
c
We then have y
and by induction y i
. The decay rates follow immediately
from the recursive formulas for the u i and y i and the special structure of A \Gamma1 .
Now, assume that A is diagonally dominant by columns a 1 ? c 1 and a n ? b
Obviously, By the induction hypothesis and Lemma 3.1 we get
a
x
x i\Gamma2
c
a
c
x
Again, for the v i
we have to establish a recursive formula. Multiplying the i-th row
of A with the (i 1)-th column of A \Gamma1 gives
a i
Multiplying the (i 1)-th row of A \Gamma1 with the (i 1)-th column of A gives
Together with Lemma 3.1 we get
and
We then have v and by induction Again, the decay results follow
immediately. 2
For matrices which are not M-matrices but satisfy the other assumptions of Theorem
3.2 we obtain that the sequences of the absolute values strictly increase or
decrease respectively.
Theorem 3.2 generalizes the result for symmetric tridiagonal matrices by Concus,
Golub, and Meurant [CGM]. In the following we specify the above result. We will
explain the connection of zero row and column sums of A and some pairwise constant
a j;i
Then we have
Theorem 3.3 Let A be an irreducible nonsingular tridiagonal matrix. Then there
exist indices s; t 2 f0; 1g such that
if and only if
Moreover, there exist indices ~ s; ~ t 2 f0; 1g such that
if and only if
s
Proof. The proof follows immediately from similar formulas for the u
and y i
as derived in Lemma 3.1 and in the proof of Theorem 3.2. 2
Note that in Theorem 3.3 we do not assume A to be diagonally dominant or positive
definite or to be a Z-matrix. For symmetric matrices Theorem 3.3 says that the first
and last pairwise constant u i and v i gives zero row sums for the first and last rows in
A and vice versa. Moreover, if r i
then the inverse of A can be partitioned as
where C 11 2 IR s;s and C 33 2 IR t+1;t+1 . Here C 11 is a flipped type D matrix while C 33
is a type D matrix. C 31 and C 13 are flat matrices, i.e. all entries of these blocks are
equal. Moreover the rows of C 12 and the columns of C 23 are flat. This structure is
illustrated in the next example.
Example 3.4
Combining Theorem 3.3 with Theorem 3.2 we get
Corollary 3.5 Let A be an irreducible tridiagonal M-matrix. If r
Then the sequences
and fy i
else
else.
If c i
s and c i
s;
Then the sequences fx i
and fv i
else.
For M-matrices or symmetric positive definite tridiagonal or banded matrices, which
are not diagonally dominant, the elements of A \Gamma1 do not decrease in general along
a row or column. This can be seen in Example 3.6.
Example 3.6
However we will establish a decay result for tridiagonal M-matrices and symmetric
positive definite matrices in the following. These results are based on the characterizations
of these matrices given in Theorem 2.7 and Corollary 2.9.
Theorem 3.7 Let A 2 IR n;n be a nonsingular irreducible tridiagonal matrix. Let
c i;i+k
Y
c i+k;i
Y
where the ff i
and fi i
are as in (2:7).
Proof. Obviously, c ii ; c i+k;i+k
and c i;i+k
are given by
c ii
c i;i+k
Moreover
Y
ff i+jA u i+k
Hence
Y
Similarly, we obtain (3.6). 2
In general one can not say anything about the ff i
and fi i
in (3.5) and (3.6). But
for M-matrices and for symmetric positive definite matrices we have the following
decay results
Corollary 3.8 Let A 2 IR n;n be an irreducible tridiagonal M-matrix. Then for
we have
Y
A (c i;i c i+k;i+k );
Proof. The proof follows immediately from Theorem 2.7 and Theorem 3.7. 2
Corollary 3.9 Let A 2 IR n;n be an irreducible tridiagonal matrix which is positive
definite. Then for A
we have
c i;i+k =@ k
Y
Proof. With Theorem 2.9 we have for a symmetric positive definite tridiagonal
matrix A that there exists a diagonal matrix D such that DA \Gamma1 D is given by (2:8)
with
Thus we have ff i
1 for all i. Since (3.5) of Theorem 3.7 is independent of multiplying
A from the left and the right with the same diagonal matrix, we obtain (3.8).Note that Corollary 3.9 also include the symmetric M-matrices. Since for M -
matrices ff i positive definite matrices,
(3.7) and (3.8) give a sharp decay result for the entries of the inverse of tridiagonal
matrices. Moreover, this results can be proved easily and elegant. The decay rates
are given in terms of A \Gamma1 . However, the next lemma and the next theorem will show
the relation of the ff i and fi i to some values determined directly from A.
For partition A as
A 11 A 12
A 21 A 22
where A 11 2 IR k;k and A 22 2 IR n\Gammak;n\Gammak , and splitt A into
, where D k
is
the block diagonal of A. If D k
is nonsingular we define
We then have
Lemma 3.10 Let A 2 IR n;n be tridiagonal and nonsingular. For
be as in (3:9). Moreover for A
~
~
c k+1;k#
If D k and ~
D k are nonsingular, then with st
we have
~
and
Here oe(T ) denotes the spectrum of the matrix T .
Thus Lemma 3.10 says the following: If we partition A as a 2 \Theta 2 block matrix then
the overlapping 2 \Theta 2 matrix of the block Jacobian matrix is equal to the negative
transposed Jacobian matrix of the related overlapping 2 \Theta 2 submatrix of A \Gamma1 .
Proof. We immediately get for -
22 ) 11 a k+1;k 0
Now consider A partioned as in (3.9). A \Gamma1 is given by
\Gamma(A=A
here (A=A 11 ) denotes the Schur complement of A, i.e. (A=A 11
11 A 21 .
We have
where
; is the last row of A \Gamma1
11 . Hence
\Gamma(A=A
a k;k+1
Thus
c k+1;k+1
Similarly we show that
c k;k
Thus
Equation (3.13) follows from (3.12) and the special structure of J . 2
We then obtain
Theorem 3.11 Let A 2 IR n;n be an irreducible tridiagonal M-matrix and let A
s be as in (3:10). Then
i+l
Proof. For all s equation (3.11) gives
~
~
thus
(ae( ~
s
~
Hence with Lemma 3.10 we obtain
s
:Moreover for symmetric positive definite matrices we obtain
Corollary 3.12 Let A 2 IR n;n be tridiagonal symmetric positive definite and let
ae i+l
A similar result is proved by Vassilevski [Vas], (see also [A] p.368). Vassilevski proved
for tridiagonal symmetric positive definite matrices A and their inverses
that
c i;i+k
c i+k;i+k
where
(v T A 11 vw T A 22 w) 1
and A is partitioned as in (3.9) for all s. The constants fl s
are known as the Cauchy-
Bunyakowski-Schwarz constants. Since A is positive definite, fl s ! 1. Originally in
[Vas] the result (3.14) is obtained from a more general result for symmetric positive
definite block tridiagonal matrices. There norms of the blocks are compared and
the equality in (3.14) becomes an inequality (-).
The proof given in [Vas] is very long and technical, at least for the point case. But
it is easy to prove that the ae s in Corollary 3.12 and the fl s in (3.15) are the same.
Thus, our approach for the nonsymmetric case gives even for the symmetric matrices
a much simpler proof of Vassilevski result.
Moreover Theorem 3.12 and Lemma 3.10 give another way to compute or estimate
the Cauchy-Bunyakowski-Schwarz constants.
Using comparison theorems for regular splittings we obtain from Theorem 3.12 and
Theorem 3.11
Corollary 3.13 Let A 2 IR n;n be tridiagonal and irreducible. Let A
A is an M-matrix
then
c i;i+k c i+k;i
If A is symmetric positive definite then
c i;i+k
Proof. The splittings
of (3.9) are regular splittings, i.e. D \Gamma1
and N k
are nonnegative matrices. The same holds for the splitting
we have
- N for all k;
With Varga's comparison theorem for regular splittings ([Var] p. 90) we obtain
Since (3.16) is independent of scaling we obtain the result easily for symmetric
positive definite matrices.
Note that in both cases ae ! 1. Thus the spectral radius of the Jacobi iteration
matrix is an upper bound for the decay of the entries of the inverse of a tridiagonal
M-matrix or symmetric positive definite matrix.
In the following we will see that this is also true for banded M-matrices. A matrix
called
For M-matrices A the eigenvalue - of smallest absolute value is real and the corresponding
eigenvector u is positive. Thus we can find a nonsingular diagonal matrix
where e is the vector of all ones. We then have
Theorem 3.14 Let A be a 2p
for any s; t with s 2
s
s
here A.
Proof. Since
We first assume that s ? t. To find the t-th column of C we have to solve
is the zero vector except the t-th entry which is 1. To do so we consider
with J := D \Gamma1 N
If we define "
Thus
The last equality follows from (3.18) and jjxjj
(see [FP]). With (3.19) we
obtain for
l
and for
l
Now let
~
where ~
. Similar we partition x (k) and x. Then
x
Thus
s
Similarly we obtain by solving x T
s
Similarly we prove the case s ! t. 2
Theorem 3.14 can be easily extended to H-matrices A, i.e. matrices for which the
comparison matrix M(A) with
is an
M-matrix. The decay rate is then the spectral radius of the jacobi matrix of M(A).
Moreover Theorem 3.14 can be also formulated for sparse matrices, not only banded
matrices, using the notation used by Meurant in [Meu].
We immediately get from Theorem 3.14
Corollary 3.15 Let A be a 2p
for any s; t with s 2
c s;t
c t;s
c t;t
s;s
Corollary 3.16 Let A be a 2p
[c s;t ]. Then for any s; t with s 2
c s;t
c s;t
The advantage of the Corollaries 3.15 and 3.16 compared with a Theorem by Meu-
rants ([Meu] Theorem 4.13) is that we just need ae and diagonal entries of A \Gamma1 to
estimate the decay.

Acknowledgement

The author thanks Ludwig Elsner and Shmuel Friedland for helpful
comments. An earlier version of this paper in which symmetric matrices are
considered, appeared as Prepint 96 - 025 of the Sonderforschungsbereich 343, Uni-
versit-at Bielefeld.



--R

Cambridge University Press

Block preconditioning for the conjugate gradient method
Inverses of band matrices and local convergence of spline projections
Decay rates for inverses of band matrices



Nonnegative matrices whose inverses are M-matrices
A Review on the inverse of symmetric tridiagonal and block tridiagonal matrices

Matrix Iterative Analysis
On Some Ways of Approximating Inverses of Banded Matrices in Connection with Deriving Preconditioners Based on Incomplete Block Factorizations
--TR

--CTR
Jitesh Jain , Stephen Cauley , Cheng-Kok Koh , Venkataramanan Balakrishnan, SASIMI: sparsity-aware simulation of interconnect-dominated circuits with non-linear devices, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
inverses of tridiagonal matrices;tridiagonal matrices;decay rates