Provide projections methods for word paths

[seblabbe]

Nice mathematical objects can be obtained when projecting appropriately a discrete path (Rauzy fractals for instance).

This patch introduces 3 projection functions for word path. It also adds 2 functions to WordMorphism and 2 matrix rotation functions to sage/matrix/constructor.py.

The first 1000 points of the Rauzy fractal :

    sage: s = WordMorphism('1->12,2->13,3->1')
    sage: D = s.fixed_point('1')
    sage: v = s.pisot_vector()
    sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
    sage: w = P(D[:1000])
    sage: w.projected_plot(v)

See more examples in doctests.

CC: @sagetrac-abmasse @videlec @robertwb @sagetrac-tjolivet @sagetrac-tmonteil

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Franco Saliola, Timo Jolivet

Merged: sage-4.7.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/8670

[seblabbe]

comment:2

There are some limit case problems :

sage: from sage.plot.plot3d.transform import *
sage: rotate_vector_on_axis((1,0,0), 0)
Traceback (most recent call last):
...
ZeroDivisionError: Rational division by zero

Will post a new patch soon.

[seblabbe]

comment:3

I fixed the above problem in the updated patch. Needs review!

Since I am adding two functions to the file sage/plot/plot3d/transform.pyx, I am also adding Robert Bradshaw in cc of this ticket. He might have some comments to share.

[seblabbe]

Does not depend on any known patch. Applies on 4.3.4.

[saliola]

comment:4

Attachment: trac_8670-word-path-projection-sl.patch.gz

1. Your definition of Pisot eigenvector is ambiguous.

Returns the left eigenvector of the incidence matrix associated
to the largest eigenvalue (in absolute value).

It is possible that there are multiple eigenvalues with the same absolute value:

sage: mu = WordMorphism('a->c,b->c,c->ab')
sage: m = matrix(mu); m
[0 0 1]
[0 0 1]
[1 1 0]
sage: m.eigenvalues()
[0, -1.414213562373095?, 1.414213562373095?]

It is not clear which eigenvector gets returned here.

Also, there may be more than one eigenvector associated to your "maximal" eigenvalue, and your method only returns one eigenvector:

sage: mu = WordMorphism('a->a,b->b,c->abc')
sage: mu.pisot_eigenvector_left()
(1, -1, 0)
sage: m = matrix(mu); m
[1 0 1]
[0 1 1]
[0 0 1]
sage: m.eigenspaces_left()
[
(1, Vector space of degree 3 and dimension 2 over Rational Field
User basis matrix:
[ 1 -1  0]
[ 0  0  1])
]

2. The method directive_vector should include a definition of what the directive vector is.

3. In your functions rotate_ith_to_zero and rotate_vector_on_axis, you first construct the matrix and then coerce it into the ring specified by the user. Why is this preferable to doing the computations directly in the ring? What about making this an option compute_in_ring=False? I think all you need to do is add the following line at the beginning:

if compute_in_ring is True:
    v = vector(ring, v)