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