Add code to lift SL2(Z/NZ) to SL2(Z) (and for m not equal 2)

[ncalexan]

This is very handy in the theory of abelian varieties... here's some code to do it. Maybe someday I'll write the patch.

def lift(A, N):
    r"""
    Lift a matrix A from SL_m(Z/NZ) to SL_m(Z).

    Follows Shimura, Lemma 1.38, p21.

    sage: N = 11
    sage: A = matrix(ZZ, 4, 4, [6, 0, 0, 9, 1, 6, 9, 4, 4, 4, 8, 0, 4, 0, 0, 8])
    sage: A.det()
    144
    sage: A.change_ring(Zmod(N)).det()
    1
    sage: L = lift(A, N)
    sage: L.det()
    1
    sage: (L - A) * Mod(1, N) == 0
    True

    sage: N = 19
    sage: B = matrix(ZZ, 4, 4, [1, 6, 10, 4, 4, 14, 15, 4, 13, 0, 1, 15, 15, 15, 17, 10])
    sage: B.det()
    4447
    sage: B.change_ring(Zmod(N)).det()
    1
    sage: L = lift(B, N)
    sage: L.det()
    1
    sage: (L - B) * Mod(1, N) == 0
    True
    """
    assert A.is_square()
    assert det(A) != 0
    m = A.nrows()
    if m == 1:
        return identity_matrix(1)

    D, U, V = A.smith_form()
    assert det(U) == 1
    assert det(V) == 1
#     print
#     print "D"
#     print D

    a = [ D[i, i] for i in range(m) ]
    b = prod(a[1:])
    W = identity_matrix(m)
    W[0, 0] = b
    W[1, 0] = b-1
    W[0, 1] = 1
#     print
#     print "W"
#     print W

    X = identity_matrix(m)
    X[0, 1] = -a[1]
#     print
#     print "X"
#     print X

    Ap = D.copy()
    Ap[0, 0] = 1
    Ap[1, 0] = 1-a[0]
    Ap[1, 1] *= a[0]
#     print
#     print "Ap"
#     print Ap

    assert (W*U*A*V*X).change_ring(Zmod(N)) == Ap.change_ring(Zmod(N))
    Cp = diagonal_matrix(a[1:])
    Cp[0, 0] *= a[0]
    C = lift(Cp, N)
#     print "C"
#     print C

    Cpp = block_diagonal_matrix(identity_matrix(1), C)
    Cpp[1, 0] = 1-a[0]
#     print "Cpp"
#     print Cpp

#     print
    return (~U * ~W * Cpp * ~X * ~V).change_ring(ZZ)