The invariant Birkhoff polytope

This notebook contains code to construct the invariant Birkhoff polytopes.

using Oscar, Permutations, Combinatorics

Welcome to Nemo version 0.43.3

Nemo comes with absolutely no warranty whatsoever

Welcome to

    _    _           _
   | |  | |         | |
   | |__| | ___  ___| | _____
   |  __  |/ _ \/ __| |/ / _ \
   | |  | |  __/ (__|   <  __/
   |_|  |_|\___|\___|_|\_\___|
    
Version 0.30.12 ...
 ... which comes with absolutely no warranty whatsoever
(c) 2015-2024 by Claus Fieker, Tommy Hofmann and Carlo Sircana

  ___   ____   ____    _    ____
 / _ \ / ___| / ___|  / \  |  _ \   |  Combining ANTIC, GAP, Polymake, Singular
| | | |\___ \| |     / _ \ | |_) |  |  Type "?Oscar" for more information
| |_| | ___) | |___ / ___ \|  _ <   |  Manual: https://docs.oscar-system.org
 \___/ |____/ \____/_/   \_\_| \_\  |  Version 1.0.4

# the degree of the polynomial pair
d = 4

4

We construct the invariant Birkhoff polytope for the pair of involutions \((\phi,\psi) = (e,(12)(34))\), i.e., for the case where \(p\) has \(4\) real roots and \(q\) has \(4\) complex roots.

# an example
M=[Matrix(Permutation(d,i)) for i in 1:factorial(d)]
phi = M[1] # phi is the identity matrix
psi = [0 1 0 0;
       1 0 0 0;
       0 0 0 1;
       0 0 1 0]
Miota = collect(phi*m*psi for m in M)
new = (M + Miota)//2
L = [reduce(hcat, n) for n in new]
V = vcat(reduce(vcat,L))
Biota = convex_hull(V)
dim(Biota),vertices(Biota),edgegraph(Biota)

(3, PointVector{QQFieldElem}[[1//2, 1//2, 0, 0, 1//2, 1//2, 0, 0, 0, 0, 1//2, 1//2, 0, 0, 1//2, 1//2], [1//2, 0, 1//2, 0, 1//2, 0, 1//2, 0, 0, 1//2, 0, 1//2, 0, 1//2, 0, 1//2], [1//2, 0, 0, 1//2, 1//2, 0, 0, 1//2, 0, 1//2, 1//2, 0, 0, 1//2, 1//2, 0], [0, 1//2, 1//2, 0, 0, 1//2, 1//2, 0, 1//2, 0, 0, 1//2, 1//2, 0, 0, 1//2], [0, 1//2, 0, 1//2, 0, 1//2, 0, 1//2, 1//2, 0, 1//2, 0, 1//2, 0, 1//2, 0], [0, 0, 1//2, 1//2, 0, 0, 1//2, 1//2, 1//2, 1//2, 0, 0, 1//2, 1//2, 0, 0]], Undirected graph with 6 nodes and 12 edges)

# function to return cycles of a permutation
function cycles(p::Permutation)
    n = length(p)
    result = Array{Int,1}[]
    todo = trues(n)
    k = 1
    while k !== nothing
        todo[k] = false
        cycle = [k]
        j = p[k]
        while j != k
            push!(cycle, j)
            todo[j] = false
            j = p[j]
        end
        push!(result, cycle)
        k = findnext(todo, k)
    end
    return result
end

# function that returns cycle type of a permutation
function cycle_length(p::Permutation)
    return sort([length(c) for c in cycles(p)])
end


# function that returns a complete list of permutations of [1:n] with distinct cycle types
function unique_cycle_permutations(n)
    perms = [Permutation(n,i) for i in 1:factorial(n)]
    unique_cycle_perms = []
    seen_cycles = Set()

    for p in perms
        cycle_type = cycle_length(p)
        if !(cycle_type in seen_cycles)
            push!(seen_cycles, cycle_type)
            push!(unique_cycle_perms, p)
        end
    end

    return unique_cycle_perms
end

unique_cycle_permutations (generic function with 1 method)

The following code produces all invariant Birkhoff polytopes for degree \(d\) and computes their dimension and number of vertices:

# permutations should swap conjugate pairs of some polynomial, so they must be self-inverse
permutations_us=[p for p in unique_cycle_permutations(d) if p*p== Permutation(d,1)]
M=[Matrix(Permutation(d,i)) for i in 1:factorial(d)]

dimV = []
n=length(permutations_us)
for i in 1:n
    phi = Matrix(permutations_us[i])
    for j in i:n
        psi = Matrix(permutations_us[j])
        Miota = collect(phi*m*psi for m in M)
        new = (M + Miota)//2
        L = [reduce(hcat, n) for n in new]
        V = vcat(reduce(vcat,L))
        Biota = convex_hull(V)
        dm = dim(Biota)
        nv = n_vertices(Biota)
        push!(dimV, [dm,nv])
    end
end
println(unique(dimV))

Any[[9, 24], [6, 12], [3, 6], [5, 13], [4, 12], [5, 8]]