title: Weakly chained diagonally dominant matrix
text: # 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_{ij})$ is strictly diagonally dominant (SDD) if $|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 $\{1,\ldots ,m\}$ and edges defined as follows: there exists an edge from $i\rightarrow j$ if and only if $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_{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
  
      ${\begin{pmatrix}1\\-1&1\\&-1&1\\&&\ddots &\ddots \\&&&-1&1\end{pmatrix}}$
  
  is WCDD.
  
  ## Properties
  
  ### Nonsingularity
  
  A WCDD matrix is nonsingular.
  
  Proof: 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\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_{i_{1}i_{1}}x_{i_{1}}=\sum _{j\neq i_{1}}a_{i_{1}j}x_{j}$
  
  and applying the triangle inequality yields
  
      $\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 $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}\neq 0$. Therefore, $|x_{i_{2}}|=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^{-1}\right\Vert _{\infty }\leq \sum _{i}\left[a_{ii}\prod _{j=1}^{i}(1-u_{j})\right]^{-1}$ where $u_{i}={\frac {1}{\left|a_{ii}\right|}}\sum _{j=i+1}^{n}\left|a_{ij}\right|.$
  
  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^{\prime \prime }(x)+g(x)=0$ for $x\in (0,1)$
  
  with Dirichlet boundary conditions $u(0)=u(1)=0$. Letting $\{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
  
      $-{\frac {1}{h^{2}}}A{\vec {u}}+{\vec {g}}=0$ where $[{\vec {g}}]_{j}=g(jh)$
  
  and
  
      $A={\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.
  
  