The Bracket Algebra

Let $\{x_1, \dots, x_n\} \subset P^{d}$ be $n$ points in projective space. The algebra generated by the $d+1 \times d+1$-minors of the matrix

\[X = \begin{pmatrix} x_{1,1} & \dots & x_{1,d} & 1 \\ & \vdots & \\ x_{n,1} & \dots & x_{n,d} & 1 \end{pmatrix}\]

is called the bracket algebra $\mathcal{B}_{n,d}$ Let $\Lambda \coloneqq \Lambda(n,d+1) \coloneqq \{[\lambda_1, \dots, \lambda_{d+1}] \mid 1\leq \lambda_1 < \dots < \lambda_{d+1} \leq n\}$ and set $[\lambda_{\pi(1)}, \dots \lambda_{\pi(d)}] = \mathrm{sgn}(\pi)[\lambda_1, \dots, \lambda_d]$ in $\mathbb{C}(\Lambda)$. Then

\[\mathbb{C}[\Lambda] / I \to \mathcal{B}_{n,d}, [\lambda_1, \dots, \lambda_{d+1}] \mapsto \det \begin{pmatrix} x_{\lambda_1, 1} & \dots & x_{\lambda_1, d} & 1 \\ & \vdots & \\ x_{\lambda_{d+1}, 1} & \dots & x_{\lambda_{d+1}, d} & 1 \end{pmatrix}\]

defines an isomorphism, where $I$ is the ideal generated by the so called Plücker relations <!– Todo –> We identify the elements of the bracket algebra with its corresponding preimage in $\mathbb{C}[\Lambda]/I$. We define a monomial ordering on the elements of $\mathbb{C}[\Lambda]$. For $[\lambda] = [\lambda_1, \dots, \lambda_{d+1}], \mu = [\mu_1, \dots, \mu_{d+1}] \in \Lambda$ we set $[\lambda] \leq [\mu]$ if and only if for some $1\leq m \leq d+1$ we have $\lambda_i = \mu_i$ for all $1\leq i \leq m$ and $\lambda_{m+1} \leq \mu_{m+1}$, i.e. $[\lambda]$ is smaller in the first entry $[\lambda]$ and $[\mu]$ differ. The degree reverse lexicographic ordering extending this ordering of the variables is called the tableaux ordering.

• BracketAlgebras.BracketAlgebra
• BracketAlgebras.BracketAlgebraElem
• BracketAlgebras.Tabloid
• BracketAlgebras.atomic_extensors
• BracketAlgebras.d
• BracketAlgebras.is_standard
• BracketAlgebras.n
• BracketAlgebras.point_labels
• BracketAlgebras.point_labels!
• BracketAlgebras.point_ordering
• BracketAlgebras.point_ordering!
• BracketAlgebras.standard_violation
• BracketAlgebras.straighten
• BracketAlgebras.straightening_sizyge

Basic bracket algebra functionality

This package implements bracket algebras using the ring interface of the Julia package AbstractAlgebra.jl. As is usual for AbstractAlgebra rings, a bracket algebra is an object of type BracketAlgebra and the elements of a bracket algebra are objects of type BracketAlgebraElem.

Constructing Bracket Algebras

Bracket algebras in this package are BracketAlgebra objects.

BracketAlgebra{T<:RingElement} <: AbstractBracketAlgebra{T}

To construct the bracket algebra $\mathcal{B}_{6,3}$, you can call

julia> BracketAlgebra(6,3)
Bracket algebra over P^3 on 6 points with point ordering 1 < 2 < 3 < 4 < 5 < 6 and coefficient ring Integers.

The standard labels for the n points is 1:n. You can give different labels to the points by calling

julia> labels = ["a", "b", "c", "d", "e", "f"];

julia> BracketAlgebra(6, 3, point_labels=labels)
Bracket algebra over P^3 on 6 points with point ordering a < b < c < d < e < f and coefficient ring Integers.

Note that if the point labels are integers, they are always expected to be equal to 1:n.

