Suppose $x, y \in \{0,1\}^d$ are binary vectors. For a matrix $M$ consider the quadratic form, \begin{align} x^T M y + (\mathbb{1} - x)^T M (\mathbb{1} - y) \end{align} Does there exist an $M$ such that for any $x$, the above quadratic form is uniquely maximized at $y=x$, and at the same time, $M$ is low rank?
While the identity matrix satisfies the first criterion, it fails to satisfy the second.
The form you consider is not quadratic but linear in $y$, if I don’t miss anything. If so, there is no hope for such matrix $M$.
Perform the change $x'=2x-\mathbb 1$, $y'=2y-\mathbb 1$, so that $x,y\in Q=\{-1,1\}^d$. Then the function you consider is $$ x^T My+(\mathbb 1-x)^TM(\mathbb 1-y)=\frac14(\mathbb 1+x')M(\mathbb 1+y')+\frac14(\mathbb 1-x')M(\mathbb 1-y')\\=\frac12\mathbb 1^TM\mathbb 1+\frac12x'^TMy', $$ so, in the new setting, we are to maximize $f_{x}(y)=x^TMy$ with $x,y\in Q$.
Let $Q^*=MQ$ be the image of $Q$ under the linear transform defined by $M$. As any affine function, the function $f_x(y^*)= x^Ty^*$ is maximized on $y^*\in Q^*$ at some vertex of the convex hull of $Q’$. But it cannot happen that all points in $Q’$ are distint vertices of the convex hull of $Q’$ if $M$ is degenerate.
Indeed, consider the smallest $k$ such that the imafe of sume $k$-dimensional face of $Q$ under $M$ is degenerate. Without loss of generality, we may assume that $M(\{-1,1\}^k\times \{0\}^{d-k})$ lies in some $(k-1)$-dimensional subspace, and restrict $M$ to the first $k$ coordinates.
There is a nonzero vector $v=(v_1,\dots,v_k)^T$ such that $Mv=0$. If some coordinate of $v$ is $0$, this means that $k$ is not minimal; hence we may assume that $v_i>0$ for all $i$, and that $v_1=\min_i v_i$. Then $(1,1,\dots,1)^T$ lies in the convex hull of $v_1^{-1}v$ and all other vectors in $\{1,-1\}^k$ So its image is not a vertex.
