mjo/cone/cone.py

   1 from sage.all import *
   2
   3 def is_lyapunov_like(L,K):
   4     r"""
   5     Determine whether or not ``L`` is Lyapunov-like on ``K``.
   6
   7     We say that ``L`` is Lyapunov-like on ``K`` if `\left\langle
   8     L\left\lparenx\right\rparen,s\right\rangle = 0` for all pairs
   9     `\left\langle x,s \right\rangle` in the complementarity set of
  10     ``K``. It is known [Orlitzky]_ that this property need only be
  11     checked for generators of ``K`` and its dual.
  12
  13     INPUT:
  14
  15     - ``L`` -- A linear transformation or matrix.
  16
  17     - ``K`` -- A polyhedral closed convex cone.
  18
  19     OUTPUT:
  20
  21     ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
  22     and ``False`` otherwise.
  23
  24     .. WARNING::
  25
  26         If this function returns ``True``, then ``L`` is Lyapunov-like
  27         on ``K``. However, if ``False`` is returned, that could mean one
  28         of two things. The first is that ``L`` is definitely not
  29         Lyapunov-like on ``K``. The second is more of an "I don't know"
  30         answer, returned (for example) if we cannot prove that an inner
  31         product is zero.
  32
  33     REFERENCES:
  34
  35     M. Orlitzky. The Lyapunov rank of an improper cone.
  36     http://www.optimization-online.org/DB_HTML/2015/10/5135.html
  37
  38     EXAMPLES:
  39
  40     The identity is always Lyapunov-like in a nontrivial space::
  41
  42         sage: set_random_seed()
  43         sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
  44         sage: L = identity_matrix(K.lattice_dim())
  45         sage: is_lyapunov_like(L,K)
  46         True
  47
  48     As is the "zero" transformation::
  49
  50         sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=8)
  51         sage: R = K.lattice().vector_space().base_ring()
  52         sage: L = zero_matrix(R, K.lattice_dim())
  53         sage: is_lyapunov_like(L,K)
  54         True
  55
  56         Everything in ``K.lyapunov_like_basis()`` should be Lyapunov-like
  57         on ``K``::
  58
  59         sage: K = random_cone(min_ambient_dim=1, max_ambient_dim=6)
  60         sage: all([ is_lyapunov_like(L,K) for L in K.lyapunov_like_basis() ])
  61         True
  62
  63     """
  64     return all([(L*x).inner_product(s) == 0
  65                 for (x,s) in K.discrete_complementarity_set()])
  66
  67
  68 def positive_operator_gens(K):
  69     r"""
  70     Compute generators of the cone of positive operators on this cone.
  71
  72     OUTPUT:
  73
  74     A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
  75     Each matrix ``P`` in the list should have the property that ``P*x``
  76     is an element of ``K`` whenever ``x`` is an element of
  77     ``K``. Moreover, any nonnegative linear combination of these
  78     matrices shares the same property.
  79
  80     EXAMPLES:
  81
  82     Positive operators on the nonnegative orthant are nonnegative matrices::
  83
  84         sage: K = Cone([(1,)])
  85         sage: positive_operator_gens(K)
  86         [[1]]
  87
  88         sage: K = Cone([(1,0),(0,1)])
  89         sage: positive_operator_gens(K)
  90         [
  91         [1 0]  [0 1]  [0 0]  [0 0]
  92         [0 0], [0 0], [1 0], [0 1]
  93         ]
  94
  95     The trivial cone in a trivial space has no positive operators::
  96
  97         sage: K = Cone([], ToricLattice(0))
  98         sage: positive_operator_gens(K)
  99         []
 100
 101     Every operator is positive on the trivial cone::
 102
 103         sage: K = Cone([(0,)])
 104         sage: positive_operator_gens(K)
 105         [[1], [-1]]
 106
 107         sage: K = Cone([(0,0)])
 108         sage: K.is_trivial()
 109         True
 110         sage: positive_operator_gens(K)
 111         [
 112         [1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
 113         [0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
 114         ]
 115
 116     Every operator is positive on the ambient vector space::
 117
 118         sage: K = Cone([(1,),(-1,)])
 119         sage: K.is_full_space()
 120         True
 121         sage: positive_operator_gens(K)
 122         [[1], [-1]]
 123
 124         sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
 125         sage: K.is_full_space()
 126         True
 127         sage: positive_operator_gens(K)
 128         [
 129         [1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
 130         [0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
 131         ]
 132
 133     A non-obvious application is to find the positive operators on the
 134     right half-plane::
 135
 136         sage: K = Cone([(1,0),(0,1),(0,-1)])
 137         sage: positive_operator_gens(K)
 138         [
 139         [1 0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
 140         [0 0], [1 0], [-1  0], [0 1], [ 0 -1]
 141         ]
 142
 143     TESTS:
 144
 145     Each positive operator generator should send the generators of the
 146     cone into the cone::
 147
 148         sage: set_random_seed()
 149         sage: K = random_cone(max_ambient_dim=4)
 150         sage: pi_of_K = positive_operator_gens(K)
 151         sage: all([ K.contains(P*x) for P in pi_of_K for x in K ])
 152         True
 153
 154     Each positive operator generator should send a random element of the
 155     cone into the cone::
 156
 157         sage: set_random_seed()
 158         sage: K = random_cone(max_ambient_dim=4)
 159         sage: pi_of_K = positive_operator_gens(K)
 160         sage: all([ K.contains(P*K.random_element(QQ)) for P in pi_of_K ])
 161         True
 162
 163     A random element of the positive operator cone should send the
 164     generators of the cone into the cone::
 165
 166         sage: set_random_seed()
 167         sage: K = random_cone(max_ambient_dim=4)
 168         sage: pi_of_K = positive_operator_gens(K)
 169         sage: L = ToricLattice(K.lattice_dim()**2)
 170         sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
 171         ....:                lattice=L,
 172         ....:                check=False)
 173         sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
 174         sage: all([ K.contains(P*x) for x in K ])
 175         True
 176
 177     A random element of the positive operator cone should send a random
 178     element of the cone into the cone::
 179
 180         sage: set_random_seed()
 181         sage: K = random_cone(max_ambient_dim=4)
 182         sage: pi_of_K = positive_operator_gens(K)
 183         sage: L = ToricLattice(K.lattice_dim()**2)
 184         sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
 185         ....:                lattice=L,
 186         ....:                check=False)
 187         sage: P = matrix(K.lattice_dim(), pi_cone.random_element(QQ).list())
 188         sage: K.contains(P*K.random_element(ring=QQ))
 189         True
 190
 191     The lineality space of the dual of the cone of positive operators
 192     can be computed from the lineality spaces of the cone and its dual::
 193
 194         sage: set_random_seed()
 195         sage: K = random_cone(max_ambient_dim=4)
 196         sage: pi_of_K = positive_operator_gens(K)
 197         sage: L = ToricLattice(K.lattice_dim()**2)
 198         sage: pi_cone = Cone([ g.list() for g in pi_of_K ],
 199         ....:                lattice=L,
 200         ....:                check=False)
 201         sage: actual = pi_cone.dual().linear_subspace()
 202         sage: U1 = [ vector((s.tensor_product(x)).list())
 203         ....:        for x in K.lines()
 204         ....:        for s in K.dual() ]
 205         sage: U2 = [ vector((s.tensor_product(x)).list())
 206         ....:        for x in K
 207         ....:        for s in K.dual().lines() ]
 208         sage: expected = pi_cone.lattice().vector_space().span(U1 + U2)
 209         sage: actual == expected
 210         True
 211
 212     The lineality of the dual of the cone of positive operators
 213     is known from its lineality space::
 214
 215         sage: set_random_seed()
 216         sage: K = random_cone(max_ambient_dim=4)
 217         sage: n = K.lattice_dim()
 218         sage: m = K.dim()
 219         sage: l = K.lineality()
 220         sage: pi_of_K = positive_operator_gens(K)
 221         sage: L = ToricLattice(n**2)
 222         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 223         ....:                 lattice=L,
 224         ....:                 check=False)
 225         sage: actual = pi_cone.dual().lineality()
 226         sage: expected = l*(m - l) + m*(n - m)
 227         sage: actual == expected
 228         True
 229
 230     The dimension of the cone of positive operators is given by the
 231     corollary in my paper::
 232
 233         sage: set_random_seed()
 234         sage: K = random_cone(max_ambient_dim=4)
 235         sage: n = K.lattice_dim()
 236         sage: m = K.dim()
 237         sage: l = K.lineality()
 238         sage: pi_of_K = positive_operator_gens(K)
 239         sage: L = ToricLattice(n**2)
 240         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 241         ....:                lattice=L,
 242         ....:                check=False)
 243         sage: actual = pi_cone.dim()
 244         sage: expected = n**2 - l*(m - l) - (n - m)*m
 245         sage: actual == expected
 246         True
 247
 248     The trivial cone, full space, and half-plane all give rise to the
 249     expected dimensions::
 250
 251         sage: n = ZZ.random_element().abs()
 252         sage: K = Cone([[0] * n], ToricLattice(n))
 253         sage: K.is_trivial()
 254         True
 255         sage: L = ToricLattice(n^2)
 256         sage: pi_of_K = positive_operator_gens(K)
 257         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 258         ....:                lattice=L,
 259         ....:                check=False)
 260         sage: actual = pi_cone.dim()
 261         sage: actual == n^2
 262         True
 263         sage: K = K.dual()
 264         sage: K.is_full_space()
 265         True
 266         sage: pi_of_K = positive_operator_gens(K)
 267         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 268         ....:                lattice=L,
 269         ....:                check=False)
 270         sage: actual = pi_cone.dim()
 271         sage: actual == n^2
 272         True
 273         sage: K = Cone([(1,0),(0,1),(0,-1)])
 274         sage: pi_of_K = positive_operator_gens(K)
 275         sage: actual = Cone([p.list() for p in pi_of_K], check=False).dim()
 276         sage: actual == 3
 277         True
 278
 279     The lineality of the cone of positive operators follows from the
 280     description of its generators::
 281
 282         sage: set_random_seed()
 283         sage: K = random_cone(max_ambient_dim=4)
 284         sage: n = K.lattice_dim()
 285         sage: pi_of_K = positive_operator_gens(K)
 286         sage: L = ToricLattice(n**2)
 287         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 288         ....:                lattice=L,
 289         ....:                check=False)
 290         sage: actual = pi_cone.lineality()
 291         sage: expected = n**2 - K.dim()*K.dual().dim()
 292         sage: actual == expected
 293         True
 294
 295     The trivial cone, full space, and half-plane all give rise to the
 296     expected linealities::
 297
 298         sage: n = ZZ.random_element().abs()
 299         sage: K = Cone([[0] * n], ToricLattice(n))
 300         sage: K.is_trivial()
 301         True
 302         sage: L = ToricLattice(n^2)
 303         sage: pi_of_K = positive_operator_gens(K)
 304         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 305         ....:                lattice=L,
 306         ....:                check=False)
 307         sage: actual = pi_cone.lineality()
 308         sage: actual == n^2
 309         True
 310         sage: K = K.dual()
 311         sage: K.is_full_space()
 312         True
 313         sage: pi_of_K = positive_operator_gens(K)
 314         sage: pi_cone = Cone([p.list() for p in pi_of_K], lattice=L)
 315         sage: pi_cone.lineality() == n^2
 316         True
 317         sage: K = Cone([(1,0),(0,1),(0,-1)])
 318         sage: pi_of_K = positive_operator_gens(K)
 319         sage: pi_cone = Cone([p.list() for p in pi_of_K], check=False)
 320         sage: actual = pi_cone.lineality()
 321         sage: actual == 2
 322         True
 323
 324     A cone is proper if and only if its cone of positive operators
 325     is proper::
 326
 327         sage: set_random_seed()
 328         sage: K = random_cone(max_ambient_dim=4)
 329         sage: pi_of_K = positive_operator_gens(K)
 330         sage: L = ToricLattice(K.lattice_dim()**2)
 331         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 332         ....:                lattice=L,
 333         ....:                check=False)
 334         sage: K.is_proper() == pi_cone.is_proper()
 335         True
 336
 337     The positive operators of a permuted cone can be obtained by
 338     conjugation::
 339
 340         sage: set_random_seed()
 341         sage: K = random_cone(max_ambient_dim=4)
 342         sage: L = ToricLattice(K.lattice_dim()**2)
 343         sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
 344         sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
 345         sage: pi_of_pK = positive_operator_gens(pK)
 346         sage: actual = Cone([t.list() for t in pi_of_pK],
 347         ....:                lattice=L,
 348         ....:                check=False)
 349         sage: pi_of_K = positive_operator_gens(K)
 350         sage: expected = Cone([(p*t*p.inverse()).list() for t in pi_of_K],
 351         ....:                   lattice=L,
 352         ....:                   check=False)
 353         sage: actual.is_equivalent(expected)
 354         True
 355
 356     A transformation is positive on a cone if and only if its adjoint is
 357     positive on the dual of that cone::
 358
 359         sage: set_random_seed()
 360         sage: K = random_cone(max_ambient_dim=4)
 361         sage: F = K.lattice().vector_space().base_field()
 362         sage: n = K.lattice_dim()
 363         sage: L = ToricLattice(n**2)
 364         sage: W = VectorSpace(F, n**2)
 365         sage: pi_of_K = positive_operator_gens(K)
 366         sage: pi_of_K_star = positive_operator_gens(K.dual())
 367         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 368         ....:                lattice=L,
 369         ....:                check=False)
 370         sage: pi_star = Cone([p.list() for p in pi_of_K_star],
 371         ....:                lattice=L,
 372         ....:                check=False)
 373         sage: M = MatrixSpace(F, n)
 374         sage: L = M(pi_cone.random_element(ring=QQ).list())
 375         sage: pi_star.contains(W(L.transpose().list()))
 376         True
 377
 378         sage: L = W.random_element()
 379         sage: L_star = W(M(L.list()).transpose().list())
 380         sage: pi_cone.contains(L) ==  pi_star.contains(L_star)
 381         True
 382     """
 383     # Matrices are not vectors in Sage, so we have to convert them
 384     # to vectors explicitly before we can find a basis. We need these
 385     # two values to construct the appropriate "long vector" space.
 386     F = K.lattice().base_field()
 387     n = K.lattice_dim()
 388
 389     tensor_products = [ s.tensor_product(x) for x in K for s in K.dual() ]
 390
 391     # Convert those tensor products to long vectors.
 392     W = VectorSpace(F, n**2)
 393     vectors = [ W(tp.list()) for tp in tensor_products ]
 394
 395     check = True
 396     if K.is_solid() or K.is_strictly_convex():
 397         # The lineality space of either ``K`` or ``K.dual()`` is
 398         # trivial and it's easy to show that our generating set is
 399         # minimal. I would love a proof that this works when ``K`` is
 400         # neither pointed nor solid.
 401         #
 402         # Note that in that case we can get *duplicates*, since the
 403         # tensor product of (x,s) is the same as that of (-x,-s).
 404         check = False
 405
 406     # Create the dual cone of the positive operators, expressed as
 407     # long vectors.
 408     pi_dual = Cone(vectors, ToricLattice(W.dimension()), check=check)
 409
 410     # Now compute the desired cone from its dual...
 411     pi_cone = pi_dual.dual()
 412
 413     # And finally convert its rays back to matrix representations.
 414     M = MatrixSpace(F, n)
 415     return [ M(v.list()) for v in pi_cone ]
 416
 417
 418 def Z_transformation_gens(K):
 419     r"""
 420     Compute generators of the cone of Z-transformations on this cone.
 421
 422     OUTPUT:
 423
 424     A list of `n`-by-``n`` matrices where ``n == K.lattice_dim()``.
 425     Each matrix ``L`` in the list should have the property that
 426     ``(L*x).inner_product(s) <= 0`` whenever ``(x,s)`` is an element the
 427     discrete complementarity set of ``K``. Moreover, any nonnegative
 428     linear combination of these matrices shares the same property.
 429
 430     EXAMPLES:
 431
 432     Z-transformations on the nonnegative orthant are just Z-matrices.
 433     That is, matrices whose off-diagonal elements are nonnegative::
 434
 435         sage: K = Cone([(1,0),(0,1)])
 436         sage: Z_transformation_gens(K)
 437         [
 438         [ 0 -1]  [ 0  0]  [-1  0]  [1 0]  [ 0  0]  [0 0]
 439         [ 0  0], [-1  0], [ 0  0], [0 0], [ 0 -1], [0 1]
 440         ]
 441         sage: K = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)])
 442         sage: all([ z[i][j] <= 0 for z in Z_transformation_gens(K)
 443         ....:                    for i in range(z.nrows())
 444         ....:                    for j in range(z.ncols())
 445         ....:                    if i != j ])
 446         True
 447
 448     The trivial cone in a trivial space has no Z-transformations::
 449
 450         sage: K = Cone([], ToricLattice(0))
 451         sage: Z_transformation_gens(K)
 452         []
 453
 454     Every operator is a Z-transformation on the ambient vector space::
 455
 456         sage: K = Cone([(1,),(-1,)])
 457         sage: K.is_full_space()
 458         True
 459         sage: Z_transformation_gens(K)
 460         [[-1], [1]]
 461
 462         sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
 463         sage: K.is_full_space()
 464         True
 465         sage: Z_transformation_gens(K)
 466         [
 467         [-1  0]  [1 0]  [ 0 -1]  [0 1]  [ 0  0]  [0 0]  [ 0  0]  [0 0]
 468         [ 0  0], [0 0], [ 0  0], [0 0], [-1  0], [1 0], [ 0 -1], [0 1]
 469         ]
 470
 471     A non-obvious application is to find the Z-transformations on the
 472     right half-plane::
 473
 474         sage: K = Cone([(1,0),(0,1),(0,-1)])
 475         sage: Z_transformation_gens(K)
 476         [
 477         [-1  0]  [1 0]  [ 0  0]  [0 0]  [ 0  0]  [0 0]
 478         [ 0  0], [0 0], [-1  0], [1 0], [ 0 -1], [0 1]
 479         ]
 480
 481     Z-transformations on a subspace are Lyapunov-like and vice-versa::
 482
 483         sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
 484         sage: K.is_full_space()
 485         True
 486         sage: lls = span([ vector(l.list()) for l in K.lyapunov_like_basis() ])
 487         sage: zs  = span([ vector(z.list()) for z in Z_transformation_gens(K) ])
 488         sage: zs == lls
 489         True
 490
 491     TESTS:
 492
 493     The Z-property is possessed by every Z-transformation::
 494
 495         sage: set_random_seed()
 496         sage: K = random_cone(max_ambient_dim=4)
 497         sage: Z_of_K = Z_transformation_gens(K)
 498         sage: dcs = K.discrete_complementarity_set()
 499         sage: all([(z*x).inner_product(s) <= 0 for z in Z_of_K
 500         ....:                                  for (x,s) in dcs])
 501         True
 502
 503     The lineality space of the cone of Z-transformations is the space of
 504     Lyapunov-like transformations::
 505
 506         sage: set_random_seed()
 507         sage: K = random_cone(max_ambient_dim=4)
 508         sage: L = ToricLattice(K.lattice_dim()**2)
 509         sage: Z_cone = Cone([ z.list() for z in Z_transformation_gens(K) ],
 510         ....:               lattice=L,
 511         ....:               check=False)
 512         sage: ll_basis = [ vector(l.list()) for l in K.lyapunov_like_basis() ]
 513         sage: lls = L.vector_space().span(ll_basis)
 514         sage: Z_cone.linear_subspace() == lls
 515         True
 516
 517     The lineality of the Z-transformations on a cone is the Lyapunov
 518     rank of that cone::
 519
 520         sage: set_random_seed()
 521         sage: K = random_cone(max_ambient_dim=4)
 522         sage: Z_of_K = Z_transformation_gens(K)
 523         sage: L = ToricLattice(K.lattice_dim()**2)
 524         sage: Z_cone  = Cone([ z.list() for z in Z_of_K ],
 525         ....:                lattice=L,
 526         ....:                check=False)
 527         sage: Z_cone.lineality() == K.lyapunov_rank()
 528         True
 529
 530     The lineality spaces of the duals of the positive operator and
 531     Z-transformation cones are equal. From this it follows that the
 532     dimensions of the Z-transformation cone and positive operator cone
 533     are equal::
 534
 535         sage: set_random_seed()
 536         sage: K = random_cone(max_ambient_dim=4)
 537         sage: pi_of_K = positive_operator_gens(K)
 538         sage: Z_of_K = Z_transformation_gens(K)
 539         sage: L = ToricLattice(K.lattice_dim()**2)
 540         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 541         ....:                lattice=L,
 542         ....:                check=False)
 543         sage: Z_cone = Cone([ z.list() for z in Z_of_K],
 544         ....:               lattice=L,
 545         ....:               check=False)
 546         sage: pi_cone.dim() == Z_cone.dim()
 547         True
 548         sage: pi_star = pi_cone.dual()
 549         sage: z_star = Z_cone.dual()
 550         sage: pi_star.linear_subspace() == z_star.linear_subspace()
 551         True
 552
 553     The trivial cone, full space, and half-plane all give rise to the
 554     expected dimensions::
 555
 556         sage: n = ZZ.random_element().abs()
 557         sage: K = Cone([[0] * n], ToricLattice(n))
 558         sage: K.is_trivial()
 559         True
 560         sage: L = ToricLattice(n^2)
 561         sage: Z_of_K = Z_transformation_gens(K)
 562         sage: Z_cone = Cone([z.list() for z in Z_of_K],
 563         ....:               lattice=L,
 564         ....:               check=False)
 565         sage: actual = Z_cone.dim()
 566         sage: actual == n^2
 567         True
 568         sage: K = K.dual()
 569         sage: K.is_full_space()
 570         True
 571         sage: Z_of_K = Z_transformation_gens(K)
 572         sage: Z_cone = Cone([z.list() for z in Z_of_K],
 573         ....:                lattice=L,
 574         ....:                check=False)
 575         sage: actual = Z_cone.dim()
 576         sage: actual == n^2
 577         True
 578         sage: K = Cone([(1,0),(0,1),(0,-1)])
 579         sage: Z_of_K = Z_transformation_gens(K)
 580         sage: Z_cone = Cone([z.list() for z in Z_of_K], check=False)
 581         sage: Z_cone.dim() == 3
 582         True
 583
 584     The Z-transformations of a permuted cone can be obtained by
 585     conjugation::
 586
 587         sage: set_random_seed()
 588         sage: K = random_cone(max_ambient_dim=4)
 589         sage: L = ToricLattice(K.lattice_dim()**2)
 590         sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
 591         sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
 592         sage: Z_of_pK = Z_transformation_gens(pK)
 593         sage: actual = Cone([t.list() for t in Z_of_pK],
 594         ....:                lattice=L,
 595         ....:                check=False)
 596         sage: Z_of_K = Z_transformation_gens(K)
 597         sage: expected = Cone([(p*t*p.inverse()).list() for t in Z_of_K],
 598         ....:                   lattice=L,
 599         ....:                   check=False)
 600         sage: actual.is_equivalent(expected)
 601         True
 602
 603     A transformation is a Z-transformation on a cone if and only if its
 604     adjoint is a Z-transformation on the dual of that cone::
 605
 606         sage: set_random_seed()
 607         sage: K = random_cone(max_ambient_dim=4)
 608         sage: F = K.lattice().vector_space().base_field()
 609         sage: n = K.lattice_dim()
 610         sage: L = ToricLattice(n**2)
 611         sage: W = VectorSpace(F, n**2)
 612         sage: Z_of_K = Z_transformation_gens(K)
 613         sage: Z_of_K_star = Z_transformation_gens(K.dual())
 614         sage: Z_cone = Cone([p.list() for p in Z_of_K],
 615         ....:               lattice=L,
 616         ....:               check=False)
 617         sage: Z_star = Cone([p.list() for p in Z_of_K_star],
 618         ....:               lattice=L,
 619         ....:               check=False)
 620         sage: M = MatrixSpace(F, n)
 621         sage: L = M(Z_cone.random_element(ring=QQ).list())
 622         sage: Z_star.contains(W(L.transpose().list()))
 623         True
 624
 625         sage: L = W.random_element()
 626         sage: L_star = W(M(L.list()).transpose().list())
 627         sage: Z_cone.contains(L) ==  Z_star.contains(L_star)
 628         True
 629     """
 630     # Matrices are not vectors in Sage, so we have to convert them
 631     # to vectors explicitly before we can find a basis. We need these
 632     # two values to construct the appropriate "long vector" space.
 633     F = K.lattice().base_field()
 634     n = K.lattice_dim()
 635
 636     # These tensor products contain generators for the dual cone of
 637     # the cross-positive transformations.
 638     tensor_products = [ s.tensor_product(x)
 639                         for (x,s) in K.discrete_complementarity_set() ]
 640
 641     # Turn our matrices into long vectors...
 642     W = VectorSpace(F, n**2)
 643     vectors = [ W(m.list()) for m in tensor_products ]
 644
 645     check = True
 646     if K.is_solid() or K.is_strictly_convex():
 647         # The lineality space of either ``K`` or ``K.dual()`` is
 648         # trivial and it's easy to show that our generating set is
 649         # minimal. I would love a proof that this works when ``K`` is
 650         # neither pointed nor solid.
 651         #
 652         # Note that in that case we can get *duplicates*, since the
 653         # tensor product of (x,s) is the same as that of (-x,-s).
 654         check = False
 655
 656     # Create the dual cone of the cross-positive operators,
 657     # expressed as long vectors.
 658     Sigma_dual = Cone(vectors, lattice=ToricLattice(W.dimension()), check=check)
 659
 660     # Now compute the desired cone from its dual...
 661     Sigma_cone = Sigma_dual.dual()
 662
 663     # And finally convert its rays back to matrix representations.
 664     # But first, make them negative, so we get Z-transformations and
 665     # not cross-positive ones.
 666     M = MatrixSpace(F, n)
 667     return [ -M(v.list()) for v in Sigma_cone ]
 668
 669
 670 def Z_cone(K):
 671     gens = Z_transformation_gens(K)
 672     L = ToricLattice(K.lattice_dim()**2)
 673     return Cone([ g.list() for g in gens ], lattice=L, check=False)
 674
 675 def pi_cone(K):
 676     gens = positive_operator_gens(K)
 677     L = ToricLattice(K.lattice_dim()**2)
 678     return Cone([ g.list() for g in gens ], lattice=L, check=False)