---
title: "Diagonally Dominant Matrices"
output:
  html_document:
    css: EML3041HTMLbook.css
    keep_md: no
    number_sections: no
    toc: yes
    toc_depth: 4
    toc_float: yes
    theme: readable
---

```{r setup, include=FALSE}
#library(prettydoc)
knitr::opts_chunk$set(echo = TRUE)
```


#### What is a diagonally dominant matrix?

A $n \times n$ square matrix $[A]$ is a diagonally dominant matrix if

$$\left|a_{ii}\right| \geq \sum^n_{\substack{j=1\\ i \neq j}} \left|a_{ij}\right| \text{ for } i=1,2,....,n$$

that is, for each row, the absolute value (also called magnitude) of the diagonal element is greater than or equal to the sum of the absolute values of the rest of the elements of that row.

**Example 1**

Give examples of matrices that are diagonally dominant and those that are not diagonally dominant.

*Solution*

The matrix

$$[A]=\begin{bmatrix}15 & 6 & 7\\ 2 & -4.1 & -2 \\ 3 & 2 & 6\end{bmatrix}$$

is a diagonally dominant matrix.

Why? Because for each and every row, the answer to the question below is Yes.

Row 1: Is $\left|a_{11}\right| \geq\left|a_{12}\right|+\left|a_{13}\right|$ ? Yes, because

$$\left|a_{11}\right|=|15|=15,\left|a_{12}\right|+\left|a_{13}\right|=|6|+|7|=13,15 \geq 13$$

Row 2: Is $\left|a_{22}\right| \geq\left|a_{21}\right|+\left|a_{23}\right|$ ? Yes, because

$$\left|a_{22}\right|=|-4.1|=4.1,\left|a_{21}\right|+\left|a_{23}\right|=|2|+|-2|=4,4.1 \geq 4$$

Row 3: Is $\left|a_{33}\right| \geq\left|a_{31}\right|+\left|a_{32}\right|$ ? Yes, because

$$\left|a_{33}\right|=|6|=6,\left|a_{31}\right|+\left|a_{32}\right|=|3|+|2|=5,6 \geq 5$$

------------------------------------------------------------------------

The matrix

$$[B] = \begin{bmatrix} -15 & 6 & 9 \\ 2 & -4 & -2 \\ 3 & -2 & 5 \end{bmatrix}$$

is a diagonally dominant matrix.

Why? Because for each and every row, the answer to the question below is Yes.

Row 1: Is $\left|b_{11}\right| \geq\left|b_{12}\right|+\left|b_{13}\right|$ ? Yes, because

$$\left|b_{11}\right|=|15|=15,\left|b_{12}\right|+\left|b_{13}\right|=|6|+|9|=15,15 \geq 15$$

Row 2: Is $\left|b_{22}\right| \geq\left|b_{21}\right|+\left|b_{23}\right|$ ? Yes, because

$$\left|b_{22}\right|=|-4|=4, \quad\left|b_{21}\right|+\left|b_{23}\right|=|2|+|-2|=4,4 \geq 4$$

Row 3: Is $\left|b_{33}\right| \geq\left|b_{31}\right|+\left|b_{32}\right|$? Yes, because

$$\left|b_{33}\right|=|5|=5,\left|b_{31}\right|+\left|b_{32}\right|=|3|+|2|=5,5 \geq 5$$

------------------------------------------------------------------------

The matrix

$$[C] = \begin{bmatrix} -15 & 6 & 9 \\ 2 & -4.1 & -2 \\ 3 & -2 & 5 \end{bmatrix}$$

is a diagonally dominant matrix.

Why? Because for each and every row, the answer to the question below is Yes.

Row 1: Is $\left|c_{11}\right| \geq\left|c_{12}\right|+\left|c_{13}\right|$? Yes, because

$$\left|c_{11}\right|=|15|=15,\left|c_{12}\right|+\left|c_{13}\right|=|6|+|9|=15,15 \geq 15$$

