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)$.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

defining_ideal — Method

defining_ideal(RS::MatroidRealizationSpace)

The ideal of the matroid realization space RS.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

inequations — Method

inequations(RS::MatroidRealizationSpace)

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

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

ambient_ring — Method

ambient_ring(RS::MatroidRealizationSpace)

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

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]

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

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

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

realization — Method

realization(RS::MatroidRealizationSpace)

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

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

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$.

Matroid realization spaces as affine schemes

Every MatroidRealizationSpace is an instance of an affine scheme. For those cases where implementations exist, the entire functionality provided for AbsAffineSchemes applies to matroid realization spaces. For example:

julia> RM = realization_space(pappus_matroid(), ground_ring=QQ)
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> OO(RM)
Localization
  of quotient
    of multivariate polynomial ring in 2 variables x1, x2
      over rational field
    by ideal (0)
  at products of (x1 - x2, x2, x1, x2 - 1, x1 + x2^2 - x2, x1 - 1, x1*x2 - x1 - x2^2)

julia> is_smooth(RM) # Calls the generic routine implemented for schemes
true

julia> x, y = gens(OO(RM)); I = ideal(OO(RM), [x - 4, y^2 - 8]);

julia> pr = blow_up(RM, I)
Blowup
  of scheme over QQ covered with 1 patch
    1b: [x1, x2]   scheme(0) \ scheme((x1 - x2)*x2*x1*(x2 - 1)*(x1 + x2^2 - x2)*(x1 - 1)*(x1*x2 - x1 - x2^2))
  in sheaf of ideals with restriction
    1b: Ideal (x1 - 4, x2^2 - 8)
