Gershgorin theorem and strictly diagonally dominant matrix

Question

A is a strictly diagonally dominant matrix. Prove $ \prod_{i=1}^n (|a_{ii}|-\sum_{j \ne i}|a_{ij}|)\leq |det(A)|$.

ps: I tried Gershgorin theorem, but I cannot prove eigenvalues are contained in different Gershgorin circles. Thanks a lot!!!

Answer 1

simple case
the underlying idea is right-- solve a simple case first -- where all Gerschgorin discs are disjoint. In this simple case we have
$0\lt \big\vert a_{i,i}\big\vert - \sum_{j\neq i}\big \vert a_{i,j}\big\vert=\Big\vert \big\vert a_{i,i}\big\vert - \sum_{j\neq i}\big \vert a_{i,j}\big\vert \Big\vert \leq \big \vert\lambda_i\big \vert$
by Gersochgorin's Discs, and mutliplying over the bound gives the result.

The key insight is that left multiplication by an invertible diagonal matrix does not change strict diagonal dominance, and we can use this to get the general case from the simple case.

general case
consider $B:= DA$
for some well chosen diagonal matrix $D$ with non-zero elements on its diagonal. As we'll see $B$ is the above simple case. To make this easy, go in two steps, $D=D^{(2)}D^{(1)}$ where $D^{(1)}$ is the 'homogenization matrix' and $D^{(2)}$ is the 'qualitative matrix'.

1.) Select $D^{(1)}$ such that $(D^{(1)}A)$ has each diagonal element $= 1$.

2.) $D^{(2)}$ has each diagonal element positive and is selected as follows:

Consider
$D^{(2)} = \begin{bmatrix}\sigma_1 &\mathbf {0}^T\\ \mathbf 0 &I_{n-1}\end{bmatrix}$ and observe that for large enough $\sigma_1$, the Gerschgorin disc associated with row one of $(D^{(2)}D^{(1)}A)$ is necessarily disjoint from the discs of rows $\geq 2$. So select (and fix) some satisfactory $\sigma_1$.

Now consider $D^{(2)} = \begin{bmatrix}\sigma_1 &0&\mathbf {0}^T\\ 0&\sigma_2&\mathbf 0^T\\ \mathbf 0& \mathbf 0 &I_{n-2}\end{bmatrix}$.
And observe that for large enough $\sigma_2$, the Gerschgorin discs associated with the first two rows of $(D^{(2)}D^{(1)}A)$ are necessarily disjoint from each other and from those of rows $\geq 3$. This process continues n-3 more times and we have

$B=DA = D^{(2)}D^{(1)}A $
where all Gerschgorin discs of $B$ are disjoint. Of course by the simple argument:

$\prod_{i=1}^n\Big(\vert b_{i,i}\vert - \sum_{j\neq i}\big \vert b_{i,j}\big\vert\Big)\leq \big \vert \det\big(B\big)\big \vert $
now rescale each side by the positive number given by $\vert\det\big(D^{-1}\big)\big \vert=\Big\vert \prod_{i=1}^n d_{i,i}\Big\vert^{-1}$ and you recover

$\prod_{i=1}^n\Big(\big\vert a_{i,i}\big\vert - \sum_{j\neq i}\big \vert a_{i,j}\big\vert\Big)$
$=\prod_{i=1}^n\Big( \vert d_{i,i}^{-1}\vert b_{i,i} - \vert d_{i,i}^{-1}\vert \cdot \sum_{j\neq i}\big \vert b_{i,j}\big\vert\Big)$
$=\Big\vert \prod_{i=1}^n d_{i,i}\Big\vert^{-1}\cdot \prod_{i=1}^n\Big(\vert b_{i,i}\vert - \sum_{j\neq i}\big \vert b_{i,j}\big\vert\Big)$
$\leq \Big\vert \prod_{i=1}^n d_{i,i}\Big\vert^{-1} \cdot\Big \vert \det\big(B\big)\Big \vert$
$= \Big \vert \det\big(D^{-1}\big)\Big\vert \cdot \Big \vert \det\big(B\big)\Big\vert$
$= \Big \vert \det\big(D^{-1}B\big)\Big \vert$
$ =\Big \vert \det\big(A\big)\Big \vert $