Strictly diagonal matrix

Question

Suppose that matrix $A$ is strictly diagonally dominant, show that $$\|A^{-1}\|_{\infty}\leq\left[\min_i\left(|a_{ii}|-\left|\sum_{\substack{j\neq i}} a_{ij}\right|\right)\right]^{-1}.$$

Answer 1

The bound is not true. Consider $$ A=\left[\begin{array}{rrr}4&1&-2\\-1&5&3\\-1&0&3\end{array}\right]. $$ Then $$ \|A^{-1}\|_\infty=\frac{31}{50}=0.64, \quad \min_i\left(|a_{ii}|-\left|\sum_{j\neq i}a_{ij}\right|\right)=2, \quad \text{but $0.64\not\leq 1/2$.} $$

Something similar is true, however. We show that with $$ \gamma:=\min_i\left(|a_{ii}|-\sum_{j\neq i}|a_{ij}|\right) \quad \text{($\gamma>0$ since $A$ is diagonally dominant)}, $$ we have $\gamma\|x\|_\infty\leq\|Ax\|_\infty$ for all $x$ and the inverse of this $\gamma$ is what you should have on the right-hand side of your statement. Indeed, let $i$ be such that $\|x\|_\infty=|x_i|$. Then $$ \begin{split} \|Ax\|_\infty&\geq|(Ax)_i|=\left|a_{ii}x_i+\sum_{j\neq i}a_{ij}x_j\right| \geq |a_{ii}||x_i|-\sum_{j\neq i}|a_{ij}||x_j|\geq|a_{ii}||x_i|-\sum_{j\neq i}|a_{ij}||x_i|\\ &=\left(|a_{ii}|-\sum_{j\neq i}|a_{ij}|\right)\|x\|_\infty\geq\gamma\|x\|_\infty. \end{split} $$ Consequently, $$ \|A^{-1}\|_\infty=\max_{x\neq 0}\frac{\|A^{-1}x\|_\infty}{\|x\|_\infty}=\max_{x\neq 0}\frac{\|x\|_\infty}{\|Ax\|_\infty}\leq\frac{1}{\gamma}. $$