# A problem in Linear algebra

Suppose $A$ is a $n$ by $n$ matrix with entries $a_{ij}$ such that $$|a_{ii}|>\sum_{k\neq i}|a_{ki}|$$ for $i=1,2,...,n$, prove $A$ is invertible.

-

## 1 Answer

We will show the contra-positive. Let $A$ be a matrix which is not invertible (hence $^tA$ is not invertible). Let $x\neq 0$ such that $^tAx=0$. We can find $1\leq i\leq n$ such that $\displaystyle|x_i|=\max_{1\leq k\leq n} |x_k|$. We have $\displaystyle\sum_{k=1}^na_{ki}x_k = 0$ hence $\displaystyle |a_{ii} x_i| =\left|\sum_{k\neq i}a_{ki}x_k\right| \leq |x_i|\sum_{k\neq i}|a_{ki}|$. We get $\displaystyle |a_{ii}|\leq \sum_{k\neq i}|a_{ki}|$.

-
Nice answer! I would have routinely answered by appealing to Gershgorin's theorem, but this is much simpler and illuminating. –  Giuseppe Negro Jun 23 '11 at 16:23
You mean the contra-positive, not the converse. –  Eric Naslund Jun 23 '11 at 16:51
@Eric Naslund : yes, you are right. I don't know why I wrote that. I will correct it readily. –  Davide Giraudo Jun 23 '11 at 16:52
@dissonance, this is exactly a proof of Gershgorin - you can compare this to the proof in wikipedia for example. –  Soarer Jun 23 '11 at 16:55