Row 2: Is $\left|c_{22}\right| \geq\left|c_{21}\right|+\left|c_{23}\right|$? Yes, because

$$\left|c_{22}\right|=|-4.1|=4,\left|c_{21}\right|+\left|c_{23}\right|=|2|+|-2|=4,4.1 \geq 4$$

Row 3: Is $\left|c_{33}\right| \geq\left|c_{31}\right|+\left|c_{32}\right|$? Yes, because

$$\left|c_{33}\right|=|5|,\left|c_{31}\right|+\left|c_{32}\right|=|3|+|2|=5,5 \geq 5$$

------------------------------------------------------------------------

The matrix

$$[D] = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \end{bmatrix}$$

is not a diagonally dominant matrix.

Why? Because for each and every row, the answer to the question below is not a Yes.

Row 1: Is $\left|d_{11}\right| \geq\left|d_{12}\right|+\left|d_{13}\right|$? Yes, because

$$\left|d_{11}\right|=\left|25\right|=25 ,\left|d_{12}\right|+\left|d_{13}\right|=|5|+|1|=6,25 \geq 6$$

Row 2: Is $\left|d_{22}\right| \geq\left|d_{21}\right|+\left|d_{23}\right|$? No, because

$$\left|d_{22}\right|=|8|=8, \left|d_{21}\right|+\left|d_{23}\right|=|64|+|1|=65,8<65$$

Row 3: Is $\left|d_{33}\right| \geq\left|d_{31}\right|+\left|d_{32}\right|$? No, because

$$\left|d_{33}\right|=|1|=1,\left|d_{31}\right|+\left|d_{32}\right|=|144|+|12|=156,  1<156$$

  

------------------------------------------------------------------------

#### What is a weak diagonally dominant matrix?

The answer is simple -- the definition of a weak(ly) diagonally dominant matrix is identical to that of a diagonally dominant matrix as the inequality used for the check is a weak inequality of greater than or equal to ($\geq$).  

------------------------------------------------------------------------

#### What is a strictly diagonally dominant matrix?

A $n \times n$ square matrix is a strictly diagonally dominant matrix if

$$\left|a_{ii}\right| > \sum^n_{\substack{j=1\\ i \neq j}} \left|a_{ij}\right| \text{ for } i=1,2,....,n$$

that is, for each row, the absolute value of the diagonal element is strictly greater than the sum of the absolute values of the rest of the elements of that row.

**Example 2**

Give examples of strictly diagonally dominant matrices and not strictly diagonally dominant matrices.

*Solution*

The matrix

$$[A] = \begin{bmatrix} 15 & 6 & 7 \\ 2 & -4.1 & -2 \\ 3 & 2 & 6 \end{bmatrix}$$

is a strictly diagonally dominant matrix

Why? Because for each and every row, the answer to the question below is Yes.

Row 1: Is $\left|a_{11}\right| >\left|a_{12}\right|+\left|a_{13}\right|$? Yes, because

$$\left|a_{11}\right|=|15|=15,\left|a_{12}\right|+\left|a_{13}\right|=|6|+|7|=13,15>13 .$$

Row 2: Is $\left|a_{22}\right| >\left|a_{21}\right|+\left|a_{23}\right|$? Yes, because

$$\left|a_{22}\right|=|-4.1|=4.1,\left|a_{21}\right|+\left|a_{23}\right|=|2|+|-2|=4,4.1>4$$

Row 3: Is $\left|a_{33}\right| > \left|a_{31}\right|+\left|a_{32}\right|$? Yes, because

$$\left|a_{33}\right|=|6|=6,\left|a_{31}\right|+\left|a_{32}\right|=|3|+|2|=5,6>5$$

------------------------------------------------------------------------

The matrix

$$[B]=\begin{bmatrix} 13 & 6 & 7 \\ 2 & -4.1 & -2 \\ 3 & 2 & 6 \end{bmatrix}$$

is a not a strictly diagonally dominant matrix

