sci.math.numanalysis
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 nonsingular. 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 nonzero
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
nonzero 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 nonzero
matrix coefficients such that:
S(1,2) <> 0 , S(2,3) <> 0 , S(3,4) <> 0 , ... ... , S(N1,N) <> 0 .
So there exists a "path" from (1) to (N) via a series of nonzero 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
* Email: Han.deBruijn@RC.TUDelft.NL  Fax: +31 15 78 37 87 * Blood