sci.math.num-analysis

SUNA31, Theorem in Ames' book
=============================

Attention is paid to page 101 in the book by William F. Ames, called "Numerical
Methods for Partial Differential Equations", Academic Press (1977).

I had the pleasure to meet professor Ames personally in Brussels (Belgium, must
have been around 1980). After I had exposed him my view upon a unified approach
towards finite difference and finite element methods, he said: "Ah, _that_ will
stop the war!". After that, he turned back to his exposure about Lie groups and
partial differential equations, and I lost contact. He was much more interested
in classical analysis than in those "unreliable" numerical methods, anyway ...

Theorem
-------
| Let there be given a matrix  S  with the following properties:
|
| (i)    S(i,i) <> 0  for all  i .
|
| (ii)   |S(i,i)| >= sum |S(i,j)|   ; with strict inequality for some  i .
|                    j<>i
|
| (iii)  S  is irreducible; that is, it can NOT be reduced to a blocked matrix
|                           by permutation of rows and columns.
|
| Then the matrix  S  is non-singular. With other words:
| the system of equations  S.x = b  has a unique solution  x .
|                                         ^^^^^^
Here the plain text condition was replaced by the weaker condition (i) in the
footnote on page 101 of the book. Question: Who is/are the true discoverer(s)
of this theorem? I suppose it's not Mr. Ames himself.

Proof:
-----
Assume the system of equations is  S.x = 0 ; suppose there exists a non-zero
solution  x  for this problem. Somewhere in the mesh there will be points (k)
where  x(k) <> 0 . Now look for a point (k) where  |x(k)|  has a maximum value
in comparison with other such points. Give it a name:  |x(k)| = M > 0 .

The equation belonging to (k) in  S  is:

    S(k,k).x(k) + sum S(k,j).x(j) = 0   . Hence, using (i):
                  j<>k

    sum |S(k,j)/S(k,k).x(j)| = |-x(k)| = M
    j<>k

Now consider only the unknowns  x(j)  where  S(k,j) <> 0 . Assume for a moment
that the  |x(j)|  are not all equal to  M . Then some of the  |x(j)|  must be
smaller than  M . (They can not be bigger:  M  was a maximum) Consequently:

    |x(k)| = sum |S(k,j)/S(k,k)|.|x(j)| < sum |S(k,j)|/|S(k,k)|.M
             j<>k                         j<>k

But, according to (ii):   sum |S(k,j)|/|S(k,k)| <= 1
                          j<>k

We conclude that:  |x(k)| < M . But  |x(k)|  was by definition equal to  M .
Hence the assumption that there exist  |x(j)|  with  S(k,j) <> 0  such that
|x(j)| <> M  must be wrong. All points which are joined with (k) by means of
non-zero matrix coefficients have the same (absolute) maximum value  M .

It is assumed that  S  is irreducible in (iii). This means that for each couple
of points in the mesh, say (1) and (N), there can be found a series of non-zero
matrix coefficients such that:

   S(1,2) <> 0 , S(2,3) <> 0 , S(3,4) <> 0 , ... ... , S(N-1,N) <> 0 .

So there exists a "path" from (1) to (N) via a series of non-zero coefficients.
Start walking at the point (k), to be identified with (1) (: what's in a name?)
Then we find, thanks to the fact that  S  is irreducible, always a point (2)
where S(1,2) <> 0  , therefore  |x(2)| = M , and a point (3) where  S(2,3) <> 0
hence |x(3)| = M . Continuing in this way, we find that the same value  M  must
be accepted for all the unknowns:  |x(i)| = M  forall  i .

Until we arrive at a point where the strict inequality according to (ii) holds.
Call this point (n), then:

  |x(n)| = sum |S(n,j)/S(n,n)|.|x(j)| = sum |S(n,j)/S(n,n)|.M
           j<>n                         j<>n

But strict inequality holds here:   sum |S(n,j)/S(n,n)|.|x(j)| > 1
                                    j<>n

Hence it is concluded that   |x(n)| > M .

But this is in contradiction with our earlier assumption that  M  represents a
maximum value. And ultimately in contradiction with the assumption that  x <> 0
is a possible solution.

This proves that the system  S.x = 0  has as it's only solution a zero vector.
Therefore the matrix  S  can not be singular. QED.

To be continued ...
-
* Han de Bruijn; Applications&Graphics | "A little bit of Physics * No
* TUD Computing Centre; P.O. Box 354   | would be NO idleness in  * Oil
* 2600 AJ  Delft; The Netherlands.     | Mathematics" (HdB).      * for
* E-mail: Han.deBruijn@RC.TUDelft.NL --| Fax: +31 15 78 37 87 ----* Blood