For the solution to the problem, please read other editorials.

This is a proof that this problem is NP-complete, just for fun.

Let \(G=(V,E)\) be any simple undirected graph, and \(k\) be any positive integer. We will show that a special case of this problem solves the clique decision problem (“does \(G\) contain a clique of \(k\) vertices?”), which is known to be NP-complete.

Let \(A\) be the adjacency matrix of \(G\), except that all diagonal elements are changed to \(2\). Formally:

\[ a_{ij}=\begin{cases} 2 & (i=j)\\ 1 & (e_{ij}\in E) \\ 0 & \text{(Otherwise)} \end{cases} \]

Let \(B\) be a \(k\times k\) matrix, where all diagonal elements are \(2\), and all other elements are \(1\). Formally:

\[ b_{ij}=\begin{cases} 2 & (i=j)\\ 1 & (i\neq j) \end{cases} \]

Due to \(2\)’s on the diagonals, if \(B\) is a submatrix of \(A\), the set of selected indices for rows and columns must be the same, and it is the set of vertices that form a clique. Conversely, for any clique of \(k\) vertices in \(G\), selecting rows and columns corresponding to vertices in the clique yields \(B\).