Weakly chained diagonally dominant matrix
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 [math]\displaystyle{ i }[/math] of a complex matrix [math]\displaystyle{ A = (a_{ij}) }[/math] is strictly diagonally dominant (SDD) if [math]\displaystyle{ |a_{ii}|\gt \textstyle{\sum_{j\neq i}}|a_{ij}| }[/math]. We say [math]\displaystyle{ A }[/math] is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with [math]\displaystyle{ \geq }[/math] instead.
The directed graph associated with an [math]\displaystyle{ m \times m }[/math] complex matrix [math]\displaystyle{ A = (a_{ij}) }[/math] is given by the vertices [math]\displaystyle{ \{1, \ldots, m\} }[/math] and edges defined as follows: there exists an edge from [math]\displaystyle{ i \rightarrow j }[/math] if and only if [math]\displaystyle{ a_{ij} \neq 0 }[/math].
Definition
A complex square matrix [math]\displaystyle{ A }[/math] is said to be weakly chained diagonally dominant (WCDD) if
- [math]\displaystyle{ A }[/math] is WDD and
- for each row [math]\displaystyle{ i_1 }[/math] that is not SDD, there exists a walk [math]\displaystyle{ i_1 \rightarrow i_2 \rightarrow \cdots \rightarrow i_k }[/math] in the directed graph of [math]\displaystyle{ A }[/math] ending at an SDD row [math]\displaystyle{ i_k }[/math].
Example
The [math]\displaystyle{ m \times m }[/math] matrix
- [math]\displaystyle{ \begin{pmatrix}1\\ -1 & 1\\ & -1 & 1\\ & & \ddots & \ddots\\ & & & -1 & 1 \end{pmatrix} }[/math]
is WCDD.
Properties
Nonsingularity
A WCDD matrix is nonsingular.[1]
Proof:[2] Let [math]\displaystyle{ A=(a_{ij}) }[/math] be a WCDD matrix. Suppose there exists a nonzero [math]\displaystyle{ x }[/math] in the null space of [math]\displaystyle{ A }[/math]. Without loss of generality, let [math]\displaystyle{ i_1 }[/math] be such that [math]\displaystyle{ |x_{i_1}|=1\geq|x_j| }[/math] for all [math]\displaystyle{ j }[/math]. Since [math]\displaystyle{ A }[/math] is WCDD, we may pick a walk [math]\displaystyle{ i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_k }[/math] ending at an SDD row [math]\displaystyle{ i_k }[/math].
Taking moduli on both sides of
- [math]\displaystyle{ -a_{i_1 i_1}x_{i_1} = \sum_{j\neq i_1} a_{i_{1} j}x_j }[/math]
and applying the triangle inequality yields
- [math]\displaystyle{ \left|a_{i_1 i_1}\right|\leq\sum_{j\neq i_1}\left|a_{i_1 j}\right|\left|x_j\right|\leq\sum_{j\neq i_1}\left|a_{i_1 j}\right|, }[/math]
and hence row [math]\displaystyle{ i_1 }[/math] is not SDD. Moreover, since [math]\displaystyle{ A }[/math] is WDD, the above chain of inequalities holds with equality so that [math]\displaystyle{ |x_{j}|=1 }[/math] whenever [math]\displaystyle{ a_{i_1 j}\neq0 }[/math]. Therefore, [math]\displaystyle{ |x_{i_2}|=1 }[/math]. Repeating this argument with [math]\displaystyle{ i_2 }[/math], [math]\displaystyle{ i_3 }[/math], etc., we find that [math]\displaystyle{ i_k }[/math] is not SDD, a contradiction. [math]\displaystyle{ \square }[/math]
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]
- [math]\displaystyle{ A }[/math] is a nonsingular WDD M-matrix.
- [math]\displaystyle{ A }[/math] is a nonsingular WDD L-matrix;
- [math]\displaystyle{ A }[/math] 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 [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ n\times n }[/math] WCDD L-matrix, we can bound its inverse as follows:[6]
- [math]\displaystyle{ \left\Vert A^{-1}\right\Vert _{\infty}\leq\sum_{i}\left[a_{ii}\prod_{j=1}^{i}(1-u_{j})\right]^{-1} }[/math] where [math]\displaystyle{ u_{i}=\frac{1}{\left|a_{ii}\right|}\sum_{j=i+1}^{n}\left|a_{ij}\right|. }[/math]
Note that [math]\displaystyle{ u_n }[/math] is always zero and that the right-hand side of the bound above is [math]\displaystyle{ \infty }[/math] whenever one or more of the constants [math]\displaystyle{ u_i }[/math] 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
- [math]\displaystyle{ u^{\prime \prime}(x) + g(x)= 0 }[/math] for [math]\displaystyle{ x \in (0,1) }[/math]
with Dirichlet boundary conditions [math]\displaystyle{ u(0)=u(1)=0 }[/math]. Letting [math]\displaystyle{ \{0,h,2h,\ldots,1\} }[/math] be a numerical grid (for some positive [math]\displaystyle{ h }[/math] that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of
- [math]\displaystyle{ -\frac{1}{h^2}A\vec{u} + \vec{g} = 0 }[/math] where [math]\displaystyle{ [\vec{g}]_j = g(jh) }[/math]
and
- [math]\displaystyle{ A = \begin{pmatrix}2 & -1\\ -1 & 2 & -1\\ & -1 & 2 & -1\\ & & \ddots & \ddots & \ddots\\ & & & -1 & 2 & -1\\ & & & & -1 & 2 \end{pmatrix}. }[/math]
Note that [math]\displaystyle{ A }[/math] is a WCDD L-matrix.
References
- ↑ Shivakumar, P. N.; Chew, Kim Ho (1974). "A Sufficient Condition for Nonvanishing of Determinants". Proceedings of the American Mathematical Society 43 (1): 63. doi:10.1090/S0002-9939-1974-0332820-0. ISSN 0002-9939. http://www.ams.org/journals/proc/1974-043-01/S0002-9939-1974-0332820-0/S0002-9939-1974-0332820-0.pdf.
- ↑ Azimzadeh, Parsiad; Forsyth, Peter A. (2016). "Weakly Chained Matrices, Policy Iteration, and Impulse Control". SIAM Journal on Numerical Analysis 54 (3): 1341–1364. doi:10.1137/15M1043431. ISSN 0036-1429.
- ↑ 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. doi:10.1090/mcom/3347. Bibcode: 2017arXiv170106951A.
- ↑ 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 [math]\displaystyle{ \Vert A^{-1}\Vert _{\infty} }[/math] 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 [math]\displaystyle{ \Vert A^{-1}\Vert _{\infty} }[/math] 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 [math]\displaystyle{ \Vert A^{-1}\Vert _{\infty} }[/math] 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.
Original source: https://en.wikipedia.org/wiki/Weakly chained diagonally dominant matrix.
Read more |