appears in a 1946 paper by Morris, in which it is described as having been “devised by Mr. T. S. Wilson.” The matrix is symmetric positive definite with determinant and inverse
so it is moderately ill conditioned with . This little matrix has been used as an example and for test purposes in many research papers and books over the years, in particular by John Todd, who described it as “the notorious matrix of T. S. Wilson”.
Rutishauser (1968) stated that “the famous Wilson matrix is not a very striking example of an ill-conditioned matrix”, on the basis that for a “positive definite symmetric matrix with integer elements not exceeding ” and he gave the positive definite matrix
for which . The matrix is therefore a factor 12 more ill conditioned than . Rutishauser did not give a proof of the stated bound.
Moler (2018) asked how ill-conditioned is relative to matrices in the set
He generated one million random matrices from and found that about 0.21 percent of them had a larger condition number than . The matrix with the largest condition number was the indefinite matrix
for which . How far is this matrix from being a worst case?
As the Wilson matrix is positive definite, we are also interested in how ill conditioned a matrix in the set
Condition Number Bounds
We first consider bounds on for . It is possible to obtain a bound from first principles by using the relation , where is the adjugate matrix, along with the fact that since has integer entries. Higham and Lettington (2021) found that the smallest bound they could obtain came from a bound of Merikoski et al. (1997): for nonsingular ,
Applying this bound to , using the fact that is monotonically increasing for , gives
Another result from Merikoski et al. (1997) gives, for symmetric positive definite ,
For , since we have , and hence
Recall that Rutishauser’s bound is . The bounds (1) and (2) remain valid if we modify the definitions of and to allow zero elements (note that Rutishauser’s matrix has a zero element).
The sets and are large: has on the order of elements. Exhaustively searching over the sets in reasonable time is possible with a carefully optimized code. Higham and Lettington (2021) use a MATLAB code that loops over all symmetric matrices with integer elements between and and
- evaluates from an explicit expression (exactly computed for such matrices) and discards if the matrix is singular;
- computes the eigenvalues of and obtains the condition number as (since is symmetric); and
- for , checks whether is positive definite by checking whether the smallest eigenvalue is positive.
The code is available at https://github.com/higham/wilson-opt.
The maximum over is attained for
which has . and determinant . The maximum over is attained for
which has and determinant . Obviously, symmetric permutations of these matrices are also optimal.
The following table summarizes the condition numbers of the matrices discussed and how close they are to the bounds.
|By random sampling||6.19||—|
|Optimal matrices in||3.91||—|
|Optimal matrices in||8.38||1.13|
Clearly, the bounds are reasonably sharp.
We do not know how Wilson constructed his matrix or to what extent he tried to maximize the condition number subject to the matrix entries being small integers. One possibility is that he constructed it via the factorization in the next section.
The Cholesky factor of the Wilson matrix is
Apart from the zero element, it is unremarkable. If we factor out the diagonal then we obtain the factorization, which has rational elements:
Suppose we drop the requirement of triangularity and ask whether the Wilson matrix has a factorization with a matrix of integers. It is known that every symmetric positive definite matrix of integers with determinant has a factorization with an matrix of integers as long as , but examples are known for for which the factorization does not exist. This result is mentioned by Taussky (1961) and goes back to Hermite, Minkowski, and Mordell. Higham and Lettington (2021) found the integer factor
of , which is block upper triangular so can be thought of as a block Cholesky factor. Higham, Lettington, and Schmidt (2021) draw on recent research that links the existence of such factorizations to number-theoretic considerations of quadratic forms to show that for the existence of an integer solution to it is necessary that a certain quadratic equation in variables has an integer solution. In the case of the Wilson matrix the equation is
The authors solve this equation computationally and find and two rational factors:
They show that these matrices are the only factors of up to left multiplication by integer orthogonal matrices.
The Wilson matrix has provided sterling service throughout the digital computer era as a convenient symmetric positive definite matrix for use in textbook examples and for testing algorithms. The recent discovery of its integer factorization has led to the development of new theory on when general integer matrices can be factored as (when is symmetric positive definite) or (a problem also considered in Higham, Lettington, and Schmidt (2021)), with integer .
Olga Taussky Todd wrote in 1961 that “matrices with integral elements have been studied for a very long time and an enormous number of problems arise, both theoretical and practical.” We wonder what else can be learned from the Wilson matrix and other integer test matrices.
This is a minimal set of references, which contain further useful references within.
- Nicholas J. Higham and Matthew C. Lettington, Optimizing and Factorizing the Wilson Matrix, to appear in Amer. Math. Monthly, 2021.
- Nicholas J. Higham, Matthew C. Lettington, and Karl Michael Schmidt, Integer Matrix Factorisations, Superalgebras and the Quadratic Form Obstruction, Linear Algebra Appl. 622, 250–267, 2021.
- Cleve B. Moler, Reviving Wilson’s Matrix, 2018.
- H. Rutishauser, On Test Matrices, 7 (no. 165), 349-365, in: Programmation en Mathematiques Numeriques, Besancon, 1968.
- Olga Taussky, Some Computational Problems Involving Integral Matrices, Journal of Research of the National Bureau of Standards Section B—Mathematical Sciences 65(1), 15–17, 1961.
Related Blog Posts
- What Is a Cholesky Factorization? (2020)
- What Is a Condition Number? (2020)
- What Is a Symmetric Positive Definite Matrix? (2020)