Rhapsodizing About Bohemian Matrices

In the November 1987 issue of SIAM News, Eric Grosse and Cleve Moler reported a \(9 \times 9\) symmetric matrix of \(1\)s and \(-1\)s for which EISPACK failed to accurately compute one of the eigenvalues on a particular machine [5]. In my January/February 2018 column, I described how surprising results can occur when computing the determinant of a matrix of small integers in floating-point arithmetic [6]. And as is well known, a matrix of \(0\)s, \(1\)s, and \(-1\)s devised by Wilkinson is a matrix that achieves the worst-case growth factor for Gaussian elimination with partial pivoting.

Matrices of small integers—innocuous as they may seem—can clearly provoke interesting behavior. In fact, such matrices have long been a subject of study, not least because analytical formulas can be obtained for the eigenvalues, inverse, determinant, etc. in many cases. For this reason, and the fact that they are stored exactly in floating-point arithmetic, they make good test matrices. A matrix that was popular in the early days of digital computing is

\[W= \begin{bmatrix}  5 &7& 6& 5 \\ 7 &10& 8& 7 \\ 6& 8& 10& 9 \\ 5& 7& 9 &10 \\ \end{bmatrix}, \]

whose inverse has moderately large integer entries. John Todd described it as “the notorious matrix \(W\) of T. S. Wilson” [9], and Moler recently investigated its properties and history [7]. A favorite of mine is the Pascal matrix, with \((i,j)\) entry \({i+j-2 \choose j-1}\). A great deal is known about this positive definite, totally positive matrix. A scaled and rotated version of the Cholesky factor of the matrix (\(\texttt{pascal(n,2)}\) in MATLAB) has the intriguing property that it is a cube root of the identity, shown here for \(n=4\):

\[\left[\begin{array}{@{\kern2pt}rrrr}
    -1 &   -1 &   -1 &   -1\\
     3 &    2 &    1 &    0\\
    -3 &   -1 &    0 &    0\\
     1 &    0 &    0 &    0\\
    \end{array}\right]^3 = I.\]

Deep connections exist between integer matrices—particularly positive definite ones—and number theory, as Olga Taussky-Todd demonstrated in her work; see [8] and an appendix to Harvey Cohn’s 1978 book on algebraic number theory [3]. In a 1991 letter, Taussky-Todd told me that “we [she and her husband, John Todd] have been really interested in batteries of test matrices.” Indeed, the Hilbert matrix was a favorite of theirs.

In scientific computing, researchers often employ increases in computing power to solve larger problems (rather than a greater number of small problems), but a systematic search of small problems can offer new insights. Recent work on Bohemian matrices combines the latter approach with theoretical analysis. Rob Corless and Steven Thornton (both of the University of Western Ontario) coined the term “Bohemian matrices”—a contraction of BOunded HEight Matrix of Integers—to denote families of matrices with entries drawn from a fixed discrete set of small integers (or some other discrete set) [4].

Thornton has been investigating the distribution of eigenvalues and characteristic polynomials of Bohemian matrices of dimensions up to about \(10\), with elements in sets such as \(\{-1,0,1\}\), using a mix of numerical and symbolic computation. The number of matrices grows rapidly with the dimension, and Thornton uses random sampling when exhaustive computation is not possible. His plots show remarkable structures and make wonderful pieces of art (see Figure 1). A collection of images is available on his website.

Various open questions have been identified concerning eigenvalue distributions, ranks, and the number of distinct characteristic polynomials in particular classes of Bohemian matrices. Some of these are listed in Thornton’s characteristic polynomial database, which contains more than \(10^9\) polynomials from a variety of Bohemian matrix families.

Last June, Corless and I organized a workshop entitled Bohemian Matrices and Applications that brought together researchers with expertise in matrix theory, numerical linear algebra, computer algebra, algebraic geometry, and number theory. Some open problems were solved and many others formulated. Videos of the introductory talks (by Corless, Thornton, and myself) and slides from the other talks are available online.

This is my last column as SIAM president. I wish Lisa Fauci all the best as she takes over the presidency in January 2019.

References

[1] Baez, J. (2011, December 15). The Beauty of Roots. Retrieved from http://math.ucr.edu/home/baez/roots/.
[2] Borwein, P., & Jörgenson, L. (2001). Visible Structures in Number Theory. Amer. Math. Monthly, 108, 897-910.
[3] Cohn, H. (1978). A Classical Invitation to Algebraic Numbers and Class Fields (with two appendices by Olga Taussky-Todd). New York, NY: Springer-Verlag.
[4] Corless, R.M., & Thornton, S.E. (2016). The Bohemian Eigenvalue Project. ACM Comm. Comput. Alg., 50, 158-160.
[5] Grosse, E., & Moler, C. (1987). Underflow Can Hurt. SIAM News, 20(6), p. 1.
[6] Higham, N.J. (2018). Snap to Structure. SIAM News, 51(1), p. 2.
[7] Moler, C. (2018, August 20). Reviving Wilson’s Matrix. Retrieved from https://blogs.mathworks.com/cleve/2018/08/20/reviving-wilsons-matrix/.
[8] Taussky, O. (1960). Matrices of Rational Integers. Bull. Amer. Math. Soc., 66, 327-346.
[9] Todd, J. (1950). The Condition of a Certain Matrix. Proc. Camb. Philos. Soc., 46, 116-118.