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 of a complex matrix is strictly diagonally dominant if. We say is SDD if all of its rows are SDD. Weakly diagonally dominant is defined with instead.
The directed graph associated with an complex matrix is given by the vertices and edges defined as follows: there exists an edge from if and only if.

Definition

A complex square matrix is said to be weakly chained diagonally dominant if
The matrix
is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.
Proof:
Let be a WCDD matrix. Suppose there exists a nonzero in the null space of.
Without loss of generality, let be such that for all.
Since is WCDD, we may pick a walk ending at an SDD row.
Taking moduli on both sides of
and applying the triangle inequality yields
and hence row is not SDD.
Moreover, since is WDD, the [|above] chain of inequalities holds with equality so that whenever.
Therefore,.
Repeating this argument with,, etc., we find that is not SDD, a contradiction.
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 is nonsingular.

Relationship with nonsingular M-matrices

The following are equivalent:
In fact, WCDD L-matrices were studied as early as 1964 in a journal article in which they appear under the alternate name of matrices of positive type.
Moreover, if is an WCDD L-matrix, we can bound its inverse as follows:
Note that is always zero and that the right-hand side of the bound above is whenever one or more of the constants is one.
Tighter bounds for the inverse of a WCDD L-matrix are known.

Applications

Due to their relationship with M-matrices, 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
with Dirichlet boundary conditions.
Letting be a numerical grid, a monotone finite difference scheme for the Poisson problem takes the form of
and
Note that is a WCDD L-matrix.