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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A zero-sum selection game on matrices: dimension, the order-three case, and complexity

Vamshi Jandhyala
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

A zero-sum selection game on matrices: dimension, the order-three case, and complexity

Vamshi Jandhyala
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon