# Prove A is nonsingular given $|a_{ii}|>\sum_{j=1,j\neq{i}}^n|a_{ij}|$ $, i=1,2,…n$

This question is taken from Linear Algebra by Zhang, Fuzhen.

Show that $$A$$ is nonsingular if $$A=(a_{ij})\in M_n(C)$$ satisfies

$$|a_{ii}|>\sum_{j=1,j\neq{i}}^n|a_{ij}|$$ $$, i=1,2,...n$$

Here is the proof given:

It suffices to show that $$Ax = 0$$ has only the trivial solution $$0$$. Suppose that $$Ax = 0$$ has a nonzero solution

$$x = (k_1, k_2,..., k_n).$$

Let $$|k_s|= \max_{1 Then $$|k_s|$$ ≠ 0.

However, the s-th equation of $$Ax = 0$$ is

$$a_{s1}k_1 + a_{s2}k_2 + ... + a_{ss}k_s + ... + a_{sn}k_n = 0$$

Thus

$$a_{ss}k_s=-\sum_{j=1,j\neq{s}}^n{a_{sj}k_j}$$ and

$$a_{ss}\le\sum_{j=1,j\neq{s}}^n{|a_{sj}\frac{k_j}{k_s}|}<\sum_{j=1,j\neq{i}}^n|a_{ij}|$$ which is a contradiction.

I understand the proof except $$|k_s|=\max_{1. Why does $$k_s$$ (which is the coefficient of $$a_{ss}$$) have to be the maximum? If it is not the maximum how do you generalize?

• you don't "understand the proof except $|k_s| = \max |k_i|$" if you don't understand why $k_s$ has to be the maximum – mathworker21 Aug 8 at 11:13
• The last line is where you'll get a problem if you do not make that assumption – G. Chiusole Aug 8 at 11:15
• The set $\{|k_1|,...,|k_n|\}$ is a finite set of real numbers, so you can find $1\le s\le n$ such that $|k_s|=\max_{1\le i\le n}k_i$ – Mishikumo2019 Aug 8 at 11:16
• @Mishikumo2019 sure, but $k_s$ is also the coefficient of $a_{ss}$ – Emin Ozkan Aug 8 at 11:17
• Look at it like this, you are choosing an $s$ such that $|k_s|$ is maximum among all the $k_i$. This exists as there are only finitely many $k's$ – Vishnu N Aug 8 at 11:38

$$k_s$$ being the maximum means $$\left|\frac{k_j}{k_s}\right|\leq1$$, which is necessary for the last line of your proof. Specifically, for $$\sum_{j=1,j\neq{s}}^n\left|a_{sj}\frac{k_j}{k_s}\right|\leq\sum_{j=1,j\neq{s}}^n\left|a_{sj}\right|$$ (Note that the proof wrongfully inserts a $$<$$ here, rather than $$\leq$$; a priori nothing stops all the $$k_j$$ from being equal. Also, the indices should still be $$s$$ rather than $$i$$ on the right-hand side.)
You pick $$s$$ so that $$k_s$$ is the largest coefficient in $$x$$. Then you use the $$s$$th row of $$A$$, so that the largest entry in $$x$$ lines up with diagonal entry in $$A$$.
• @EminOzkan You pick $s$ so that $k_s$ is the largest coefficient in $x$. Then you use the $s$th row of $A$, so that the largest entry in $x$ lines up with diagonal entry in $A$. – Arthur Aug 8 at 11:26
If $$|k_s|$$ is not the maximum value of $$|k_1|,\dots, |k_n|$$, then we do cannot say that $$\frac{k_j}{k_s}a_{sj} < |a_{sj}|$$, and therefore, the last line of the proof is not correct.