A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 x 2 submatrices

• 成果类型: Article
• 署名作者: Hirai, Hiroshi; Iwamasa, Yuni
• 署名单位: University of Tokyo; Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01676-5
• 发表日期: 2022
• 页码: 1-37
• 关键词: Complexity

摘要

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A(alpha beta)x(alpha beta)), where A(alpha beta) is a 2 x 2 matrix over a field F and x(alpha beta) is an indeterminate for alpha = 1, 2, ..., mu and beta = 1, 2, ..., v. 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 O((mu v)(2) min{mu, v))-time algorithm for computing the symbolic rank of a (2 x 2)-type generic partitioned matrix of size 2 mu x 2v. 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 of A for an arbitrary field F.