Posted by: Alexandre Borovik | July 18, 2011

## Alan Turing and linear algebra

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 $n$th order and $x$ and $b$ vectors of the $n$th 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).

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$