Frames Numerically

Working with frames exactly is often very slow, and not possible. Instead it may often be benificial to work with frames defined numerically. Here frames are defined with the Julia Matrix type with entries being any subtype of Number. Functionality for computing spectrums over matricies wiht entries of BigFloat is not natively supported by julia but can be provided using a package such as GenericLinearAlgebra.jl.

Basic Functionality

FrameTheory.is_frame — Method

is_frame(gram) -> Tuple{Bool,Int}

Arguments

gram::Matrix{Number}: A square matrix defined over any sub type of Number

Returns

frame_bool::Bool
d::Int

Determines if the matrix gram is the Gram matrix for some frame. Returns a boolean frame_bool if the provided matrix is the Gram matrix of a frame for some d-dimensional space. If frame_bool' is 'false then d would be nothing. To utilize this function for types BigFloat or Complex{BigFloat} you will need to use a package such as GenericLinearAlgebra.

Examples

julia> ζ = exp(2*pi*im/7);

julia> Phi = [1.0 ζ   ζ^2 ζ^3 ζ^4 ζ^5 ζ^6;
              1 ζ^2 ζ^4 ζ^6 ζ   ζ^3 ζ^5;
              1 ζ^4 ζ   ζ^5 ζ^2 ζ^6 ζ^3];

julia> gram = Phi'*Phi;

julia> is_frame(gram)
(true, 3)

source

FrameTheory.is_equiangular — Method

is_equiangular(gram) -> Tuple{Bool,Number,Number}

Arguments

gram::Matrix{Number}: A square matrix.

Returns

equiangular_bool::Bool
a::Number
b::Number

Determines if the matrix gram is the Gram matrix for some collection of equiangular vectors. Returns a boolean equiangular_bool if the provided matrix is the Gram matrix of a collection of equiangular lines. With a being the vectors common 'magnitudes' and b the 'angle'. If equiangular_bool is False, then a and b will be nothing. To utilize this function for types BigFloat or Complex{BigFloat} you will need to use a package such as GenericLinearAlgebra.

Examples

julia> ζ = exp(2*pi*im/7);

julia> Phi = [1.0 ζ   ζ^2 ζ^3 ζ^4 ζ^5 ζ^6;
              1 ζ^2 ζ^4 ζ^6 ζ   ζ^3 ζ^5;
              1 ζ^4 ζ   ζ^5 ζ^2 ζ^6 ζ^3];

julia> gram = Phi'*Phi;

julia> is_equiangular(gram)
(true, 3.0, 2.0000000000000004)

source

FrameTheory.is_frame_tight — Method

is_frame_tight(gram) -> Tuple{Bool,Number}

Arguments

gram::Matrix{Number}: A square matrix which is the Gram matrix for a frame.

Returns

tight_bool::Bool
c::Number

Determines if the matrix gram is the Gram matrix for frame which is tight. If so returns c being the constant such that gram^2=c*gram. If tight_bool is False, then c will be nothing. To utilize this function for types BigFloat or Complex{BigFloat} you will need to use a package such as GenericLinearAlgebra.

Examples

julia> ζ = exp(2*pi*im/7);

julia> Phi = [1.0 ζ   ζ^2 ζ^3 ζ^4 ζ^5 ζ^6;
              1 ζ^2 ζ^4 ζ^6 ζ   ζ^3 ζ^5;
              1 ζ^4 ζ   ζ^5 ζ^2 ζ^6 ζ^3];

julia> gram = Phi'*Phi;

julia> is_frame_tight(gram)
(true, 7.000000000000001)

source

FrameTheory.is_ETF — Method

is_ETF(gram) -> Tuple{Bool,Number,Number,Number}

Arguments

gram::Matrix{Number}: A square matrix defined over the Reals or Complexes

Returns

etf_bool::Bool
a::Number
b::Number
c::Number
d::Int

Determines if the matrix gram is the Gram matrix for some collection of vectors which form an equiangular tight frame (ETF). Calls and returns the same parameters from is_frame, is_equiangular, and is_frame_tight. To utilize this function for types BigFloat or Complex{BigFloat} you will need to use a package such as GenericLinearAlgebra.

Examples

A 3x7 Paley (3,2,7)-ETF.

julia> ζ = exp(2*pi*im/7);

julia> Phi = [1.0 ζ   ζ^2 ζ^3 ζ^4 ζ^5 ζ^6;
              1 ζ^2 ζ^4 ζ^6 ζ   ζ^3 ζ^5;
              1 ζ^4 ζ   ζ^5 ζ^2 ζ^6 ζ^3];

julia> gram = Phi'*Phi;

julia> is_ETF(gram)
(true, 3.0, 2.0000000000000004, 7.000000000000001, 3)

source

Constructions

A common method for numerically constructing ETFs is by the method of Alternating Projections. This method is not guaranteed to converge but can be used to try and determine if such an ETF exists.

