how to minimize trace(mod(A*X,2)) for A ,X matrices

Question

I have a constant binary matrix $A$ (entries $0$ or $1$) and an unknown matrix $X$ which is also binary. I'd like to find $X$ that minimizes $trace(mod(A*X),2))$. So basically I do a matrix multiply of $A$ and $X$ as if they are over finite field GF(2), that's what the $mod(*,2)$ is doing, but I want the trace over the integers. The $mod$ operation creates problems for all what I tried. Any suggestions on how to do this? ($X$ is constrained to be an invertible matrix over GF(2))

Answer 1

One may use elementary column operations to bring $A$ to column reduced echelon form. This, in particular, implies that for some invertible matrix $X_1\in GL_n(GF(2))$, we have $$ AX_1=\pmatrix{I_k&0\\ \ast&L} $$ where $L$ is a lower triangular matrix with a zero diagonal ($I_k$ is void if the first row of $A$ is zero; $L$ is empty and $AX_1=I$ if $A$ is invertible). Now let $C$ be the $k\times k$ permutation matrix for a cyclic shift and $$ X_2=\pmatrix{C\\ &I_{n-k}}. $$ Then $$ AX_1X_2=\pmatrix{C&0\\ \ast&L} $$ has a zero diagonal. Hence its integer matrix reincarnation also has a zero diagonal and a zero trace.