[ ] Self-contained Matlab function that takes a matrix of generators (permutations), one per row, and returns the closure of that as matrix with the same convention.
[ ] Function that computes all the permutations of a row vector under the action of generators. Either use the Dimino function above, or an orbit algorithm.
[ ] Function that returns the permutation that maps a row vector to another row vector if it exists from the closure of a list of generators. Bonus point if it returns the corresponding word.
generator is x1 = [2 3 4 1]
we want to map [1 1 2 2] to [2 2 1 1]`
Then output would be perm = [3 4 1 2], and word = [1 1] meaning x1 * x1
How to compute words?
Convention is: positive indices are generators, negative indices are generator inverses
[1 2 -1] is x1 x2 x1^-1
Take the list of elements from Dimino, we write the i-th element el{i}, assuming identity is the first one.
By convention, gen(i) = xi if i > 0 and gen(i) = x{-i}^-1 if i < 0.
We maintain three additional vectors G (generator index), I (image index), L (length), they represent a graph.
We have that action(gen(G(i)), el{i}) == el{I(i)}, L(i) = L(I(i)) + 1. For the identity G(1) = I(1) = L(1) = 0 (basically, G and I are not used for the identity).
Now, fill these vectors minimizing L(i). For that, maintain a list of elements that have been discovered, starting with the identity, called toCheck.
(depth first graph traversal of the Cayley graph of the group)
while ~isempty(toCheck)
h = toCheck(1)
remove h from toCheck
apply generators to el{h}, see if you find any new element
if yes, update G, I, L accordingly
add the new elements to toCheck
end
Put all of this in an
extrassubfolder[ ] Self-contained Matlab function that takes a matrix of generators (permutations), one per row, and returns the closure of that as matrix with the same convention.
[ ] Function that computes all the permutations of a row vector under the action of generators. Either use the Dimino function above, or an orbit algorithm.
[ ] Function that returns the permutation that maps a row vector to another row vector if it exists from the closure of a list of generators. Bonus point if it returns the corresponding word.
generator is
x1 = [2 3 4 1]we want to map[1 1 2 2]to [2 2 1 1]`Then output would be
perm = [3 4 1 2], andword = [1 1]meaningx1 * x1How to compute words?
Convention is: positive indices are generators, negative indices are generator inverses
[1 2 -1]isx1 x2 x1^-1Take the list of elements from Dimino, we write the
i-th elementel{i}, assuming identity is the first one.By convention,
gen(i) = xiifi > 0andgen(i) = x{-i}^-1ifi < 0.We maintain three additional vectors
G(generator index),I(image index),L(length), they represent a graph.We have that
action(gen(G(i)), el{i}) == el{I(i)},L(i) = L(I(i)) + 1. For the identityG(1) = I(1) = L(1) = 0(basically,GandIare not used for the identity).Now, fill these vectors minimizing
L(i). For that, maintain a list of elements that have been discovered, starting with the identity, calledtoCheck.(depth first graph traversal of the Cayley graph of the group)
(example: 2x2 rubik cube)