py3: matroids.utilities.lift_cross_ratios

[jhpalmieri]

The documentation for the method matroids.utilities.lift_cross_ratios says This method will create a unique candidate representation ``Z``. It gives different answers in Python 2 and Python 3, yielding a doctest failure with py3. Is the representation not unique and both are valid answers? The code contains several loops over dictionaries, and so the loops can happen in different orders; does that matter?

CC: @sagetrac-Stefan @sagetrac-Rudi @sagetrac-zgershkoff

Component: matroid theory

Author: John Palmieri

Branch/Commit: ba75541

Reviewer: Travis Scrimshaw

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

[jhpalmieri]

comment:1

In particular, with Python 3:

File "src/sage/matroids/utilities.py", line 543, in sage.matroids.utilities.lift_cross_ratios
Failed example:
    Z
Expected:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0  1 -z -1  0]
Got:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0 -1  z  1  0]

[jhpalmieri]

comment:2

A really drastic fix would be to just delete this function entirely, and also its companion lift_map. They are only used in one place, in the representation method in linear_matroid.pyx, and then only if an optional argument lift_map is specified, but no doctests use lift_map and so the code is untested. That makes me wary of keeping it around: does it actually work? Will it continue to work with Python 3?

A proper fix to this ticket would add doctests to representation which use lift_map.

If we end up deleting those two functions, these changes would also be required:

diff --git a/src/sage/matroids/advanced.py b/src/sage/matroids/advanced.py
index 8d8a02ed1b..61cfa3a187 100644
--- a/src/sage/matroids/advanced.py
+++ b/src/sage/matroids/advanced.py
@@ -40,8 +40,6 @@ This adds the following to the main namespace:
         - :func:`setprint() <sage.matroids.utilities.setprint>`
         - :func:`newlabel() <sage.matroids.utilities.newlabel>`
         - :func:`get_nonisomorphic_matroids() <sage.matroids.utilities.get_nonisomorphic_matroids>`
-        - :func:`lift_cross_ratios() <sage.matroids.linear_matroid.lift_cross_ratios>`
-        - :func:`lift_map() <sage.matroids.linear_matroid.lift_map>`
 
 AUTHORS:
 
@@ -56,7 +54,7 @@ from .rank_matroid import RankMatroid
 from .circuit_closures_matroid import CircuitClosuresMatroid
 from .basis_matroid import BasisMatroid
 from .linear_matroid import LinearMatroid, RegularMatroid, BinaryMatroid, TernaryMatroid, QuaternaryMatroid
-from .utilities import setprint, newlabel, get_nonisomorphic_matroids, lift_cross_ratios, lift_map
+from .utilities import setprint, newlabel, get_nonisomorphic_matroids
 from . import lean_matrix
 from .extension import LinearSubclasses, MatroidExtensions
 from .union_matroid import MatroidUnion, MatroidSum, PartitionMatroid
diff --git a/src/sage/matroids/linear_matroid.pxd b/src/sage/matroids/linear_matroid.pxd
index 3f0c8d8809..a1fe6b455e 100644
--- a/src/sage/matroids/linear_matroid.pxd
+++ b/src/sage/matroids/linear_matroid.pxd
@@ -17,7 +17,7 @@ cdef class LinearMatroid(BasisExchangeMatroid):
     cdef list _setup_internal_representation(self, matrix, reduced_matrix, ring, keep_initial_representation)
     cdef __exchange_value(self, long x, long y)
 
-    cpdef representation(self, B=*, reduced=*, labels=*, order=*, lift_map=*)
+    cpdef representation(self, B=*, reduced=*, labels=*, order=*)
     cpdef _current_rows_cols(self, B=*)
     cpdef representation_vectors(self)
     cpdef LeanMatrix _basic_representation(self, B=*)
diff --git a/src/sage/matroids/linear_matroid.pyx b/src/sage/matroids/linear_matroid.pyx
index 3fb15c4a6e..c4710db327 100644
--- a/src/sage/matroids/linear_matroid.pyx
+++ b/src/sage/matroids/linear_matroid.pyx
@@ -118,7 +118,7 @@ from sage.matroids.matroid cimport Matroid
 from sage.matroids.basis_exchange_matroid cimport BasisExchangeMatroid
 from .lean_matrix cimport LeanMatrix, GenericMatrix, BinaryMatrix, TernaryMatrix, QuaternaryMatrix, PlusMinusOneMatrix, generic_identity
 from .set_system cimport SetSystem
-from .utilities import newlabel, spanning_stars, spanning_forest, lift_cross_ratios
+from .utilities import newlabel, spanning_stars, spanning_forest
 from sage.graphs.spanning_tree import kruskal
 from sage.graphs.graph import Graph
 
@@ -465,7 +465,7 @@ cdef class LinearMatroid(BasisExchangeMatroid):
 
     # representations
 
