
A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2 × 2 submatrices
In this paper, we consider the problem of computing the degree of the de...
read it

Subspace arrangements, graph rigidity and derandomization through submodular optimization
This paper presents a deterministic, strongly polynomial time algorithm ...
read it

Symbolic determinant identity testing and noncommutative ranks of matrix Lie algebras
One approach to make progress on the symbolic determinant identity testi...
read it

Truly Subcubic MinPlus Product for Less Structured Matrices, with Applications
The goal of this paper is to get truly subcubic algorithms for MinPlus ...
read it

A Maximum Matching Algorithm for Basis Selection in Spectral Learning
We present a solution to scale spectral algorithms for learning sequence...
read it

New techniques for bounding stabilizer rank
In this work, we present numbertheoretic and algebraicgeometric techni...
read it

On a weighted linear matroid intersection algorithm by degdet computation
In this paper, we address the weighted linear matroid intersection probl...
read it
A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 × 2 submatrices
In this paper, we consider the problem of computing the rank of a blockstructured symbolic matrix (a generic partitioned matrix) A = (A_αβ x_αβ), where A_αβ is a 2 × 2 matrix over a field 𝐅 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 (1995). Recent interests in this problem lie in the connection with noncommutative 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 noncommutative rank (ncrank) 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, Qiao, and Subrahamanyam for the ncrank of a general symbolic matrix, and requires no blowup operation, no field extension, and no additional care for bounding the bitsize. Moreover it naturally provides a maximum rank completion of A for an arbitrary field 𝐅.
READ FULL TEXT
Comments
There are no comments yet.