julia> BracketAlgebra(6,3,point_labels=[2,1,3,4,5,6])
ERROR: When point_labels is a Vector of Integers, it must equal collect(1:n)

You can also construct bracket algebras with different orderings of the points. This translates to changing the ordering in the elements of $\Lambda$ above.

julia> labels = ["a", "b", "c", "d", "e", "f"];

julia> BracketAlgebra(6, 3, point_labels=labels)
Bracket algebra over P^3 on 6 points with point ordering a < b < c < d < e < f and coefficient ring Integers.

julia> BracketAlgebra(6, 3, [2,1,3,4,5,6], point_labels=labels)
Bracket algebra over P^3 on 6 points with point ordering b < a < c < d < e < f and coefficient ring Integers.

To access the contents of the fields of a BracketAlgebra the following access functions are provided

n(B::BracketAlgebra)

julia> n(BracketAlgebra(6,3))
6

d(B::BracketAlgebra)

julia> d(BracketAlgebra(6,3))
3

point_ordering(B::BracketAlgebra)

julia> point_ordering(BracketAlgebra(6,3,[2,1,3,4,5,6]))
6-element Vector{Int64}:
 2
 1
 3
 4
 5
 6

point_labels(B::BracketAlgebra)

To change the point ordering of an existing bracket algebra call

point_ordering!(B::BracketAlgebra, point_ordering::AbstractVector{<:Integer}=collect(1:B.n))

julia> point_ordering!(BracketAlgebra(6,3), [6,5,4,3,2,1])
Bracket algebra over P^3 on 6 points with point ordering 6 < 5 < 4 < 3 < 2 < 1 and coefficient ring Integers.

The generators of a bracket algebra, i.e. the brackets in the bracket algebra, can be computed by AbstractAlgebra.gens.

julia> gens(BracketAlgebra(4,2))
4-element Vector{BracketAlgebraElem{BigInt}}:
 [2, 3, 4]
 [1, 3, 4]
 [1, 2, 4]
 [1, 2, 3]

julia> gens(BracketAlgebra(4,2,[2,1,3,4]))
4-element Vector{BracketAlgebraElem{BigInt}}:
 [1, 3, 4]
 [2, 3, 4]
 [2, 1, 4]
 [2, 1, 3]

To change the point labels of an existin bracket algebra call

point_labels!(B::BracketAlgebra, new_labels::AbstractVector)

julia> point_labels!(BracketAlgebra(6,3), ["a", "b", "c", "d", "e", "f"])
Bracket algebra over P^3 on 6 points with point ordering a < b < c < d < e < f and coefficient ring Integers.

julia> point_labels!(BracketAlgebra(6,3), [2,1,3,4,5,"a"])
Bracket algebra over P^3 on 6 points with point ordering 2 < 1 < 3 < 4 < 5 < a and coefficient ring Integers.

julia> point_labels!(BracketAlgebra(6,3), [2,1,3,4,5,6])
ERROR: When point_labels is a Vector of Integers, it must equal collect(1:n)

The coefficient ring of the bracket algebra can be accessed via AbstractAlgebra.base_ring

julia> base_ring(BracketAlgebra(4,2,[1,2,3,4],Rational{BigInt}))
Rationals

julia> base_ring(BracketAlgebra(4,2,[1,2,3,4],BigInt))
Integers

julia> base_ring(BracketAlgebra(4,2,[1,2,3,4],AbstractAlgebra.GF(13)))
Finite field F_13

Constructing bracket algebra elements

The elements of a bracket algebra are BracketAlgebraElem objects.

BracketAlgebraElem{T<:Union{RingElem,Number}} <: AbstractBracketAlgebraElem{T}

The easiest way to construct bracket algebra elements is to first construct a bracket algebra B and then constructing the elements with B(bracket), where bracket is a vector of point labels of length d(B)+1, as in the following example

julia> B = BracketAlgebra(4, 2, point_labels = ["a","b","c","d"])
Bracket algebra over P^2 on 4 points with point ordering a < b < c < d and coefficient ring Integers.

julia> B(["a","b","c"])
["a", "b", "c"]

