Weakly chained diagonally dominant matrix explained

In mathematics, the weakly chained diagonally dominant matrices are a family of nonsingular matrices that include the strictly diagonally dominant matrices.

Definition

Preliminaries

We say row

i

of a complex matrix

A=(aij)

is strictly diagonally dominant (SDD) if

|aii|>style{\sumj

}|a_|. We say

A

is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with

\geq

instead.

The directed graph associated with an

m x m

complex matrix

A=(aij)

is given by the vertices

\{1,\ldots,m\}

and edges defined as follows: there exists an edge from

ij

if and only if

aij0

.

Definition

A complex square matrix

A

is said to be weakly chained diagonally dominant (WCDD) if

A

is WDD and

i1

that is not SDD, there exists a walk

i1i2ik

in the directed graph of

A

ending at an SDD row

ik

.

Example

The

m x m

matrix

\begin{pmatrix}1\\ -1&1\\ &-1&1\\ &&\ddots&\ddots\\ &&&-1&1 \end{pmatrix}

is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.[1]

Proof:[2] Let

A=(aij)

be a WCDD matrix. Suppose there exists a nonzero

x

in the null space of

A

.Without loss of generality, let

i1

be such that
|x
i1

|=1\geq|xj|

for all

j

.Since

A

is WCDD, we may pick a walk

i1 → i2 → … → ik

ending at an SDD row

ik

.

Taking moduli on both sides of

-a
i1i1
x
i1

=

\sum
ji1
a
i1j

xj

and applying the triangle inequality yields
\left|a
i1i1
\right|\leq\sum
ji1
\left|a
i1j

\right|\left|xj\right|\leq\sum

ji1
\left|a
i1j

\right|,

and hence row

i1

is not SDD.Moreover, since

A

is WDD, the above chain of inequalities holds with equality so that

|xj|=1

whenever
a
i1j

≠ 0

.Therefore,
|x
i2

|=1

.Repeating this argument with

i2

,

i3

, etc., we find that

ik

is not SDD, a contradiction.

\square

Recalling that an irreducible matrix is one whose associated directed graph is strongly connected, a trivial corollary of the above is that an irreducibly diagonally dominant matrix (i.e., an irreducible WDD matrix with at least one SDD row) is nonsingular.[3]

Relationship with nonsingular M-matrices

The following are equivalent:[4]

A

is a nonsingular WDD M-matrix.

A

is a nonsingular WDD L-matrix;

A

is a WCDD L-matrix;

In fact, WCDD L-matrices were studied (by James H. Bramble and B. E. Hubbard) as early as 1964 in a journal article[5] in which they appear under the alternate name of matrices of positive type.

Moreover, if

A

is an

n x n

WCDD L-matrix, we can bound its inverse as follows:[6]

\left\VertA-1\right\Vertinfty\leq\sumi\left[aii

i
\prod
j=1

(1-uj)\right]-1

  where  

ui=

1
\left|aii\right|
n
\sum
j=i+1

\left|aij\right|.

Note that

un

is always zero and that the right-hand side of the bound above is

infty

whenever one or more of the constants

ui

is one.

Tighter bounds for the inverse of a WCDD L-matrix are known.[7] [8] [9] [10]

Applications

Due to their relationship with M-matrices (see above), WCDD matrices appear often in practical applications.An example is given below.

Monotone numerical schemes

WCDD L-matrices arise naturally from monotone approximation schemes for partial differential equations.

For example, consider the one-dimensional Poisson problem

u\prime(x)+g(x)=0

  for  

x\in(0,1)

with Dirichlet boundary conditions

u(0)=u(1)=0

.Letting

\{0,h,2h,\ldots,1\}

be a numerical grid (for some positive

h

that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of
-1
h2

A\vec{u}+\vec{g}=0

  where  

[\vec{g}]j=g(jh)

and

A=\begin{pmatrix}2&-1\\ -1&2&-1\\ &-1&2&-1\\ &&\ddots&\ddots&\ddots\\ &&&-1&2&-1\\ &&&&-1&2 \end{pmatrix}.

Note that

A

is a WCDD L-matrix.

Notes and References

  1. Shivakumar. P. N.. Chew. Kim Ho. A Sufficient Condition for Nonvanishing of Determinants. Proceedings of the American Mathematical Society. 43. 1. 1974. 63. 0002-9939. 10.1090/S0002-9939-1974-0332820-0. free.
  2. Azimzadeh. Parsiad. Forsyth. Peter A.. Weakly Chained Matrices, Policy Iteration, and Impulse Control. SIAM Journal on Numerical Analysis. 54. 3. 2016. 1341–1364. 0036-1429. 10.1137/15M1043431. 1510.03928. 29143430 .
  3. Book: Horn. Roger A.. Johnson. Charles R.. Matrix analysis. 1990. Cambridge University Press, Cambridge.
  4. Azimzadeh. Parsiad. A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-Matrix. Mathematics of Computation. 2019. 88. 316. 783–800. 10.1090/mcom/3347. 1701.06951. 2017arXiv170106951A. 3356041 .
  5. Bramble. James H.. Hubbard. B. E.. Journal of Mathematical Physics. 43. 1964. 117–132. On a finite difference analogue of an elliptic problem which is neither diagonally dominant nor of non-negative type. 10.1002/sapm1964431117.
  6. Shivakumar. P. N.. Williams. Joseph J.. Ye. Qiang. Marinov. Corneliu A.. On Two-Sided Bounds Related to Weakly Diagonally Dominant M-Matrices with Application to Digital Circuit Dynamics. SIAM Journal on Matrix Analysis and Applications. 17. 2. 1996. 298–312. 0895-4798. 10.1137/S0895479894276370.
  7. Cheng. Guang-Hui. Huang. Ting-Zhu. An upper bound for

    \VertA-1\Vertinfty

    of strictly diagonally dominant M-matrices. Linear Algebra and Its Applications. 426. 2–3. 2007. 667–673. 0024-3795. 10.1016/j.laa.2007.06.001. free.
  8. Li. Wen. The infinity norm bound for the inverse of nonsingular diagonal dominant matrices. Applied Mathematics Letters. 21. 3. 2008. 258–263. 0893-9659. 10.1016/j.aml.2007.03.018. free.
  9. Wang. Ping. An upper bound for

    \VertA-1\Vertinfty

    of strictly diagonally dominant M-matrices. Linear Algebra and Its Applications. 431. 5–7. 2009. 511–517. 0024-3795. 10.1016/j.laa.2009.02.037. free.
  10. Huang. Ting-Zhu. Zhu. Yan. Estimation of

    \VertA-1\Vertinfty

    for weakly chained diagonally dominant M-matrices. Linear Algebra and Its Applications. 432. 2–3. 2010. 670–677. 0024-3795. 10.1016/j.laa.2009.09.012. free.