# Markov transformations¶

Markov transformation

EXAMPLES:

TODO:

• Remove cylinder code from matrix cocycle

• Remove rounded_string_vector from matrix cocycle

AUTHORS:

• Sébastien Labbé, initial version, January 2016

class slabbe.markov_transformation.MarkovTransformation(partition, transitions, linear_maps)

Bases: object

Markov Transformation

INPUT:

• partition – dict, mapping each key to a cone (matrix)

• transitions – dict, mapping each key to set of keys

• linear_maps – dict, mapping each key to a linear map (matrix)

EXAMPLES:

Brun MCF algorithm is a Markov transformation:

sage: import itertools
sage: B12 = matrix(3, [1,0,0, 1,1,0, 0,0,1])
sage: B13 = matrix(3, [1,0,0, 0,1,0, 1,0,1])
sage: B21 = matrix(3, [1,1,0, 0,1,0, 0,0,1])
sage: B23 = matrix(3, [1,0,0, 0,1,0, 0,1,1])
sage: B31 = matrix(3, [1,0,1, 0,1,0, 0,0,1])
sage: B32 = matrix(3, [1,0,0, 0,1,1, 0,0,1])
sage: gens = (B23, B32, B13, B31, B12, B21)
sage: alphabet = [123, 132, 213, 231, 312, 321]
sage: partition = dict(zip(alphabet, gens))
sage: def B(i,j,k): return int('{}{}{}'.format(i,j,k))
sage: transitions = {B(i,j,k):[B(i,j,k), B(i,k,j), B(k,i,j)]
....:         for i,j,k in itertools.permutations((1,2,3))}
sage: linear_maps = partition
sage: from slabbe.markov_transformation import MarkovTransformation
sage: T = MarkovTransformation(partition, transitions, linear_maps)

automaton()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.automaton()
Automaton with 12 states

identity_matrix()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.identity_matrix()
[1 0 0]
[0 1 0]
[0 0 1]

language()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.language()
Regular language over [-321, -312, -231, -213, -132, -123,
123, 132, 213, 231, 312, 321]
defined by: Automaton with 12 states

n_cylinders_edges(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: E = T.n_cylinders_edges(1)
sage: len(E)
39

n_cylinders_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: A,B = zip(*list(T.n_cylinders_iterator(1)))
sage: sorted(A)
[word: -321, word: -321, word: -312, word: -312, word: -231, word: -231,
word: -213, word: -213, word: -132, word: -132, word: -123, word: -123,
word: 123, word: 123, word: 132, word: 132, word: 213, word: 213,
word: 231, word: 231, word: 312, word: 312, word: 321, word: 321]
sage: sorted(B)
[
[0 1 0]  [0 1 0]  [0 1 1]  [0 1 1]  [1 1 0]  [1 1 0]  [1 1 0]  [1 1 0]
[0 1 1]  [1 3 1]  [0 1 0]  [1 3 1]  [1 1 1]  [1 2 1]  [2 2 1]  [2 3 1]
[1 3 1], [0 1 1], [1 3 1], [0 1 0], [2 3 1], [2 2 1], [1 2 1], [1 1 1],
<BLANKLINE>
[1 1 1]  [1 1 1]  [1 1 1]  [1 1 1]  [1 2 1]  [1 2 1]  [1 2 1]  [1 2 1]
[1 1 0]  [1 2 1]  [2 2 1]  [2 3 1]  [1 1 0]  [1 1 1]  [2 2 1]  [2 2 1]
[2 3 1], [2 2 1], [1 2 1], [1 1 0], [2 2 1], [2 2 1], [1 1 0], [1 1 1],
<BLANKLINE>
[1 3 1]  [1 3 1]  [2 2 1]  [2 2 1]  [2 2 1]  [2 2 1]  [2 3 1]  [2 3 1]
[0 1 0]  [0 1 1]  [1 1 0]  [1 1 1]  [1 2 1]  [1 2 1]  [1 1 0]  [1 1 1]
[0 1 1], [0 1 0], [1 2 1], [1 2 1], [1 1 0], [1 1 1], [1 1 1], [1 1 0]
]

n_matrices_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: A,B = list(zip(*list(T.n_matrices_iterator(1))))
sage: sorted(A)
[word: -321,
word: -312,
word: -231,
word: -213,
word: -132,
word: -123,
word: 123,
word: 132,
word: 213,
word: 231,
word: 312,
word: 321]
sage: sorted(B)
[
[1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]
[0 1 0]  [0 1 0]  [0 1 0]  [0 1 0]  [0 1 1]  [0 1 1]  [1 1 0]  [1 1 0]
[0 1 1], [0 1 1], [1 0 1], [1 0 1], [0 0 1], [0 0 1], [0 0 1], [0 0 1],
<BLANKLINE>
[1 0 1]  [1 0 1]  [1 1 0]  [1 1 0]
[0 1 0]  [0 1 0]  [0 1 0]  [0 1 0]
[0 0 1], [0 0 1], [0 0 1], [0 0 1]
]


TESTS:

sage: list(T.n_matrices_iterator(0))
[(
[1 0 0]
[0 1 0]
word: , [0 0 1]
)]

n_words_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: sorted(T.n_words_iterator(1))
[word: -321,
word: -312,
word: -231,
word: -213,
word: -132,
word: -123,
word: 123,
word: 132,
word: 213,
word: 231,
word: 312,
word: 321]


TESTS:

sage: list(T.n_words_iterator(0))
[word: ]

plot_n_cylinders(n, labels=True)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: G = T.plot_n_cylinders(3)


TESTS:

sage: G = T.plot_n_cylinders(0)

tikz_n_cylinders(n, labels=None, scale=1)

INPUT:

• labels – None, True or False (default: None), if None, it takes value True if n is 1.

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: t = T.tikz_n_cylinders(1, labels=True, scale=4)
sage: t
\documentclass[tikz]{standalone}
\usepackage{amsmath}
\begin{document}
\begin{tikzpicture}
[scale=4]
...
... 56 lines not printed (2702 characters in total) ...
...
\end{tikzpicture}
\end{document}

sage: from sage.misc.temporary_file import tmp_filename
sage: filename = tmp_filename('temp','.pdf')
sage: _ = t.pdf(filename)

word_to_matrix(w)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.word_to_matrix([123,321,-231])
[1 1 1]
[0 1 0]
[1 1 2]


Empty word:

sage: T.word_to_matrix([])
[1 0 0]
[0 1 0]
[0 0 1]

class slabbe.markov_transformation.MarkovTransformationGenerators

Bases: object

Brun()
Selmer()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T
Markov Transformation on 12 atoms with alphabet
[-321, -312, -231, -213, -132, -123, 123, 132, 213, 231, 312, 321]

slabbe.markov_transformation.rounded_string_vector(v, digits=4)

EXAMPLES:

sage: from slabbe.matrix_cocycle import rounded_string_vector
sage: v = (-0.144337567297406, 0.166666666666667)
sage: rounded_string_vector(v)
'(-0.1443, 0.1667)'
sage: rounded_string_vector(v, digits=6)
'(-0.144338, 0.166667)'