Let \(A=(a_{ij})\) be an \(n\times n\) complex matrix satisfying \[ |a_{ii}|>\sum_{j\ne i}|a_{ij}| \] for every \(1\le i\le n\). Prove that \(A\) is invertible.
Solution
1. Suppose\[ Ax=0 \]for some nonzero vector\[ x=(x_1,\ldots,x_n)^t\in\CC^n. \]Choose an index \(i\) such that\[ \abs{x_i} = \max_{1\leq j\leq n}\abs{x_j}. \]Then\[ \abs{x_i}>0. \]
Since \(x\neq0\), at least one coordinate is nonzero. A finite set of nonnegative real numbers has a maximum, so such an index \(i\) exists, and its maximal modulus is positive.
2. The \(i\)th row equation implies\[ \abs{a_{ii}}\abs{x_i} \leq \left( \sum_{j\neq i}\abs{a_{ij}} \right) \abs{x_i}. \]
The equation \(Ax=0\) gives \[ a_{ii}x_i = -\sum_{j\neq i}a_{ij}x_j. \] Taking absolute values and using the triangle inequality, \[ \abs{a_{ii}}\abs{x_i} \leq \sum_{j\neq i} \abs{a_{ij}}\abs{x_j}. \] By the choice of \(i\) in step 1, \[ \abs{x_j}\leq\abs{x_i} \] for every \(j\). Substitution gives the displayed bound.
3. The assumption \(x\neq0\) is impossible.
Strict diagonal dominance gives \[ \sum_{j\neq i}\abs{a_{ij}} < \abs{a_{ii}}. \] Since \(\abs{x_i}>0\), step 2 therefore yields \[ \abs{a_{ii}}\abs{x_i} < \abs{a_{ii}}\abs{x_i}, \] a contradiction.
4. The kernel of \(A\) is trivial.
Step 3 shows that no nonzero vector can satisfy \(Ax=0\).
5. The matrix \(A\) is invertible.
By step 4, the linear map \[ A:\CC^n\longrightarrow\CC^n \] is injective. Since domain and codomain have the same finite dimension, it is bijective, hence \(A\) is invertible.
6. Q.E.D.
Step 5 is the required conclusion.