Let $S = \begin{pmatrix} A & B \\ B & A \end{pmatrix} \in \mathbb{R}^{2n \times 2n}$ be a positive semi-definite matrix with matrices $A, B \in \mathbb{R}^{n \times n}$ being symmetric. Let $y_{1}, y_{2} \in \{0,1\}^{n\times 1}$ be two binary vectors.
The optimization problem is to maximize the following quadratic convex function with binary constraints: $$ \text{maximize}_{y_{1}, y_{2} \in \{0,1\}^{n\times 1}} \bigl(\begin{smallmatrix} y_1 \\ y_2 \end{smallmatrix}\bigr)^{\mathrm{T}} S \bigl(\begin{smallmatrix} y_1 \\ y_2 \end{smallmatrix}\bigr), $$ i.e., selecting a principal submatrix to maximize the sum of entry values.
I wonder if it is possible to show that an optimal solution has $y_1 = y_2$? Since the problem is so symmetric, this seems a bit intuitive to me.
The answer is no. As a counterexample, with $n=1$: take $A = 1, B = -1$. The optimal solutions are $(1,0),(0,1)$. A similar phenomenon occurs in general with $A = I, B = -I$.