# 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}
\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)'
```