Trac #15824: Remove deprecated code from matrix/

Removes deprecated code from #3794, #5460, #6094, #6115, #7852, #11603,
#12840, #13012 and #13643.

URL: http://trac.sagemath.org/15824
Reported by: aapitzsch
Ticket author(s): André Apitzsch
Reviewer(s): Ralf Stephan
Trac #15973: Allow GAP to compile on OS X 10.4

I don't know whether this affects any other platform...

{{{
gcc -I. -I../.. -DCONFIG_H
-I/Users/student/Desktop/sage-6.2.beta4/local/include -Wall -g -O2  -O2
-g   -o sysfiles.o -c ../../src/sysfiles.c
../../src/sysfiles.c:3075:15: error: conflicting types for 'sys_errlist'
In file included from ../../src/sysfiles.h:20:0,
                 from ../../src/sysfiles.c:21:
/usr/include/stdio.h:274:30: note: previous declaration of 'sys_errlist'
was here
make[4]: *** [sysfiles.o] Error 1
make[3]: *** [compile] Error 2
Error building GAP.

real    11m47.329s
user    7m23.375s
sys     2m4.167s
************************************************************************
Error installing package gap-4.7.4
************************************************************************
}}}
Dima on [https://groups.google.com/forum/#!msg/sage-
release/6Vh55hF7UXk/cITCg5T83EkJ this sage-release thread] gives the
correct solution - to add -DHAVE_SYS_ERRLIST to the CFLAGS.