with domain
  scheme over QQ covered with 2 patches
    1a: [(s1//s0), x1, x2]   scheme(-(s1//s0)*x1 + 4*(s1//s0) + x2^2 - 8) \ scheme((x1 - x2)*x2*x1*(x2 - 1)*(x1 - 1)*(x1 + x2^2 - x2)*(x1*x2 - x1 - x2^2))
    2a: [(s0//s1), x2]       scheme(0) \ scheme(((s0//s1)*x2^2 - 8*(s0//s1) - x2 + 4)*x2*((s0//s1)*x2^2 - 8*(s0//s1) + 4)*(x2 - 1)*((s0//s1)*x2^2 - 8*(s0//s1) + 3)*((s0//s1)*x2^2 - 8*(s0//s1) + x2^2 - x2 + 4)*((s0//s1)*x2^3 - (s0//s1)*x2^2 - 8*(s0//s1)*x2 + 8*(s0//s1) - x2^2 + 4*x2 - 4))
and exceptional divisor
  effective cartier divisor defined by
    sheaf of ideals with restrictions
      1a: Ideal (x1 - 4)
      2a: Ideal (x2^2 - 8)
      
julia> first(affine_charts(codomain(pr))) === RM
true

Note, however, that there are also cases which are not covered. For instance, one realization of the fano_matroid() is $\mathrm{Spec}(\mathbb Z/2 \mathbb Z)$ which is not (yet) supported by the schemes framework.

Self-projecting realization spaces of self-projecting matroids

A matroid $M$ of rank $d$ on $[n]$ is self-projecting, if for any two rank $d-1$ flats $F_1,F_2$ there is no element $e\in[n]$ such that $F_1\cup F_2 = [n]\setminus e$. For self-projecting matroids one can compute the self-projecting realization space, a subspace of the realization space of the matroid. This space is the Zariski closure of the space of realizations $V$ which satisfy that there exists a diagonal matrix $D$ with only non-zero entries in the diagonal such that $V\cdot D\cdot V^t = 0$.

is_selfprojecting — Method

is_selfprojecting(mat::Matroid)

Return a boolean which states whether mat satisfies the property to be self-projecting.

Examples

julia> m = fano_matroid()
Matroid of rank 3 on 7 elements

julia> is_selfprojecting(m)
true

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

satisfies_disjointbasisproperty — Method

satisfies_disjointbasisproperty(mat::Matroid)

Return a boolean stating whether mat has two disjoint bases.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

defining_ideal — Method

defining_ideal(RS::MatroidRealizationSpaceSelfProjecting)

The ideal of the matroid realization space RS.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

inequations — Method

inequations(RS::MatroidRealizationSpaceSelfProjecting)

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

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

ambient_ring — Method

ambient_ring(RS::MatroidRealizationSpaceSelfProjecting)

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

selfprojecting_realization_ideal — Method

selfprojecting_realization_ideal(m::Matroid; saturate::Bool = false, check::Bool = true)

Compute the defining_ideal of a selfprojecting realization space

Warning

This function is slow except for small matroids!

Examples

julia> m = matroid_from_nonbases([[1,2,3],[4,5,6]],6)
Matroid of rank 3 on 6 elements

julia> selfprojecting_realization_ideal(m)
Ideal generated by
  0

julia> m = uniform_matroid(3,6)
Matroid of rank 3 on 6 elements

julia> selfprojecting_realization_ideal(m)
Ideal generated by
  x1*x2*x3 - x1*x2*x4 - x1*x3*x4 + x1*x4 + x2*x3*x4 - x2*x3

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

selfprojecting_realization_space — Method

selfprojecting_realization_space(m::Matroid; B::Union{GroundsetType,Nothing}=nothing; check::Bool = true)

Compute the selfprojecting realization space of a selfprojecting matroid.

A basis B can be given that will correspond to the identity matrix in the realization. If nothing is given, a choice will be made.

The keyword argument check states whether the matroid will be checked for self-projectivity. The default is true.

Warning

This function uses the computation of the selfprojecting_realization_ideal. Therefore, it is slow except for small matroids.

Examples

julia> m = matroid_from_nonbases([[1,2,3],[4,5,6]],6)
Matroid of rank 3 on 6 elements

julia> selfprojecting_realization_space(m)
The selfprojecting realization space is
  [1   0   1   0    1    1]
  [0   1   1   0   x1   x1]
  [0   0   0   1    1   x2]
in the multivariate polynomial ring in 2 variables over QQ
avoiding the zero loci of the polynomials
RingElem[x2, -x1, -x2 + 1, -x1 + 1]

julia> m = uniform_matroid(3,6)
Matroid of rank 3 on 6 elements

julia> selfprojecting_realization_space(m,B=[4,5,6])
The selfprojecting realization space is
  [1    1    1   1   0   0]
  [1   x1   x3   0   1   0]
  [1   x2   x4   0   0   1]
in the multivariate polynomial ring in 4 variables over QQ
within the vanishing set of the ideal
Ideal (x1*x2*x3 - x1*x2*x4 - x1*x3*x4 + x1*x4 + x2*x3*x4 - x2*x3)
avoiding the zero loci of the polynomials
RingElem[x1*x4 - x1 - x2*x3 + x2 + x3 - x4, -x1 + x2, -x2 + 1, x1 - 1, -x3 + x4, -x4 + 1, x3 - 1, x1*x4 - x2*x3, x2 - x4, -x1 + x3, x2, -x1, x4, -x3]

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

selfprojecting_realization_matrix — Method

selfprojecting_realization_matrix(m::Matroid, Bas::Vector{Int}, F::Ring;
                                  Ideal::Union{Ideal,Nothing} = nothing,
                                  check::Bool = true)

Compute a template for a selfprojecting realization and return the ambient ring and the matrix.

The input Bas defines the basis of the matriod that is chosen to be represented by the identity matrix in the realization.

The defining ideal of the selfprojecting realization space of the given matroid can optionally be entered. Otherwise it will be computed.

The keyword argument check states whether the matroid will be checked for self-projectivity. The default is true.

Warning

This function uses the computation of the selfprojecting_realization_ideal. Therefore, it is slow except for small matroids.

Examples

julia> m = matroid_from_nonbases([[1,2,3],[4,5,6]],6)
Matroid of rank 3 on 6 elements

julia> R, M = selfprojecting_realization_matrix(m,[1,2,4])
(Multivariate polynomial ring in 2 variables over QQ, [1 0 1 0 1 1; 0 1 1 0 x1 x1; 0 0 0 1 1 x2])

julia> M
[1   0   1   0    1    1]
[0   1   1   0   x1   x1]
[0   0   0   1    1   x2]

julia> m = uniform_matroid(3,6)
Matroid of rank 3 on 6 elements

julia> R, M = selfprojecting_realization_matrix(m,[1,2,3])
(Quotient of multivariate polynomial ring by ideal (x1*x2*x3 - x1*x2*x4 - x1*x3*x4 + x1*x4 + x2*x3*x4 - x2*x3), [1 0 0 1 1 1; 0 1 0 1 x1 x3; 0 0 1 1 x2 x4])

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

dimension — Method

dimension(MRS::MatroidRealizationSpaceSelfProjecting)::Int

Return the dimension of the selfprojecting realization space of a selfprojecting matroid.

Examples

julia> dimension(selfprojecting_realization_space(uniform_matroid(3,6)))
3

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

There is a collection with selfprojecting matroids and their (selfprojecting) realization spaces in oscarDB. The object type for the database entries is SelfProjectingMatroidRealizations. It has the following properties.

name — Method

name(MR::SelfProjectingMatroidRealizations)

Return the identifier of MR in the database.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

matroid — Method

matroid(MR::SelfProjectingMatroidRealizations)

Return the matroid of MR.

rank — Method

rank(MR::SelfProjectingMatroidRealizations)

Return the rank of the matroid underlying MR.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

length_groundset — Method

length_groundset(MR::SelfProjectingMatroidRealizations)

Return the size of the groundset of the matroid underlying MR.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

dim_r — Method

dim_r(MR::SelfProjectingMatroidRealizations)

Return the (affine) dimension of the realization space of MR.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

dim_s — Method

dim_s(MR::SelfProjectingMatroidRealizations)

Return the (affine) dimension of the self-projecting realization space of MR.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

equality_of_realizationspaces — Method

equality_of_realizationspaces(MR::SelfProjectingMatroidRealizations)

Return a boolean which states whether the self-projecting realization space and the realization space of MR are equal.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

Status

This part of OSCAR is in an experimental state; please see Adding new projects to experimental for what this means.

Contact

Please direct questions about this part of OSCAR to the following people.

On general matroid realizations:

On selfprojecting matroid realizations:

You can ask questions in the OSCAR Slack.

Alternatively, you can raise an issue on github.