# Choosing the best submatrix

Let $$\mathbf{A}_{m\times n}$$ be a matrix with non-negative elements. Assume that a submatrix $$\mathbf{B}$$ from $$\mathbf{A}$$ is defined as \begin{align} B_{i,j} = \begin{cases} A_{i,j}, & i\in\mathcal{I},\\ 0, & \text{otherwise}, \end{cases} \end{align} where $$\mathcal{I}$$ is a subset of $$\{1,2,\cdots,m\}$$.

For a constant size of $$\mathcal{I}$$, how does one should select $$\mathcal{I}$$ such that the following quantity becomes maximum $$\|\mathbf{B}^\mathrm{T}\mathbf{B}\|_1+\|\mathbf{B}\mathbf{B}^\mathrm{T}\|_1,$$ where $$\|.\|_1$$ is defined as the sum of the all elements of the matrix, and superscript $$(.)^{\mathrm{T}}$$ denotes the transpose operatrion.

You can solve the problem via integer programming as follows. For $$i\in\{1,\dots,m\}$$, let binary decision variable $$x_i$$ indicate whether row $$i$$ is selected. Then $$B_{i,j}=A_{i,j}x_i$$, so the problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} x_i x_j$$ subject to $$\sum_{i=1}^m x_i = s$$, where $$s$$ is the desired cardinality of $$\mathcal{I}$$. Now use a mixed integer quadratic programming (MIQP) solver.
Alternatively, you can linearize the quadratic objective by introducing a new decision variable $$y_{i,j} \ge 0$$, with $$1 \le i < j \le m$$, to represent the product $$x_i x_j$$. The resulting mixed integer linear programming (MILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} y_{i,j}$$ subject to linear constraints: \begin{align} \sum_{i=1}^m x_i &= s\\ y_{i,j} &\le x_i \\ y_{i,j} &\le x_j \\ y_{i,j} &\ge x_i + x_j - 1 \end{align} Optionally, you can use the cardinality constraint to strengthen the formulation by including an additional constraint $$\sum_{i:ij} y_{j,i} = (s-1) x_j$$ for $$j\in\{1,\dots,m\}$$.