from sage.all import *

def is_lyapunov_like(L,K):
    r"""
    Determine whether or not ``L`` is Lyapunov-like on ``K``.

    We say that ``L`` is Lyapunov-like on ``K`` if `\left\langle
    L\left\lparenx\right\rparen,s\right\rangle = 0` for all pairs
    `\left\langle x,s \right\rangle` in the complementarity set of
    ``K``. It is known [Orlitzky]_ that this property need only be
    checked for generators of ``K`` and its dual.

    INPUT:

    - ``L`` -- A linear transformation or matrix.

    - ``K`` -- A polyhedral closed convex cone.

    OUTPUT:

    ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
    and ``False`` otherwise.

    .. WARNING::

        If this function returns ``True``, then ``L`` is Lyapunov-like
        on ``K``. However, if ``False`` is returned, that could mean one
        of two things. The first is that ``L`` is definitely not
        Lyapunov-like on ``K``. The second is more of an "I don't know"
        answer, returned (for example) if we cannot prove that an inner
        product is zero.

    REFERENCES:

    M. Orlitzky. The Lyapunov rank of an improper cone.
    http://www.optimization-online.org/DB_HTML/2015/10/5135.html

    EXAMPLES:

    The identity is always Lyapunov-like in a nontrivial space::

        sage: set_random_seed()
        sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
        sage: L = identity_matrix(K.lattice_dim())
        sage: is_lyapunov_like(L,K)
        True

    As is the "zero" transformation::

        sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
        sage: R = K.lattice().vector_space().base_ring()
        sage: L = zero_matrix(R, K.lattice_dim())
        sage: is_lyapunov_like(L,K)
        True

        Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
        on ``K``::

        sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
        sage: all([ is_lyapunov_like(L,K) for L in K.lyapunov_like_basis() ])
        True

    """
    return all([(L*x).inner_product(s) == 0
                for (x,s) in K.discrete_complementarity_set()])


def motzkin_decomposition(K):
    r"""
    Return the pair of components in the Motzkin decomposition of this cone.

    Every convex cone is the direct sum of a strictly convex cone and a
    linear subspace [Stoer-Witzgall]_. Return a pair ``(P,S)`` of cones
    such that ``P`` is strictly convex, ``S`` is a subspace, and ``K``
    is the direct sum of ``P`` and ``S``.

    .. NOTE::

        The name "Motzkin decomposition" is not standard. The result
        is usually stated as the "decomposition theorem", or "cone
        decomposition theorem."

    OUTPUT:

    An ordered pair ``(P,S)`` of closed convex polyhedral cones where
    ``P`` is strictly convex, ``S`` is a subspace, and ``K`` is the
    direct sum of ``P`` and ``S``.

    REFERENCES:

    .. [Stoer-Witzgall] J. Stoer and C. Witzgall. Convexity and
       Optimization in Finite Dimensions I. Springer-Verlag, New
       York, 1970.

    EXAMPLES:

    The nonnegative orthant is strictly convex, so it is its own
    strictly convex component and its subspace component is trivial::

        sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
        sage: (P,S) = motzkin_decomposition(K)
        sage: K.is_equivalent(P)
        True
        sage: S.is_trivial()
        True

    Likewise, full spaces are their own subspace components::

        sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
        sage: K.is_full_space()
        True
        sage: (P,S) = motzkin_decomposition(K)
        sage: K.is_equivalent(S)
        True
        sage: P.is_trivial()
        True

    TESTS:

    A random point in the cone should belong to either the strictly
    convex component or the subspace component. If the point is nonzero,
    it cannot be in both::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8)
        sage: (P,S) = motzkin_decomposition(K)
        sage: x = K.random_element(ring=QQ)
        sage: P.contains(x) or S.contains(x)
        True
        sage: x.is_zero() or (P.contains(x) != S.contains(x))
        True

    The strictly convex component should always be strictly convex, and
    the subspace component should always be a subspace::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8)
        sage: (P,S) = motzkin_decomposition(K)
        sage: P.is_strictly_convex()
        True
        sage: S.lineality() == S.dim()
        True

    A strictly convex cone should be equal to its strictly convex component::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, strictly_convex=True)
        sage: (P,_) = motzkin_decomposition(K)
        sage: K.is_equivalent(P)
        True

    The generators of the components are obtained from orthogonal
    projections of the original generators [Stoer-Witzgall]_::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8)
        sage: (P,S) = motzkin_decomposition(K)
        sage: A = S.linear_subspace().complement().matrix()
        sage: proj_S_perp = A.transpose() * (A*A.transpose()).inverse() * A
        sage: expected_P = Cone([ proj_S_perp*g for g in K ], K.lattice())
        sage: P.is_equivalent(expected_P)
        True
        sage: A = S.linear_subspace().matrix()
        sage: proj_S = A.transpose() * (A*A.transpose()).inverse() * A
        sage: expected_S = Cone([ proj_S*g for g in K ], K.lattice())
        sage: S.is_equivalent(expected_S)
        True
    """
    # The lines() method only returns one generator per line. For a true
    # line, we also need a generator pointing in the opposite direction.
    S_gens = [ direction*gen for direction in [1,-1] for gen in K.lines() ]
    S = Cone(S_gens, K.lattice(), check=False)

    # Since ``S`` is a subspace, the rays of its dual generate its
    # orthogonal complement.
    S_perp = Cone(S.dual(), K.lattice(), check=False)
    P = K.intersection(S_perp)

    return (P,S)


