Prove that if $A \in \mathcal{M}_n$ is a strictly diagonally dominant matrix then it admits an $A=M-N$ decomposition.

Question

Given an $A \in \mathcal M_n$ matrix which is strictly diagonally dominant, meaning that $$|a_{ii}| > \sum_{j=1 j \neq i}^n |a_{ij}|$$ Prove that it admits a decomposition $A=M-N$ such that $m_{ii} = a_{ii}$ and $|m_{ii}| > \displaystyle\sum_{j=1 j \neq i} (|m_{ij}| + |n_{ij}|)$. Moreover, it verifies that if $i \neq j$ and $a_{ij} \neq 0$, then $m_{ij},n_{ij} \neq 0$

My attempt

In order to prove this result, first of all I can easily define $m_{ii} = a_{ii}$, and now check the second condition is verified. $$|m_{ii}| = |a_{ii}| > \sum_{j=1 j \neq i}^n |a_{ij}| = \sum_{j=1 j \neq i}^n |m_{ij} - n_{ij}|$$ Using triangular inequality: $$|m_{ii}| > \sum_{j=1 j \neq i}^n |m_{ij} - n_{ij}| \geq \sum_{j=1 j \neq i}^n |m_{ij}| - |n_{ij}|$$ This is where I get stuck since I seem to get just the opositte operation of what it is asked. I think I may be going in the wrong direction, but I can't think of other way to solve the problem. Any help is truly appreciated.

Answer 1

If the last condition didn't exist, you could simply set $N = 0$ and $M = A$. So the idea is to start with this and add a little perturbation on $N$. Take $\varepsilon \in \mathbb{C}^*$ small (or $\mathbb{R}^*$ if you have real matrices, you didn't specify it) and consider $n_{ij} = \varepsilon$ if $i \neq j$, $0$ else and $M = A + N$.

As $\varepsilon \neq 0$, the last condition is fulfilled and the fact that $N$ has a null diagonal implies that for all $i$, $m_{ii} = a_{ii}$. All what we have left to check is the inequalities. Let $1 \leqslant i \leqslant n$. \begin{align*} |m_{ii}| - \sum_{j \neq i} (|m_{ij}| + |n_{ij}|) & = |a_{ii}| - \sum_{j \neq i} (|a_{ij} + \varepsilon| + |\varepsilon|)\\ & \geqslant |a_{ii}| - \sum_{j \neq i} (|a_{ij}| + 2|\varepsilon|)\\ & = |a_{ii}| - \sum_{j \neq i} |a_{ij}| + (2n - 2)|\varepsilon|. \end{align*} Choose $\displaystyle |\varepsilon| < \frac{1}{2n - 2}\min_{1 \leqslant i \leqslant n}\left\{|a_{ii}| - \sum_{j \neq i} |a_{ij}|\right\}$ and your problem is solved.

Answer 2

Let $D$ denote the diagonal of $A$ and let $\delta \in (0,1)$ be given. Then $$A = D + (A-D) = D + \delta(A - D) + (1-\delta)(A-D) = M - N,$$ where we have defined $$ M = M(\delta) = D + \delta(A-D), \quad N = N(\delta) = (1-\delta)(D-A)$$ It is straightforward to verify that $$m_{ij} = \begin{cases} a_{ii} & i = j \\ \delta a_{ij} & i \not = j \end{cases}, \quad n_{ij} = \begin{cases} 0 & i = j \\ -(1-\delta) a_{ij} & i \not = j \end{cases}.$$ The salient point is the fact that $D$ is diagonal and $A-D$ has a zero diagonal. Since $\delta \not = 0$ and $(1-\delta) \not = 0$ we have $$\left( i \not = j \wedge a_{ij} \not = 0 \right) \quad \Rightarrow \quad \left( m_{ij} \not = 0 \wedge n_{ij} \not = 0 \right) $$ Since the matrix $A$ is strictly diagonally dominant by rows we have the inequality $$ \forall i \: : \: |a_{ij}| > \sum_{j\not =i} |a_{ij}|.$$ Let $i$ be given and choose any $j \not = i$. Then $$|a_{ij}| = |\delta a_{ij} + (1-\delta) a_{ij}| = |\delta a_{ij}| + |(1-\delta)a_{ij}| = |m_{ij}| + |n_{ij}|.$$ We can now conclude that $$\forall i \: : \: |m_{ii}| > \sum_{j \not = i} \left(|m_{ij}| + |n_{ij}|\right).$$ The special case of $\delta = 0$ corresponds to the splitting used by the Jacobi iteration for solving the linear system $Ax = b$, i.e., $$x_0 = 0, \quad \forall n \in \mathbb{N} \: : \: M x_n = N x_{n-1} + b.$$ It would be interesting to learn if the case of $\delta \not = 0$ has practical applications.