Details

Autor(en) / Beteiligte

• Hirai, Hiroshi
• Iwamasa, Yuni

Titel

A combinatorial algorithm for computing the rank of a generic partitioned matrix with [Formula omitted] submatrices

Ist Teil von

• Mathematical programming, 2022-09, Vol.195 (1-2), p.1

Ort / Verlag

Springer

Erscheinungsjahr

2022

Link zum Volltext

Quelle

EBSCOhost Business Source Ultimate

Beschreibungen/Notizen

• In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) [Formula omitted], where [Formula omitted] is a [Formula omitted] matrix over a field [Formula omitted] and [Formula omitted] is an indeterminate for [Formula omitted] and [Formula omitted]. 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 [Formula omitted]-time algorithm for computing the symbolic rank of a [Formula omitted]-type generic partitioned matrix of size [Formula omitted]. 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 [Formula omitted].