Statistical mechanics of the maximum-average submatrix problem

We study the maximum-average submatrix problem, wherein given an N x N matrix J, one needs to find the k x k submatrix with the largest average number of entries. We investigate the problem for random matrices J, whose entries are i.i.d. random variables, by mapping it to a variant of the Sherrington-Kirkpatrick spin-glass model at fixed magnetisation. We analytically characterise the phase diagram of the model as a function of the submatrix average and the size of the submatrix k in the limit N → ∞. We consider submatrices of size k=mN with 0