Unimodular configurations and complete fans

Proof. Cramer’s rule expresses as the determinant of the displayed basis replacement. A nonzero such determinant has absolute value one, so it equals its sign. Formula (2.1) determines every column. Matching two labelled lattice bases therefore matches all columns by an element of . □

Proof. Any independent subset of a unimodular system extends to a column lattice basis. In particular, the port lattice in either operation is saturated and has a direct-sum complement. The quotient lattices and the asserted ranks follow. Every primitive circuit in a unimodular system has coefficients in . Extend a circuit with one element removed to a lattice basis and apply Cramer’s rule. This justifies the sign alignment of triangle ports.

The -sum assertion follows by block determinants. For a -sum write

A full output basis uses either columns from the first side and from the second, or from the first and from the second. Its determinant factors into a full side determinant and a quotient-projection determinant. The latter is the determinant obtained by appending the port column in the original side. Both nonzero factors have absolute value one.

For a -sum write

and put , . A full output basis has columns from the two sides. Its projections span and , so and . There are three cases, . In the first and last, the determinant again factors into a full side determinant and a projection determinant; append on the other side to see that the latter also has absolute value one.

In the middle case, choose first-side columns whose projections form a basis of , and second-side columns whose projections form a basis of . Each projection determinant has absolute value one, because appending the two port basis columns gives a full side minor. Integral column elimination reduces the two remaining columns to . If , the original maximal-minor conditions, using in turn the additional port , , or , give

Thus a nonzero is in . The same holds for . Their two-dimensional determinant is or , and is nonzero for the selected output basis. This proves uniform unimodularity.

Finally, reduction modulo two identifies the underlying sums. An output dependence separates into two side sums equal to the same vector in the common port space. Express that vector using the same subset of port labels on both sides. The resulting two side cycles have symmetric difference equal to the output cycle, with the ports deleted. Conversely, matched side cycles give an output dependence. This is precisely the binary - or -sum rule. Reduction modulo two preserves independence in a unimodular system, so it identifies the underlying matroids. □

Proof. Sign changes and antipodal duplication preserve the maximal-minor condition. Give an undoubled output ray the coefficient . For a doubled pair give the respective positive coefficients

Their difference is , so these coefficients give a strictly positive relation among all output rays. A spanning configuration with a strictly positive relation positively spans its whole space, since the negative of any one generator is a nonnegative combination of the others.

Conversely, simplify a given ray system to one reference vector on each unoriented line. Uniform unimodularity makes this a simple regular configuration. A line occurs either once or as an antipodal pair; let record the latter. Full positive span gives a strictly positive rational relation among the rays, and clearing denominators gives an integral one. On a doubled line take the difference of its two coefficients; on an undoubled line take its signed coefficient relative to the reference vector. These entries form the required . The regular orientation theorem and integral rigidity identify the reference realization with one constructed from the lattice blocks.

A coordinate vanishes identically on exactly when its element is a coloop. If no undoubled element is a coloop, its coordinate hyperplane is a proper subspace of the relation space. Finitely many proper rational hyperplanes cannot cover that space, so an integral relation avoids their union. Explicitly, for an integral relation basis , take and choose an integer outside the finitely many roots of its relevant nonzero coordinate polynomials. When there are no undoubled elements, the zero relation is allowed. □

Proof. Away from the finitely many facet hyperplanes, define

Cross a facet hyperplane at a point lying on no other distinct facet hyperplane and on no proper face of a facet in that hyperplane. For each facet block containing the crossing point, its contribution to the jump is a common sign times the corresponding entry of , hence zero. Generic polygonal paths join any two generic points using only such crossings, so is constant. Its value is . In dimension one, the empty-facet equation gives the same assertion for the two half-lines.

Since is a nonnegative integer summand of at a generic interior point of , it is zero or one. The selected cones have disjoint interiors, and their closed union contains every generic point, so they cover the ambient space.

To control their boundaries, let be a face of a selected cone and put . Project all selected cones having as a face to . Their facets are the images of the original facets containing . After compatible choices of orientations, the projected incidence sign differs from by a factor depending only on and . Every selected cone having as a facet also has as a face, so the original row equation cancels all projected contributions. Coincident projected facets cause no difficulty, since cancellation holds before their contributions are combined.

The same crossing argument now shows that the projected cones have constant nonnegative integral multiplicity. This multiplicity is positive because at least one cone contains , so they cover the quotient. Consequently the original star of covers a neighborhood of every . Indeed, the facet inequalities containing descend to the quotient, whereas all other facet inequalities are strict at and remain strict in a sufficiently small common neighborhood.

