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 $i$ of a complex matrix $A = (a_)$ is strictly diagonally dominant (SDD) if $, a_, >\textstyle, a_,$. 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_)$ is given by the vertices $\$ and edges defined as follows: there exists an edge from $i \rightarrow j$ if and only if $a_ \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_1$ that is ''not'' SDD, there exists a walk $i_1 \rightarrow i_2 \rightarrow \cdots \rightarrow i_k$ in the directed graph of $A$ ending at an SDD row $i_k$.

Example

The $m \times m$ matrix
:$\begin1\\ -1 & 1\\ & -1 & 1\\ & & \ddots & \ddots\\ & & & -1 & 1 \end$
is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.

''Proof'':
Let $A=(a_)$ 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_, =1\geq, x_j,$ for all $j$.
Since $A$ is WCDD, we may pick a walk $i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_k$ ending at an SDD row $i_k$.

Taking moduli on both sides of
:$-a_x_ = \sum_ a_x_j$
and applying the triangle inequality yields
:$\left, a_\\leq\sum_\left, a_\\left, x_j\\leq\sum_\left, a_\,$
and hence row $i_1$ is not SDD.
Moreover, since $A$ is WDD, the above chain of inequalities holds with equality so that $, x_, =1$ whenever $a_\neq0$.
Therefore, $, x_, =1$.
Repeating this argument with $i_2$, $i_3$, etc., we find that $i_k$ 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.

Relationship with nonsingular M-matrices

The following are equivalent:
* $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 in which they appear under the alternate name of ''matrices of positive type''.

Moreover, if $A$ is an $n\times n$ WCDD L-matrix, we can bound its inverse as follows:
:\left\Vert A^\right\Vert _\leq\sum_\left _\prod_^(1-u_)\right   where   $u_=\frac\sum_^\left, a_\.$
Note that $u_n$ is always zero and that the right-hand side of the bound above is $\infty$ whenever one or more of the constants $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
:$u^(x) + g(x)= 0$   for   $x \in (0,1)$
with Dirichlet boundary conditions $u(0)=u(1)=0$.
Letting $\$ be a numerical grid (for some positive $h$ that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of
:$-\fracA\vec + \vec = 0$   where   $$vecj = g(jh)
and
:$A = \begin2 & -1\\ -1 & 2 & -1\\ & -1 & 2 & -1\\ & & \ddots & \ddots & \ddots\\ & & & -1 & 2 & -1\\ & & & & -1 & 2 \end.$
Note that $A$ is a WCDD L-matrix.

References

{{reflist

Matrices