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 = (a _{ij} ) is strictly diagonally dominant (SDD) if |a _{ii} |> style{\sum _{j ≠} }|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 = (a _{ij} ) is given by the vertices \{ 1 , \ldots, m\} and edges defined as follows: there exists an edge from i → j if and only if a _{ij} ≠ 0 .

Definition

A complex square matrix

A is said to be weakly chained diagonally dominant (WCDD) ifA is WDD and

• for each row

i _{1} that is not SDD, there exists a walk i _{1} → i _{2} → … → i _{k} in the directed graph of A ending at an SDD row i _{k} .

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 = (a _{ij} ) be a WCDD matrix. Suppose there exists a nonzero x in the null space of A .Without loss of generality, let i _{1} be such that |x _{i _{1}} | =1 \geq|x _{j|} for all j .Since A is WCDD, we may pick a walk i _{1 →} i _{2 → … →} i _{k} ending at an SDD row i _{k} .

Taking moduli on both sides of

- a _{i _{1} i _{1}} x _{i _{1}} = \sum _{j ≠ i _{1}} a _{i _{1} j} x _{j} and applying the triangle inequality yields\left|a _{i _{1} i _{1}} \right|\leq\sum _{j ≠ i _{1}} \left|a _{i _{1} j} \right|\left|x _{j\right|\leq\sum} ^{j ≠ i _{1}} \left|a _{i _{1} j} \right|, and hence row i _{1} is not SDD.Moreover, since A is WDD, the above chain of inequalities holds with equality so that |x _{j} | =1 whenever a _{i _{1} j} ≠ 0 .Therefore, |x _{i _{2}} | =1 .Repeating this argument with i _{2} , i _{3} , etc., we find that i _{k} 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\Vert A ^{-1} \right\Vert _{infty} \leq\sum _{i} \left[a _{ii} \prod ^{i} _{j =1} ( 1- u _{j} )\right] ^{-1}   where   u _{i} = (1)/(\left|a _{ii} \right|) \sum ^{n} _{j = i +1} \left|a _{ij} \right|. Note that u _{n} is always zero and that the right-hand side of the bound above is inf ty whenever one or more of the constants u _{i} 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, 2 h,\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)/(h ^{2}) A\vec{u} + \vec{g} = 0   where   [\vec{g}] _{j} = g(jh) andA = \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 \Vert A ^{-1} \Vert _{infty} 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 \Vert A ^{-1} \Vert _{infty} 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 \Vert A ^{-1} \Vert _{infty} 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.