MathDB
Non-negative linear combinations cover Z^n

Source: 2021 Miklos Schweitzer, P1

November 2, 2021
linear algebranumber theory

Problem Statement

Let n,m∈Nn, m \in \mathbb{N}; a1,…,am∈Zna_1,\ldots, a_m \in \mathbb{Z}^n. Show that nonnegative integer linear combinations of these vectors give exactly the whole Zn\mathbb{Z}^n lattice, if m≥nm \ge n and the following two statements are satisfied:
[*] The vectors do not fall into the half-space of Rn\mathbb{R}^n containing the origin (i.e. they do not fall on the same side of an n−1n-1 dimensional subspace), [*] the largest common divisor (not pairwise, but together) of n×nn \times n minor determinants of the matrix (a1,…,am)(a_1,\ldots, a_m) (which is of size m×nm \times n and the ii-th column is aia_i as a column vector) is 11.
Back to ProblemsView on AoPS