Weakly chained diagonally dominant matrix

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

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 ${\displaystyle |a_{ii}|>\textstyle {\sum _{j\neq i}}|a_{ij}|}$. 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\times m$ complex matrix $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 $A$ is said to be weakly chained diagonally dominant (WCDD) if

• $A$ is WDD and
• for each row $i$ of $A$, there exists a path in the directed graph of $A$ from $i$ to an SDD row.

Note that if $i$ is itself an SDD row, the trivial path ${\displaystyle i\rightarrow i}$ satisfies the second requirement in the above definition.

Example

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 $i$ we start at, we can find a path ${\displaystyle i\rightarrow (i-1)\rightarrow (i-2)\rightarrow \cdots \rightarrow 1}$.

The matrix

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

is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.^[1][2]

Proof: Suppose $\lambda =0$ is an eigenvalue of the WCDD matrix $A=(a_{ij})$. Let $x$ be an associated nonzero eigenvector with components of modulus at most unity. Let $r$ be such that ${\displaystyle |x_{r}|=1\geq |x_{j}|}$ for all $j$. Since $A$ is WCDD, there is a path ${\displaystyle i\rightarrow i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{n}}$ such that ${\displaystyle i_{n}}$ is SDD. By the Gershgorin circle theorem,

${\displaystyle \left|\lambda -a_{ii}\right|=\left|a_{ii}\right|\leq \sum _{j\neq i}\left|a_{ij}\right|\left|x_{j}\right|\leq \sum _{j\neq i}\left|a_{ij}\right|.}$

Since $A$ is WDD, it follows that ${\displaystyle |a_{ii}|=\textstyle {\sum _{j\neq r}}|a_{ij}|}$, and hence $i$ is not SDD. Therefore, the above inequalities hold with equality, so that ${\displaystyle |x_{j}|=1}$ whenever ${\displaystyle |a_{ij}|\neq 0}$. Repeating the same argument as above with ${\displaystyle i=i_{1}}$, ${\displaystyle i=i_{2}}$, etc., we find that ${\displaystyle i_{n}}$ 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 M-matrices

The following are equivalent:^[1]

• $A$ is a nonsingular WDD L-matrix;
• $A$ is a WCDD L-matrix;
• $A$ is a WDD M-matrix.

In fact, WCDD L-matrices were studied (by James H. Bramble and B. E. Hubbard) as early as 1964 in a journal article^[4] in which they appear under the alternate name of matrices of positive type.

Moreover, if $A$ is a WCDD L-matrix, we can bound its inverse as follows:^[5]

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

Tighter bounds for the inverse of a WCDD L-matrix are known.^[6][7]

Applications

Due to their relationship with M-matrices (see above), WCDD matrices appear often in practical applications. Some examples are given below.

Markov decision processes

Consider a Markov chain on the finite state space $\{1,\ldots ,m\}$. Let ${\displaystyle \{\pi \}}$ be a (finite) set of stationary policies and ${\displaystyle P(\pi )}$ be the transition matrix for the chain under policy $\pi$. Let ${\displaystyle \rho (\pi )\in [0,1]^{m}}$ denote an $m$-vector corresponding to the discount factor at each state of the Markov chain. Because each ${\displaystyle P(\pi )}$ is a right stochastic matrix, ${\displaystyle \{I-\operatorname {diag} (\rho (\pi ))P(\pi )\}}$ is a family of WDD L-matrices. Convergence of R. A. Howard's policy iteration algorithm to the solution of a Markov decision process is guaranteed whenever this family consists only of inverse-positive matrices.^[8] This occurs if and only if each member of the family is WCDD.^[1]

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)=f(x)}$   for   $x\in (0,1)$

with Dirichlet boundary conditions $u(0)=u(1)=0$. Letting ${\displaystyle \{0,h,2h,\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

${\displaystyle A{\vec {u}}={\vec {f}}}$   where   ${\displaystyle {\vec {f}}_{j}=f(jh)}$

and

${\displaystyle A={\frac {1}{h^{2}}}{\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.

References

1. 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.
2. 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.
3. Horn, Roger A.; Johnson, Charles R. (1990). "Matrix analysis". Cambridge University Press, Cambridge.
4. 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.
5. 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.
6. 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.
7. 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.
8. Bokanowski, Olivier; Maroso, Stefania; Zidani, Hasnaa (2009). "Some Convergence Results for Howard's Algorithm". SIAM Journal on Numerical Analysis. 47 (4): 3001–3026. doi:10.1137/08073041X. ISSN 0036-1429.