A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2x2 Submatrices
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2x2 Submatrices
复制标题
计算具有 2x2 子矩阵的通用划分矩阵的秩的组合算法
DOI：
10.1007/978-3-030-45771-6_16
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Iwamasa Yuni
中科院分区：
文献类型：
--
作者：
Hirai Hiroshi;Iwamasa Yuni
本文考虑块结构符号矩阵(一般分块矩阵)的秩计算问题，其中域上有一个矩阵，并且是一个不定矩阵。这个问题可以看作二部匹配问题的代数推广，岩田和Murota(SIAM矩阵分析应用16(3)：719-734,1995)考虑了这个问题。最近对这一问题的兴趣在于与伊万尼奥斯等人的非对易埃德蒙兹问题有关。(Comput Complex 27：561-593,2018)和Garg等人。(已找到。电脑。数学课。20：223-290,2020)，其中岩田和Murota的结果隐含地指出对于这类符号矩阵，秩和非交换秩(NC-秩)是相同的。本文的主要结果是计算a-型广义分块矩阵符号秩的一种简单的组合时间算法。我们的算法是受到了伊万尼奥斯等人提出的Wong序列算法的启发。对于一般符号矩阵的NC阶，不需要爆破操作，不需要域扩展，也不需要额外注意比特大小的界限。此外，它自然为任意域提供了最大秩补全为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.