Totally equimodular matrices: decomposition and triangulation

• 成果类型: Article; Early Access
• 署名作者: Chervet, Patrick; Grappe, Roland; Vallee, Mathieu
• 署名单位: Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02347-z
• 发表日期: 2026-03-26
• 关键词: Hilbert basis; Polyhedral cone; Totally equimodular matrix; totally unimodular matrix; triangulation; UNIMODULAR TRIANGULATIONS; INTEGER ANALOG; CARATHEODORY; bounds; bases

摘要

Totally equimodular matrices generalize totally unimodular matrices and arise in the context of box-totally dual integral polyhedra. This work further explores the parallels between these two classes and introduces foundational building blocks for constructing totally equimodular matrices. Consequently, we present a decomposition theorem for totally equimodular matrices of full row rank. Building on this decomposition theorem, we prove that simplicial cones whose generators form the rows of a totally equimodular matrix satisfy strong integrality decomposition properties. More precisely, we provide the Hilbert basis for these cones and construct regular unimodular Hilbert triangulations in most cases. We conjecture that cases not covered here do not exist.