[Math] Relationship between Diagonally dominant and Well Conditioned matrices

matricesnumerical linear algebranumerical methods

While solving linear systems by iterative methods is common pay attention to Diagonally dominant matrices, equivalently when studying stability of interpolation methods (and other kind of approximations) we look for well conditioned matrices to avoid huge oscillations with a small change in the system.

I'm looking for any relationships between well-conditioned matrices and diagonally dominant matrices and for bounds in $\kappa$ constant.

For sake of completeness I will define the subjects involved in my question

Definition 1 (Well conditioned matrix): Let $A$ be a matrix, and $\|\cdot\|$ a matrix norm. We call $A$ well conditioned if:

$$
\kappa_{\| \cdot \| }(A) = \| A \| \cdot \|A^{-1} \| \approx 1
$$

When $\kappa_{\| \cdot \| } \gg 1 $ we call it ill conditioned. And $\kappa_{\| \cdot \| }(A)$ is the condition number related to the matrix $A$ and the norm.

Definition 2 (Diagonally dominant matrix): Let $A$ be a square matrix rank $n$, we call it diagonally dominant if for each $i$ row:

$$
|a_{ii}| \ge \sum_{i \ne j}^n | a_{ij} | \; \forall i
$$

Best Answer

Matrices which are diagonally dominant can be arbitrarily ill-conditioned. As a specific example, we consider the one dimension discrete Laplacian $L_n$ of dimension $n$. Here the condition number is $\kappa_2(L_n) = O(n^2)$.

However, a matrix $A$ which is strictly diagonally dominant by rows with dominance factor $\epsilon$ is at most a row scaling away from a matrix $D^{-1}A$ which has condition number $$\kappa_\infty(D^{-1} A) \leq \frac{1 + \epsilon}{1 - \epsilon}.$$

The proof follows now. The dominance factor $\epsilon_i$ corresponding to the $i$th row, is given by $$\epsilon_i = \frac{\sum_{j\not=i} |a_{ij}|}{|a_{ii}|} < 1.$$ The dominance factor $\epsilon$ is given by $$\epsilon = \max \epsilon_i < 1.$$ It follows, that $$ \sum_{j\not =i} |a_{ij}| \leq \epsilon |a_{ii}|,$$ for each row. Now let $D$ denote the diagonal of $A$. Then $D$ is nonsingular because $A$ is strictly diagonally dominant and $$B = D^{-1}A = I - E$$ where $$\|E\|_\infty = \epsilon.$$ The triangle inequality implies that $$\|B\|_\infty \leq 1 + \epsilon.$$ Moreover, $\|E\|_\infty < 1$ implies that $B$ is nonsingular with $$B^{-1} = \sum_{j=0}^\infty E^j.$$ It follows, that $$\|B^{-1}\|_\infty \leq \sum_{j=0}^\infty \epsilon^j = \frac{1}{1 - \epsilon}.$$ The inequality $$\kappa_\infty(D^{-1} A) \leq \frac{1 + \epsilon}{1 - \epsilon}$$ follows readily. Similar definitions and results apply to matrices which are strictly diagonally dominant by columns.

Sadly, matrices with small values of $\epsilon$ are not frequently occurring.

Related Question