5
$\begingroup$

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 Answers 1

6

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}|$.

  • 0
    Nice answer! I would have routinely answered by appealing to [Gershgorin's theorem](http://en.wikipedia.org/wiki/Gershgorin_circle_theorem), but this is much simpler and illuminating.2011-06-23
  • 1
    You mean the contra-positive, not the converse.2011-06-23
  • 1
    @Eric Naslund : yes, you are right. I don't know why I wrote that. I will correct it readily.2011-06-23
  • 1
    @dissonance, this is exactly a proof of Gershgorin - you can compare this to the proof in wikipedia for example.2011-06-23