Gábor Ivanyos:
Computing the non-commutative rank of a matrix space
The (ordinary) rank of a linear space of matrices is the maximum among the ranks of its elements. The noncommutative rank is the maximum rank when we allow taking linear combinations of the matrices with coefficients from a sufficiently "large" skewfield and consider the rank over that skewfield. Computing it is a relaxation of determining the ordinary (commutative) rank. A useful and important characterization can be given in terms of a large common zero block of the matrices in the space after a change of basis. We present a deterministic polynomial time algorithm that computes the noncommutative rank. Note that existence of an efficient deterministic method computing the ordinary rank is a famous open problem in polynomial identity testing. The algorithm, which is analogous to finding maximal matchings in bipartite graphs, gives lower and upper witnesses for the rank. The lower witness is a polynomial invariant of a space of sub-matrices while the upper witness is given by a common zero block. We will also discuss some applications.