Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Nonnegative Matrix Factorization Requires Irrationality


Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. Nonnegative matrix factorization requires irrationality. SIAM Journal on Applied Algebra and Geometry (SIAGA), 1(1):285–307, 2017.


Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative nxm matrix M into a product of a nonnegative nxd matrix W and a nonnegative dxm matrix H. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries.

Suggested BibTeX entry:

    author = {Dmitry Chistikov and Stefan Kiefer and Ines Marusic and Mahsa Shirmohammadi and James Worrell},
    journal = {SIAM Journal on Applied Algebra and Geometry (SIAGA)},
    number = {1},
    pages = {285--307},
    publisher = {SIAM},
    title = {Nonnegative Matrix Factorization Requires Irrationality},
    volume = {1},
    year = {2017}

PDF (439 kB)
See ...