Nonnegative rank

  • Kaie Kubjas (Aalto University)
Live Stream


Let M be a matrix with nonnegative entries. Its nonnegative rank is the smallest natural number r such that M can be written as a sum of r rank one matrices whose entries are nonnegative. Cohen and Rothblum asked in 1993: Given a non-negative matrix with rational entries, does its non-negative rank over the rational numbers agree with its non-negative rank over the real numbers? After 23 years, two groups (Chistikov et al; Shitov) simultaneously posted papers where they construct matrices that answer this question negatively. Matrices whose nonnegative rank over reals differs from their nonnegative rank over rationals have restricted sets of nonnegative factorizations. This means that they are on the boundary of the set of matrices of nonnegative rank at most r. These boundaries are completely understood for matrices of nonnegative rank at most three. Connection with rigidity theory allows to obtain partial understanding of boundaries for higher nonnegative rank. For nonnegative rank at most three, complete understanding of boundaries allows one to derive semi-algebraic characterizations of these sets.


17.03.20 21.02.22

Nonlinear Algebra Seminar Online (NASO)

MPI for Mathematics in the Sciences Live Stream

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail