Implement the lift theorem for linear matroids

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

The `lift theorem' gives conditions under which a matroid representation over a partial field can be transformed to a representation over another partial field, using a lift function to map the cross ratios.

Regardless whether these conditions are met, there is a polynomial-time procedure to construct a candidate representation over the target partial field, given a lift function. If the conditions of the theorem are met, then this candidate representation is the right one.

Write a method for LinearMatroid, which given a lift function, generates such a candidate representation.

CC: @sagetrac-Stefan @sagetrac-yomcat

Component: matroid theory

Author: Rudi Pendavingh

Branch/Commit: 7f020ea

Reviewer: Michael Welsh

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

[35e1b81c-f27a-4274-bfe3-67d727b6c772]

comment:38

All good.

[35e1b81c-f27a-4274-bfe3-67d727b6c772]

Reviewer: Michael Welsh

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:40

Sorry Michael, but I just stumbled across the fact that there will be instances that this code cannot handle, due to the fact that min_spanning_tree() does not work on disconnected graphs. I had assumed it would just return a spanning forest.

So I need to repair that. It will not take long. I will ask for another review in a minute.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

f85417e

Made lift_cross-ratios suitable for disconnected matroids

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d46d8e3 to f85417e

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:42

That's the minimal modification that will solve this issue. I will perhaps think about a more efficient one later.

Again, sorry for the turbulence. I was just working on a method for testing if a matroid is ternary and ran into exactly this issue.

Needs review!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5390330

Replaced a non-ascii character

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f85417e to 5390330

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:44

The patchbot was unhappy about a non-ascii character. Think I got it.

[35e1b81c-f27a-4274-bfe3-67d727b6c772]

comment:45

Something isn't quite right:

sage: start_matrix = matrix(GF(19), [[18, 18, 18, 18, 18, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 5], [1, 0, 0, 0, 0, 0, 18, 18, 18, 18, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 14], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 18, 18, 18, 18, 0, 0, 0, 0, 0, 0, 5, 4, 18], [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 18, 18, 18, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 18, 18, 0, 14, 18, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 18, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1]])
sage: start_matrix
[18 18 18 18 18 18  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 18  0  5]
[ 1  0  0  0  0  0 18 18 18 18 18  0  0  0  0  0  0  0  0  0  0  0 15 14]
[ 0  1  0  0  0  0  1  0  0  0  0 18 18 18 18  0  0  0  0  0  0  5  4 18]
[ 0  0  1  0  0  0  0  1  0  0  0  1  0  0  0 18 18 18  0  0  0  0  0  0]
[ 0  0  0  1  0  0  0  0  1  0  0  0  1  0  0  1  0  0 18 18  0 14 18  0]
[ 0  0  0  0  1  0  0  0  0  1  0  0  0  1  0  0  1  0  1  0 18  0  0  0]
[ 0  0  0  0  0  1  0  0  0  0  1  0  0  0  1  0  0  1  0  1  1  1  1  1]
sage: GM = lift_map('gm')
sage: Z = lift_cross_ratios(start_matrix, GM)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-11-d7b7e5f1514f> in <module>()
----> 1 Z = lift_cross_ratios(start_matrix, GM)

/Applications/sage-devel/local/lib/python2.7/site-packages/sage/matroids/utilities.pyc in lift_cross_ratios(A, lift_map)
    494 
    495         if cr != plus_one1 and not cr in lift_map:
--> 496             raise ValueError("Input matrix has a cross ratio "+str(cr)+", which is not in the lift_map")
    497         # - write the entry as a product of cross ratios of A
    498         div = True

ValueError: Input matrix has a cross ratio 15, which is not in the lift_map
sage: M = LinearMatroid(start_matrix)
sage: M.cross
M.cross_ratio   M.cross_ratios  
sage: M.cross_ratios()
{4, 5, 6, 14, 15, 16}

To clarify, that's a random GM matrix that I had lying around, represented over GF(19) as per everything I did in my thesis.

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:46

Replying to @sagetrac-yomcat:

Something isn't quite right:

--> 496 raise ValueError("Input matrix has a cross ratio "+str(cr)+", which is not in the lift_map")

 sage: M.cross_ratios()
 {4, 5, 6, 14, 15, 16}

Yes, it has 15 as a cross ratio. But 15 is in the lift map! I'll figure it out.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d293bc3	15 now in the golden mean lift map
d5ef7c7	OK so I'm paranoid now

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5390330 to d5ef7c7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

7f020ea

And now 15 actually maps to the right element too

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d5ef7c7 to 7f020ea

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:49

OK, thanks a lot for finding that bug.

Turns out there was something wrong with the gm definition in lift_map. It should have mapped GF(19)(15), but didn't!

Now repaired. Have a look.

[35e1b81c-f27a-4274-bfe3-67d727b6c772]

comment:50

Now it's working as far as I can tell.

Is there anything else planned on partial fields and stuff? I should be turning my thesis into paper(s) soonish, and I'd hate to have to rewrite all my code because you made a new function.

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:51

Replying to @sagetrac-yomcat:

Now it's working as far as I can tell.

Is there anything else planned on partial fields and stuff? I should be turning my thesis into paper(s) soonish, and I'd hate to have to rewrite all my code because you made a new function.

Well, here's a few things I might do:

• add a few maps to lift_map;
• make lift_cross_ratios design it's own lift map / target ring based on the cross ratios of the given matrix;
• speed up lift_cross_ratios, _local_binary_matroid, _local_ternary_matroid;
• kill #15296 But they are not on the top of my list, so can't say when. The first one is quite easy, so I might work on that between harder tasks.

I doubt if that will make any of your code outdated. Making real gm-matrices from your gf19-matrices (and latex-ing them) just became easier, so that can never hurt.

What kind of functionality were you thinking of?

[35e1b81c-f27a-4274-bfe3-67d727b6c772]

comment:52

Replying to @sagetrac-Rudi:

I doubt if that will make any of your code outdated. Making real gm-matrices from your gf19-matrices (and latex-ing them) just became easier, so that can never hurt.

I had some pretty gnarly grep routines to do that for me, so losing them is a plus.

What kind of functionality were you thinking of?

A way to test if a given GF(4)/5 matrix is GM or not. But that's a pipe dream, and working in GF(19) wasn't too bad when I stopped doing complete enumeration of matrices.

I'm about to start working on it, and if anything seems like it could be useful in general I'll make some tickets.

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:53

Replying to @sagetrac-yomcat:

What kind of functionality were you thinking of?

A way to test if a given GF(4)/5 matrix is GM or not.

After is_ternary, I intend to work on is_quarternary. That function will tell you if a GF(5)-matrix is GM. For GF(5) / other fields I have no plans right now. They are much harder, GF(4) is the last nice one.

[vbraun]

Changed branch from u/Rudi/implement_the_lift_theorem_for_linear_matroids to 7f020ea