DETERMINANT OPTIMIZATION ON BINARY MATRICES

摘要

Structural connections between m x n (-1,1)-matrices A such that A has the maximum number of (2 x 2)-submatrices with nonzero determinant and m x n (-1,1)-matrices B that maximize det(B~tB) are explored. The two types of matrices can be defined as solutions to two instances of the same optimization problem. The focus is on matrices satisfying the former property, specifically the most difficult case when A is n x n with n = 4k + 1, k a natural number. Constructive approaches and a tabu search are developed and are found to provide near-optimal solutions for 13 < n ≤ 41. The best known solutions to date are found for n = 4k + 1 ≤ 41.