Metraipolis › archive › dc_bd8dacbcb7ff

Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns — arXiv:2608.12075

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.12075
License (as archived): CC0-1.0
Archived: 2026-10-19T05:52:51.494Z
SHA-256 of the archived text: b5e3e7c92a28dce01797ec5f7ff1ee763c03bbc8f74f7692b2320a757256e344
Stable URL of this page: https://metraipolis.com/documento/dc_bd8dacbcb7ff

How to cite

Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns — arXiv:2608.12075 — arXiv (en), https://arxiv.org/abs/2608.12075 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd8dacbcb7ff (Metraipolis archive dc_bd8dacbcb7ff, sha256 b5e3e7c92a28dce01797ec5f7ff1ee763c03bbc8f74f7692b2320a757256e344)

BibTeX

@misc{dcbd8dacbcb7ff,
  title = {Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns — arXiv:2608.12075},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.12075},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd8dacbcb7ff; sha256 b5e3e7c92a28dce01797ec5f7ff1ee763c03bbc8f74f7692b2320a757256e344},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12075. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2608.12075 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:48:37.119Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).