X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Fcone.py;h=1a3ee3b2fad16e3a05938cb7b9c6a0beae9518d1;hb=f9d0571d553891281fd31949871e27e1f973a281;hp=3c582e681a8ea0c6d985cc89d5492a5481578801;hpb=826580027d1f9d32a0317c5ad90a9d69cda7795d;p=sage.d.git

diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py
index 3c582e6..1a3ee3b 100644
--- a/mjo/cone/cone.py
+++ b/mjo/cone/cone.py
@@ -214,24 +214,22 @@ def _restrict_to_space(K, W):
 
 def discrete_complementarity_set(K):
     r"""
-    Compute the discrete complementarity set of this cone.
+    Compute a discrete complementarity set of this cone.
 
-    The complementarity set of a cone is the set of all orthogonal pairs
-    `(x,s)` such that `x` is in the cone, and `s` is in its dual. The
-    discrete complementarity set is a subset of the complementarity set
-    where `x` and `s` are required to be generators of their respective
-    cones.
-
-    For polyhedral cones, the discrete complementarity set is always
-    finite.
+    A discrete complementarity set of `K` is the set of all orthogonal
+    pairs `(x,s)` such that `x \in G_{1}` and `s \in G_{2}` for some
+    generating sets `G_{1}` of `K` and `G_{2}` of its dual. Polyhedral
+    convex cones are input in terms of their generators, so "the" (this
+    particular) discrete complementarity set corresponds to ``G1
+    == K.rays()`` and ``G2 == K.dual().rays()``.
 
     OUTPUT:
 
     A list of pairs `(x,s)` such that,
 
       * Both `x` and `s` are vectors (not rays).
-      * `x` is a generator of this cone.
-      * `s` is a generator of this cone's dual.
+      * `x` is one of ``K.rays()``.
+      * `s` is one of ``K.dual().rays()``.
       * `x` and `s` are orthogonal.
 
     REFERENCES:
@@ -687,3 +685,125 @@ def lyapunov_rank(K):
 
     beta += len(LL(K))
     return beta
+
+
+
+def is_lyapunov_like(L,K):
+    r"""
+    Determine whether or not ``L`` is Lyapunov-like on ``K``.
+
+    We say that ``L`` is Lyapunov-like on ``K`` if `\left\langle
+    L\left\lparenx\right\rparen,s\right\rangle = 0` for all pairs
+    `\left\langle x,s \right\rangle` in the complementarity set of
+    ``K``. It is known [Orlitzky]_ that this property need only be
+    checked for generators of ``K`` and its dual.
+
+    INPUT:
+
+    - ``L`` -- A linear transformation or matrix.
+
+    - ``K`` -- A polyhedral closed convex cone.
+
+    OUTPUT:
+
+    ``True`` if it can be proven that ``L`` is Lyapunov-like on ``K``,
+    and ``False`` otherwise.
+
+    .. WARNING::
+
+        If this function returns ``True``, then ``L`` is Lyapunov-like
+        on ``K``. However, if ``False`` is returned, that could mean one
+        of two things. The first is that ``L`` is definitely not
+        Lyapunov-like on ``K``. The second is more of an "I don't know"
+        answer, returned (for example) if we cannot prove that an inner
+        product is zero.
+
+    REFERENCES:
+
+    .. [Orlitzky] M. Orlitzky. The Lyapunov rank of an
+       improper cone (preprint).
+
+    EXAMPLES:
+
+    The identity is always Lyapunov-like in a nontrivial space::
+
+        sage: set_random_seed()
+        sage: K = random_cone(min_ambient_dim = 1, max_rays = 8)
+        sage: L = identity_matrix(K.lattice_dim())
+        sage: is_lyapunov_like(L,K)
+        True
+
+    As is the "zero" transformation::
+
+        sage: K = random_cone(min_ambient_dim = 1, max_rays = 5)
+        sage: R = K.lattice().vector_space().base_ring()
+        sage: L = zero_matrix(R, K.lattice_dim())
+        sage: is_lyapunov_like(L,K)
+        True
+
+    Everything in ``LL(K)`` should be Lyapunov-like on ``K``::
+
+        sage: K = random_cone(min_ambient_dim = 1, max_rays = 5)
+        sage: all([is_lyapunov_like(L,K) for L in LL(K)])
+        True
+
+    """
+    return all([(L*x).inner_product(s) == 0
+                for (x,s) in discrete_complementarity_set(K)])
+
+
+def random_element(K):
+    r"""
+    Return a random element of ``K`` from its ambient vector space.
+
+    ALGORITHM:
+
+    The cone ``K`` is specified in terms of its generators, so that
+    ``K`` is equal to the convex conic combination of those generators.
+    To choose a random element of ``K``, we assign random nonnegative
+    coefficients to each generator of ``K`` and construct a new vector
+    from the scaled rays.
+
+    A vector, rather than a ray, is returned so that the element may
+    have non-integer coordinates. Thus the element may have an
+    arbitrarily small norm.
+
+    EXAMPLES:
+
+    A random element of the trivial cone is zero::
+
+        sage: set_random_seed()
+        sage: K = Cone([], ToricLattice(0))
+        sage: random_element(K)
+        ()
+        sage: K = Cone([(0,)])
+        sage: random_element(K)
+        (0)
+        sage: K = Cone([(0,0)])
+        sage: random_element(K)
+        (0, 0)
+        sage: K = Cone([(0,0,0)])
+        sage: random_element(K)
+        (0, 0, 0)
+
+    TESTS:
+
+    Any cone should contain an element of itself::
+
+        sage: set_random_seed()
+        sage: K = random_cone(max_rays = 8)
+        sage: K.contains(random_element(K))
+        True
+
+    """
+    V = K.lattice().vector_space()
+    F = V.base_ring()
+    coefficients = [ F.random_element().abs() for i in range(K.nrays()) ]
+    vector_gens  = map(V, K.rays())
+    scaled_gens  = [ coefficients[i]*vector_gens[i]
+                         for i in range(len(vector_gens)) ]
+
+    # Make sure we return a vector. Without the coercion, we might
+    # return ``0`` when ``K`` has no rays.
+    v = V(sum(scaled_gens))
+    return v