Suppose lies in two selected cones and let be their minimal faces containing . If , no selected cone can have both as faces, since their relative interiors meet at . Their stars would therefore be disjoint collections of selected cones, each covering a neighborhood of . This contradicts generic multiplicity one, so .

For two selected cones, choose in the relative interior of their intersection and let be this common minimal face. A functional exposing is nonnegative on the intersection and vanishes at its relative-interior point, hence on the entire intersection. The intersection is therefore exactly . The selected cones and all their faces form a complete fan.

Completeness places every in a selected maximal cone. By the definition of an allowed block, must be a listed extreme ray of that cone. Thus every prescribed ray occurs. Conversely, a complete fan on has allowed maximal blocks, two maximal cones on opposite sides of each facet, and covering degree one. Its indicator satisfies (3.1). □

Proof. For , minimize subject to and . The optimum is at most one and is attained at a basic solution with independent support. Extend that support to a ray basis. Uniform unimodularity makes all basic coefficients integral, so their sum is zero or one and is either zero or a member of . Applying the same argument with one column removed shows that this column cannot lie in the convex hull of the others.

Positive spanning puts the origin in the interior of . Every vertex of

is determined by independent active ray normals, which form a lattice basis. The polar is therefore integral, proving reflexivity; the displayed lattice-point statement proves terminality. The radial face fan of is the normal fan of and has the required rays. □

Proof. Finiteness follows from Dickson’s lemma in each orthant. For effectivity, intersect the rational kernel with an orthant and triangulate the resulting pointed rational cone. Choose integral primitive generators for each simplicial cone. An indecomposable lattice point is either one of these generators or lies in their bounded half-open fundamental parallelepiped, because a coefficient at least one permits subtraction of a generator. Enumerating these finite sets and retaining the conformally minimal nonzero vectors gives the Graver basis.

An allowed replacement preserves (3.1); Theorem 3.1 therefore gives another complete fan. For connectivity, let be two fan indicators. If , choose a primitive vector . Then lies coordinatewise between and , and

Iteration reaches . A coordinate absent from both endpoints never appears, proving the last assertion. □

Proof. Seymour’s decomposition, regular orientation uniqueness and integral rigidity give precisely the ray configurations in Section 2. Lemma 3.2 gives their initial fans, and Lemma 3.3 reaches every solution of (3.1) from those fans. The gluing theorem identifies these solutions with exactly the required complete fans.

A lattice isomorphism preserves the oriented ray matroid and the maximal cones. Conversely, match an ordered ray basis under an oriented-matroid isomorphism. Integral rigidity extends that match uniquely to all rays; matching the maximal blocks then matches every cone and face. □

Proof. Every cone generated by rays in has the direct-sum form , where . Each is a face. Choose functionals strictly positive on the nonzero vectors of the other pointed cones and zero on . Consequently, for a complete fan , its cones lying in form a complete fan . Completeness follows by applying completeness of to points in that summand.

Every cone of is a product of cones of these factor fans. Conversely, choose one full-dimensional cone of each factor and take . A full-dimensional cone of contains . Its factor cones must be the , since distinct full-dimensional cones of a factor fan have disjoint interiors. Therefore every product of full-dimensional factor cones belongs to . Taking faces proves the claimed equality and uniqueness.

For the final assertion, the usual matroid component decomposition splits the real spans. Choose a column basis in each component. Their union is a column basis of the entire configuration, hence an integral basis by uniform unimodularity. The real direct sum therefore splits the lattice as well. □

Proof. Write the seed’s polar polytope as

Choose a generic rational vector and perturb the right-hand sides to , for sufficiently small positive rational . Every original inequality remains a facet inequality, because a relative-interior point of its original facet has strict slack in all the other inequalities, and this property persists under a small perturbation. The perturbed polytope remains bounded and full-dimensional. Genericity makes it simple, since an intersection of more than facet hyperplanes imposes a nontrivial rational linear equation on the perturbation parameters.

For sufficiently small , each vertex’s active normals are a subset of the normals active at one vertex of . Indeed, otherwise a sequence of such vertices as would contradict compactness and the limiting active equations. Thus the new normal fan subdivides the seed and has exactly the same rays. Every maximal cone is generated by an independent ray basis, so it is smooth. Its defining rational polytope, after integral dilation, proves projectivity.

The anticanonical support function of the seed takes value one on every ray and is convex. It remains the anticanonical support function on the subdivision, because no ray was added. Hence the new anticanonical divisor is nef. Its section polytope is the full-dimensional , so it is big. The resulting smooth variety is therefore weak Fano. □

