# The Extraction of Maximal-Sum Principal Submatrix and Its Applications
## 1 Introduction  
The theory, application, and algorithm on maximal-sum submatrix (MSS) have received a lot of attention recently [1; 2]. The MSS problem, also known as the maximum subarray problem [3; 4], is to find the submatrix that maximizes the sum of matrix elements in it. The solutions to many application problems, such as solving the rectilinear picture compression [5] and finding a subset of genes that is relatively highly expressed among a subset of patients [1], can be converted to finding the maximal-sum submatrix from a matrix. The rows and columns in a matrix similar to the above two examples represent two different variables with different meanings.  
However, there is also a special kind of real matrix from practice applications, whose rows and columns represent the same variable, such as correlation coefficient matrix, covariance matrix, and adjacency matrix. One of these specific cases is selecting the most informative principal submatrix of a pre-specified size from a covariance matrix [6] or the maximum edge-weighted subgraph from a weighted undirected graph [7]. It is necessary to choose the same k rows and k columns for the maximum sum submatrix to have practical significance. Therefore, finding the \(k\)-order MSS is transformed into finding the \(k\)-order maximal-sum principal submatrix (MSPS).  
Although the issue of finding the MSPS is much closer to the MSS problem, there are still many differences between the two issues, including:  
1. The integer programming models describing the two problems are different;
2. The formats of their solutions to the problems are different;
3. The purposes of the application problems are different.  
Therefore, the algorithm for solving the MSPS issue differs from that for solving the MSS problem.  
In fact, extracting the MSPS from a real matrix is a typical combinatorial optimization problem and an NP-hard problem [1]. The challenge lies in the high computational complexity of finding an accurate solution. The total number of searches for the \(k\)-order MSPSfrom an \(n\)-order real matrix \(A\) is \(C_{n}^{k}=(n-k)!/(k!)\). When \(n\) and \(k\) are both relatively large, the computational cost is very large.  
To improve the computational efficiency, there are two ways that can be taken into account. One is to reduce the number of comparisons of two submatrices; the other is to reduce the number of addition operations for submatrix elements. We, in this paper, construct a fast algorithm to extract the maximal-sum principal submatrix from a real matrix, called the fusion row update accelerated algorithm, and apply this algorithm to the color combination selection problem to maximize color difference and the stock investment portfolio selection to minimize correlation degree, which decreases the investment risk in the view of the volatility of daily returns.  
The remainder of the paper is organized as follows. Section 2 briefly surveys the related works. Section 3 describes the problem and derives related properties. Section 4 develops the algorithm for finding the MSPS. Section 5 conducts several numerical experiments to demonstrate the efficiency and the solution quality of our proposed algorithm. Section 6 presents two applications. Section 7 concludes the paper and lists the limitations of the proposed algorithm.