def positive_operator_gens(K):
    r"""
    Compute generators of the cone of positive operators on this cone.

    OUTPUT:

    A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
    Each matrix ``P`` in the list should have the property that ``P*x``
    is an element of ``K`` whenever ``x`` is an element of
    ``K``. Moreover, any nonnegative linear combination of these
    matrices shares the same property.

    EXAMPLES:

    Positive operators on the nonnegative orthant are nonnegative matrices::

        sage: K = Cone([(1,)])
        sage: positive_operator_gens(K)
        [[1]]

        sage: K = Cone([(1,0),(0,1)])
        sage: positive_operator_gens(K)
        [
        [1 0]  [0 1]  [0 0]  [0 0]
        [0 0], [0 0], [1 0], [0 1]
        ]

    The trivial cone in a trivial space has no positive operators::

        sage: K = Cone([], ToricLattice(0))
        sage: positive_operator_gens(K)
        []

    Every operator is positive on the trivial cone::

        sage: K = Cone([(0,)])
        sage: positive_operator_gens(K)
        [[1], [-1]]

        sage: K = Cone([(0,0)])
        sage: K.is_trivial()
        True
        sage: positive_operator_gens(K)
        [
        [1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
        [0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
        ]

    Every operator is positive on the ambient vector space::

        sage: K = Cone([(1,),(-1,)])
        sage: K.is_full_space()
        True
        sage: positive_operator_gens(K)
        [[1], [-1]]

        sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
        sage: K.is_full_space()
        True
        sage: positive_operator_gens(K)
        [
        [1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
        [0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
        ]

    A non-obvious application is to find the positive operators on the
    right half-plane::

        sage: K = Cone([(1,0),(0,1),(0,-1)])
        sage: positive_operator_gens(K)
        [
        [1 0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
        [0 0], [1 0], [-1  0], [0 1], [ 0 -1]
        ]

    TESTS:

    Each positive operator generator should send the generators of the
    cone into the cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: all([ K.contains(P*x) for P in pi_of_K for x in K ])
        True

    Each positive operator generator should send a random element of the
    cone into the cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: all([ K.contains(P*K.random_element(QQ)) for P in pi_of_K ])
        True

    A random element of the positive operator cone should send the
    generators of the cone into the cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
        ....:                lattice=L,
        ....:                check=False)
        sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
        sage: all([ K.contains(P*x) for x in K ])
        True

    A random element of the positive operator cone should send a random
    element of the cone into the cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
        ....:                lattice=L,
        ....:                check=False)
        sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
        sage: K.contains(P*K.random_element(ring=QQ))
        True

    The lineality space of the dual of the cone of positive operators
    can be computed from the lineality spaces of the cone and its dual::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.dual().linear_subspace()
        sage: U1 = [ vector((s.tensor_product(x)).list())
        ....:        for x in K.lines()
        ....:        for s in K.dual() ]
        sage: U2 = [ vector((s.tensor_product(x)).list())
        ....:        for x in K
        ....:        for s in K.dual().lines() ]
        sage: expected = pi_cone.lattice().vector_space().span(U1 + U2)
        sage: actual == expected
        True

    The lineality of the dual of the cone of positive operators
    is known from its lineality space::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: n = K.lattice_dim()
        sage: m = K.dim()
        sage: l = K.lineality()
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(n**2)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                 lattice=L,
        ....:                 check=False)
        sage: actual = pi_cone.dual().lineality()
        sage: expected = l*(m - l) + m*(n - m)
        sage: actual == expected
        True

    The dimension of the cone of positive operators is given by the
    corollary in my paper::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: n = K.lattice_dim()
        sage: m = K.dim()
        sage: l = K.lineality()
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(n**2)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.dim()
        sage: expected = n**2 - l*(m - l) - (n - m)*m
        sage: actual == expected
        True

    The trivial cone, full space, and half-plane all give rise to the
    expected dimensions::

        sage: n = ZZ.random_element().abs()
        sage: K = Cone([[0] * n], ToricLattice(n))
        sage: K.is_trivial()
        True
        sage: L = ToricLattice(n^2)
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.dim()
        sage: actual == n^2
        True
        sage: K = K.dual()
        sage: K.is_full_space()
        True
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.dim()
        sage: actual == n^2
        True
        sage: K = Cone([(1,0),(0,1),(0,-1)])
        sage: pi_of_K = positive_operator_gens(K)
        sage: actual = Cone([p.list() for p in pi_of_K], check=False).dim()
        sage: actual == 3
        True

    The lineality of the cone of positive operators follows from the
    description of its generators::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: n = K.lattice_dim()
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(n**2)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.lineality()
        sage: expected = n**2 - K.dim()*K.dual().dim()
        sage: actual == expected
        True

    The trivial cone, full space, and half-plane all give rise to the
    expected linealities::

        sage: n = ZZ.random_element().abs()
        sage: K = Cone([[0] * n], ToricLattice(n))
        sage: K.is_trivial()
        True
        sage: L = ToricLattice(n^2)
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = pi_cone.lineality()
        sage: actual == n^2
        True
        sage: K = K.dual()
        sage: K.is_full_space()
        True
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
        sage: pi_cone.lineality() == n^2
        True
        sage: K = Cone([(1,0),(0,1),(0,-1)])
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_cone = Cone([p.list() for p in pi_of_K], check=False)
        sage: actual = pi_cone.lineality()
        sage: actual == 2
        True

    A cone is proper if and only if its cone of positive operators
    is proper::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: K.is_proper() == pi_cone.is_proper()
        True

    The positive operators of a permuted cone can be obtained by
    conjugation::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
        sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
        sage: pi_of_pK = positive_operator_gens(pK)
        sage: actual = Cone([t.list() for t in pi_of_pK],
        ....:                lattice=L,
        ....:                check=False)
        sage: pi_of_K = positive_operator_gens(K)
        sage: expected = Cone([(p*t*p.inverse()).list() for t in pi_of_K],
        ....:                   lattice=L,
        ....:                   check=False)
        sage: actual.is_equivalent(expected)
        True

    A transformation is positive on a cone if and only if its adjoint is
    positive on the dual of that cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: F = K.lattice().vector_space().base_field()
        sage: n = K.lattice_dim()
        sage: L = ToricLattice(n**2)
        sage: W = VectorSpace(F, n**2)
        sage: pi_of_K = positive_operator_gens(K)
        sage: pi_of_K_star = positive_operator_gens(K.dual())
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: pi_star = Cone([p.list() for p in pi_of_K_star],
        ....:                lattice=L,
        ....:                check=False)
        sage: M = MatrixSpace(F, n)
        sage: L = M(pi_cone.random_element(ring=QQ).list())
        sage: pi_star.contains(W(L.transpose().list()))
        True

        sage: L = W.random_element()
        sage: L_star = W(M(L.list()).transpose().list())
        sage: pi_cone.contains(L) ==  pi_star.contains(L_star)
        True
    """
    # Matrices are not vectors in Sage, so we have to convert them
    # to vectors explicitly before we can find a basis. We need these
    # two values to construct the appropriate "long vector" space.
    F = K.lattice().base_field()
    n = K.lattice_dim()

    tensor_products = [ s.tensor_product(x) for x in K for s in K.dual() ]

    # Convert those tensor products to long vectors.
    W = VectorSpace(F, n**2)
    vectors = [ W(tp.list()) for tp in tensor_products ]

    check = True
    if K.is_solid() or K.is_strictly_convex():
        # The lineality space of either ``K`` or ``K.dual()`` is
        # trivial and it's easy to show that our generating set is
        # minimal. I would love a proof that this works when ``K`` is
        # neither pointed nor solid.
        #
        # Note that in that case we can get *duplicates*, since the
        # tensor product of (x,s) is the same as that of (-x,-s).
        check = False

    # Create the dual cone of the positive operators, expressed as
    # long vectors.
    pi_dual = Cone(vectors, ToricLattice(W.dimension()), check=check)

    # Now compute the desired cone from its dual...
    pi_cone = pi_dual.dual()

    # And finally convert its rays back to matrix representations.
    M = MatrixSpace(F, n)
    return [ M(v.list()) for v in pi_cone ]