-    cpdef representation(self, B=None, reduced=False, labels=None, order=None, lift_map=None):
+    cpdef representation(self, B=None, reduced=False, labels=None, order=None):
         r"""
         Return a matrix representing the matroid.
 
@@ -501,10 +501,6 @@ cdef class LinearMatroid(BasisExchangeMatroid):
         - ``order`` -- (default: ``None``) an ordering of the groundset
           elements. If provided, the columns (and, in case of a reduced
           representation, rows) will be presented in the given order.
-        - ``lift_map`` -- (default: ``None``) a dictionary containing the cross
-          ratios of the representing matrix in its domain. If provided, the
-          representation will be transformed by mapping its cross ratios according
-          to ``lift_map``.
 
         OUTPUT:
 
@@ -521,11 +517,6 @@ cdef class LinearMatroid(BasisExchangeMatroid):
         corresponds to an identity. If only ``order`` is not ``None``, the
         columns of this matrix will be permuted accordingly.
 
-        If a ``lift_map`` is provided, then the resulting matrix will be lifted
-        using the method
-        :func:`lift_cross_ratios() <sage.matroids.utilities.lift_cross_ratios>`
-        See the docstring of this method for further details.
-
         .. NOTE::
 
             A shortcut for ``M.representation()`` is ``Matrix(M)``.
@@ -593,16 +584,10 @@ cdef class LinearMatroid(BasisExchangeMatroid):
                 B = self.__subset(B)
                 A = self._basic_representation(B)
             A = A.matrix_from_rows_and_columns(range(A.nrows()), order_idx)
-            if lift_map is None:
-                if labels:
-                    return (A._matrix_(), order)
-                else:
-                    return A._matrix_()
+            if labels:
+                return (A._matrix_(), order)
             else:
-                if labels:
-                    return (lift_cross_ratios(A._matrix_(), lift_map), order)
-                else:
-                    return lift_cross_ratios(A._matrix_(), lift_map)
+                return A._matrix_()
         else:
             if B is None:
                 B = frozenset(self.basis())
@@ -623,16 +608,10 @@ cdef class LinearMatroid(BasisExchangeMatroid):
                     Ci.append(C.index(e))
                     Cl.append(e)
             A = A.matrix_from_rows_and_columns(Ri, Ci)
-            if lift_map is None:
-                if labels or labels is None:
-                    return (A._matrix_(), Rl, Cl)
-                else:
-                    return A._matrix_()
+            if labels or labels is None:
+                return (A._matrix_(), Rl, Cl)
             else:
-                if labels or labels is None:
-                    return (lift_cross_ratios(A._matrix_(), lift_map), Rl, Cl)
-                else:
-                    return lift_cross_ratios(A._matrix_(), lift_map)
+                return A._matrix_()
 
     cpdef _current_rows_cols(self, B=None):
         """

[sagetrac-Rudi]

comment:4

I am the original author of this code.

The output matrix Z is constructed so that a certain collection of entries is equal to 1. This collection is exactly the set of T chosen in line 567--569 of utilities.py.

    T = set()
    for C in G.connected_components():
        T.update(G.subgraph(C).min_spanning_tree())

From the failed doctest, it appears that in py3 the output has a 1 in position (3,4) instead of (3,2) in py2. So T is constructed differently under py3.
G is just the support graph of the input matrix, and does not depend on how it is constructed. So this tells me that Graph.min_spanning_tree() has changed its behaviour in py3. It the new behaviour of this routine is consistent between different calls, then the output of lift_cross_ratios will be consistent as well. So then it will suffice to adjust the output Z in the doctest.

Otherwise, it may be possible to force consistency Graph.min_spanning_tree() in py3, but I do not know how. Unfortunately I cannot test this either -- don't have Sage set up for working with py3.

Sorry I cannot do more. Hope this helps.

[jhpalmieri]

comment:5

Thanks very much for the comments. min_spanning_tree has indeed changed from Python 2 to Python 3, so we will just have different outputs for the doctests for the two versions.

[jhpalmieri]

Branch: u/jhpalmieri/matroid-utilities

[jhpalmieri]

Commit: ba75541

[jhpalmieri]

comment:7

Here is a branch which has different doctests for py2 and py3, and it also adds a doctest for the representation method which uses the lift_map optional argument. It also has different outputs depending on the version of Python.

I think it is likely that the difference is with min_spanning_tree. At least for the doctest for lift_cross_ratios, I checked the particular matrix involved, and py2 and py3 give different spanning trees for the graph produced from that matrix. I couldn't see a way to get the same spanning tree, hence different doctests depending on the version of Python.

---

New commits:

ba75541

trac 27787: fix py3 doctest for lift_cross_ratios in sage.matroids.utilities

[jhpalmieri]

Author: John Palmieri

[tscrim]

comment:8

From Rudi's comment:4, I agree that this is the correct fix.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from u/jhpalmieri/matroid-utilities to ba75541