论文标题
识别矩阵和多面体的笛卡尔产品
Recognizing Cartesian products of matrices and polytopes
论文作者
论文摘要
矩阵$ s_1 \ in \ mathbb {r}^{m_1 \ times n_1} $和$ s_2 \ in \ mathbb {r}^{m_2 \ times n_2} $是$ \ mathbb {r} r}^r}^n tipes in \ mathbb {m_2 \ time n_2 n_2 n_2} $列是$ S_1 $的每列的串联，每列的$ S_2 $。我们的主要结果是针对以下问题的多项式时间算法：给定矩阵$ s $，是1种产品$ s $，直到排的排列？我们的主要动机是矩阵的1产品与笛卡尔产品之间的紧密联系，这贯穿了松弛矩阵的概念。确定给定矩阵是否是一个松弛矩阵是一个有趣的问题，其复杂性是未知的，我们的算法将问题降低为不可还原实例。我们的算法是基于最大程度地降低信息理论中表达相互信息的对称的函数。我们还给出了多项式时间算法，以识别一种更复杂的基质产物，称为2-产品。最后，作为我们的1产品和2产物识别算法的推论，我们获得了一种多项式时间算法，以识别$ 2 $级的矩阵基碱基多型的松弛矩阵。
The 1-product of matrices $S_1 \in \mathbb{R}^{m_1 \times n_1}$ and $S_2 \in \mathbb{R}^{m_2 \times n_2}$ is the matrix in $\mathbb{R}^{(m_1+m_2) \times (n_1n_2)}$ whose columns are the concatenation of each column of $S_1$ with each column of $S_2$. Our main result is a polynomial time algorithm for the following problem: given a matrix $S$, is $S$ a 1-product, up to permutation of rows and columns? Our main motivation is a close link between the 1-product of matrices and the Cartesian product of polytopes, which goes through the concept of slack matrix. Determining whether a given matrix is a slack matrix is an intriguing problem whose complexity is unknown, and our algorithm reduces the problem to irreducible instances. Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information in information theory. We also give a polynomial time algorithm to recognize a more complicated matrix product, called the 2-product. Finally, as a corollary of our 1-product and 2-product recognition algorithms, we obtain a polynomial time algorithm to recognize slack matrices of $2$-level matroid base polytopes.