Proof. The conformal-decomposition proof of Lemma 3.3 keeps every block coordinate between its two endpoint values. A block absent at both endpoints can never appear, and every changing block is inserted or removed only once. Uniform unimodularity makes each independent rank- block smooth. The same positive-gluing and primitive-replacement proofs apply after all other block columns are deleted; the stated seed survives this restriction. This proves both assertions. □

Proof. Use the representation of in , with edge order

Negate the two columns and , and call the resulting matrix . Repeat its ten columns with multiplicities

The resulting map is surjective and unimodular, and

Put , a lattice of rank , and define

The origin is an interior point. The covector is strictly positive on every signed column of . Thus has strictly positive coefficients, so the lower bounds in (5.1) bound .

Translate by to identify with . A vertex has independent positive-support columns, so it uses at most one copy of each edge. On the original five labels its support graph has no isolated vertex, because every is positive. Column signs do not change linear independence. A disconnected independent support would have components of sizes two and three. The two-vertex component forces equal positive margins and a positive column, so it must be the edge . The other three vertices would then have margins , but their three columns are positive and , making that component infeasible. Thus the support is connected. Independent columns of the unsigned incidence matrix give either a tree or an odd unicyclic graph. A tree would require its two bipartition classes to have equal margin sums, namely , independently of the column signs. No subset of sums to . No singleton or pair does, and complements cover the remaining possibilities. Consequently every vertex has exactly five positive coordinates, on an odd unicyclic graph. These five columns form a basis of , so every vertex is integral and nondegenerate.

All thirteen inequalities in (5.1) are facets. For a doubled edge, start at , set one copy to zero and the other to two. For the singleton edges, write for the coordinate unit vectors in and use the kernel vectors

The signed incidence relations give , while has zero in coordinate and is positive elsewhere. Taking and covers the remaining two edges. Splitting the first three group totals between their two copies gives a point on precisely the required coordinate hyperplane. Thus each coordinate inequality is a facet.

At a vertex, the five positive-coordinate columns form a lattice basis of . Hence the remaining eight coordinate functionals form a basis of , by the exact sequence

Therefore is smooth, with primitive facet normals and lattice distance one from the origin. Its polar is a smooth Fano polytope with thirteen vertices. The complete facet-normal configuration is a Gale dual of , so it is uniformly unimodular, since complementary maximal minors agree up to sign. Its matroid is the dual of a parallel extension of . Contracting the extra series elements recovers .

For completeness, -minor avoidance is preserved by the stated operations. The matroid is self-dual, -connected, and neither graphic nor cographic; these are standard properties of the exceptional block in Seymour’s theorem [12]. Here is the relevant minor-locality argument. Represent a binary -sum by two spaces meeting in the port plane. After contractions on both sides, their images still meet in an image of that plane, of dimension at most two. If an minor survives, its induced partition into the two sides therefore has connectivity at most two. Its -connectivity forces one surviving side to have at most two elements. Any dimension of that side outside the span of the other would produce a cocircuit of size at most two, which does not have. Thus these elements lie in the image of the port plane. Over , its nonzero vectors are images of the three ports; any collapsed port subspace can itself be contracted using port elements. Simplicity excludes duplicate surviving port vectors. The minor is therefore already a minor of the other summand. The same argument with port spaces of dimensions zero and one handles - and -sums. Duality preserves avoidance because is self-dual. Graphic and cographic matroids have no such minor, so constructions starting only with them cannot give the ray matroid just obtained. □

Proof. The ray matroid of a uniformly unimodular system is regular, and regularity is preserved under minors. We prove the converse by an explicit construction.

Let be an integral unimodular representation of a regular matroid in a rank- lattice ; loops and repeated columns are allowed at this stage. Introduce a private coordinate for every label and take

Every vector is nonzero and primitive, and no two lie on the same positive ray. When , its two vectors are opposite, which is allowed. A full independent subset must use at least one vector from each pair, and exactly pairs are used in full. Adding the two columns in a full pair and eliminating the private coordinates reduces its determinant, up to sign, to the corresponding -column minor of . Thus the new ray system is uniformly unimodular. Contracting all the recovers the original represented matroid, including its loops and parallel elements.

Add any missing opposite rays, keeping only one vector on each positive ray. The resulting uniformly unimodular system positively spans. Proposition 4.2 realizes it as the rays of a smooth projective weak Fano fan. Choose positive integral ample support numbers . The Fano multiwedge construction of [6] replaces each ray by

