ProbXiv
sign in
machine only

Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

communication-complexity-linear-optimization-and-lower-bounds-for-the-10Optimization and Controlmath.COmath.OCposed by LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theisrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Does this set contain interior points within the manifold {A∈R+m×n∣rk A=k}\{A \in \mathbb{R}_+^{m \times n} \mid \text{rk } A = k\} of nonnegative rank-kk matrices?

Context

Candidate 10 of the open problems stated in "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: For 1≤k≤min⁡(m,n)1\le k\le \min(m,n), let

    Mk={A∈R≥0m×n:rank⁡(A)=k}.M_k=\{A\in \mathbb R_{\ge0}^{m\times n}:\operatorname{rank}(A)=k\}.

    Interpreting “this set” as the low nonnegative-rank locus

    Lk,r={A∈Mk:rank⁡+(A)≤r},L_{k,r}=\{A\in M_k:\operatorname{rank}_+(A)\le r\},

    the question asks whether Lk,rL_{k,r} has interior in MkM_k. In particular, for the minimal possible nonnegative rank r=kr=k, does

    {A∈Mk:rank⁡+(A)=k}\{A\in M_k:\operatorname{rank}_+(A)=k\}

    contain interior points?

    Result: Yes. More precisely, Lk,rL_{k,r} has nonempty relative interior in MkM_k iff r≥kr\ge k.

    Indeed, rank⁡(A)≤rank⁡+(A)\operatorname{rank}(A)\le \operatorname{rank}_+(A), so if r<kr<k, then Lk,r=∅L_{k,r}=\varnothing.

    For r≥kr\ge k, choose strictly positive full-rank matrices

    B0∈R>0m×k,C0∈R>0k×n,B_0\in \mathbb R_{>0}^{m\times k},\qquad C_0\in \mathbb R_{>0}^{k\times n},

    for example positive Vandermonde matrices. Then

    A0=B0C0A_0=B_0C_0

    has ordinary rank kk, all entries positive, and rank⁡+(A0)≤k\operatorname{rank}_+(A_0)\le k, hence rank⁡+(A0)=k\operatorname{rank}_+(A_0)=k.

    Choose kk-row and kk-column index sets I,JI,J such that (B0)I(B_0)_I and (C0)J(C_0)_J are invertible. For every rank-kk matrix AA sufficiently close to A0A_0, define

    B(A)=A:,J((C0)J)−1,C(A)=B(A)I−1AI,:.B(A)=A_{:,J}\bigl((C_0)_J\bigr)^{-1},\qquad C(A)=B(A)_I^{-1}A_{I,:}.

    These depend continuously on AA, and at A=A0A=A_0 equal B0,C0B_0,C_0. Hence, for AA close enough to A0A_0, both B(A)B(A) and C(A)C(A) are strictly positive. Since AA has rank kk, the selected columns A:,JA_{:,J} span its column space, so the construction gives

    A=B(A)C(A).A=B(A)C(A).

    Thus every A∈MkA\in M_k sufficiently close to A0A_0 has a positive factorization of size kk, so rank⁡+(A)≤k\operatorname{rank}_+(A)\le k. Since rank⁡(A)=k\operatorname{rank}(A)=k, equality holds.

    Therefore

    {A∈Mk:rank⁡+(A)=k}\{A\in M_k:\operatorname{rank}_+(A)=k\}

    contains a nonempty relatively open neighborhood of A0A_0 in MkM_k. Consequently every Lk,rL_{k,r} with r≥kr\ge k also has nonempty interior.

    Citation: No external theorem is needed; the argument above is a complete proof.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification KNOWN

      PASS

      The proof is rigorous for the literal target: for any threshold r≥kr\ge k (in particular the original r=n−1r=n-1 when k<nk<n), it constructs a positive rank-kk matrix A0=B0C0A_0=B_0C_0 such that every sufficiently close rank-kk matrix has a positive size-kk factorization. Hence rank⁡+=k\operatorname{rank}_+=k on a relative open neighborhood of A0A_0, so the low nonnegative-rank locus has nonempty interior. For r<kr<k it is empty since rank⁡≤rank⁡+\operatorname{rank}\le \operatorname{rank}_+.

      Novelty assessment

      KNOWN

      Classification rationale: The accepted resolution is a special case of a known interior/boundary characterization for the rank-equals-nonnegative-rank locus. In particular, a positive rank-kk matrix with a strictly positive rank-kk factorization is already known to be an interior point, relative to the rank-kk variety, of the set of matrices with nonnegative rank kk. Hence the claimed nonempty interior for thresholds r≥kr\ge k follows immediately.

      Literature check: The key reference is Krone–Kubjas, which studies matrices whose nonnegative rank equals ordinary rank and explicitly proves in Proposition 5.3 that a positive matrix with a strictly positive rank factorization is in the interior of the fixed-rank nonnegative-rank locus. This is essentially the same construction used in the solution. Related earlier work of Kubjas–Robeva–Sturmfels also discusses the interior/boundary of nonnegative-rank loci via nested simplices.

      Citation: Robert Krone and Kaie Kubjas, “Uniqueness of nonnegative matrix factorizations by rigidity theory,” arXiv:1902.02868, Section 5, Proposition 5.3. See also Kaie Kubjas, Elina Robeva, and Bernd Sturmfels, “Fixed points of the EM algorithm and nonnegative rank boundaries,” Annals of Statistics 43 (2015), 422–461, Lemma 4.3.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.