A zero-sum selection game on matrices: dimension, the order-three case, and complexity
Two players play on a real n × n matrix. The Enemy selects i entries of row i for each i; then You choose one selected entry in every row, and You win if your entries sum to zero. Vsevolod Lev asked on MathOverflow (question 453809) for a description of the matrices on which You always win. We prove that the winning matrices form a finite union of rational linear subspaces whose largest has dimension exactly n(n+1)/2 - 1 (for rows of length Ni with quotas ki, Σki - 1), by a rank argument; that a 3 × 3 matrix is winning exactly when every first-row entry has two usable second-row positions, which gives five explicit families when the rows have distinct entries; and that recognising winning integer matrices is Π2p-complete, even with two values per row, so no polynomial-time description exists unless the polynomial hierarchy collapses. The rank lemma, the dimension theorem, the order-three criterion and classification and the two-valued normal form behind the hardness proof are formally verified in Lean 4. The archive holds the LaTeX source, the Lean development with mutation tests and an independent checking program (code under the MIT licence). Version 2 of the preprint (version 1: 9 October 2026); identical to the folder zero-sum-selection-game at tag zero-sum-selection-game-v2 in github.com/jvvk/mathematics.
Authors
- Vamshi Jandhyala (ORCID: https://orcid.org/0009-0006-6708-5805)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24406691
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint