+def _basically_the_same(K1, K2):
+ r"""
+ Test whether or not ``K1`` and ``K2`` are "basically the same."
+
+ This is a hack to get around the fact that it's difficult to tell
+ when two cones are linearly isomorphic. We have a proposition that
+ equates two cones, but represented over `\mathbb{Q}`, they are
+ merely linearly isomorphic (not equal). So rather than test for
+ equality, we test a list of properties that should be preserved
+ under an invertible linear transformation.
+
+ OUTPUT:
+
+ ``True`` if ``K1`` and ``K2`` are basically the same, and ``False``
+ otherwise.
+
+ EXAMPLES:
+
+ Any proper cone with three generators in `\mathbb{R}^{3}` is
+ basically the same as the nonnegative orthant::
+
+ sage: K1 = Cone([(1,0,0), (0,1,0), (0,0,1)])
+ sage: K2 = Cone([(1,2,3), (3, 18, 4), (66, 51, 0)])
+ sage: _basically_the_same(K1, K2)
+ True
+
+ Negating a cone gives you another cone that is basically the same::
+
+ sage: K = Cone([(0,2,-5), (-6, 2, 4), (0, 51, 0)])
+ sage: _basically_the_same(K, -K)
+ True
+
+ TESTS:
+
+ Any cone is basically the same as itself::
+
+ sage: K = random_cone(max_dim = 8)
+ sage: _basically_the_same(K, K)
+ True
+
+ After applying an invertible matrix to the rows of a cone, the
+ result should be basically the same as the cone we started with::
+
+ sage: K1 = random_cone(max_dim = 8)
+ sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
+ sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
+ sage: _basically_the_same(K1, K2)
+ True
+
+ """
+ if K1.lattice_dim() != K2.lattice_dim():
+ return False
+
+ if K1.nrays() != K2.nrays():
+ return False
+
+ if K1.dim() != K2.dim():
+ return False
+
+ if K1.lineality() != K2.lineality():
+ return False
+
+ if K1.is_solid() != K2.is_solid():
+ return False
+
+ if K1.is_strictly_convex() != K2.is_strictly_convex():
+ return False
+
+ if len(LL(K1)) != len(LL(K2)):
+ return False
+
+ C_of_K1 = discrete_complementarity_set(K1)
+ C_of_K2 = discrete_complementarity_set(K2)
+ if len(C_of_K1) != len(C_of_K2):
+ return False
+
+ if len(K1.facets()) != len(K2.facets()):
+ return False
+
+ return True
+
+
+
+def _rho(K, K2=None):
+ r"""
+ Restrict ``K`` into its own span, or the span of another cone.
+
+ INPUT:
+
+ - ``K2`` -- another cone whose lattice has the same rank as this
+ cone.
+
+ OUTPUT:
+
+ A new cone in a sublattice.
+
+ EXAMPLES::
+
+ sage: K = Cone([(1,)])
+ sage: _rho(K) == K
+ True
+
+ sage: K2 = Cone([(1,0)])
+ sage: _rho(K2).rays()
+ N(1)
+ in 1-d lattice N
+ sage: K3 = Cone([(1,0,0)])
+ sage: _rho(K3).rays()
+ N(1)
+ in 1-d lattice N
+ sage: _rho(K2) == _rho(K3)
+ True
+
+ TESTS:
+
+ The projected cone should always be solid::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8)
+ sage: K_S = _rho(K)
+ sage: K_S.is_solid()
+ True
+
+ And the resulting cone should live in a space having the same
+ dimension as the space we restricted it to::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8)
+ sage: K_S = _rho(K, K.dual() )
+ sage: K_S.lattice_dim() == K.dual().dim()
+ True
+
+ This function should not affect the dimension of a cone::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8)
+ sage: K.dim() == _rho(K).dim()
+ True
+
+ Nor should it affect the lineality of a cone::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8)
+ sage: K.lineality() == _rho(K).lineality()
+ True
+
+ No matter which space we restrict to, the lineality should not
+ increase::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8)
+ sage: K.lineality() >= _rho(K).lineality()
+ True
+ sage: K.lineality() >= _rho(K, K.dual()).lineality()
+ True
+
+ If we do this according to our paper, then the result is proper::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8, strictly_convex=False, solid=False)
+ sage: K_S = _rho(K)
+ sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K_SP.is_proper()
+ True
+ sage: K_SP = _rho(K_S, K_S.dual())
+ sage: K_SP.is_proper()
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8, strictly_convex=True, solid=False)
+ sage: K_S = _rho(K)
+ sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K_SP.is_proper()
+ True
+ sage: K_SP = _rho(K_S, K_S.dual())
+ sage: K_SP.is_proper()
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8, strictly_convex=False, solid=True)
+ sage: K_S = _rho(K)
+ sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K_SP.is_proper()
+ True
+ sage: K_SP = _rho(K_S, K_S.dual())
+ sage: K_SP.is_proper()
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim = 8, strictly_convex=True, solid=True)
+ sage: K_S = _rho(K)
+ sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K_SP.is_proper()
+ True
+ sage: K_SP = _rho(K_S, K_S.dual())
+ sage: K_SP.is_proper()
+ True
+
+ Test Proposition 7 in our paper concerning the duals and
+ restrictions. Generate a random cone, then create a subcone of
+ it. The operation of dual-taking should then commute with rho::
+
+ sage: set_random_seed()
+ sage: J = random_cone(max_dim = 8, solid=False, strictly_convex=False)
+ sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
+ sage: K_W_star = _rho(K, J).dual()
+ sage: K_star_W = _rho(K.dual(), J)
+ sage: _basically_the_same(K_W_star, K_star_W)
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: J = random_cone(max_dim = 8, solid=True, strictly_convex=False)
+ sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
+ sage: K_W_star = _rho(K, J).dual()
+ sage: K_star_W = _rho(K.dual(), J)
+ sage: _basically_the_same(K_W_star, K_star_W)
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: J = random_cone(max_dim = 8, solid=False, strictly_convex=True)
+ sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
+ sage: K_W_star = _rho(K, J).dual()
+ sage: K_star_W = _rho(K.dual(), J)
+ sage: _basically_the_same(K_W_star, K_star_W)
+ True
+
+ ::
+
+ sage: set_random_seed()
+ sage: J = random_cone(max_dim = 8, solid=True, strictly_convex=True)
+ sage: K = Cone(random_sublist(J.rays(), 0.5), lattice=J.lattice())
+ sage: K_W_star = _rho(K, J).dual()
+ sage: K_star_W = _rho(K.dual(), J)
+ sage: _basically_the_same(K_W_star, K_star_W)
+ True
+
+ """
+ if K2 is None:
+ K2 = K
+
+ # First we project K onto the span of K2. This will explode if the
+ # rank of ``K2.lattice()`` doesn't match ours.
+ span_K2 = Cone(K2.rays() + (-K2).rays(), lattice=K.lattice())
+ K = K.intersection(span_K2)
+
+ # Cheat a little to get the subspace span(K2). The paper uses the
+ # rays of K2 as a basis, but everything is invariant under linear
+ # isomorphism (i.e. a change of basis), and this is a little
+ # faster.
+ W = span_K2.linear_subspace()
+
+ # We've already intersected K with the span of K2, so every
+ # generator of K should belong to W now.
+ W_rays = [ W.coordinate_vector(r) for r in K.rays() ]
+
+ L = ToricLattice(K2.dim())
+ return Cone(W_rays, lattice=L)
+
+
+
+def discrete_complementarity_set(K):
+ r"""
+ Compute the discrete complementarity set of this cone.
+
+ The complementarity set of this cone is the set of all orthogonal
+ pairs `(x,s)` such that `x` is in this cone, and `s` is in its
+ dual. The discrete complementarity set restricts `x` and `s` to be
+ generators of their respective cones.
+
+ OUTPUT:
+
+ A list of pairs `(x,s)` such that,
+
+ * `x` is a generator of this cone.
+ * `s` is a generator of this cone's dual.
+ * `x` and `s` are orthogonal.
+
+ EXAMPLES:
+
+ The discrete complementarity set of the nonnegative orthant consists
+ of pairs of standard basis vectors::
+
+ sage: K = Cone([(1,0),(0,1)])
+ sage: discrete_complementarity_set(K)
+ [((1, 0), (0, 1)), ((0, 1), (1, 0))]
+
+ If the cone consists of a single ray, the second components of the
+ discrete complementarity set should generate the orthogonal
+ complement of that ray::
+
+ sage: K = Cone([(1,0)])
+ sage: discrete_complementarity_set(K)
+ [((1, 0), (0, 1)), ((1, 0), (0, -1))]
+ sage: K = Cone([(1,0,0)])
+ sage: discrete_complementarity_set(K)
+ [((1, 0, 0), (0, 1, 0)),
+ ((1, 0, 0), (0, -1, 0)),
+ ((1, 0, 0), (0, 0, 1)),
+ ((1, 0, 0), (0, 0, -1))]
+
+ When the cone is the entire space, its dual is the trivial cone, so
+ the discrete complementarity set is empty::
+
+ sage: K = Cone([(1,0),(-1,0),(0,1),(0,-1)])
+ sage: discrete_complementarity_set(K)
+ []
+
+ TESTS:
+
+ The complementarity set of the dual can be obtained by switching the
+ components of the complementarity set of the original cone::
+
+ sage: set_random_seed()
+ sage: K1 = random_cone(max_dim=6)
+ sage: K2 = K1.dual()
+ sage: expected = [(x,s) for (s,x) in discrete_complementarity_set(K2)]
+ sage: actual = discrete_complementarity_set(K1)
+ sage: sorted(actual) == sorted(expected)
+ True
+
+ """
+ V = K.lattice().vector_space()
+
+ # Convert the rays to vectors so that we can compute inner
+ # products.
+ xs = [V(x) for x in K.rays()]
+ ss = [V(s) for s in K.dual().rays()]
+
+ return [(x,s) for x in xs for s in ss if x.inner_product(s) == 0]
+
+
+def LL(K):
+ r"""
+ Compute the space `\mathbf{LL}` of all Lyapunov-like transformations
+ on this cone.
+
+ OUTPUT:
+
+ A list of matrices forming a basis for the space of all
+ Lyapunov-like transformations on the given cone.
+
+ EXAMPLES:
+
+ The trivial cone has no Lyapunov-like transformations::
+
+ sage: L = ToricLattice(0)
+ sage: K = Cone([], lattice=L)
+ sage: LL(K)
+ []
+
+ The Lyapunov-like transformations on the nonnegative orthant are
+ simply diagonal matrices::
+
+ sage: K = Cone([(1,)])
+ sage: LL(K)
+ [[1]]
+
+ sage: K = Cone([(1,0),(0,1)])
+ sage: LL(K)
+ [
+ [1 0] [0 0]
+ [0 0], [0 1]
+ ]
+
+ sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
+ sage: LL(K)
+ [
+ [1 0 0] [0 0 0] [0 0 0]
+ [0 0 0] [0 1 0] [0 0 0]
+ [0 0 0], [0 0 0], [0 0 1]
+ ]
+
+ Only the identity matrix is Lyapunov-like on the `L^{3}_{1}` and
+ `L^{3}_{\infty}` cones [Rudolf et al.]_::
+
+ sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
+ sage: LL(L31)
+ [
+ [1 0 0]
+ [0 1 0]
+ [0 0 1]
+ ]
+
+ sage: L3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
+ sage: LL(L3infty)
+ [
+ [1 0 0]
+ [0 1 0]
+ [0 0 1]
+ ]
+
+ If our cone is the entire space, then every transformation on it is
+ Lyapunov-like::
+
+ sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
+ sage: M = MatrixSpace(QQ,2)
+ sage: M.basis() == LL(K)
+ True
+
+ TESTS:
+
+ The inner product `\left< L\left(x\right), s \right>` is zero for
+ every pair `\left( x,s \right)` in the discrete complementarity set
+ of the cone::
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim=8)
+ sage: C_of_K = discrete_complementarity_set(K)
+ sage: l = [ (L*x).inner_product(s) for (x,s) in C_of_K for L in LL(K) ]
+ sage: sum(map(abs, l))
+ 0
+
+ The Lyapunov-like transformations on a cone and its dual are related
+ by transposition, but we're not guaranteed to compute transposed
+ elements of `LL\left( K \right)` as our basis for `LL\left( K^{*}
+ \right)`
+
+ sage: set_random_seed()
+ sage: K = random_cone(max_dim=8)
+ sage: LL2 = [ L.transpose() for L in LL(K.dual()) ]
+ sage: V = VectorSpace( K.lattice().base_field(), K.lattice_dim()^2)
+ sage: LL1_vecs = [ V(m.list()) for m in LL(K) ]
+ sage: LL2_vecs = [ V(m.list()) for m in LL2 ]
+ sage: V.span(LL1_vecs) == V.span(LL2_vecs)
+ True
+
+ """
+ V = K.lattice().vector_space()
+
+ C_of_K = discrete_complementarity_set(K)
+
+ tensor_products = [ s.tensor_product(x) for (x,s) in C_of_K ]
+
+ # Sage doesn't think matrices are vectors, so we have to convert
+ # our matrices to vectors explicitly before we can figure out how
+ # many are linearly-indepenedent.
+ #
+ # The space W has the same base ring as V, but dimension
+ # dim(V)^2. So it has the same dimension as the space of linear
+ # transformations on V. In other words, it's just the right size
+ # to create an isomorphism between it and our matrices.
+ W = VectorSpace(V.base_ring(), V.dimension()**2)
+
+ # Turn our matrices into long vectors...
+ vectors = [ W(m.list()) for m in tensor_products ]
+
+ # Vector space representation of Lyapunov-like matrices
+ # (i.e. vec(L) where L is Luapunov-like).
+ LL_vector = W.span(vectors).complement()
+
+ # Now construct an ambient MatrixSpace in which to stick our
+ # transformations.
+ M = MatrixSpace(V.base_ring(), V.dimension())
+
+ matrix_basis = [ M(v.list()) for v in LL_vector.basis() ]
+
+ return matrix_basis
+
+
+