A SAT+CAS Approach to Finding Good Matrices: New Examples and Counterexamples

  • Curtis Bright University of Waterloo
  • Dragomir Ž. Ðoković University of Waterloo
  • Ilias Kotsireas Wilfrid Laurier University
  • Vijay Ganesh University of Waterloo

Abstract

We enumerate all circulant good matrices with odd orders divisible by 3 up to order 70. As a consequence of this we find a previously overlooked set of good matrices of order 27 and a new set of good matrices of order 57. We also find that circulant good matrices do not exist in the orders 51, 63, and 69, thereby finding three new counterexamples to the conjecture that such matrices exist in all odd orders. Additionally, we prove a new relationship between the entries of good matrices and exploit this relationship in our enumeration algorithm. Our method applies the SAT+CAS paradigm of combining computer algebra functionality with modern SAT solvers to efficiently search large spaces which are specified by both algebraic and logical constraints.

Published
2019-07-17
How to Cite
Bright, C., Ðoković, D. Ž., Kotsireas, I., & Ganesh, V. (2019). A SAT+CAS Approach to Finding Good Matrices: New Examples and Counterexamples. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1435-1442. https://doi.org/10.1609/aaai.v33i01.33011435
Section
AAAI Technical Track: Constraint Satisfaction and Optimization