Why? Because for each and every row, the answer to the question below is not a Yes.

Row 1: Is $\left|b_{11}\right| > \left|b_{12}\right|+\left|b_{13}\right|$? No, because

$$\left|b_{11}\right|=|13|=13,\left|b_{12}\right|+\left|b_{13}\right|=|6|+|7|=13,13 = 13$$

Row 2: Is $\left|b_{22}\right| >\left|b_{21}\right|+\left|b_{23}\right|$? Yes, because

$$\left|b_{22}\right|=|-4.1|=4.1,\left|b_{21}\right|+\left|b_{23}\right|=|2|+|-2|=4,4.1>4$$

Row 3: Is $\left|b_{33}\right| >\left|b_{31}\right|+\left|b_{32}\right|$? Yes, because

$$\left|b_{33}\right|=|6|=6,\left|b_{31}\right|+\left|b_{32}\right|=|3|+|2|=5,6>5$$

------------------------------------------------------------------------

The matrix

$$[C]=\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \end{bmatrix}$$

is not a strictly diagonally dominant matrix.

Why? Because for each and every row, the answer to the question below is not a Yes.

Row 1: Is $\left|c_{11}\right| \geq\left|c_{12}\right|+\left|c_{13}\right|$? Yes, because

$$\left|c_{11}\right|=|25|=25,\left|c_{12}\right|+\left|c_{13}\right|=|5|+|1|=6,25>6$$

Row 2: Is $\left|c_{22}\right| \geq\left|c_{21}\right|+\left|c_{23}\right|$? No, because

$$\left|c_{22}\right|=|8|=8, \left|c_{21}\right|+\left|c_{23}\right|=|64|+|1|=65,8<65$$

Row 3: Is $\left|c_{33}\right| \geq\left|c_{31}\right|+\left|c_{32}\right|$? No, because

$$\left|c_{33}\right|=|1|=1, c_{31}|+| c_{32}|=| 144|+| 12 \mid=156,  1<156$$

  

#### What is an irreducible diagonally dominant matrix?

A $n \times n$ square matrix is an irreducible diagonally dominant matrix if

$$[A]\ \text{is irreducible},$$

$$\left|a_{ii}\right| \geq \sum^n_{\substack{j=1\\ i \neq j}} \left|a_{ij}\right| \text{ for } i=1,2,....,n\ \text{and}$$

$$\left|a_{ii}\right| > \sum^n_{\substack{j=1\\ i \neq j}} \left|a_{ij}\right| \text{ for at least one row, } i=1,2,....,n$$

The second condition means that for each row, the absolute value (also called magnitude) of the diagonal element is greater than or equal to the sum of the absolute values of the rest of the elements of that row. The third condition means that for at least one row, the absolute value (also called magnitude) of the diagonal element is greater than the sum of the absolute values of the rest of the elements of that row.

------------------------------------------------------------------------

**Example 3**

Give examples of matrices that are irreducibly diagonally dominant and those that are not irreducibly diagonally dominant.

*Solution*

The matrix

$$[A]=\begin{bmatrix} 15 & 6 & 7 \\ 2 & -4.1 & -2 \\ 3 & 2 & 6 \end{bmatrix}$$

is an irreducible diagonally dominant matrix. Why? Because $[A]$ irreducible and the answer to every question below is Yes.

Row 1: Is $\left|a_{11}\right| \geq\left|a_{12}\right|+\left|a_{13}\right|$? Yes, because

$$\left|a_{11}\right|=|15|,\left|a_{12}\right|+\left|a_{13}\right|=|6|+|7|=13,15>13 .$$

Row 2: Is $\left|a_{22}\right| \geq\left|a_{21}\right|+\left|a_{23}\right|$? Yes, because

$$\left|a_{22}\right|=|-4.1|=4.1,\left|a_{21}\right|+\left|a_{23}\right|=|2|+|-2|=4,4.1>4$$

