0
$\begingroup$

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<i<n} {|k_i|}$ 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<i<n} {|k_i|}$. 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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – mathworker21 Aug 8 at 11:13
  • $\begingroup$ The last line is where you'll get a problem if you do not make that assumption $\endgroup$ – G. Chiusole Aug 8 at 11:15
  • $\begingroup$ 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$ $\endgroup$ – Mishikumo2019 Aug 8 at 11:16
  • $\begingroup$ @Mishikumo2019 sure, but $k_s$ is also the coefficient of $a_{ss}$ $\endgroup$ – Emin Ozkan Aug 8 at 11:17
  • $\begingroup$ 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$ $\endgroup$ – Vishnu N Aug 8 at 11:38
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @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$. $\endgroup$ – Arthur Aug 8 at 11:26
  • $\begingroup$ Thank you. That was the answer I was looking for. Can a comment be the answer a question? $\endgroup$ – Emin Ozkan Aug 8 at 11:28
  • $\begingroup$ @EminOzkan Not really. But I can add it to my answer. $\endgroup$ – Arthur Aug 8 at 11:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.