# The Extraction of Maximal-Sum Principal Submatrix and Its Applications
## 3 Problem Description and Related Property
### Problem Description  
The notations in this paper are defined as follows. Vectors are represented as bold lowercase characters \(x,y\), etc. Matrices are represented as uppercase characters \(A,B,\) etc. Elements in vectors and matrices, as well as scalars in general, are represented as normal italic characters, \(x_{i},m_{ij},i,\) etc.  
Let an \(n\)-order real matrix \(A=\big{(}a_{ij}\big{)}_{n\times n}(\forall i,j\in L)\), where \(L=\{1,2,3,\cdots,n\}\) is a sequence number set and \(|\cdot|\) is the cardinal number of a set.  
**Definition 1**.: _Let \(I\subseteq L,|I|=k\); the submatrix \(A_{I}^{(k)}\) consisting of the cross elements of \(1\) rows and \(I\) columns contained in the real matrix \(A\) is called the \(k\)-order principal submatrix of matrix \(A\)._  
**Definition 2**.: _Among all \(k\)-order principal submatrices of \(A\), the maximal-sum principal submatrix (MSPS) \(A_{I^{*}}^{(k)}\) maximizes the sum of the elements._The problem of finding the MSPS of matrix \(A\) can be formulized as an optimization problem:  
\[A_{I^{*}}^{(k)}=arg\underset{I\subseteq\mathbb{L}}{\max}\Big{\|}A_{I}^{(k)} \Big{\|}_{S} \tag{1}\]  
where the sum of matrix elements is denoted by \(\left\|\cdot\right\|_{S}\), i.e.,  
\[\left\|A\right\|_{S}=\sum_{i,j\in\mathbb{L}}a_{ij} \tag{2}\]  
Let \(I^{*}\) be the optimal index set and \(A_{I^{*}}^{(k)}\) be the optimal solution. The optimal value is \(S^{*}\) as  
\[S^{*}=\left\|A_{I^{*}}^{(k)}\right\|_{S}=\underset{I\subseteq\mathbb{L}}{ \max}\Big{\|}A_{I}^{(k)}\Big{\|}_{S}=\sum_{i,j\in I^{*}}a_{ij} \tag{3}\]  
It is easy to know that matrix \(A\) and its transposed matrix \(A^{\mathbb{T}}\) have the same MSPS and the optimal index set, as well as the optimal solution. If a positive integer \(k\) is specified, both the optimal index set and the optimal solution perhaps are not unique, but the optimal value is unique.  
**Example 1**.: Let \(A\) be a real matrix, \(A=\begin{bmatrix}2&-1&3&0\\ -1&0&4&2\\ 3&4&2&2\\ 1&2&2&-1\end{bmatrix}\). When \(k=2\), there are two optimal solutions \(A_{\{1,3\}}^{(2)}=\begin{bmatrix}2&3\\ 3&2\end{bmatrix}\) and \(A_{\{2,3\}}^{(2)}=\begin{bmatrix}0&4\\ 4&2\end{bmatrix}\), the corresponding optimal index sets are respectively \(I^{*}=\{1,3\}\) and \(I^{*}=\{2,3\}\), and the optimal value is \(S^{*}=10\).  
**Example 2**.: _Matrix \(A\) is a non-negative symmetric matrix of \(m\)-order,_  
\[A=\begin{bmatrix}m&m-1&m-2&\cdots&1\\ m-1&m-1&m-2&\cdots&1\\ m-2&m-2&m-2&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&1\end{bmatrix}.\]  
_For the matrix, if \(k\) is specified, the MSPS of \(k\)-order is_  
\[A_{I^{*}}^{(k)}=\begin{bmatrix}m&m-1&\cdots&m-k+1\\ m-1&m-1&\cdots&m-k+1\\ \vdots&\vdots&\ddots&\vdots\\ m-k+1&m-k+1&m-k+1&m-k+1\end{bmatrix}.\]  
_The optimal index set \(I^{*}=\{1,2,\cdots,k\}\), and the optimal value is_  
\[S^{*}=k^{2}m-\sum_{i=1}^{k}(k-i)[2(k-i)+1]=k^{2}m-\frac{k(k-1)(4k+1)}{6}.\]  
**Remark**.: _The matrix \(A\) in this example is related to the optimal layout of the stacked graph for visualizing multi-dimensional time series data [13]._