You can also generate a bracket algebra element in the same way by providing the indices of the labels.

julia> B = BracketAlgebra(4, 2, point_labels = ["a","b","c","d"])
Bracket algebra over P^2 on 4 points with point ordering a < b < c < d and coefficient ring Integers.

julia> B([1,2,3])
["a", "b", "c"]

Brackets are alternating, therefore

julia> B = BracketAlgebra(4, 2, point_labels = ["a","b","c","d"])
Bracket algebra over P^2 on 4 points with point ordering a < b < c < d and coefficient ring Integers.

julia> B([2,1,3])
 - ["a", "b", "c"]

julia> B([2,2,3])
0

Elements a of the coefficient ring of a bracket algebra B can be coerced into the bracket algebra by calling B(a). B() will construct the zero element of B. zero(B) and one(B) are also implemented to return the zero and one element of B as well as methods for functions iszero(b) and isone(b) to check whether a bracket algebra element is the zero or one element.

julia> B = BracketAlgebra(4, 2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> B(1)
1

julia> typeof(B(1))
BracketAlgebraElem{BigInt}

julia> B()
0

julia> zero(B)
0

julia> one(B)
1

julia> isone(one(B))
true

julia> iszero(zero(B))
true

Brackets can be added, multiplied and multiplied with elements of the base ring to form more complex bracket expressions. Internally they are stored according to the tableaux ordering, which is also why it is not recommended to change the point ordering of a bracket algebra, which already has existing elements (see point_ordering!).

julia> B = BracketAlgebra(4, 2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> B([1,2,3])*B([2,3,4]) + 2*B([1,2,4])^2 - B([2,3,4])*B([1,3,4])
 - [2, 3, 4][1, 3, 4] + 2[1, 2, 4]^2 + [2, 3, 4][1, 2, 3]

It is also possible to construct bracket algebra expressions by providing a vector of coefficients and a vector of exponent vectors of an expression.

julia> B = BracketAlgebra(4, 2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> gens(B)
4-element Vector{BracketAlgebraElem{BigInt}}:
 [2, 3, 4]
 [1, 3, 4]
 [1, 2, 4]
 [1, 2, 3]

julia> B([1,-2], [[1,2,3,4], [1,0,0,1]])
[2, 3, 4][1, 3, 4]^2[1, 2, 4]^3[1, 2, 3]^4 - 2[2, 3, 4][1, 2, 3]

The bracket algebra that a BracketAlgebraElem object b is an element of can be accessed via parent(b)

julia> B = BracketAlgebra(4, 2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> b = B([1,2,3])
[1, 2, 3]

julia> parent(b) === B
true

Arithmetic operations for bracket algebra elements

For bracket algebra elements the following arithmetic operations are implemented:

julia> B = BracketAlgebra(4,2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> b1 = B([1,2,3]) * B([1,2,4]) + B([2,3,4])
[1, 2, 4][1, 2, 3] + [2, 3, 4]

julia> b2 = B([1,2,3]) * B([2,3,4])
[2, 3, 4][1, 2, 3]

julia> 2*b1 # multiplication with integers
2[1, 2, 4][1, 2, 3] + 2[2, 3, 4]

julia> -b1 # additive inverse
 - [1, 2, 4][1, 2, 3] - [2, 3, 4]

julia> b1^3 # raising bracket algebra expressions to an integer power
[1, 2, 4]^3[1, 2, 3]^3 + 3[2, 3, 4][1, 2, 4]^2[1, 2, 3]^2 + 3[2, 3, 4]^2[1, 2, 4][1, 2, 3] + [2, 3, 4]^3

julia> b1+b2 # addition of bracket algebra elements
[2, 3, 4][1, 2, 3] + [1, 2, 4][1, 2, 3] + [2, 3, 4]

julia> b1-b2 # subtraction of bracket algebra elements
 - [2, 3, 4][1, 2, 3] + [1, 2, 4][1, 2, 3] + [2, 3, 4]

julia> b1*b2 # multiplication of bracket algebra elements
[2, 3, 4][1, 2, 4][1, 2, 3]^2 + [2, 3, 4]^2[1, 2, 3]

We can also compare representatives of bracket algebra monomials with regards to the tableuaux ordering.

julia> B = BracketAlgebra(4,2)
Bracket algebra over P^2 on 4 points with point ordering 1 < 2 < 3 < 4 and coefficient ring Integers.

julia> b1 = B([1,2,3]) * B([2,3,4])
[2, 3, 4][1, 2, 3]

julia> b2 = B([1,2,3]) * B([1,2,4])
[1, 2, 4][1, 2, 3]

julia> b3 = B([2,3,4])
[2, 3, 4]

julia> b1 < b2
false

julia> b1 > b2
true

julia> b1 > b3
true

Bracket algebra elements as polynomials

We can query information about the chosen representative in $\mathbb{C}[\Lambda]$ of a bracket algebra element as a polynomial. These are implemented as extensions of functions in the AbstractAlgebra.jl package.

julia> B = BracketAlgebra(4,2);

julia> b = B([1,2,3]) * B([2,3,4]) + 2*B([1,3,4]) * B([1,2,3])
[2, 3, 4][1, 2, 3] + 2[1, 3, 4][1, 2, 3]

julia> length(b) # number of terms of b
2

julia> degrees(b) # degree of b in gens(parent(b))
4-element Vector{Int64}:
 1
 1
 0
 1

julia> total_degree(b) # tatal degree of b
2

julia> collect(coefficients(b)) # coefficients of the terms of b in tableaux ordering
2-element Vector{BigInt}:
 1
 2

julia> collect(monomials(b)) # monomials making up the terms of b in tableaux ordering
2-element Vector{BracketAlgebraElem{BigInt}}:
 [2, 3, 4][1, 2, 3]
 [1, 3, 4][1, 2, 3]

julia> collect(terms(b)) # terms of b in tableaux ordering
2-element Vector{BracketAlgebraElem{BigInt}}:
 [2, 3, 4][1, 2, 3]
 2[1, 3, 4][1, 2, 3]

julia> collect(exponent_vectors(b)) # exponent vectors of terms of b in tableaux ordering
2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]

julia> coeff(b, 2) # coefficient of second term
2

julia> coeff(b, [0,1,0,1]) # coefficient of the term with exponent vector [0,1,0,1]
2

julia> monomial(b, 2) # monomial of second term
[1, 3, 4][1, 2, 3]

julia> exponent_vector(b, 2) # exponent vector of second term
4-element Vector{Int64}:
 0
 1
 0
 1

julia> term(b, 2) # second term
2[1, 3, 4][1, 2, 3]

julia> leading_term(b) # leading term of b
[2, 3, 4][1, 2, 3]

julia> leading_monomial(b) # leading monomial of b
[2, 3, 4][1, 2, 3]

julia> leading_coefficient(b) # leading coefficient of b
1

You can evaluate a bracket expression b of a bracket algebra B at a coordinization of the points in homogeneous coordinates. For that provide the coordinization as a $d\times n$ matrix, where the columns correspond to the point coordinates and call evaluate(b, coordinization)

julia> B = BracketAlgebra(4,2);

julia> b = B([2,3,4]) * B([1,2,4])
[2, 3, 4][1, 2, 4]

julia> coordinization = [0 1 0 1; 0 0 1 1]
2×4 Matrix{Int64}:
 0  1  0  1
 0  0  1  1

julia> evaluate(b, coordinization)
-1.0

julia> x = hcat(transpose(coordinization), ones(4,1)) # matrix X as in introduction
4×3 Matrix{Float64}:
 0.0  0.0  1.0
 1.0  0.0  1.0
 0.0  1.0  1.0
 1.0  1.0  1.0

julia> det(x[[2,3,4], :]) * det(x[[1,2,4], :])
-1.0

Straightening

We want to define a normal form for bracket algebra elements. This is achieved by the isomorphism $\mathcal{B}_{n,d} \cong \mathbb{C}[\Lambda]/I$.

Straightening syziges

Let $1\leq s \leq d+1$, $\alpha \in \Lambda(n, s-1)$, $\beta \in \Lambda(n, d+2)$ and $\gamma \in \Lambda(n, d + 1 - s)$. For $\tau = \{\tau_1 < \dots <\tau_s\}\subset \{1, \dots, d+2\}$ let $\tau^\ast = \{1, \dots, d+2\} \setminus \tau = \{\tau^\ast_1 < \dots < \tau^\ast_{d+2-s}}$ and

\[\mathrm{sgn}(\tau*, \tau) = \mathrm{sgn} \begin{pmatrix} 1 & 2 & 3 & \dots & d+2-s & d+2-s+1 & \dots & d+2 \\ \tau^\ast_1 & \tau^\ast_2 & \tau^\ast_3 & \dots & \tau^\ast_{d+2-s} & \tau_1 & \dots & \tau_s \end{pmatrix}.\]

We define the straightening syzige

\[[[\alpha, \dot{\beta}, \gamma]] = \sum_{\tau \in \mathrm{Pot}_s(\underline{d+2})} \mathrm{sgn}(\tau*, \tau) [\alpha_1, \dots, \alpha_{s-1}, \beta_{\tau^\ast_1}, \dots, \beta_{\tau^\ast_{d+2-s}}][\beta_{\tau_1}, \dots, \beta_{\tau_s}, \gamma_1, \dots, \gamma_{d+1-s}] \in \mathbb{C}(\Lambda).\]

The straightening syzige of \alpha, \beta and \gamma in a bracket algebra B can be constructed using the function straightening_syzige

straightening_sizyge(α::Vector{<:Integer}, β::Vector{<:Integer}, γ::Vector{<:Integer}, B::BracketAlgebra)

julia> B = BracketAlgebra(6,2)
Bracket algebra over P^2 on 6 points with point ordering 1 < 2 < 3 < 4 < 5 < 6 and coefficient ring Integers.

julia> α = [1]
1-element Vector{Int64}:
 1

julia> β = [5,6,2,3]
4-element Vector{Int64}:
 5
 6
 2
 3

julia> γ = [4]
1-element Vector{Int64}:
 4

julia> straightening_sizyge(α, β, γ, B)
[2, 3, 4][1, 5, 6] + [2, 4, 5][1, 3, 6] - [2, 4, 6][1, 3, 5] - [3, 4, 5][1, 2, 6] + [3, 4, 6][1, 2, 5] + [4, 5, 6][1, 2, 3]

Tabloids

Further we need to introduce the notions of tabloids. Let $[\lambda_1]\dots[lambda_k] \in \mathbb{C}[\Lambda]$ be a monomial, such that $[\lambda_1]\leq \dots \leq [\lambda_k]$. The associated tabloid to the monomial is

\[ \begin{pmatrix} \lambda_1 \\ \vdots \\ \lambda_k \end{pmatrix}.\]

In this package tabloids are objects of the struct Tabloid.

Tabloid

We can associate a tabloid to a bracket algebra monomial by the tabloid corresponding to its representative. A tabloid is said to be standard, iff its rows are ordered.

standard_violation(t::Tabloid)

julia> standard_violation(Tabloid([1 2 3; 1 4 5; 1 5 6; 2 3 4], [1,2,3,4,5,6]))
CartesianIndex(3, 2)

julia> standard_violation(Tabloid([1 2 3; 1 2 4], [1,2,3,4]))

standard_violation(b::BracketAlgebraElem)

is_standard(t::Tabloid)

is_standard(b::BracketAlgebraElem)

The straightening algorithm

It can be shown that the straightening syziges form a Groebner basis of the Ideal $I$ with $\mathcal{B}_{n,d} \cong \mathbb{C}[\Lambda]/I$ with regards to the tablueax order. The result of the reduction of an element with this Groebner basis will lead to a representative, in which the tabloid corresponding to each term is standard. This Groebner basis reduction is called the straightening algorithm. It can be performed by iteratively adding appropriate multiples of straightening syziges to the representative until the tabloids corresponding to all monomials in the expression are standard. Let

\[\begin{pmatrix} \lambda_{1,1}& \dots & \lambda_{1, d+1}\\ &\vdots \\ \lambda_{k,1} & \dots & \lambda_{k, d+1} \end{pmatrix}\]

be a non standard tabloid corresponding to a term in a bracket algebra element $b$. Let $(r,s)$ be the first index, where the tabloid is not standard, meaning $\lambda_{r,s} > \lambda_{r+1,s}$. Let $\alpha = [\lambda_{r,1}, \dots, \lambda_{r, s-1}]$, $\beta = [\lambda_{r, s}, \dots, \lambda_{r, d+1}, \lambda_{r+1, 1}, \dots, \lambda_{r+1, s-1}]$, $\gamma = [\lambda_{r+1, s}, \dots, \lambda_{r+1, d+1}]$, then $b = b - [\lambda_{1,1}, \dots, \lambda_{1, d+1}]\dots [\lambda_{r-1, 1}, \dots, \lambda_{r-1, d+1}] [\lambda_{r+2,1}, \dots, \lambda_{r+2, d+1}]\dots [\lambda_{k,1}, \dots, \lambda_{k, d+1}] [[\alpha\dot{\beta}\gamma]] \in \mathcal{B}_{n,d}$, but the violation to the standardness occurs later in the tabloid of the adjusted term. Therefore the straightening algorithm terminates and returns a representative, where every term is standard.

straighten(b::BracketAlgebraElem)

julia> B = BracketAlgebra(6, 2)
Bracket algebra over P^2 on 6 points with point ordering 1 < 2 < 3 < 4 < 5 < 6 and coefficient ring Integers.

julia> b = B([1,4,5])*B([1,5,6])*B([2,3,4])
[2, 3, 4][1, 5, 6][1, 4, 5]

julia> straighten(b)
[2, 5, 6][1, 4, 5][1, 3, 4] - [3, 5, 6][1, 4, 5][1, 2, 4] + [4, 5, 6][1, 4, 5][1, 2, 3]

The straightening algorithm makes it possible to decide if two elements are equal as by basic Groebner basis results two elements of a bracket algebra are equal if and only if their representative after Groebner basis reduction (after straightening in the case of bracket algebras) are equal.

julia> B = BracketAlgebra(6,2)
Bracket algebra over P^2 on 6 points with point ordering 1 < 2 < 3 < 4 < 5 < 6 and coefficient ring Integers.

julia> α = [1,2]
2-element Vector{Int64}:
 1
 2

julia> β = [2,3,4,5]
4-element Vector{Int64}:
 2
 3
 4
 5

julia> γ = Int[]
Int64[]

julia> straighten(straightening_sizyge(α, β, γ, B))
0

julia> straightening_sizyge(α, β, γ, B) == zero(B)
true

julia> b = B([1,4,5])*B([1,5,6])*B([2,3,4])
[2, 3, 4][1, 5, 6][1, 4, 5]

julia> straighten(b)
[2, 5, 6][1, 4, 5][1, 3, 4] - [3, 5, 6][1, 4, 5][1, 2, 4] + [4, 5, 6][1, 4, 5][1, 2, 3]

julia> b + B([2,3,4]) * straightening_sizyge(α, β, γ, B)
[2, 3, 4][1, 5, 6][1, 4, 5] - [2, 3, 4]^2[1, 2, 5] + [2, 3, 5][2, 3, 4][1, 2, 4] - [2, 4, 5][2, 3, 4][1, 2, 3]

julia> straighten(b + B([2,3,4]) * straightening_sizyge(α, β, γ, B))
[2, 5, 6][1, 4, 5][1, 3, 4] - [3, 5, 6][1, 4, 5][1, 2, 4] + [4, 5, 6][1, 4, 5][1, 2, 3]

julia> b == b + B([2,3,4]) * straightening_sizyge(α, β, γ, B)
true

Atomic extensors

atomic_extensors(b::BracketAlgebraElem)