Gordan's lemma

Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways.

• Let [math]\displaystyle{ A }[/math] be a matrix of integers. Let [math]\displaystyle{ M }[/math] be the set of non-negative integer solutions of [math]\displaystyle{ A \cdot x = 0 }[/math]. Then there exists a finite subset of vectors in [math]\displaystyle{ M }[/math], such that every element of [math]\displaystyle{ M }[/math] is a linear combination of these vectors with non-negative integer coefficients.
• The semigroup of integral points in a rational convex polyhedral cone is finitely generated.
• An affine toric variety is an algebraic variety (this follows from the fact that the prime spectrum of the semigroup algebra of such a semigroup is, by definition, an affine toric variety).

The lemma is named after the mathematician Paul Gordan (1837–1912). Some authors have misspelled it as "Gordon's lemma".

Proofs

There are topological and algebraic proofs.

Topological proof

Let [math]\displaystyle{ \sigma }[/math] be the dual cone of the given rational polyhedral cone. Let [math]\displaystyle{ u_1, \dots, u_r }[/math] be integral vectors so that [math]\displaystyle{ \sigma = \{ x \mid \langle u_i, x \rangle \ge 0, 1 \le i \le r \}. }[/math] Then the [math]\displaystyle{ u_i }[/math]'s generate the dual cone [math]\displaystyle{ \sigma^{\vee} }[/math]; indeed, writing C for the cone generated by [math]\displaystyle{ u_i }[/math]'s, we have: [math]\displaystyle{ \sigma \subset C^{\vee} }[/math], which must be the equality. Now, if x is in the semigroup

[math]\displaystyle{ S_\sigma = \sigma^\vee \cap \mathbb{Z}^d, }[/math]

then it can be written as

[math]\displaystyle{ x = \sum_i n_i u_i + \sum_i r_i u_i, }[/math]

where [math]\displaystyle{ n_i }[/math] are nonnegative integers and [math]\displaystyle{ 0 \le r_i \le 1 }[/math]. But since x and the first sum on the right-hand side are integral, the second sum is a lattice point in a bounded region, and so there are only finitely many possibilities for the second sum (the topological reason). Hence, [math]\displaystyle{ S_{\sigma} }[/math] is finitely generated.

Algebraic proof

The proof is based on a fact that a semigroup S is finitely generated if and only if its semigroup algebra [math]\displaystyle{ \mathbb{C}[S] }[/math] is a finitely generated algebra over [math]\displaystyle{ \mathbb{C} }[/math]. To prove Gordan's lemma, by induction (cf. the proof above), it is enough to prove the following statement: for any unital subsemigroup S of [math]\displaystyle{ \mathbb{Z}^d }[/math],

If S is finitely generated, then [math]\displaystyle{ S^+ = S \cap \{ x \mid \langle x, v \rangle \ge 0 \} }[/math], v an integral vector, is finitely generated.

Put [math]\displaystyle{ A = \mathbb{C}[S] }[/math], which has a basis [math]\displaystyle{ \chi^a, \, a \in S }[/math]. It has [math]\displaystyle{ \mathbb{Z} }[/math]-grading given by

[math]\displaystyle{ A_n = \operatorname{span} \{ \chi^a \mid a \in S, \langle a, v \rangle = n \} }[/math].

By assumption, A is finitely generated and thus is Noetherian. It follows from the algebraic lemma below that [math]\displaystyle{ \mathbb{C}[S^+] = \oplus_0^\infty A_n }[/math] is a finitely generated algebra over [math]\displaystyle{ A_0 }[/math]. Now, the semigroup [math]\displaystyle{ S_0 = S \cap \{ x \mid \langle x, v \rangle = 0 \} }[/math] is the image of S under a linear projection, thus finitely generated and so [math]\displaystyle{ A_0 = \mathbb{C}[S_0] }[/math] is finitely generated. Hence, [math]\displaystyle{ S^+ }[/math] is finitely generated then.

Lemma: Let A be a [math]\displaystyle{ \mathbb{Z} }[/math]-graded ring. If A is a Noetherian ring, then [math]\displaystyle{ A^+ = \oplus_0^{\infty} A_n }[/math] is a finitely generated [math]\displaystyle{ A_0 }[/math]-algebra.

Proof: Let I be the ideal of A generated by all homogeneous elements of A of positive degree. Since A is Noetherian, I is actually generated by finitely many [math]\displaystyle{ f_i's }[/math], homogeneous of positive degree. If f is homogeneous of positive degree, then we can write [math]\displaystyle{ f = \sum_i g_i f_i }[/math] with [math]\displaystyle{ g_i }[/math] homogeneous. If f has sufficiently large degree, then each [math]\displaystyle{ g_i }[/math] has degree positive and strictly less than that of f. Also, each degree piece [math]\displaystyle{ A_n }[/math] is a finitely generated [math]\displaystyle{ A_0 }[/math]-module. (Proof: Let [math]\displaystyle{ N_i }[/math] be an increasing chain of finitely generated submodules of [math]\displaystyle{ A_n }[/math] with union [math]\displaystyle{ A_n }[/math]. Then the chain of the ideals [math]\displaystyle{ N_i A }[/math] stabilizes in finite steps; so does the chain [math]\displaystyle{ N_i = N_i A \cap A_n. }[/math]) Thus, by induction on degree, we see [math]\displaystyle{ A^+ }[/math] is a finitely generated [math]\displaystyle{ A_0 }[/math]-algebra.

Applications

A multi-hypergraph over a certain set [math]\displaystyle{ V }[/math] is a multiset of subsets of [math]\displaystyle{ V }[/math] (it is called "multi-hypergraph" since each hyperedge may appear more than once). A multi-hypergraph is called regular if all vertices have the same degree. It is called decomposable if it has a proper nonempty subset that is regular too. For any integer n, let [math]\displaystyle{ D(n) }[/math] be the maximum degree of an indecomposable multi-hypergraph on n vertices. Gordan's lemma implies that [math]\displaystyle{ D(n) }[/math] is finite. Proof: for each subset S of vertices, define a variable x_S (a non-negative integer). Define another variable d (a non-negative integer). Consider the following set of n equations (one equation per vertex):[math]\displaystyle{ \sum_{S\ni v} x_S - d = 0 \text{ for all } v\in V }[/math]Every solution (x,d) denotes a regular multi-hypergraphs on [math]\displaystyle{ V }[/math], where x defines the hyperedges and d is the degree. By Gordan's lemma, the set of solutions is generated by a finite set of solutions, i.e., there is a finite set [math]\displaystyle{ M }[/math] of multi-hypergraphs, such that each regular multi-hypergraph is a linear combination of some elements of [math]\displaystyle{ M }[/math]. Every non-decomposable multi-hypergraph must be in [math]\displaystyle{ M }[/math] (since by definition, it cannot be generated by other multi-hypergraph). Hence, the set of non-decomposable multi-hypergraphs is finite.

See also

• Birkhoff algorithm is an algorithm that, given a bistochastic matrix (a matrix which solves a particular set of equations), finds a decomposition of it into integral matrices. It is related to Gordan's lemma in that it shows that the set of these matrices is generated by a finite set of integral matrices.

See also

• Dickson's lemma