Partitions and Young tableaux
AbstractAlgebra.jl provides basic support for computations with Young tableaux, skew diagrams and the characters of permutation groups (implemented src/generic/YoungTabs.jl
). All functionality of permutations is accessible in the Generic
submodule.
Partitions
The basic underlying object for those concepts is Partition
of a number $n$, i.e. a sequence of positive integers $n_1, \ldots, n_k$ which sum to $n$. Partitions in AbstractAlgebra.jl are represented internally by non-increasing Vector
s of Int
s. Partitions are printed using the standard notation, i.e. $9 = 4 + 2 + 1 + 1 + 1$ is shown as $4_1 2_1 1_3$ with the subscript indicating the count of a summand in the partition.
AbstractAlgebra.Generic.Partition
— TypePartition(part::Vector{<:Integer}[, check::Bool=true]) <: AbstractVector{Int}
Represent integer partition in the non-increasing order.
part
will be sorted, if necessary. Checks for validity of input can be skipped by calling the (inner) constructor with false
as the second argument.
Functionally Partition
is a thin wrapper over Vector{Int}
.
Fieldnames:
n::Int
- the partitioned numberpart::Vector{Int}
- a non-increasing sequence of summands ofn
.
Examples
julia> p = Partition([4,2,1,1,1])
4₁2₁1₃
julia> p.n == sum(p.part)
true
Array interface
Partition
is a concrete (immutable) subtype of AbstractVector{Integer}
and implements the standard Array interface.
Base.size
— Methodsize(p::Partition)
Return the size of the vector which represents the partition.
Examples
julia> p = Partition([4,3,1]); size(p)
(3,)
Base.getindex
— Methodgetindex(p::Partition, i::Integer)
Return the i
-th part (in non-increasing order) of the partition.
These functions work on the level of p.part
vector.
One can easily iterate over all partitions of $n$ using the Generic.partitions
function.
AbstractAlgebra.Generic.partitions
— Functionpartitions(n::Integer)
Return the vector of all permutations of n
. For an unsafe generator version see partitions!
.
Examples
julia> Generic.partitions(5)
7-element Vector{AbstractAlgebra.Generic.Partition{Int64}}:
1₅
2₁1₃
3₁1₂
2₂1₁
4₁1₁
3₁2₁
5₁
You may also have a look at JuLie.jl package for more utilities related to partitions.
The number of all partitions can be computed by the hidden function _numpart
. Much faster implementation is available in Nemo.jl.
AbstractAlgebra.Generic._numpart
— Function_numpart(n::Integer)
Return the number of all distinct integer partitions of n
. The function uses Euler pentagonal number theorem for recursive formula. For more details see OEIS sequence A000041. Note that _numpart(0) = 1
by convention.
Since Partition
is a subtype of AbstractVector
generic functions which operate on vectors should work in general. However the meaning of conj
has been changed to agree with the traditional understanding of conjugation of Partitions
:
Base.conj
— Methodconj(part::Partition)
Return the conjugated partition of part
, i.e. the partition corresponding to the Young diagram of part
reflected through the main diagonal.
Examples
julia> p = Partition([4,2,1,1,1])
4₁2₁1₃
julia> conj(p)
5₁2₁1₂
Base.conj
— Methodconj(part::Partition, v::Vector)
Return the conjugated partition of part
together with permuted vector v
.
Young Diagrams and Young Tableaux
Mathematically speaking Young diagram is a diagram which consists of rows of square boxes such that the number of boxes in each row is no less than the number of boxes in the previous row. For example partition $4_1 3_2 1$ represents the following diagram.
┌───┬───┬───┬───┐
│ │ │ │ │
├───┼───┼───┼───┘
│ │ │ │
├───┼───┼───┤
│ │ │ │
├───┼───┴───┘
│ │
└───┘
Young Tableau is formally a bijection between the set of boxes of a Young Diagram and the set $\{1, \ldots, n\}$. If a bijection is increasing along rows and columns of the diagram it is referred to as standard. For example
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┼───┤
│ 8 │ 9 │10 │
├───┼───┴───┘
│11 │
└───┘
is a standard Young tableau of $4_1 3_2 1$ where the bijection assigns consecutive natural numbers to consecutive (row-major) cells.
Constructors
In AbstractAlgebra.jl Young tableau are implemented as essentially row-major sparse matrices, i.e. YoungTableau <: AbstractMatrix{Int}
but only the defining Partition
and the (row-major) fill-vector is stored.
AbstractAlgebra.Generic.YoungTableau
— TypeYoungTableau(part::Partition[, fill::Vector{Int}=collect(1:sum(part))]) <: AbstractMatrix{Int}
Return the Young tableaux of partition part
, filled linearly by fill
vector. Note that fill
vector is in row-major format.
Fields:
part
- the partition defining Young diagramfill
- the row-major fill vector: the entries of the diagram.
Examples
julia> p = Partition([4,3,1]); y = YoungTableau(p)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> y.part
4₁3₁1₁
julia> y.fill
8-element Vector{Int64}:
1
2
3
4
5
6
7
8
For convenience there exists an alternative constructor of YoungTableau
, which accepts a vector of integers and constructs Partition
internally.
YoungTableau(p::Vector{Integer}[, fill=collect(1:sum(p))])
Array interface
To make YoungTableaux
array-like we implement the following functions:
Base.size
— Methodsize(Y::YoungTableau)
Return size
of the smallest array containing Y
, i.e. the tuple of the number of rows and the number of columns of Y
.
Examples
julia> y = YoungTableau([4,3,1]); size(y)
(3, 4)
Base.getindex
— Methodgetindex(Y::YoungTableau, n::Integer)
Return the column-major linear index into the size(Y)
-array. If a box is outside of the array return 0
.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> y[1]
1
julia> y[2]
5
julia> y[4]
2
julia> y[6]
0
Also the double-indexing corresponds to (row, column)
access to an abstract array.
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> y[1,2]
2
julia> y[2,3]
7
julia> y[3,2]
0
Functions defined for AbstractArray
type based on those (e.g. length
) should work. Again, as in the case of Partition
the meaning of conj
is altered to reflect the usual meaning for Young tableaux:
Base.conj
— Methodconj(Y::YoungTableau)
Return the conjugated tableau, i.e. the tableau reflected through the main diagonal.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> conj(y)
┌───┬───┬───┐
│ 1 │ 5 │ 8 │
├───┼───┼───┘
│ 2 │ 6 │
├───┼───┤
│ 3 │ 7 │
├───┼───┘
│ 4 │
└───┘
Pretty-printing
Similarly to permutations we have two methods of displaying Young Diagrams:
AbstractAlgebra.Generic.setyoungtabstyle
— Functionsetyoungtabstyle(format::Symbol)
Select the style in which Young tableaux are displayed (in REPL or in general as string). This can be either
:array
- as matrices of integers, or:diagram
- as filled Young diagrams (the default).
The difference is purely esthetical.
Examples
julia> Generic.setyoungtabstyle(:array)
:array
julia> p = Partition([4,3,1]); YoungTableau(p)
1 2 3 4
5 6 7
8
julia> Generic.setyoungtabstyle(:diagram)
:diagram
julia> YoungTableau(p)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
Ulitility functions
AbstractAlgebra.Generic.matrix_repr
— Methodmatrix_repr(a::Perm)
Return the permutation matrix as a sparse matrix representing a
via natural embedding of the permutation group into the general linear group over $\mathbb{Z}$.
Examples
julia> p = Perm([2,3,1])
(1,2,3)
julia> matrix_repr(p)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 3 stored entries:
⋅ 1 ⋅
⋅ ⋅ 1
1 ⋅ ⋅
julia> Array(ans)
3×3 Matrix{Int64}:
0 1 0
0 0 1
1 0 0
matrix_repr(Y::YoungTableau)
Construct sparse integer matrix representing the tableau.
Examples
julia> y = YoungTableau([4,3,1]);
julia> matrix_repr(y)
3×4 SparseArrays.SparseMatrixCSC{Int64, Int64} with 8 stored entries:
1 2 3 4
5 6 7 ⋅
8 ⋅ ⋅ ⋅
Base.fill!
— Methodfill!(Y::YoungTableaux, V::Vector{<:Integer})
Replace the fill vector Y.fill
by V
. No check if the resulting tableau is standard (i.e. increasing along rows and columns) is performed.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> fill!(y, [2:9...])
┌───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 5 │
├───┼───┼───┼───┘
│ 6 │ 7 │ 8 │
├───┼───┴───┘
│ 9 │
└───┘
Characters of permutation groups
Irreducible characters (at least over field of characteristic $0$) of the full group of permutations $S_n$ correspond via Specht modules to partitions of $n$.
AbstractAlgebra.Generic.character
— Methodcharacter(lambda::Partition)
Return the $\lambda$-th irreducible character of permutation group on sum(lambda)
symbols. The returned character function is of the following signature:
chi(p::Perm[, check::Bool=true]) -> BigInt
The function checks (if p
belongs to the appropriate group) can be switched off by calling chi(p, false)
. The values computed by $\chi$ are cached in look-up table.
The computation follows the Murnaghan-Nakayama formula: $\chi_\lambda(\sigma) = \sum_{\text{rimhook }\xi\subset \lambda}(-1)^{ll(\lambda\backslash\xi)} \chi_{\lambda \backslash\xi}(\tilde\sigma)$ where $\lambda\backslash\xi$ denotes the skew diagram of $\lambda$ with $\xi$ removed, $ll$ denotes the leg-length (i.e. number of rows - 1) and $\tilde\sigma$ is permutation obtained from $\sigma$ by the removal of the longest cycle.
For more details see e.g. Chapter 2.8 of Group Theory and Physics by S.Sternberg.
Examples
julia> G = SymmetricGroup(4)
Full symmetric group over 4 elements
julia> chi = character(Partition([3,1])); # character of the regular representation
julia> chi(one(G))
3
julia> chi(perm"(1,3)(2,4)")
-1
AbstractAlgebra.Generic.character
— Methodcharacter(lambda::Partition, p::Perm, check::Bool=true) -> BigInt
Return the value of lambda
-th irreducible character of the permutation group on permutation p
.
AbstractAlgebra.Generic.character
— Methodcharacter(lambda::Partition, mu::Partition, check::Bool=true) -> BigInt
Return the value of lambda-th
irreducible character on the conjugacy class represented by partition mu
.
The values computed by characters are cached in an internal dictionary Dict{Tuple{BitVector,Vector{Int}}, BigInt}
. Note that all of the above functions return BigInts
. If you are sure that the computations do not overflow, variants of the last two functions using Int
are available:
character(::Type{Int}, lambda::Partition, p::Perm[, check::Bool=true])
character(::Type{Int}, lambda::Partition, mu::Partition[, check::Bool=true])
The dimension $\dim \lambda$ of the irreducible module corresponding to partition $\lambda$ can be computed using Hook length formula
AbstractAlgebra.Generic.rowlength
— Functionrowlength(Y::YoungTableau, i, j)
Return the row length of Y
at box (i,j)
, i.e. the number of boxes in the i
-th row of the diagram of Y
located to the right of the (i,j)
-th box.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> Generic.rowlength(y, 1,2)
2
julia> Generic.rowlength(y, 2,3)
0
julia> Generic.rowlength(y, 3,3)
0
AbstractAlgebra.Generic.collength
— Functioncollength(Y::YoungTableau, i, j)
Return the column length of Y
at box (i,j)
, i.e. the number of boxes in the j
-th column of the diagram of Y
located below of the (i,j)
-th box.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> Generic.collength(y, 1,1)
2
julia> Generic.collength(y, 1,3)
1
julia> Generic.collength(y, 2,4)
0
AbstractAlgebra.Generic.hooklength
— Functionhooklength(Y::YoungTableau, i, j)
Return the hook-length of an element in Y
at position (i,j)
, i.e the number of cells in the i
-th row to the right of (i,j)
-th box, plus the number of cells in the j
-th column below the (i,j)
-th box, plus 1
.
Return 0
for (i,j)
not in the tableau Y
.
Examples
julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘
julia> hooklength(y, 1,1)
6
julia> hooklength(y, 1,3)
3
julia> hooklength(y, 2,4)
0
AbstractAlgebra.Generic.dim
— Methoddim(Y::YoungTableau) -> BigInt
Return the dimension (using hook-length formula) of the irreducible representation of permutation group $S_n$ associated the partition Y.part
.
Since the computation overflows easily BigInt
is returned. You may perform the computation of the dimension in different type by calling dim(Int, Y)
.
Examples
julia> dim(YoungTableau([4,3,1]))
70
julia> dim(YoungTableau([3,1])) # the regular representation of S_4
3
The character associated with Y.part
can also be used to compute the dimension, but as it is expected the Murnaghan-Nakayama is much slower even though (due to caching) consecutive calls are fast:
julia> λ = Partition(collect(12:-1:1))
12₁11₁10₁9₁8₁7₁6₁5₁4₁3₁2₁1₁
julia> @time dim(YoungTableau(λ))
0.224430 seconds (155.77 k allocations: 7.990 MiB)
9079590132732747656880081324531330222983622187548672000
julia> @time dim(YoungTableau(λ))
0.000038 seconds (335 allocations: 10.734 KiB)
9079590132732747656880081324531330222983622187548672000
julia> G = SymmetricGroup(sum(λ))
Full symmetric group over 78 elements
julia> @time character(λ, one(G))
0.000046 seconds (115 allocations: 16.391 KiB)
9079590132732747656880081324531330222983622187548672000
julia> @time character(λ, one(G))
0.001439 seconds (195 allocations: 24.453 KiB)
9079590132732747656880081324531330222983622187548672000
Low-level functions and characters
As mentioned above character
functions use the Murnaghan-Nakayama rule for evaluation. The implementation follows
Dan Bernstein, The computational complexity of rules for the character table of $S_n$ Journal of Symbolic Computation, 37 (6), 2004, p. 727-748,
implementing the following functions. For precise definitions and meaning please consult the paper cited.
AbstractAlgebra.Generic.partitionseq
— Functionpartitionseq(lambda::Partition)
Return a sequence (as BitVector
) of false
s and true
s constructed from lambda
: tracing the lower contour of the Young Diagram associated to lambda
from left to right a true
is inserted for every horizontal and false
for every vertical step. The sequence always starts with true
and ends with false
.
partitionseq(seq::BitVector)
Return the essential part of the sequence seq
, i.e. a subsequence starting at first true
and ending at last false
.
AbstractAlgebra.Generic.is_rimhook
— Methodis_rimhook(R::BitVector, idx::Integer, len::Integer)
R[idx:idx+len]
forms a rim hook in the Young Diagram of partition corresponding to R
iff R[idx] == true
and R[idx+len] == false
.
AbstractAlgebra.Generic.MN1inner
— FunctionMN1inner(R::BitVector, mu::Partition, t::Integer, charvals)
Return the value of $\lambda$-th irreducible character on conjugacy class of permutations represented by partition mu
, where R
is the (binary) partition sequence representing $\lambda$. Values already computed are stored in charvals::Dict{Tuple{BitVector,Vector{Int}}, Int}
. This is an implementation (with slight modifications) of the Murnaghan-Nakayama formula as described in
Dan Bernstein,
"The computational complexity of rules for the character table of Sn"
_Journal of Symbolic Computation_, 37(6), 2004, p. 727-748.
Skew Diagrams
Skew diagrams are formally differences of two Young diagrams. Given $\lambda$ and $\mu$, two partitions of $n+m$ and $m$ (respectively). Suppose that each of cells of $\mu$ is a cell of $\lambda$ (i.e. parts of $\mu$ are no greater than the corresponding parts of $\lambda$). Then the skew diagram denoted by $\lambda/\mu$ is the set theoretic difference the of sets of boxes, i.e. is a diagram with exactly $n$ boxes:
AbstractAlgebra.Generic.SkewDiagram
— TypeSkewDiagram(lambda::Partition, mu::Partition) <: AbstractMatrix{Int}
Implements a skew diagram, i.e. a difference of two Young diagrams represented by partitions lambda
and mu
. (below dots symbolise the removed entries)
Examples
julia> l = Partition([4,3,2])
4₁3₁2₁
julia> m = Partition([3,1,1])
3₁1₂
julia> xi = SkewDiagram(l,m)
3×4 AbstractAlgebra.Generic.SkewDiagram{Int64}:
⋅ ⋅ ⋅ 1
⋅ 1 1
⋅ 1
SkewDiagram
implements array interface with the following functions:
Base.size
— Methodsize(xi::SkewDiagram)
Return the size of array where xi
is minimally contained. See size(Y::YoungTableau)
for more details.
Base.in
— Methodin(t::Tuple{Integer,Integer}, xi::SkewDiagram)
Check if box at position (i,j)
belongs to the skew diagram xi
.
Base.getindex
— Methodgetindex(xi::SkewDiagram, n::Integer)
Return 1
if linear index n
corresponds to (column-major) entry in xi.lam
which is not contained in xi.mu
. Otherwise return 0
.
The support for skew diagrams is very rudimentary. The following functions are available:
AbstractAlgebra.Generic.is_rimhook
— Methodis_rimhook(xi::SkewDiagram)
Check if xi
represents a rim-hook diagram, i.e. its diagram is edge-connected and contains no $2\times 2$ squares.
AbstractAlgebra.Generic.leglength
— Functionleglength(xi::SkewDiagram[, check::Bool=true])
Compute the leglength of a rim-hook xi
, i.e. the number of rows with non-zero entries minus one. If check
is false
function will not check whether xi
is actually a rim-hook.
AbstractAlgebra.Generic.matrix_repr
— Methodmatrix_repr(xi::SkewDiagram)
Return a sparse representation of the diagram xi
, i.e. a sparse array A
where A[i,j] == 1
if and only if (i,j)
is in xi.lam
but not in xi.mu
.