Minimal density conjugation of binary matrices

We define the notion of minimal density of an n×n binary matrix, which is the smallest number of non-zero entries a matrix can have after conjugation by an element of GL(n,2). We give upper bounds on the minimal density for two important cases. We discuss how minimal density behaves with respect to block diagonal matrices and Jordan blocks whose eigenvalues are all one. We also give an algorithm for computing the minimal density which is reasonably fast when the density is low. Finally, we compute the largest minimal density that an n×n matrix can have when n≠6k+1 for k⩾2.