Row 3: Is $\left|a_{33}\right| \geq\left|a_{31}\right|+\left|a_{32}\right|$? Yes, because

$$\left|a_{33}\right|=|6|\left|a_{31}\right|+\left|a_{32}\right|=|3|+|2|=5,6>5$$

Is the inequality satisfied strictly for at least one row? Yes, it is satisfied for Row 1 (Row 2 and Row 3 do too satisfy the inequality strictly but is not necessary)

------------------------------------------------------------------------

The matrix

$$[B]=\begin{bmatrix} -15 & 6 & 9 \\ 2 & -4 & -2 \\ 3 & -2 & 5 \end{bmatrix}$$

is a not an irreducible diagonally dominant matrix. Why? Because $[B]$ irreducible but the answer to every question below is not a Yes.

Row 1: Is $\left|b_{11}\right| \geq\left|b_{12}\right|+\left|b_{13}\right|$? Yes, because

$$\left|b_{11}\right|=|15|=15,\left|b_{12}\right|+\left|b_{13}\right|=|6|+|9|=15,15 \geq 15$$

Row 2: Is $\left|b_{22}\right| \geq\left|b_{21}\right|+\left|b_{23}\right|$? Yes, because

$$\left|b_{22}\right|=|-4|=4, \left|b_{21}\right|+\left|b_{23}\right|=|2|+|-2|=4,4 \geq 4$$

Row 3: Is $\left|b_{33}\right| \geq\left|b_{31}\right|+\left|b_{32}\right|$? Yes, because

$$\left|b_{33}\right|=|5|=5,\left|b_{31}\right|+\left|b_{32}\right|=|3|+|2|=5,5 \geq 5$$

Is the inequality satisfied strictly for at least one row? No.

------------------------------------------------------------------------

The matrix

$$[C]=\begin{bmatrix} -15 & 6 & 9 \\ 2 & -4.1 & -2 \\ 3 & -2 & 5 \end{bmatrix}$$

is an irreducible diagonally dominant matrix. Why? Because $[C]$ irreducible and the answer to every question below is Yes.

Row 1: Is $\left|c_{11}\right| \geq\left|c_{12}\right|+\left|c_{13}\right|$? Yes, because

$$\left|c_{11}\right|=|15|,\left|c_{12}\right|+\left|c_{13}\right|=|6|+|9|=15,15 \geq 15$$

Row 2: Is $\left|c_{22}\right| \geq\left|c_{21}\right|+\left|c_{23}\right|$? Yes, because

$$\left|c_{22}\right|=|-4.1|=4.1, \left|c_{21}\right|+\left|c_{23}\right|=|2|+|-2|=4,4.1 \geq 4$$

Row 3: Is $\left|c_{33}\right| \geq\left|c_{31}\right|+\left|c_{32}\right|$? Yes, because

$$\left|c_{33}\right|=|5|,\left|c_{31}\right|+\left|c_{32}\right|=|3|+|2|=5,5 \geq 5$$

Is the inequality satisfied strictly for at least one row? Yes, it is satisfied for Row 2.

------------------------------------------------------------------------

The matrix

$$[D]=\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \end{bmatrix}$$

is not an irreducible diagonally dominant matrix. Why? Because $[D]$ is irreducible but the answer to every question below is not a Yes.

Row 1: Is $\left|d_{11}\right| \geq\left|d_{12}\right|+\left|d_{13}\right|$? Yes, because

$$\left|d_{11}\right|=|25|=25,\left|d_{12}\right|+\left|d_{13}\right|=|5|+|1|=6,25>6$$

Row 2: Is $\left|d_{22}\right| \geq\left|d_{21}\right|+\left|d_{23}\right|$? No, because

$$\left|d_{22}\right|=|8|=8, \left|d_{21}\right|+\left|d_{23}\right|=|64|+|1|=65,8<65$$

Row 3: Is $\left|d_{33}\right| \geq\left|d_{31}\right|+\left|d_{32}\right|$? No, because

