how to minimize $sum(sum(\mod(A^T X A,2)))$

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 $sum(sum(mod(A^T X A,2)))$; that is the number of 1's in $\mod(A^T X A,2)$. $A$ is a constant binary $k \times n$ matrix; $X$ is an invertible $k \times k$ matrix. Any suggestions on how to do this?

Answer 1

Here is a partial answer. Let $\mathbb F=GF(2)$ and $r=\operatorname{rank}(A)$. There exists a vector subspace $V\subseteq\mathbb F^n$ such that $A^TV=\operatorname{range}(A^T)$. It follows that $$ \begin{aligned} \operatorname{rank}(A^TXA) &\ge\dim(V\cap\operatorname{range}(XA))\\ &=\dim V+\dim\operatorname{range}(XA)-\dim(V+\operatorname{range}(XA))\\ &\ge\dim V+\dim\operatorname{range}(XA)-n\\ &=2r-n.\\ \end{aligned} $$ Thus $\operatorname{rank}(A^TXA)\ge\max(2r-n,0)$. Hence $A^TA$ has $\max(2r-n,0)$ linearly independent columns. In turn, the number of ones in $A^TXA$ is at least $\max(2r-n,0)$.

When $2r\le n$, the aforementioned lower bound is sharp. That is, there exists some $X\in GL_n(\mathbb F)$ such that $A^TXA=0$: just take any $X$ that takes the range of $A$ into the null space of $A^T$. For instance, by using elementary row and column operations, we may express $A$ as $P\pmatrix{I_r\\ &0}Q$, where $P$ and $Q$ are products of elementary matrices in $GL_n(\mathbb F)$. Take $X=(P^{-1})^T\pmatrix{0&I_{n-r}\\ I_r&0}P^{-1}$. Then $A^TXA=0$.

When $r>\frac{n}{2}$, however, the aforementioned lower bound is not always achievable. For example, consider the case where $u=(1,1)^T$, $$ A=\pmatrix{I_2&u\\ 0&0}, \quad X=\pmatrix{Y_{2\times 2}&z\\ z^T&w}, \quad A^TXA=\pmatrix{Y&Yu\\ u^TY&u^TYu}. $$ In this example, we have $n=3,\,r=2$ and $\max(2r-n,0)=1$. However, $A^TXA$ cannot possibly has only one nonzero element. For, if $X$ is invertible, then $Y$ is either invertible or rank-one. Hence it contains at least one $1$. So, if $A^TXA$ has only one $1$, then $Yu$ and $u^TY$ must be zero. Since $u$ is the all-one vector, this means all elements of $Y$ have the same parity. But then $Y$ will be the all-one matrixwhich is a contradiction to the assumption that $A^TXA$ only one $1$.