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