Posted by: Alexandre Borovik | July 18, 2011

Alan Turing and linear algebra

The Alan Turing Building at the University of ...

Alan Turing Building, University of Manchester. Image via Wikipedia

In a recent paper by Joseph F. Grcar  Mathematicians of Gaussian elimination in Notices of AMS, Alan Turing is named among mathematicians who put linear algebra in the form and shape  now  presented  to undergraduate students;  indeed, he was one on the first mathematicians who  formulated Gaussian elimination in matrix form, and perhaps the first one who was motivated to do so by future use of electronic computers for solving systems of linear equations. What follows are some excerpts from his paper of 1948 ,  the year when he moved to Manchester.

Turing’s introductory remarks can now be found, and in almost the same words, in dozens (if not hundreds) linear algebra textbooks:

Let us suppose we are given a set of linear equations Ax = b to solve. Here A represents a square matrix of the nth order and x and b vectors of the nth order. We may either treat this problem as it stands and attempt to find x, or we may solve the more general problem of finding the inverse of the matrix A, and then allow it to operate on b giving the required solution of the equations as x = A^{-1}b. If we are quite certain that we only require the solution to the one set of equations, the former approach has the advantage of involving less work (about one-third the number of multiplications by almost all methods). If, however, we wish to solve a number of sets of equations with the same matrix A it is more convenient to work out the inverse and apply it to each of the vectors b. This involves, in addition, n^2 multiplications and n recordings for each vector, compared with a total of about n^3 multiplications in an independent solution.

Then Turing introduces the main theme of his paper: control of errors of calculations:

There are other advantages in having an inverse. From the coefficients of the inverse we can see at once how sensitive the solution is to small changes in the coefficients of A and of b.  [...]  This enables us to estimate the accuracy of the solution if we can judge the accuracy of the data, that is, of the matrix A and the vector b, and also enables us to correct for any small changes which we may wish to make in these data.

And these are  his visionary words:

It seems probable that with the advent of electronic computers it will become standard practice to find the inverse. This time has, however, not yet arrived and some consideration is therefore given in this paper to solutions without inversion. A form of compromise involving less work than inversion, but including some of the advantages, is also considered.

This theorem is of course instantly recognisable; it is less known that it belongs to Turing:

THEOREM ON TRIANGULAR RESOLUTION. If the principal minors of the matrix A are non-singular, then there is a unique unit lower triangular matrix L, a unique diagonal matrix D, with non-zero diagonal elements, and a unique unit upper triangular matrix U such that A = LDU. Similarly there are unique L', D', U' such that A = U'D'L'.

And here is a sketch of its proof:

The process of replacing the rows of a matrix by linear combinations of other rows may be regarded as left-multiplication of the matrix by another matrix, this second matrix having coefficients which describe the linear combinations required. Each stage of the above-described elimination process is of this nature, so that we first convert the equations Ax = b into J_{1} Ax = J_{1} b and record J_{1} A and J_{1} b . We then convert them into J_{2} J_{1} Ax = J_{2} J_{1} b, and so on, until we finally have J_{n} \cdots J_{1} Ax = J_{n} \cdots J_{1}b. In accordance with the theorem on triangular resolution we may write J_{n}\cdots J_{1} = L^{-1} and J_{n}\cdots J_{1}A = DU. The matrix DU is upper triangular, that is, it has no coefficients other than zeros below the diagonal. The matrix L^{-1} and its inverse L are lower triangular.

And I wrote this post because (a) I teach linear algebra and (b) my office in in Alan Turing Building (see photo kindly suggested by WordPress).

About these ads

Responses

  1. The formula doesn’t parse because, instead of the backslash for \cdots, a spurious character hex value 92 has crept in. J_{n}\cdots J_{1}A = DU

    • Steve, many thanks — this allowed me to fix the problem.

  2. It says something about the esteem with which Alan Turing is held by computer people in Manchester that the University of Manchester’s Department of Computer Science is located in the Kilburn Building, named for Tom Kilburn, an electronic engineer. Likewise, the one-day seminar held at University of Manchester in 2004 to commemorate the 50th anniversary of Turing’s death was organized by the Mathematics Department, and sponsored by the LMS, the British Logic Colloquium, and the British Society for the History of Mathematics. It is a great pity that the Manchester’s computer science community, for some reason, has seemed incapable or unwilling to honour Turing.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 78 other followers

%d bloggers like this: