Weakly chained diagonally dominant matrix

We say row $i$ of a complex matrix $A\; =\; (a\_\{ij\})$ is strictly diagonally dominant (SDD) if $|a\_\{ii\}|>\backslash textstyle\{\backslash sum\_\{j\backslash neq\; i\}\}|a\_\{ij\}|$. We say $A$ is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with $\backslash geq$ instead.

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

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

• $A$ is WDD and
• for each row $i\_1$ that is not SDD, there exists a walk $i\_1\; \backslash rightarrow\; i\_2\; \backslash rightarrow\; \backslash cdots\; \backslash rightarrow\; i\_k$ in the directed graph of $A$ ending at an SDD row $i\_k$.

File:Graph of a WCDD matrix.png

The $m\; \backslash times\; m$ matrix

:$\backslash begin\{pmatrix\}1\backslash \backslash$

-1 & 1\\

& -1 & 1\\

& & \ddots & \ddots\\

& & & -1 & 1

\end{pmatrix}

is WCDD.

A WCDD matrix is nonsingular.{{cite journal|last1=Shivakumar|first1=P. N.|last2=Chew|first2=Kim Ho|title=A Sufficient Condition for Nonvanishing of Determinants|journal=Proceedings of the American Mathematical Society|volume=43|issue=1|year=1974|pages=63|issn=0002-9939|doi=10.1090/S0002-9939-1974-0332820-0|url=http://www.ams.org/journals/proc/1974-043-01/S0002-9939-1974-0332820-0/S0002-9939-1974-0332820-0.pdf|doi-access=free}}

Proof:{{cite journal|last1=Azimzadeh|first1=Parsiad|last2=Forsyth|first2=Peter A.|title=Weakly Chained Matrices, Policy Iteration, and Impulse Control|journal=SIAM Journal on Numerical Analysis|volume=54|issue=3|year=2016|pages=1341–1364|issn=0036-1429|doi=10.1137/15M1043431|arxiv=1510.03928|s2cid=29143430 }}

Let $A=(a\_\{ij\})$ be a WCDD matrix. Suppose there exists a nonzero $x$ in the null space of $A$.

Without loss of generality, let $i\_1$ be such that $|x\_\{i\_1\}|=1\backslash geq|x\_j|$ for all $j$.

Since $A$ is WCDD, we may pick a walk $i\_1\backslash rightarrow\; i\_2\backslash rightarrow\backslash cdots\backslash rightarrow\; i\_k$ ending at an SDD row $i\_k$.

Taking moduli on both sides of

:$-a\_\{i\_1\; i\_1\}x\_\{i\_1\}\; =\; \backslash sum\_\{j\backslash neq\; i\_1\}\; a\_\{i\_\{1\}\; j\}x\_j$

and applying the triangle inequality yields

:$\backslash left|a\_\{i\_1\; i\_1\}\backslash right|\backslash leq\backslash sum\_\{j\backslash neq\; i\_1\}\backslash left|a\_\{i\_1\; j\}\backslash right|\backslash left|x\_j\backslash right|\backslash leq\backslash sum\_\{j\backslash neq\; i\_1\}\backslash left|a\_\{i\_1\; j\}\backslash right|,$

and hence row $i\_1$ is not SDD.

Moreover, since $A$ is WDD, the above chain of inequalities holds with equality so that $|x\_\{j\}|=1$ whenever $a\_\{i\_1\; j\}\backslash neq0$.

Therefore, $|x\_\{i\_2\}|=1$.

Repeating this argument with $i\_2$, $i\_3$, etc., we find that $i\_k$ is not SDD, a contradiction. $\backslash 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.{{cite book|last1=Horn|first1=Roger A.|last2=Johnson|first2=Charles R.|title=Matrix analysis|year=1990|publisher=Cambridge University Press, Cambridge}}

The following are equivalent:{{cite journal|last1=Azimzadeh|first1=Parsiad|title=A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-Matrix|journal=Mathematics of Computation|year=2019|volume=88|issue=316|pages=783–800|doi=10.1090/mcom/3347|arxiv=1701.06951|bibcode=2017arXiv170106951A|s2cid=3356041 }}

• $A$ is a nonsingular WDD M-matrix.
• $A$ is a nonsingular WDD L-matrix;
• $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{{cite journal|last1=Bramble|first1=James H.|last2=Hubbard|first2=B. E.|journal=Journal of Mathematical Physics|volume=43|year=1964|pages=117–132|title=On a finite difference analogue of an elliptic problem which is neither diagonally dominant nor of non-negative type|doi=10.1002/sapm1964431117}} in which they appear under the alternate name of matrices of positive type.

Moreover, if $A$ is an $n\backslash times\; n$ WCDD L-matrix, we can bound its inverse as follows:{{cite journal|last1=Shivakumar|first1=P. N.|last2=Williams|first2=Joseph J.|last3=Ye|first3=Qiang|last4=Marinov|first4=Corneliu A.|title=On Two-Sided Bounds Related to Weakly Diagonally Dominant M-Matrices with Application to Digital Circuit Dynamics|journal=SIAM Journal on Matrix Analysis and Applications|volume=17|issue=2|year=1996|pages=298–312|issn=0895-4798|doi=10.1137/S0895479894276370}}

:$\backslash left\backslash Vert\; A^\{-1\}\backslash right\backslash Vert\; \_\{\backslash infty\}\backslash leq\backslash sum\_\{i\}\backslash left[a\_\{ii\}\backslash prod\_\{j=1\}^\{i\}(1-u\_\{j\})\backslash right]^\{-1\}$   where   $u\_\{i\}=\backslash frac\{1\}\{\backslash left|a\_\{ii\}\backslash right|\}\backslash sum\_\{j=i+1\}^\{n\}\backslash left|a\_\{ij\}\backslash right|.$

Note that $u\_n$ is always zero and that the right-hand side of the bound above is $\backslash infty$ whenever one or more of the constants $u\_i$ is one.

Tighter bounds for the inverse of a WCDD L-matrix are known.{{cite journal|last1=Cheng|first1=Guang-Hui|last2=Huang|first2=Ting-Zhu|title=An upper bound for $\backslash Vert\; A^\{-1\}\backslash Vert\; \_\{\backslash infty\}$ of strictly diagonally dominant M-matrices|journal=Linear Algebra and Its Applications|volume=426|issue=2–3|year=2007|pages=667–673|issn=0024-3795|doi=10.1016/j.laa.2007.06.001|doi-access=free}}{{cite journal|last1=Li|first1=Wen|title=The infinity norm bound for the inverse of nonsingular diagonal dominant matrices|journal=Applied Mathematics Letters|volume=21|issue=3|year=2008|pages=258–263|issn=0893-9659|doi=10.1016/j.aml.2007.03.018|doi-access=free}}{{cite journal|last1=Wang|first1=Ping|title=An upper bound for $\backslash Vert\; A^\{-1\}\backslash Vert\; \_\{\backslash infty\}$ of strictly diagonally dominant M-matrices|journal=Linear Algebra and Its Applications|volume=431|issue=5–7|year=2009|pages=511–517|issn=0024-3795|doi=10.1016/j.laa.2009.02.037|doi-access=free}}{{cite journal|last1=Huang|first1=Ting-Zhu|last2=Zhu|first2=Yan|title=Estimation of $\backslash Vert\; A^\{-1\}\backslash Vert\; \_\{\backslash infty\}$ for weakly chained diagonally dominant M-matrices|journal=Linear Algebra and Its Applications|volume=432|issue=2–3|year=2010|pages=670–677|issn=0024-3795|doi=10.1016/j.laa.2009.09.012|doi-access=free}}

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

An example is given below.

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

For example, consider the one-dimensional Poisson problem

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

with Dirichlet boundary conditions $u(0)=u(1)=0$.

Letting $\backslash \{0,h,2h,\backslash ldots,1\backslash \}$ be a numerical grid (for some positive $h$ that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of

:$-\backslash frac\{1\}\{h^2\}A\backslash vec\{u\}\; +\; \backslash vec\{g\}\; =\; 0$   where   $[\backslash vec\{g\}]\_j\; =\; g(jh)$

and

:

-1 & 2 & -1\\

& -1 & 2 & -1\\

& & \ddots & \ddots & \ddots\\

& & & -1 & 2 & -1\\

& & & & -1 & 2

\end{pmatrix}.

Note that $A$ is a WCDD L-matrix.

{{reflist}}

Category:Matrices (mathematics)