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 .
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]
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.
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
^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.
^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.
^Horn, Roger A.; Johnson, Charles R. (1990). Matrix analysis. Cambridge University Press, Cambridge.
^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.
^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.
^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.
^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.
^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.
^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.
^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.