There is another problem with an unknown `-no_pie` flag as well which is
passed to the linker, which on 10.4 and 10.5 is not supported - see
[http://trac.macports.org/ticket/34064 this Macports bug report].

URL: http://trac.sagemath.org/15973
Reported by: kcrisman
Ticket author(s): Karl-Dieter Crisman
Reviewer(s): Volker Braun
Trac #13609: symbolic arithmetic errors

Consider the following code:

{{{
ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
r1,r2 = var('r1,r2')
expression = -(c1*r2 - c2*r1)/c3
print expression.substitute(r1=z, r2=z)
}}}

This produces a TypeError: unsupported operand parent(s) for '*':
'Finite Field in z of size 2pow8' and 'Rational Field'. I know that
'expression' is not an element of the ring 'poly', but using a
PolynomialRing is the only way I found to achieve symbolic arithmetic on
finite fields.

However, the interesting story is that if I replace the expression by

{{{
expression = -(r2 - c2*r1)/c3
}}}

it work perfectly well, but if instead the expression is

{{{
expression = -(c1 + r2 - c2*r1)/c3
}}}

then I get a segmentation fault.

To make things a little bit more interesting I can rename r1 and r2 to a
and b:

{{{
ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
a,b = var('a,b')
expression = -(c1*b - c2*a)/c3
print expression.substitute(a=z, b=z)
}}}

Then it works fine, but produces a segmentation fault for,

{{{
expression = -(c1 + b - c2*a)/c3
}}}

so you can think that it might be a problem with the use of the names r1
and r2. But this is not the case, if I rename the PolynomialRing
variables instead, from c's to x's:

{{{
ff.<z> = GF(2**8, 'z')
poly.<x1,x2,x3> = PolynomialRing(ff, 3, 'x')
r1,r2 = var('r1,r2')
expression = -(x1*r2 - x2*r1)/x3
print expression.substitute(r1=z, r2=z)
}}}

Then it works again for the first two expressions but produces a
segmentation fault for the third too.

Any idea of what is going wrong here?

Apply [attachment:trac_13609-rebase.patch]

URL: http://trac.sagemath.org/13609
Reported by: llpamies
Ticket author(s): Burcin Erocal
Reviewer(s): Jean-Pierre Flori
Trac #13774: Irreducible Cartan types created as reducibles

{{{
sage: c = CartanType([["A",2]])
sage: c.is_irreducible()
False
}}}

As a consequence, e.g. the cartan_matrix() method fails too.

'''Updated:'''

Patch submitted. Now:

{{{
sage: c = CartanType([["A",2]])
sage: c.is_irreducible()
True
sage: c = CartanType(["A2"])
sage: c.is_irreducible()
True
}}}

URL: http://trac.sagemath.org/13774
Reported by: JesusTorrado
Ticket author(s): Jesús Torrado
Reviewer(s): Travis Scrimshaw, Darij Grinberg
Trac #15922: Allow list of transitions in FiniteStateMachine.add_transistions_from_function

The transition function callback in
{{{sage.combinat.finite_state_machine.add_transistions_from_function}}}
may now also return a list of transitions in order to add multiple
transitions between a pair of states.

URL: http://trac.sagemath.org/15922
Reported by: cheuberg
Ticket author(s): Clemens Heuberger
Reviewer(s): Daniel Krenn
Trac #15923: Incorrect TypeError in FiniteStateMachine.add_from_transition_function

A TypeError occurring in the callback function {{{sage.combinat.finite_s
tate_machine.FiniteStateMachine.add_from_transition_function}}}
is incorrectly caught and leads to a misleading ValueError.

Old behaviour:
   {{{
   sage: def transition(state, where):
   sage: ...    return (vector([0,0]),1)
   sage: Transducer(transition, input_alphabet=[0], initial_states=[0])
   Traceback (click to the left of this block for traceback)
   ...
   ValueError: The callback function for add_from_transition is expected
to
   return a pair (new_state, output_label) or a list of such pairs. For
the
   state 0 and the input letter 0, it however returned [((0, 0), 1)],
which
   is not acceptable.
   }}}

New behaviour:
   {{{
   sage: def transition(state, where):
   sage: ...    return (vector([0,0]),1)
   sage: Transducer(transition, input_alphabet=[0], initial_states=[0])
   Traceback (click to the left of this block for traceback)
   ...
   TypeError: mutable vectors are unhashable
   }}}

URL: http://trac.sagemath.org/15923
Reported by: cheuberg
Ticket author(s): Clemens Heuberger
Reviewer(s): Daniel Krenn
Trac #15924: Allow non-hashable output labels in FiniteStateMachine.prepone_output

Previously, non-hashable output labels led to errors in
{{{sage.combinat.finite_state_machine.FiniteStateMachine.prepone_output}
}}.
This is now corrected.

URL: http://trac.sagemath.org/15924
Reported by: cheuberg
Ticket author(s): Clemens Heuberger, Daniel Krenn
Reviewer(s): Daniel Krenn
Trac #15925: Use Brzozowski' algorithm as default for minimizing non-deterministic automata

For a non-deterministic automaton, just merging states which are
indistinguishable for any suffix does not give a minimal non-
deterministic
automaton in every case (see e.g. http://cs.stackexchange.com/a/12712 ).
This would be done by Moore's algorithm and only gives a smaller
automaton.
To obtain an equivalent minimal deterministic automaton, we use
Brzozowski's
algorithm, which first computes a determinisation of the non-
deterministic
automaton.

URL: http://trac.sagemath.org/15925
Reported by: skropf
Ticket author(s): Clemens Heuberger, Daniel Krenn, Sara Kropf
Reviewer(s): Daniel Krenn
Trac #15331: Do not try to create embedded number field morphisms for non-embedded number fields

The attempt to create an embedded number field morphisms for non-
embedded number fields currently fails (and should of course fail).
{{{
sage: L.<i> = NumberField(x^2 + 1)
sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',),
embedding=L(i/2+3))
sage: from sage.rings.number_field import number_field_morphisms
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(R, self)
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded in __instancecheck__
}}}
However, instead of running into an infinite recursion, a quick and
simple `ValueError` (or perhaps `TypeError`) should be raised.

URL: http://trac.sagemath.org/15331
Reported by: SimonKing
Ticket author(s): Simon King, Marc Mezzarobba,  Jean-Pierre Flori
Reviewer(s): Marc Mezzarobba, Jean-Pierre Flori
Trac #15907: Improvements for affine factorization crystal

This patch provides some improvements for the affine factorization
crystal.
Before this patch
{{{
sage: from sage.combinat.crystals.affine_factorization import
AffineFactorizationCrystal
sage: W = WeylGroup(['A',3], prefix='s')
sage: w0 = W.long_element()
sage: %timeit B = AffineFactorizationCrystal(w0,6)
1 loops, best of 3: 131 s per loop
}}}
After this patch
{{{
sage: from sage.combinat.crystals.affine_factorization import
AffineFactorizationCrystal
sage: W = WeylGroup(['A',3], prefix='s')
sage: w0 = W.long_element()
sage: %timeit B = AffineFactorizationCrystal(w0,6)
1 loops, best of 3: 2.86 us per loop
}}}

URL: http://trac.sagemath.org/15907
Reported by: aschilling
Ticket author(s): Anne Schilling
Reviewer(s): Travis Scrimshaw
Trac #15286: Latin squares

This patch creates a file `latin_squares.py` in combinat/designs/, and
implements several constructions of mutually orthogonal latin squares,
as found in Douglas Stinson's book "Combinatorial Designs: Constructions
and Analysis".

Nathann

URL: http://trac.sagemath.org/15286
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #15975: FiniteStateMachine.determine_alphabets: corrected description of parameter reset

When the parameter reset is true, then not only the input but also the
output alphabet is erased.

URL: http://trac.sagemath.org/15975
Reported by: skropf
Ticket author(s): Sara Kropf
Reviewer(s): Clemens Heuberger, Daniel Krenn
Updated Sage version to 6.2.beta5