def Z_transformation_gens(K):
    r"""
    Compute generators of the cone of Z-transformations on this cone.

    OUTPUT:

    A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
    Each matrix ``L`` in the list should have the property that
    ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element the
    discrete complementarity set of ``K``. Moreover, any nonnegative
    linear combination of these matrices shares the same property.

    EXAMPLES:

    Z-transformations on the nonnegative orthant are just Z-matrices.
    That is, matrices whose off-diagonal elements are nonnegative::

        sage: K = Cone([(1,0),(0,1)])
        sage: Z_transformation_gens(K)
        [
        [ 0 -1]  [ 0  0]  [-1  0]  [1 0]  [ 0  0]  [0 0]
        [ 0  0], [-1  0], [ 0  0], [0 0], [ 0 -1], [0 1]
        ]
        sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
        sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
        ....:                    for i in range(z.nrows())
        ....:                    for j in range(z.ncols())
        ....:                    if i != j ])
        True

    The trivial cone in a trivial space has no Z-transformations::

        sage: K = Cone([], ToricLattice(0))
        sage: Z_transformation_gens(K)
        []

    Every operator is a Z-transformation on the ambient vector space::

        sage: K = Cone([(1,),(-1,)])
        sage: K.is_full_space()
        True
        sage: Z_transformation_gens(K)
        [[-1], [1]]

        sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
        sage: K.is_full_space()
        True
        sage: Z_transformation_gens(K)
        [
        [-1  0]  [1 0]  [ 0 -1]  [0 1]  [ 0  0]  [0 0]  [ 0  0]  [0 0]
        [ 0  0], [0 0], [ 0  0], [0 0], [-1  0], [1 0], [ 0 -1], [0 1]
        ]

    A non-obvious application is to find the Z-transformations on the
    right half-plane::

        sage: K = Cone([(1,0),(0,1),(0,-1)])
        sage: Z_transformation_gens(K)
        [
        [-1  0]  [1 0]  [ 0  0]  [0 0]  [ 0  0]  [0 0]
        [ 0  0], [0 0], [-1  0], [1 0], [ 0 -1], [0 1]
        ]

    Z-transformations on a subspace are Lyapunov-like and vice-versa::

        sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
        sage: K.is_full_space()
        True
        sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
        sage: zs  = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
        sage: zs == lls
        True

    TESTS:

    The Z-property is possessed by every Z-transformation::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: dcs = K.discrete_complementarity_set()
        sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
        ....:                                  for (x,s) in dcs])
        True

    The lineality space of the cone of Z-transformations is the space of
    Lyapunov-like transformations::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: Z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ],
        ....:               lattice=L,
        ....:               check=False)
        sage: ll_basis = [ vector(l.list()) for l in K.lyapunov_like_basis() ]
        sage: lls = L.vector_space().span(ll_basis)
        sage: Z_cone.linear_subspace() == lls
        True

    The lineality of the Z-transformations on a cone is the Lyapunov
    rank of that cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: Z_cone  = Cone([ z.list() for z in Z_of_K ],
        ....:                lattice=L,
        ....:                check=False)
        sage: Z_cone.lineality() == K.lyapunov_rank()
        True

    The lineality spaces of the duals of the positive operator and
    Z-transformation cones are equal. From this it follows that the
    dimensions of the Z-transformation cone and positive operator cone
    are equal::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: pi_of_K = positive_operator_gens(K)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: pi_cone = Cone([p.list() for p in pi_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: Z_cone = Cone([ z.list() for z in Z_of_K],
        ....:               lattice=L,
        ....:               check=False)
        sage: pi_cone.dim() == Z_cone.dim()
        True
        sage: pi_star = pi_cone.dual()
        sage: z_star = Z_cone.dual()
        sage: pi_star.linear_subspace() == z_star.linear_subspace()
        True

    The trivial cone, full space, and half-plane all give rise to the
    expected dimensions::

        sage: n = ZZ.random_element().abs()
        sage: K = Cone([[0] * n], ToricLattice(n))
        sage: K.is_trivial()
        True
        sage: L = ToricLattice(n^2)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: Z_cone = Cone([z.list() for z in Z_of_K],
        ....:               lattice=L,
        ....:               check=False)
        sage: actual = Z_cone.dim()
        sage: actual == n^2
        True
        sage: K = K.dual()
        sage: K.is_full_space()
        True
        sage: Z_of_K = Z_transformation_gens(K)
        sage: Z_cone = Cone([z.list() for z in Z_of_K],
        ....:                lattice=L,
        ....:                check=False)
        sage: actual = Z_cone.dim()
        sage: actual == n^2
        True
        sage: K = Cone([(1,0),(0,1),(0,-1)])
        sage: Z_of_K = Z_transformation_gens(K)
        sage: Z_cone = Cone([z.list() for z in Z_of_K], check=False)
        sage: Z_cone.dim() == 3
        True

    The Z-transformations of a permuted cone can be obtained by
    conjugation::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: L = ToricLattice(K.lattice_dim()**2)
        sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
        sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
        sage: Z_of_pK = Z_transformation_gens(pK)
        sage: actual = Cone([t.list() for t in Z_of_pK],
        ....:                lattice=L,
        ....:                check=False)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: expected = Cone([(p*t*p.inverse()).list() for t in Z_of_K],
        ....:                   lattice=L,
        ....:                   check=False)
        sage: actual.is_equivalent(expected)
        True

    A transformation is a Z-transformation on a cone if and only if its
    adjoint is a Z-transformation on the dual of that cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=4)
        sage: F = K.lattice().vector_space().base_field()
        sage: n = K.lattice_dim()
        sage: L = ToricLattice(n**2)
        sage: W = VectorSpace(F, n**2)
        sage: Z_of_K = Z_transformation_gens(K)
        sage: Z_of_K_star = Z_transformation_gens(K.dual())
        sage: Z_cone = Cone([p.list() for p in Z_of_K],
        ....:               lattice=L,
        ....:               check=False)
        sage: Z_star = Cone([p.list() for p in Z_of_K_star],
        ....:               lattice=L,
        ....:               check=False)
        sage: M = MatrixSpace(F, n)
        sage: L = M(Z_cone.random_element(ring=QQ).list())
        sage: Z_star.contains(W(L.transpose().list()))
        True

        sage: L = W.random_element()
        sage: L_star = W(M(L.list()).transpose().list())
        sage: Z_cone.contains(L) ==  Z_star.contains(L_star)
        True
    """
    # Matrices are not vectors in Sage, so we have to convert them
    # to vectors explicitly before we can find a basis. We need these
    # two values to construct the appropriate "long vector" space.
    F = K.lattice().base_field()
    n = K.lattice_dim()

    # These tensor products contain generators for the dual cone of
    # the cross-positive transformations.
    tensor_products = [ s.tensor_product(x)
                        for (x,s) in K.discrete_complementarity_set() ]

    # Turn our matrices into long vectors...
    W = VectorSpace(F, n**2)
    vectors = [ W(m.list()) for m in tensor_products ]

    check = True
    if K.is_solid() or K.is_strictly_convex():
        # The lineality space of either ``K`` or ``K.dual()`` is
        # trivial and it's easy to show that our generating set is
        # minimal. I would love a proof that this works when ``K`` is
        # neither pointed nor solid.
        #
        # Note that in that case we can get *duplicates*, since the
        # tensor product of (x,s) is the same as that of (-x,-s).
        check = False

    # Create the dual cone of the cross-positive operators,
    # expressed as long vectors.
    Sigma_dual = Cone(vectors, lattice=ToricLattice(W.dimension()), check=check)

    # Now compute the desired cone from its dual...
    Sigma_cone = Sigma_dual.dual()

    # And finally convert its rays back to matrix representations.
    # But first, make them negative, so we get Z-transformations and
    # not cross-positive ones.
    M = MatrixSpace(F, n)
    return [ -M(v.list()) for v in Sigma_cone ]


def Z_cone(K):
    gens = Z_transformation_gens(K)
    L = ToricLattice(K.lattice_dim()**2)
    return Cone([ g.list() for g in gens ], lattice=L, check=False)

def pi_cone(K):
    gens = positive_operator_gens(K)
    L = ToricLattice(K.lattice_dim()**2)
    return Cone([ g.list() for g in gens ], lattice=L, check=False)