论文标题
一种用于计算$ 2 \ times 2 $子贴片的通用分区矩阵等级的组合算法
A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices
论文作者
论文摘要
在本文中，我们考虑了计算块结构符号矩阵（一个通用分区矩阵）$ a =（a_ {αβ} x_ {αβ}）$的问题对于$α= 1,2，\ dots，μ$和$β= 1,2，\ dots，ν$。这个问题可以看作是两分匹配问题的代数概括，伊瓦塔和穆塔（1995）被考虑。 Recent interests in this problem lie 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 states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. 本文的主要结果是一种简单而组合的$ O（（（（μν）^2 \ min \ {μ，ν\}）$ - 计算计算符号级别的时间算法，用于计算$（2 \ times 2）$ - 类型的通用分区矩阵的符号级别，大小$2μ\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {^2 \ o（（2）$（2 \ timess 2）$ 2m \ \ \ \ \ \ fime。我们的算法灵感来自Ivanyos，Qiao和Subrahamanyam的Wong序列算法，用于一般符号基质的NC级别，并且不需要不爆炸操作，不进行场扩展，并且不需要界定界定位尺寸的额外护理。此外，它自然提供了任意字段$ \ mathbf {f} $的最大排名完成$ a $。
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 \times 2$ matrix over a field $\mathbf{F}$ and $x_{αβ}$ is an indeterminate for $α= 1,2,\dots, μ$ and $β= 1,2, \dots, ν$. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (1995). Recent interests in this problem lie 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 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 \times 2)$-type generic partitioned matrix of size $2μ\times 2ν$. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam 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 $\mathbf{F}$.
