# Find index for submatrix with maximum sum

Given an N-dimensional matrix A, I want to find an M<N dimensional index array I such that the submatrix A[I, I] has the maximum element sum over all such I vectors.

For example for 3-dimensional

A =
1  2  3
4  5  6
7  8  9


and 2-dimensional index [1,3]

A[(1,3), (1,3)] =
1  3
7  9


So basically this is a discrete optimisation problem with N choose M possible solutions.

Is there an efficient way to find the best solution?

• Are the entries in $A$ all nonnegative, or could some entries be negative? – Brian Borchers Jan 10 at 16:32
• @BrianBorchers, $A$ is a correlation matrix, so potentially [-1,1]. But most use cases for me have only nonnegative elements (or small neg numbers can be treated as 0 considering estimation error). – jf328 Jan 13 at 0:53