A combinatorial algorithm for computing the rank of a generic partitioned matrix with $$2 \times 2$$ submatrices
A combinatorial algorithm for computing the rank of a generic partitioned matrix with $$2 \times 2$$ submatrices
复制标题
用于计算具有 $$2 imes 2$$ 子矩阵的通用划分矩阵的秩的组合算法
DOI：
10.1007/s10107-021-01676-5
复制
发表时间：
2021
影响因子：
2.7
通讯作者：
Hirai Hiroshi and Iwamasa Yuni
中科院分区：
文献类型：
--
作者：
Yuho Tanaka;Kazunori Uruma;Tomoki Nakao;Yuni Iwamasa;田中 勇帆，雨車 和憲，中尾 朋喜;Hirai Hiroshi and Iwamasa Yuni;Hirai Hiroshi and Iwamasa Yuni
本文考虑了一个块结构符号矩阵（一般分块矩阵）的秩计算问题，其中该矩阵在一个域上是一个不定式。Iwata和Murota （SIAM J .矩阵学报，16(3):719-734,1995）考虑了这个问题，它可以看作是二部匹配问题的代数推广。最近对该问题的兴趣在于与Ivanyos等人（Comput Complex 27:561-593, 2018）和Garg等人（Found.）的非交换Edmonds问题的联系。第一版。数学。20:23 - 290,2020)，其中Iwata和Murota的结果隐式地说明了这类符号矩阵的秩和非交换秩（nc-rank）是相同的。本文的主要成果是计算大小为a型的一般划分矩阵的符号秩的一种简单的组合时间算法。我们的算法的灵感来自于Ivanyos等人对一般符号矩阵的nc秩的Wong序列算法，并且不需要放大操作，不需要域扩展，也不需要额外的关心位大小的边界。此外，它自然地为任意字段提供a的最大秩补全。
In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix), whereis amatrix over a fieldandis an indeterminate forand. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds’ problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial-time algorithm for computing the symbolic rank of a-type generic partitioned matrix of size. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion ofAfor an arbitrary field.