{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih5mfn7iii22q3lt7d43g3attrb25syn3xgmnzt6wmdpopz5aizi4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf3zukqgc4p2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.14037v1",
  "publishedAt": "2026-02-17T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Angshul Majumdar"
  ],
  "textContent": "**Authors:** Angshul Majumdar\n\nWe study the decision problem Affine Rank Minimization, denoted ARM(k). The input consists of rational matrices A_1,...,A_q in Q^{m x n} and rational scalars b_1,...,b_q in Q. The question is whether there exists a real matrix X in R^{m x n} such that trace(A_l^T X) = b_l for all l in {1,...,q} and rank(X) <= k. We first prove membership: for every fixed k >= 1, ARM(k) lies in the existential theory of the reals by giving an explicit existential encoding of the rank constraint using a constant-size factorization witness. We then prove existential-theory-of-reals hardness via a polynomial-time many-one reduction from ETR to ARM(k), where the target instance uses only affine equalities together with a single global constraint rank(X) <= k. The reduction compiles an ETR formula into an arithmetic circuit in gate-equality normal form and assigns each circuit quantity to a designated entry of X. Affine semantics (constants, copies, addition, and negation) are enforced by linear constraints, while multiplicative semantics are enforced by constant-size rank-forcing gadgets. Soundness is certified by a fixed-rank gauge submatrix that removes factorization ambiguity. We prove a composition lemma showing that gadgets can be embedded without unintended interactions, yielding global soundness and completeness while preserving polynomial bounds on dimension and bit-length. Consequently, ARM(k) is complete for the existential theory of the reals; in particular, ARM(3) is complete. This shows that feasibility of purely affine constraints under a fixed constant rank bound captures the full expressive power of real algebraic feasibility.",
  "title": "Affine Rank Minimization is ER Complete"
}