Misplaced Pages

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 ${\displaystyle i}$ of a complex matrix ${\displaystyle A=(a_{ij})}$ is strictly diagonally dominant (SDD) if ${\displaystyle |a_{ii}|>\textstyle {\sum _{j\neq i}}|a_{ij}|}$. We say ${\displaystyle A}$ is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with ${\displaystyle \geq }$ instead.

The directed graph associated with an ${\displaystyle m\times m}$ complex matrix ${\displaystyle A=(a_{ij})}$ is given by the vertices ${\displaystyle \{1,\ldots ,m\}}$ and edges defined as follows: there exists an edge from ${\displaystyle i\rightarrow j}$ if and only if ${\displaystyle a_{ij}\neq 0}$.

Definition

A complex square matrix ${\displaystyle A}$ is said to be weakly chained diagonally dominant (WCDD) if

• ${\displaystyle A}$ is WDD and
• for each row ${\displaystyle i_{1}}$ that is not SDD, there exists a walk ${\displaystyle i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{k}}$ in the directed graph of ${\displaystyle A}$ ending at an SDD row ${\displaystyle i_{k}}$.

Example

The ${\displaystyle m\times m}$ matrix

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

is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.

Proof: Let ${\displaystyle A=(a_{ij})}$ be a WCDD matrix. Suppose there exists a nonzero ${\displaystyle x}$ in the null space of ${\displaystyle A}$. Without loss of generality, let ${\displaystyle i_{1}}$ be such that ${\displaystyle |x_{i_{1}}|=1\geq |x_{j}|}$ for all ${\displaystyle j}$. Since ${\displaystyle A}$ is WCDD, we may pick a walk ${\displaystyle i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{k}}$ ending at an SDD row ${\displaystyle i_{k}}$.

Taking moduli on both sides of

${\displaystyle -a_{i_{1}i_{1}}x_{i_{1}}=\sum _{j\neq i_{1}}a_{i_{1}j}x_{j}}$

and applying the triangle inequality yields

${\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|,}$

and hence row ${\displaystyle i_{1}}$ is not SDD. Moreover, since ${\displaystyle A}$ is WDD, the above chain of inequalities holds with equality so that ${\displaystyle |x_{j}|=1}$ whenever ${\displaystyle a_{i_{1}j}\neq 0}$. Therefore, ${\displaystyle |x_{i_{2}}|=1}$. Repeating this argument with ${\displaystyle i_{2}}$, ${\displaystyle i_{3}}$, etc., we find that ${\displaystyle i_{k}}$ is not SDD, a contradiction. ${\displaystyle \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.

Relationship with nonsingular M-matrices

The following are equivalent:

• ${\displaystyle A}$ is a nonsingular WDD M-matrix.
• ${\displaystyle A}$ is a nonsingular WDD L-matrix;
• ${\displaystyle 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 in which they appear under the alternate name of matrices of positive type.

Moreover, if ${\displaystyle A}$ is an ${\displaystyle n\times n}$ WCDD L-matrix, we can bound its inverse as follows:

${\displaystyle \left\Vert A^{-1}\right\Vert _{\infty }\leq \sum _{i}\left^{-1}}$   where   ${\displaystyle u_{i}={\frac {1}{\left|a_{ii}\right|}}\sum _{j=i+1}^{n}\left|a_{ij}\right|.}$

Note that ${\displaystyle u_{n}}$ is always zero and that the right-hand side of the bound above is ${\displaystyle \infty }$ whenever one or more of the constants ${\displaystyle u_{i}}$ is one.

Tighter bounds for the inverse of a WCDD L-matrix are known.

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

${\displaystyle u^{\prime \prime }(x)+g(x)=0}$   for   ${\displaystyle x\in (0,1)}$

with Dirichlet boundary conditions ${\displaystyle u(0)=u(1)=0}$. Letting ${\displaystyle \{0,h,2h,\ldots ,1\}}$ be a numerical grid (for some positive ${\displaystyle h}$ that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of

${\displaystyle -{\frac {1}{h^{2}}}A{\vec {u}}+{\vec {g}}=0}$   where   ${\displaystyle _{j}=g(jh)}$

and

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

Note that ${\displaystyle A}$ is a WCDD L-matrix.

References

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 ${\displaystyle \Vert A^{-1}\Vert _{\infty }}$ 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 ${\displaystyle \Vert A^{-1}\Vert _{\infty }}$ 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 ${\displaystyle \Vert A^{-1}\Vert _{\infty }}$ 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.

• Matrices