Math and science::Algebra

Diagonally dominant

A matrix is diagonally dominant iff each diagonal entry is larger than the sum of the off-diagonal entries of the same row, in absolute value terms.

And this property is important because:

Diagonally dominant matrices are invertible.

Can you remember the proof?

Proof

A matrix $M$ is not invertable iff there exists an $\vec{x}$ such that $M \vec{x} = 0$ . Strategically focus on the largest element of $\vec{x}$ , say $x_{i}$ . For $M \vec{x} = 0$ to be true, the other $x$ 's must be able to cancel out $x_{i}$ when they are multiplied by the respective columns of $M$ . But for the $i^{th}$ row of $M$ , where $m_{i i}$ is larger absolutely than the sum of the other elements, this isn't possible. So such an $\vec{x}$ cannot exist, so $M$ must be invertible.

Essense

When the largest element of $x_{i}$ conspires with the diagonally dominant entry in column $i$ of $M$ , this product cannot be cancelled by the other terms.

Why must it be the sum?

Why is it not sufficient for the diagonal entries to simply be the largest absolute value? An example demonstrates:

[\begin{matrix} 10 & 5 & 5 \\ 1 & 5 & - 4 \\ 9 & - 1 & 10 \end{matrix}] [\begin{matrix} 1 \\ - 1 \\ - 1 \end{matrix}] = 0