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 and Z-operators 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_operator_gens(K):
 434     r"""
 435     Compute generators of the cone of Z-operators 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 and Z-operators on closed convex cones.
 450
 451     EXAMPLES:
 452
 453     Z-operators 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_operator_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_operator_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-operators::
 470
 471         sage: K = Cone([], ToricLattice(0))
 472         sage: Z_operator_gens(K)
 473         []
 474
 475     Every operator is a Z-operator on the ambient vector space::
 476
 477         sage: K = Cone([(1,),(-1,)])
 478         sage: K.is_full_space()
 479         True
 480         sage: Z_operator_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_operator_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-operators on the
 493     right half-plane::
 494
 495         sage: K = Cone([(1,0),(0,1),(0,-1)])
 496         sage: Z_operator_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-operators 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_operator_gens(K) ])
 509         sage: zs == lls
 510         True
 511
 512     TESTS:
 513
 514     The Z-property is possessed by every Z-operator::
 515
 516         sage: set_random_seed()
 517         sage: K = random_cone(max_ambient_dim=4)
 518         sage: Z_of_K = Z_operator_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-operators is the space of
 525     Lyapunov-like operators::
 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_operator_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-operators 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_operator_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 and Z-operator
 552     cones are equal. From this it follows that the dimensions of the
 553     Z-operator cone and positive operator cone are equal::
 554
 555         sage: set_random_seed()
 556         sage: K = random_cone(max_ambient_dim=4)
 557         sage: pi_of_K = positive_operator_gens(K)
 558         sage: Z_of_K = Z_operator_gens(K)
 559         sage: L = ToricLattice(K.lattice_dim()**2)
 560         sage: pi_cone = Cone([p.list() for p in pi_of_K],
 561         ....:                lattice=L,
 562         ....:                check=False)
 563         sage: Z_cone = Cone([ z.list() for z in Z_of_K],
 564         ....:               lattice=L,
 565         ....:               check=False)
 566         sage: pi_cone.dim() == Z_cone.dim()
 567         True
 568         sage: pi_star = pi_cone.dual()
 569         sage: z_star = Z_cone.dual()
 570         sage: pi_star.linear_subspace() == z_star.linear_subspace()
 571         True
 572
 573     The trivial cone, full space, and half-plane all give rise to the
 574     expected dimensions::
 575
 576         sage: n = ZZ.random_element().abs()
 577         sage: K = Cone([[0] * n], ToricLattice(n))
 578         sage: K.is_trivial()
 579         True
 580         sage: L = ToricLattice(n^2)
 581         sage: Z_of_K = Z_operator_gens(K)
 582         sage: Z_cone = Cone([z.list() for z in Z_of_K],
 583         ....:               lattice=L,
 584         ....:               check=False)
 585         sage: actual = Z_cone.dim()
 586         sage: actual == n^2
 587         True
 588         sage: K = K.dual()
 589         sage: K.is_full_space()
 590         True
 591         sage: Z_of_K = Z_operator_gens(K)
 592         sage: Z_cone = Cone([z.list() for z in Z_of_K],
 593         ....:                lattice=L,
 594         ....:                check=False)
 595         sage: actual = Z_cone.dim()
 596         sage: actual == n^2
 597         True
 598         sage: K = Cone([(1,0),(0,1),(0,-1)])
 599         sage: Z_of_K = Z_operator_gens(K)
 600         sage: Z_cone = Cone([z.list() for z in Z_of_K], check=False)
 601         sage: Z_cone.dim() == 3
 602         True
 603
 604     The Z-operators of a permuted cone can be obtained by conjugation::
 605
 606         sage: set_random_seed()
 607         sage: K = random_cone(max_ambient_dim=4)
 608         sage: L = ToricLattice(K.lattice_dim()**2)
 609         sage: p = SymmetricGroup(K.lattice_dim()).random_element().matrix()
 610         sage: pK = Cone([ p*k for k in K ], K.lattice(), check=False)
 611         sage: Z_of_pK = Z_operator_gens(pK)
 612         sage: actual = Cone([t.list() for t in Z_of_pK],
 613         ....:                lattice=L,
 614         ....:                check=False)
 615         sage: Z_of_K = Z_operator_gens(K)
 616         sage: expected = Cone([(p*t*p.inverse()).list() for t in Z_of_K],
 617         ....:                   lattice=L,
 618         ....:                   check=False)
 619         sage: actual.is_equivalent(expected)
 620         True
 621
 622     An operator is a Z-operator on a cone if and only if its
 623     adjoint is a Z-operator on the dual of that cone::
 624
 625         sage: set_random_seed()
 626         sage: K = random_cone(max_ambient_dim=4)
 627         sage: F = K.lattice().vector_space().base_field()
 628         sage: n = K.lattice_dim()
 629         sage: L = ToricLattice(n**2)
 630         sage: W = VectorSpace(F, n**2)
 631         sage: Z_of_K = Z_operator_gens(K)
 632         sage: Z_of_K_star = Z_operator_gens(K.dual())
 633         sage: Z_cone = Cone([p.list() for p in Z_of_K],
 634         ....:               lattice=L,
 635         ....:               check=False)
 636         sage: Z_star = Cone([p.list() for p in Z_of_K_star],
 637         ....:               lattice=L,
 638         ....:               check=False)
 639         sage: M = MatrixSpace(F, n)
 640         sage: L = M(Z_cone.random_element(ring=QQ).list())
 641         sage: Z_star.contains(W(L.transpose().list()))
 642         True
 643
 644         sage: L = W.random_element()
 645         sage: L_star = W(M(L.list()).transpose().list())
 646         sage: Z_cone.contains(L) ==  Z_star.contains(L_star)
 647         True
 648     """
 649     # Matrices are not vectors in Sage, so we have to convert them
 650     # to vectors explicitly before we can find a basis. We need these
 651     # two values to construct the appropriate "long vector" space.
 652     F = K.lattice().base_field()
 653     n = K.lattice_dim()
 654
 655     # These tensor products contain generators for the dual cone of
 656     # the cross-positive operators.
 657     tensor_products = [ s.tensor_product(x)
 658                         for (x,s) in K.discrete_complementarity_set() ]
 659
 660     # Turn our matrices into long vectors...
 661     W = VectorSpace(F, n**2)
 662     vectors = [ W(m.list()) for m in tensor_products ]
 663
 664     check = True
 665     if K.is_proper():
 666         # All of the generators involved are extreme vectors and
 667         # therefore minimal. If this cone is neither solid nor
 668         # strictly convex, then the tensor product of ``s`` and ``x``
 669         # is the same as that of ``-s`` and ``-x``. However, as a
 670         # /set/, ``tensor_products`` may still be minimal.
 671         check = False
 672
 673     # Create the dual cone of the cross-positive operators,
 674     # expressed as long vectors.
 675     Sigma_dual = Cone(vectors, lattice=ToricLattice(W.dimension()), check=check)
 676
 677     # Now compute the desired cone from its dual...
 678     Sigma_cone = Sigma_dual.dual()
 679
 680     # And finally convert its rays back to matrix representations.
 681     # But first, make them negative, so we get Z-operators and
 682     # not cross-positive ones.
 683     M = MatrixSpace(F, n)
 684     return [ -M(v.list()) for v in Sigma_cone ]
 685
 686
 687 def LL_cone(K):
 688     gens = K.lyapunov_like_basis()
 689     L = ToricLattice(K.lattice_dim()**2)
 690     return Cone([ g.list() for g in gens ], lattice=L, check=False)
 691
 692 def Z_cone(K):
 693     gens = Z_operator_gens(K)
 694     L = ToricLattice(K.lattice_dim()**2)
 695     return Cone([ g.list() for g in gens ], lattice=L, check=False)
 696
 697 def pi_cone(K):
 698     gens = positive_operator_gens(K)
 699     L = ToricLattice(K.lattice_dim()**2)
 700     return Cone([ g.list() for g in gens ], lattice=L, check=False)