Weakly chained diagonally dominant matrix

Summary

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

Venn Diagram showing the containment of weakly chained diagonally dominant (WCDD) matrices relative to weakly diagonally dominant (WDD) and strictly diagonally dominant (SDD) matrices.

Definition

edit

Preliminaries

edit

We say row   of a complex matrix   is strictly diagonally dominant (SDD) if  . We say   is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with   instead.

The directed graph associated with an   complex matrix   is given by the vertices   and edges defined as follows: there exists an edge from   if and only if  .

Definition

edit

A complex square matrix   is said to be weakly chained diagonally dominant (WCDD) if

  •   is WDD and
  • for each row   that is not SDD, there exists a walk   in the directed graph of   ending at an SDD row  .

Example

edit
 
The directed graph associated with the WCDD matrix in the example. The first row, which is SDD, is highlighted. Note that regardless of which node   we start at, we can find a walk  .

The   matrix

 

is WCDD.

Properties

edit

Nonsingularity

edit

A WCDD matrix is nonsingular.[1]

Proof:[2] Let   be a WCDD matrix. Suppose there exists a nonzero   in the null space of  . Without loss of generality, let   be such that   for all  . Since   is WCDD, we may pick a walk   ending at an SDD row  .

Taking moduli on both sides of

 

and applying the triangle inequality yields

 

and hence row   is not SDD. Moreover, since   is WDD, the above chain of inequalities holds with equality so that   whenever  . Therefore,  . Repeating this argument with  ,  , etc., we find that   is not SDD, a contradiction.  

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

edit

The following are equivalent:[4]

  •   is a nonsingular WDD M-matrix.
  •   is a nonsingular WDD L-matrix;
  •   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   is an   WCDD L-matrix, we can bound its inverse as follows:[6]

    where    

Note that   is always zero and that the right-hand side of the bound above is   whenever one or more of the constants   is one.

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

Applications

edit

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

Monotone numerical schemes

edit

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

For example, consider the one-dimensional Poisson problem

    for    

with Dirichlet boundary conditions  . Letting   be a numerical grid (for some positive   that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of

    where    

and

 

Note that   is a WCDD L-matrix.

References

edit
  1. ^ Shivakumar, P. N.; Chew, Kim Ho (1974). "A Sufficient Condition for Nonvanishing of Determinants" (PDF). Proceedings of the American Mathematical Society. 43 (1): 63. doi:10.1090/S0002-9939-1974-0332820-0. ISSN 0002-9939.
  2. ^ Azimzadeh, Parsiad; Forsyth, Peter A. (2016). "Weakly Chained Matrices, Policy Iteration, and Impulse Control". SIAM Journal on Numerical Analysis. 54 (3): 1341–1364. arXiv:1510.03928. doi:10.1137/15M1043431. ISSN 0036-1429. S2CID 29143430.
  3. ^ Horn, Roger A.; Johnson, Charles R. (1990). Matrix analysis. Cambridge University Press, Cambridge.
  4. ^ Azimzadeh, Parsiad (2019). "A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-Matrix". Mathematics of Computation. 88 (316): 783–800. arXiv:1701.06951. Bibcode:2017arXiv170106951A. doi:10.1090/mcom/3347. S2CID 3356041.
  5. ^ Bramble, James H.; Hubbard, B. E. (1964). "On a finite difference analogue of an elliptic problem which is neither diagonally dominant nor of non-negative type". Journal of Mathematical Physics. 43: 117–132. doi:10.1002/sapm1964431117.
  6. ^ Shivakumar, P. N.; Williams, Joseph J.; Ye, Qiang; Marinov, Corneliu A. (1996). "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): 298–312. doi:10.1137/S0895479894276370. ISSN 0895-4798.
  7. ^ Cheng, Guang-Hui; Huang, Ting-Zhu (2007). "An upper bound for   of strictly diagonally dominant M-matrices". Linear Algebra and Its Applications. 426 (2–3): 667–673. doi:10.1016/j.laa.2007.06.001. ISSN 0024-3795.
  8. ^ Li, Wen (2008). "The infinity norm bound for the inverse of nonsingular diagonal dominant matrices". Applied Mathematics Letters. 21 (3): 258–263. doi:10.1016/j.aml.2007.03.018. ISSN 0893-9659.
  9. ^ Wang, Ping (2009). "An upper bound for   of strictly diagonally dominant M-matrices". Linear Algebra and Its Applications. 431 (5–7): 511–517. doi:10.1016/j.laa.2009.02.037. ISSN 0024-3795.
  10. ^ Huang, Ting-Zhu; Zhu, Yan (2010). "Estimation of   for weakly chained diagonally dominant M-matrices". Linear Algebra and Its Applications. 432 (2–3): 670–677. doi:10.1016/j.laa.2009.09.012. ISSN 0024-3795.