Bohemian matrices

From HandWiki
Short description: Set of matrices


A Bohemian matrix family[1] is a set of matrices whose free entries come from a single discrete, usually finite, population, denoted by the matrix list P. Each input of any matrix from this particular Bohemian matrix family is required to be an element of the set P. Such matrices containing these properties are defined as Bohemian matrices. Bohemian matrices may possess additional structure, a Toeplitz matrix or an upper Hessenberg matrix, for example. Usually only one Bohemian matrix family with a fixed population P is studied at a time, so one can classify any given matrix as being Bohemian or not without significant ambiguity.

Blue, yellow, and gold fractal doily with a tilted hamster-face in the middle (that's just pareidolia, but inescapable). Triple symmetry with sharp points at 9 o'clock, at 1 o'clock, and 5 o'clock.
A density plot of all eigenvalues of all dimension 15 by 15 Bohemian upper Hessenberg zero diagonal matrices with population cube roots of -1

Applications

Software testing

One application of Bohemian matrices is to test software applied in linear algebra. Bohemian matrices are (usually) distinctly represented on a computer,[2] and one can identify for extreme behavior either by exhaustive search (for small dimensions), random sampling, or optimization techniques. A prominent example is Steven E. Thornton, who had solved for more than two trillion eigenvalue problems. In doing so, he uncovered instances of convergence failure in some popular software systems. [3]

An anymatrix is an extensible MATLAB matrix collection capturing a set of optimal classes of Bohemian matrices.

See also Cleve Moler's blog post on Bohemian Matrices in the Matlab Gallery.

Improved bounds

In a talk given at the 2018 Bohemian Matrices and Applications Workshop, Nick Higham explained how he utilized genetic algorithms on Bohemian matrices with population P={-1, 0, 1} to sharpen lower bounds on the maximal growth factor for rook pivoting.[4]

Connections to other fields

Random matrices

Bohemian matrices can be studied through random sampling. Such studies might be considered part of the field of random matrices. However, most of the focus of the study of random matrices to date has been on real symmetric or Hermitian matrices, or on matrices whose entries are drawn from a continuous distribution (such as Gaussian ensembles). Notable exceptions include the work of Terence Tao and Van Vu.[5][6]

Bernoulli and Hadamard matrices

Matrices with entries only from ±1 are sometimes called Bernoulli matrices,[7] which are therefore examples of Bohemian matrices. A Hadamard matrix is a Bernoulli matrix that satisfies a further property, namely that its determinant is maximal. Therefore Hadamard matrices are also Bohemian. Hadamard matrices (and indeed Bernoulli matrices) have been studied for much longer than the name "Bohemian matrix" has existed, but the kinds of questions one can ask about Hadamard matrices (the original question was which matrices have maximal determinant) can also be asked about other Bohemian matrices. One of the first generalizations of Hadamard matrices was to what are now sometimes called Butson-type Hadamard matrices, whose entries are qth roots of unity for q > 2. These can also be considered prototypical Bohemian matrices.

Graph theory

Matrices with discrete entries, particularly incidence matrices, play a crucial role in understanding graph theory. The outcomes of graph theory aid in explaining certain phenomena encountered in Bohemian matrix experiments. Conversely, experiments conducted in the manner advocated by Bohemian matrix workers can provide useful information for graphs.[8]

Combinatorics

A significant number of the open problems listed in the Encyclopedia of Integer Sequences under Bohemian matrices are combinatorial in nature. For instance, A306782 lists a table of the number of distinct minimal polynomials for Bernoulli matrices (that is, Bohemian matrices with population ±1) up to and including dimension 5. The numbers for higher dimensions are not known. The number of Bernoulli matrices of dimension 6 is 236=68,719,476,736; while this set could likely be searched exhaustively (it is delightfully parallel), the greater-than-exponential growth of the number of matrices soon defeats brute force. There are symmetries that might be taken advantage of, as is done [8] for zero-one matrices, but these seem to require sophisticated combinatorial knowledge.

Number theory

Number theorists have worked on polynomials with restricted coefficients for a very long time. For instance, Littlewood polynomials have coefficients ±1 when expressed in the monomial basis. Kurt Mahler was concerned with the problem,[9] as were Andrew Odlyzko, Bjorn Poonen[10] and Peter Borwein.[11]

By using companion matrices, each of these restricted-coefficient polynomial problems can be considered to be a Bohemian matrix problem. However, the characteristic polynomial of a Bohemian matrix might have coefficients that are exponentially large in the dimension, so the converse is not true and these areas of study are not equivalent.[12]

There are other connections, to Magic Squares for instance. See Kathleen Ollerenshaw's book with D. Brée.[13] The following paper explicitly connects Bohemian matrices to quadratic forms.[14]

Solution of polynomial equations

A commonly-used technique to find polynomial roots is to construct a companion matrix for it and use numerical eigenvalue solvers to find the eigenvalues, which are then the roots of the original polynomial. It seems counterintuitive and wasteful to do this, but it can be quite practical. This is the default method of NumPy's Polynomial package. The method is frequently numerically stable,[15] but sometimes does not work well if the polynomial coefficients are large or the polynomial is otherwise ill-conditioned.

One can sometimes improve the situation by finding a minimal height companion matrix for the polynomial by looking for such in a Bohemian matrix family.[16] No efficient general-purpose techniques for this are known, however.

History

The name "Bohemian matrices", together with the idea that it might be useful to categorize problems in this way, appeared in print by ISSAC 2016.[17] The name arises from the mnemonic BOunded HEight Matrix of Integers (BOHEMI), although the classification has since been extended to other discrete populations including non-integer populations[18] (including for example Gaussian integers). The breadth and utility of the idea of making this categorization is becoming increasingly apparent: the first significant journal publication was[19] although smaller publications appeared before that. As of March 2022, publications explicitly using the name, aside from those cited elsewhere in this article, include[20][21][22]

The first workshop on the subject was held in 2018 at the University of Manchester and was entitled Bohemian Matrices and Applications. The idea can be considered to be a specialization in the sense of George Pólya, in that Bohemian matrix families are restricted to having certain entries and are thus special matrices. The idea can also be considered a generalization, because instead of merely having entries either 0 or 1 as in an incidence matrix of a graph or -1 and 1 as in the companion matrix of a Littlewood polynomial, the Bohemian family can have entries that are otherwise bounded, discrete, or (usually) both.

The idea is somewhat similar to that of sign pattern matrices, in which two matrices with real entries are considered equivalent if the corresponding entries have the same sign, and that theory looks for common properties.[23] A Bohemian matrix with population P={-1, 0, 1} is an example of a sign pattern matrix, and so it has all the properties of such matrices, but it may also have special properties owing to its Bohemian nature.

References

  1. ↑ Higham, Nicholas J (December 2018). "Rhapsodizing about Bohemian Matrices". Society for Industrial and Applied Mathematics. https://sinews.siam.org/Details-Page/rhapsodizing-about-bohemian-matrices. 
  2. ↑ Higham, Nicholas J. "Bohemian Matrices in Numerical Linear Algebra". https://www.maths.manchester.ac.uk/~higham/conferences/bohemian/higham_bohemian18.pdf. 
  3. ↑ Thornton, Steven E (April 2019). Algorithms for Bohemian Matrices (PhD thesis). Western University. Archived from the original on 7 March 2022. Retrieved 1 March 2022.
  4. ↑ Higham, Nicholas J. "Bohemian Matrices in Numerical Linear Algebra". https://www.maths.manchester.ac.uk/~higham/conferences/bohemian/higham_bohemian18.pdf. 
  5. ↑ Tao, Terence; Vu, Van (January 2006). "On random ±1 matrices: Singularity and determinant". Random Structures and Algorithms 28 (1): 1–23. doi:10.1002/rsa.20109. https://doi.org/10.1002/rsa.20109. Retrieved 2 March 2022. 
  6. ↑ Vu, Van (2008). "Random Discrete Matrices". Horizons of Combinatorics. Bolyai Society Mathematical Studies. 17. pp. 257–289. doi:10.1007/978-3-540-77200-2_13. ISBN 978-3-540-77199-9. 
  7. ↑ Tao, Terence; Vu, Van (January 2006). "On random ±1 matrices: Singularity and determinant". Random Structures and Algorithms 28 (1): 1–23. doi:10.1002/rsa.20109. https://doi.org/10.1002/rsa.20109. Retrieved 2 March 2022. 
  8. ↑ 8.0 8.1 Živković, Miodrag (2006). "Classification of small (0, 1) matrices". Linear Algebra and Its Applications 414 (1): 310–346. doi:10.1016/j.laa.2005.10.010. 
  9. ↑ Mahler, Kurt (1963). "On two extremum properties of polynomials". Illinois Journal of Mathematics 7 (4): 681–701. doi:10.1215/ijm/1255645104. 
  10. ↑ Odlyzko, Andrew (September 1992). "Zeros of polynomials with 0,1 coefficients". Algorithms Seminar: 169. 
  11. ↑ Borwein, Peter B.; Jörgenson, Loki (December 2001). "Visible Structures in Number Theory". American Mathematical Monthly 108 (10): 897–910. doi:10.1080/00029890.2001.11919824. https://www.jstor.org/stable/2695413. Retrieved 3 March 2022. 
  12. ↑ Calkin, Neil J; Chan, Eunice Y.S.; Corless, Robert M. (2 June 2021). "Some facts and conjectures about Mandelbrot polynomials". Maple Transactions 1 (1): 13. doi:10.5206/mt.v1i1.14037. 
  13. ↑ Ollerenshaw, Kathleen; Brée, D (1998). Most-perfect pandiagonal magic squares. IMA. 
  14. ↑ Higham, Nicholas J; Lettington, Matthew (2022). "Optimizing and Factorizing the Wilson Matrix". The American Mathematical Monthly 129 (5): 454–465. doi:10.1080/00029890.2022.2038006. http://eprints.maths.manchester.ac.uk/2803/. Retrieved 3 March 2022. 
  15. ↑ Edelman, Alan; Murakami, H (April 1995). "Polynomial roots from companion matrix eigenvalues". Mathematics of Computation 64 (210): 763–776. doi:10.1090/S0025-5718-1995-1262279-2. Bibcode: 1995MaCom..64..763E. https://www.ams.org/journals/mcom/1995-64-210/S0025-5718-1995-1262279-2/S0025-5718-1995-1262279-2.pdf. Retrieved 2 March 2022. 
  16. ↑ Chan, Eunice Y.S.; Corless, Robert M. (6 February 2017). "A new kind of companion matrix". Electronic Journal of Linear Algebra 32: 335–342. doi:10.13001/1081-3810.3400. 
  17. ↑ Corless, Robert M.; Thornton, Steven E. (2017). "The Bohemian Eigenvalue Project". ACM Communications in Computer Algebra 50 (4): 158–160. doi:10.1145/3055282.3055289. https://dl.acm.org/doi/abs/10.1145/3055282.3055289. Retrieved 28 February 2022. 
  18. ↑ Corless, Robert (2 June 2021). "What can we learn from Bohemian Matrices". Maple Transactions 1 (1). doi:10.5206/mt.v1i1.14039. 
  19. ↑ Chan, Eunice Y.S.; Corless, Robert M.; Gonzalez-Vega, Laureano; Sendra, J. Rafael; Sendra, Juana; Thornton, Steven E. (September 2020). "Upper Hessenberg and Toeplitz Bohemians". Linear Algebra and Its Applications 601: 72–100. doi:10.1016/j.laa.2020.03.037. https://doi.org/10.1016/j.laa.2020.03.037. Retrieved 3 March 2022. 
  20. ↑ Fasi, Massimiliano; Negri Porzio, Gian Maria (2020). "Determinants of normalized Bohemian upper Hessenberg matrices". The Electronic Journal of Linear Algebra 36 (36): 352–366. doi:10.13001/ela.2020.5053. 
  21. ↑ Chan, Eunice Y.S.; Corless, Robert M.; Gonzalez-Vega, Laureano; Sendra, J. Rafael; Sendra, Juana (May 2022). "Inner Bohemian Inverses". Applied Mathematics and Computation 421 (15): 126945. doi:10.1016/j.amc.2022.126945. 
  22. ↑ Bogoya, Manuel; Serra-Capizzano, Stefano; Trotti, Ken (2022). "Upper Hessenberg and Toeplitz Bohemian matrix sequences: a note on their asymptotical eigenvalues and singular values". Electronic Transactions on Numerical Analysis 55: 76–91. doi:10.1553/etna_vol55s76. https://etna.math.kent.edu/vol.55.2022/pp76-91.dir/pp76-91.pdf. Retrieved 3 March 2022. 
  23. ↑ Hall, Frank J; Li, Zhongshan (2013). Hogben, Leslie. ed. Sign Pattern Matrices (2nd ed.). Handbook of Linear Algebra: CRC Press. pp. 42-1—42-32. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Bohemian_matrices&oldid=3370985"