Matroid Realization Spaces

Let $M$ be a matroid of rank $d$ on a ground set $E$ of size $n$. Its realization space $\mathcal{R}(M)$ is an affine scheme that parameterizes all hyperplane arrangements that realize the matroid $M$ (up to the action of $PGL(r)$). We provide functions that determine the affine coordinate ring of $\mathcal{R}(M)$.

is_realizable — Method

is_realizable(M; char::Union{Int,Nothing}=nothing, q::Union{Int,Nothing}=nothing)

If char = nothing, then this function determines whether the matroid is realizable over some field.
If char == 0, then this function determines whether the matroid is realizable over some field of characteristic 0.
If char = p is prime, this function determines whether the matroid is realizable over the finite field $GF(p)$.
If char == p and q is a power of p, this function determines whether the matroid is realizable over the finite field $GF(q)$.

source

defining_ideal — Method

defining_ideal(RS::MatroidRealizationSpace)

The ideal of the matroid realization space RS.

source

inequations — Method

inequations(RS::MatroidRealizationSpace)

Generators of the localizing semigroup of RS. These are the polynomials that need to be nonzero in any realization.

source

ambient_ring — Method

ambient_ring(RS::MatroidRealizationSpace)

The polynomial ring containing the ideal defining_ideal(RS) and the polynomials in inequations(RS).

source

realization_space — Method

realization_space(
  M::Matroid;
  B::Union{GroundsetType,Nothing}=nothing,
  saturate::Bool=false,
  simplify::Bool=true,
  char::Union{Int,Nothing}=nothing,
  q::Union{Int,Nothing}=nothing,
  ground_ring::Ring=ZZ
)::MatroidRealizationSpace

This function returns the data for the coordinate ring of the matroid realization space of the matroid M as a MatroidRealizationSpace. This function has several optional parameters.

B is a basis of M that specifies which columns of realization_matrix(M) form an identity matrix. The default is nothing, in which case the basis is chosen for you.
saturate determines whether defining_ideal(M) should be saturated with respect to the semigroup generated by inequations(M). The default is false. The saturation can be rather slow for large instances.
simplify determines whether a reduced realization space is returned which means that the equations are used to eliminate variables as far as possible. The default is true.
char specifies the characteristic of the coefficient ring. The returned realization space is then the space of all realizations over fields of characteristic char. The default is nothing.
q is an integer and assumed to be a prime power q=p^k. The returned realization space is then the space of all realizations over the field $GF(p^k)$. The default is nothing.
ground_ring is a ring and specifies the groundring over which one wants to consider the realization space, e.g. QQ or GF(p). The groudring ZZ means that we compute the space of realizations over all fields. The default is ZZ.

Examples

julia> M = fano_matroid();

julia> RS = realization_space(M)
The realization space is
  [0   1   1   1   1   0   0]
  [1   0   1   1   0   1   0]
  [1   0   1   0   1   0   1]
in the integer ring
within the vanishing set of the ideal
2ZZ

julia> realization_space(non_fano_matroid())
The realization space is
  [1   1   0   0   1   1   0]
  [0   1   1   1   1   0   0]
  [0   1   1   0   0   1   1]
in the integer ring
avoiding the zero loci of the polynomials
RingElem[2]

julia> realization_space(pappus_matroid(), char=0)
The realization space is
  [1   0   1   0   x2   x2                 x2^2    1    0]
  [0   1   1   0    1    1   -x1*x2 + x1 + x2^2    1    1]
  [0   0   0   1   x2   x1                x1*x2   x1   x2]
in the multivariate polynomial ring in 2 variables over QQ
avoiding the zero loci of the polynomials
RingElem[x1 - x2, x2, x1, x2 - 1, x1 + x2^2 - x2, x1 - 1, x1*x2 - x1 - x2^2]

julia> realization_space(uniform_matroid(3,6))
The realization space is
  [1   0   0   1    1    1]
  [0   1   0   1   x1   x3]
  [0   0   1   1   x2   x4]
in the multivariate polynomial ring in 4 variables over ZZ
avoiding the zero loci of the polynomials
RingElem[x1*x4 - x2*x3, x2 - x4, x1 - x3, x1*x4 - x1 - x2*x3 + x2 + x3 - x4, x3 - x4, x4 - 1, x3 - 1, x3, x4, x1 - x2, x2 - 1, x1 - 1, x1, x2]

source

realization — Method

realization(M::Matroid; B::Union{GroundsetType,Nothing} = nothing,
  saturate::Bool=false,
  char::Union{Int,Nothing}=nothing, q::Union{Int,Nothing}=nothing
)::MatroidRealizationSpace

This function tries to find one realization in the matroid realization space of the matroid M. The output is again a MatroidRealizationSpace.

If the matroid is only realizable over an extension of the prime field the extension field is specified as a splitting field of an irreducible polynomial. Every root of this polynomial gives an equivalent realization of the matroid.

This function has several optional parameters. Note that one must input either the characteristic or a specific field of definition for the realization.

B is a basis of M that specifies which columns of realization_matrix(M) form the identity matrix. The default is nothing, in which case the basis is chosen for you.
char specifies the characteristic of the coefficient ring, and is used to determine if the matroid is realizable over a field of this characteristic. The default is nothing.
q is an integer, and when char = p, this input is used to determine whether the matroid is realizable over the finite field $GF(p^{q})$. The default is nothing.
reduce determines whether a reduced realization space is returned which means that the equations are used to eliminate variables as far as possible. The default is true.
saturate determines whether defining_ideal(M) should be saturated with respect to the semigroup generated by inequations(M). The default is false. This can be rather slow for large instances.

Examples

julia> realization(pappus_matroid(), char=0)
One realization is given by
  [1   0   1   0   2   2   4   1   0]
  [0   1   1   0   1   1   1   1   1]
  [0   0   0   1   2   3   6   3   2]
in the rational field

julia> realization(pappus_matroid(), q=4)
One realization is given by
  [1   0   1   0   x1 + 1   x1 + 1   x1    1        0]
  [0   1   1   0        1        1    1    1        1]
  [0   0   0   1   x1 + 1       x1    1   x1   x1 + 1]
in the multivariate polynomial ring in 1 variable over GF(2)
within the vanishing set of the ideal
Ideal (x1^2 + x1 + 1)

julia> realization(uniform_matroid(3,6), char=5)
One realization is given by
  [1   0   0   1   1   1]
  [0   1   0   1   4   3]
  [0   0   1   1   3   2]
in the prime field of characteristic 5

source

realization — Method

realization(RS::MatroidRealizationSpace)

This function tries to find one realization in the matroid realization RS. The output is again a MatroidRealizationSpace.

source

If $B$ is the polynomial ring ambient_ring(RS), $I$ the ideal defining_ideal(RS), and $U$ the multiplicative semigroup generated by inequations(RS), then the coordinate ring of the realization space $\mathcal{R}(M)$ is isomorphic to $U^{-1}B/I$.