$$\left|d_{33}\right|=|1|=1,| d_{31}|+| d_{32}|=| 144|+| 12 \mid=156,  1<156$$

There is no need to check for strict inequality condition.

------------------------------------------------------------------------

#### What is an irreducible matrix?

A square matrix is called reducible matrix if the following is true. Take the indices $i=1,2,....,n$ and see if they can be divided into two disjoint nonempty sets $i_1,i_2,....,i_\alpha$ and $j_1,j_2,....,j_\beta$ such that

$$n=\alpha + \beta,\ \text{and}$$

and

$$a_{{i_k}{j_l}}=0,\ k=1,2,....,\alpha\ \text{and}\ l=1,2,....,\beta$$

If the square matrix is not reducible, it is called an irreducible matrix.

A square matrix $[A]$ is called reducible matrix if and only if for any perturbation matrix $[P]$, the matrix multiplication $[P]^T[A][P]$ results in a block upper triangular matrix.

------------------------------------------------------------------------

**Example 4**

Give examples of irreducible and reducible matrices.

*Solution*

The matrix

$$[A]=\begin{bmatrix} 0 & 5 & 7 \\ 8 & 0 & 0 \\ 10 & 0 & 0 \end{bmatrix}$$

is an irreducible matrix.

------------------------------------------------------------------------

The matrix

$$[B]=\begin{bmatrix} 5 & 0 & 0 \\ 0 & 4 & 6 \\ 10 & 0 & 0 \end{bmatrix}$$

is a reducible matrix. Why? Take the indices $i=1,2,3$ and see that they can be divided into two disjoint nonempty sets 1 and 2,3 such that,

$$\alpha = 1, \beta = 2,\ \text{giving}\ \alpha + \beta = 1+2 = 3,\ \text{and}$$

$$b_{{i_k}{j_l}}=0,\ k=1 \ \text{and}\ l = 1,2$$

------------------------------------------------------------------------

#### Implications of diagonally dominant matrices?

If a square matrix is strictly diagonally dominant

-   then the matrix is non-singular [1].

-   then if the matrix is symmetric with non-negative diagonal entries, the matrix is positive semi-definite [1].

-   then if the matrix is the coefficient matrix for a set of simultaneous linear equations, the iterative Gauss-Seidel numerical method will always converge [2].

-   then if the matrix is the coefficient matrix for a set of simultaneous linear equations, the iterative Jordan numerical method will always converge [2].

-   then if the diagonal entries of the matrix are positive, the real parts of the matrix eigenvalues are positive [1].

-   then if the diagonal entries of the matrix are negative, the real parts of the matrix eigenvalues are negative [1].

-   then if the matrix is column dominant, no pivoting is needed for Gaussian elimination [2].

-   then if the matrix is column dominant, no pivoting is needed for LU factorization [2].

If a square matrix is irreducible diagonally dominant

-   then if the matrix is the coefficient matrix for a set of simultaneous linear equations, the iterative Gauss-Seidel numerical method will always converge.

-   then if the matrix is the coefficient matrix for a set of simultaneous linear equations, the iterative Jordan numerical method will always converge.

-   the matrix is non-singular [2].

-   If a square matrix is diagonally dominant (also called weakly diagonally dominant)

-   then if the matrix is column dominant, no pivoting is needed for Gaussian elimination [3].

-   then if the matrix is column dominant, no pivoting is needed for LU factorization [3].

------------------------------------------------------------------------

#### References

[1] Briggs, Keith. "Diagonally Dominant Matrix." FromMathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. <http://mathworld.wolfram.com/DiagonallyDominantMatrix.html>

[2] Diagonally Dominant Matrix, see <https://en.wikipedia.org/wiki/Diagonally_dominant_matrix>, last accessed on November 4, 2016.

[3] "Lecture 4: A Gaussian Elimination Example", see <http://www.cs.yale.edu/homes/spielman/BAP/lect4.pdf>, last accessed on November 4, 2016.
