Minimal density conjugation of binary matrices (Q544134)

Let \(d(M)\) denote the density (the number of non-zero entries) of an \(n\times n\) non-singular binary matrix \(M\). The minimal density of \(M\) is defined to be: \(\delta (M)=\min \{d(LML^{-1}): L\in GL(n,2)\}\). The authors characterize the minimal density of \(M\) when \(M\) is a companion matrix of a polynomial of degree at most four. The minimal density of a Jordan block whose eigenvalues are all one has been computed. The authors show that the minimal density of an \(n\times n\) matrix is bounded above by \(3n/2\). An algorithm for computing the minimal density (when it is low) is given.