The result is a smooth projective uniformly unimodular Fano fan. Contract its pure extra vectors, delete the newly added opposite rays, and contract the retained . The resulting matroid is exactly the prescribed regular matroid. The empty matroid is obtained by deleting all rays of the fan of . □

Proof. Necessity holds because every ray matrix is integral and rational representability is preserved under minors. Conversely, choose an integral representation of a rational matroid and use the same private-coordinate vectors and as in the preceding proof. They are distinct primitive positive rays, including when the original matroid has loops or parallel elements. Beginning with the fan of a product of projective lines, successively insert each prescribed ray by a star subdivision. These subdivisions preserve projectivity and completeness. A projective toric resolution by further star subdivisions makes the fan smooth and retains all prescribed rays [3, 11.1].

Apply the divisible-index form of the same Fano multiwedge construction [6] to this smooth projective fan. Contract the pure extra rays, delete every retained ray other than the labeled , and contract the . The resulting matroid is the original one, while the ambient Fano variety has the required divisibility and UT-free properties. The empty case follows from any such Fano variety by deletion. □

Proof. Set . Then and , with . Thus is combinatorially a tetrahedron times an interval, with vertices given by and either or . At each vertex the active normals are one of and three members of

Every such set is a lattice basis, proving smoothness. All inequalities are facets at lattice distance one from the interior origin, so the integral polytope is reflexive.

Every vertex has all four original coordinates odd. Consequently is an integral translate of twice a lattice polytope, and every edge contains an interior lattice point. It has no unimodular triangular face. On the other hand, have determinant two. □

Proof. Choose any independent rays and an interior point of their cone lying on no wall of . This point lies in the interior of a maximal cone . Express the chosen rays in the lattice basis of , obtaining an integral matrix . There are positive vectors with . Every row of must contain a positive entry. Each column has at most one such entry, equal to one. Since is square, there is exactly one in every row and column. Permuting columns therefore gives with a nonnegative integral matrix with zero diagonal.

The inequality prohibits a directed cycle in the support graph of , since along such a cycle it would imply successively and eventually . Thus a simultaneous row and column permutation makes strictly triangular. It follows that . □

Proof. Let be a vertex of a smooth reflexive polytope, with active primitive outward normals and dual basis . Reflexivity gives , and its inward primitive edge directions are . Write another facet normal as . The maximum of over the corner parallelepiped at is exactly . Deep monotonicity puts this parallelepiped inside the polytope, whose -inequality is . Apply Lemma 6.1 to the normal fan. □

Proof. In a maximal-cone basis , write with and . If is another ray, then the difference between its rounded coefficient and the value prescribed by that cone’s Cartier point is

Here smoothness makes the integral. This quantity is nonnegative for every exactly when . The toric support-function criterion for nefness proves the equivalence of the coordinate and nefness conditions.

Applying the coordinate criterion to the outside generator across a wall gives the wall condition, since its positive coordinates are the negatives of the negative wall coefficients. Conversely, under the wall condition a wall relation has either no negative term, or exactly one term . For every , the intersection with is nonnegative by subadditivity of the ceiling function, applied to the positive side of that relation. The invariant-curve criterion then gives nefness.

Each wall has two outside coefficients equal to one. The wall condition therefore gives for every invariant curve. The toric strict-convexity criterion makes ample, even though projectivity was not initially assumed. The corner computation in Corollary 6.2 now identifies the coordinate condition with deep monotonicity. □

Proof. Let have dimension , and choose independent rays spanning it. Choose in the relative interior of their positive cone, avoiding every intersection of dimension less than , for . These are finitely many proper linear subspaces of . In a maximal-cone basis containing , write for the chosen ray columns, with . Each column of has at most one positive entry. Thus has at most positive coordinates in this basis. Its minimal fan face has dimension at most . The choice of forces and .

The quotient star is a complete smooth fan in . Its lattice is the indicated quotient because the generators of extend to a lattice basis. Let be any original ray whose image is nonzero. Choose a maximal quotient cone containing and lift it to a maximal cone containing . In the lifted basis, the coordinates of outside are nonnegative and not all zero. Their sum is at most one, so exactly one is one and all the others are zero. Hence is exactly a primitive ray of the quotient fan. Conversely, every quotient-fan ray is an image of an original ray.

Finally, relative to any quotient maximal-cone basis, the coordinates of a projected ray are a subset of its coordinates in the lifted basis. Their positive sum is still at most one. Thus the quotient fan satisfies the criterion and is deeply monotone by Proposition 6.3. This proves the assertion for any ray-generated subspace, hence for every matroid contraction. □