Armed with basic knowledge about lattices in R^n and volumes, we can define two properties of regions that will later prove crucial. A region is convex if given any two points in the region, all points between them are in the region. More formally, given v1 and v2 in the region, we want av1 + (1-a)v2 to be in the region for every real number a between 0 and 1. A region is symmetric if it’s symmetric about the point 0, i.e. if given v1 in the region, the point –v1 is in the region.
Both of these properties are preserved under linear transformations, defined as maps between vector spaces over the same field such that T(v1 + v2) = T(v1) + T(v2) and T(kv) = kT(v) (for a fixed finite basis, every matrix of the right size defines a unique linear transformation and vice versa). To see why, if S is symmetric, then so is T(S): given T(v) in T(S), v is in S, so –v is in S, so that -T(v) = T(-v) is in S. Similarly, if S is convex, then given T(v1) and T(v2) in T(S), we have aT(v1) + (1-a)T(v2) = T(av1) + T((1-a)v2) = T(av1 + (1-a)v2).
Clearly, every nonempty convex, symmetric region contains 0. Given any v in the region, –v is in the region, so that 0.5v + 0.5(-v) = 0 is in the region. Minkowski’s theorem states more: if L is any lattice in V = R^n such that V/L has volume m, and S is a convex, symmetric region of volume more than m2^n, then S contains a point in L other than 0.
The proof of Minkowski’s theorem relies on the intuition that in certain circumstances, if we compress a region to a region of smaller volume, then two points must be collapsed to the same point. To see why, we take the quotient V/2L, where 2L is the set of all points of the form 2v where v is in L.
If A is a matrix corresponding to the lattice L, then |A| has absolute value m. Then 2A corresponds to 2L, and |2A| = 2^n|A| because 2A is formed by multiplying each one of the n rows of A by 2. So V/2L has volume m2^n, which is smaller than the volume of S. This means that two distinct points of S, say x and y, must be collapsed to the same point in V/2L. In other words, x + 2L = y + 2L, so that x–y = 2v for some v in L.
Since S is symmetric, the point –y is in S. Since it’s convex, x/2 + (-y)/2 = (x–y)/2 is in S. Since x and y are distinct, (x–y)/2 is not zero. Further, since x–y = 2v, (x–y)/2 = v which is in L.