Paper Info
Title
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 ˟ 2 Submatrices.
Abstract
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 \times 2\) matrix over a field \(\mathbf {F}\) and \(x_{\alpha \beta }\) is an indeterminate for \(\alpha = 1,2,\dots , \mu \) and \(\beta = 1,2, \dots , \nu \). This problem can be viewed as an algebraic generalization of the bipartite matching problem, and was considered by Iwata and Murota (1995). One of recent interests on this problem lies in the connection with non-commutative Edmonds’ problem by Ivanyos, Qiao and Subrahamanyam (2018), and Garg, Gurvits, Oliveiva and Wigderson (2019), where a result by Iwata and Murota implicitly says that the rank and the non-commutative rank (nc-rank) are the same for this class of symbolic matrices.
Year
DOI
Venue
2020
10.1007/978-3-030-45771-6_16
IPCO
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Hiroshi Hirai182.99
Yuni Iwamasa252.84