1. A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2×2 submatrices.
- Author
-
Hirai, Hiroshi and Iwamasa, Yuni
- Subjects
MATRICES (Mathematics) ,ALGORITHMS ,MATHEMATICS ,GENERALIZATION ,BIPARTITE graphs - Abstract
In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A α β x α β) , where A α β is a 2 × 2 matrix over a field F and x α β is an indeterminate for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν . 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 ((μ ν) 2 min { μ , ν }) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ × 2 ν . 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 . [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF