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