FrameTheory.NumCons.rand_etf_from_alt_proj — Function

NumCons.rand_etf_from_alt_proj(T, d, n[; iters]) -> Matrix{T}

Arguments

T::Type: A Type for a number such as Float64, Complex{Float64}
d::Int: dimension.
n::Int: number of vectors.
iters::Int=1000: number of iterations to try and converge.

Returns

gram::Matrix{T}: The Gram matrix, if one exists, of a d by n ETF. Or non-sense if the algorithm failed to converge.

To utilize this function for types BigFloat or Complex{BigFloat} you will need to use a package such as GenericLinearAlgebra.

Examples

A real 3x6 ETF

julia> gram = NumCons.rand_etf_from_alt_proj(Float64, 3, 6);

julia> is_ETF(gram)
(true, 1.0, 0.19999999999999998, 1.9999999999999998, 3)

A complex 2x4 ETF

julia> gram = NumCons.rand_etf_from_alt_proj(Complex{Float64}, 2, 4);

julia> is_ETF(gram)
(true, 1.0, 0.3333333333333331, 1.9999999999999996, 2)

No real 2x4 ETF exists A complex 2x4 ETF

julia> gram = NumCons.rand_etf_from_alt_proj(Float64, 2, 4);

julia> is_ETF(gram)
(false, nothing, nothing, nothing, 4)

source

Exactification

In some cases it is possible to exactify a numerically defined matrix. To do this we implement try_exactify using the Oscar.jl function guess.

FrameTheory.try_exactify — Function

try_exactify(A[; maxdeg, maxbits]) -> Union{RealMatrix,ComplexMatrix}

Arguments

A::Matrix{BigFloat}: A matrix which is numerically very close to a matrix with algebraic entries.
maxdeg: see Oscar.jl documentation on guess.
maxbits: see Oscar.jl documentation on guess.

Returns

gram::MatElem{CalciumFieldElem}: The exactified matrix

If unable to exactify, an error will be thrown. This function is very finichy, and often fails. It is recommended to use BigFloat or Complex{BigFloat}.

Examples

julia> using GenericLinearAlgebra;

julia> gram = NumCons.rand_etf_from_alt_proj(BigFloat, 3, 6, iters=5000);

julia> exact_gram = try_exactify(gram);

julia> is_ETF(exact_gram)
(true, 1, 0.200000 {1/5}, 2, 3)

source

Binder Finder

FrameTheory.binder_finder — Method

binder_finder(gram) -> Matrix{Int}

Arguments

gram::Matrix{Number}: The Gram matrix of an ETF.

Returns

binder::Matrix{Int}: The Binder of the provided frame, where each row denotes a simplex.

This function follows the implementation from [6].

Examples

julia> ζ = exp(2*pi*im/3);

julia> sic = [
          1    1       1    -1 -1  -1    0   0      0;
          0    0       0     1  ζ  ζ^2  -1 -1*ζ   -1*ζ^2;
         -1  -1*ζ^2  -1*ζ    0  0   0    1  ζ^2     ζ
       ];

julia> gram = sic'*sic;

julia> is_ETF(gram)
(true, 2.0, 0.9999999999999992, 6.0, 3)

julia> binder_finder(gram)
12×9 Matrix{Int64}:
 1  1  1  0  0  0  0  0  0
 1  0  0  1  0  0  1  0  0
 1  0  0  0  1  0  0  0  1
 1  0  0  0  0  1  0  1  0
 0  1  0  1  0  0  0  0  1
 0  1  0  0  1  0  0  1  0
 0  1  0  0  0  1  1  0  0
 0  0  1  1  0  0  0  1  0
 0  0  1  0  1  0  1  0  0
 0  0  1  0  0  1  0  0  1
 0  0  0  1  1  1  0  0  0
 0  0  0  0  0  0  1  1  1

source

The Projective Symmetry Group of an ETF

FrameTheory.projective_symmetry_group — Method

projective_symmetry_group(gram) -> PermGroup

Arguments

gram::Matrix{Number}: A square matrix which is the Gram matrix of some ETF.
verbose::Bool: (Default false).

Returns

G::PermGroup: The group of permutations of the vector of the frame, that correspond to switching equivalences.

This algorithm uses a modified version of the breath first search based Gap code by Joey Iverson: https://github.com/jwiverson/frame-symmetries/blob/main/symp.gap. This implementation instead chooses to use a depth first search approach for better memory management. This algorithm implements the algorithm from section 4 of [7]. Over R or C this algorithm utilizes Proposition 3.3 from the same paper.

Examples

The following is an example of a 2x4 ETF with a 2-transitive symmetry group.

julia> gram = numericalize(ExactCons.dx2d_etf_from_prime_power(3));

julia> typeof(gram)
Matrix{Complex{BigFloat}}

julia> G = projective_symmetry_group(gram)
Permutation group of degree 4

julia> transitivity(G, 1:4)
2

julia> describe(G)
"A4"

source