X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Fcone.py;h=a5482b3aa95f7198938007c4be615c4e7a97e17d;hb=b97553aaaf9734644bee13bf484014f817456b26;hp=777d45e1a3e7a72a5ebbb167fd1ef6540c745282;hpb=81a763e35b3e4322be6c60a815064be1f0dfcc3c;p=sage.d.git

diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py
index 777d45e..a5482b3 100644
--- a/mjo/cone/cone.py
+++ b/mjo/cone/cone.py
@@ -80,6 +80,50 @@ def discrete_complementarity_set(K):
     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 ``MatrixSpace`` object `M` such that every matrix `L \in M` is
+    Lyapunov-like on this cone.
+
+    """
+    V = K.lattice().vector_space()
+
+    C_of_K = discrete_complementarity_set(K)
+
+    matrices = [x.tensor_product(s) 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 matrices ]
+
+    # 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())
+
+    matrices = [ M(v.list()) for v in LL_vector.basis() ]
+
+    return matrices
+
+
+
 def lyapunov_rank(K):
     r"""
     Compute the Lyapunov (or bilinearity) rank of this cone.
@@ -123,17 +167,18 @@ def lyapunov_rank(K):
 
     REFERENCES:
 
-    1. M.S. Gowda and J. Tao. On the bilinearity rank of a proper cone
-       and Lyapunov-like transformations, Mathematical Programming, 147
+    .. [Gowda/Tao] M.S. Gowda and J. Tao. On the bilinearity rank of a proper
+       cone and Lyapunov-like transformations, Mathematical Programming, 147
        (2014) 155-170.
 
-    2. G. Rudolf, N. Noyan, D. Papp, and F. Alizadeh, Bilinear
+    .. [Rudolf et al.] G. Rudolf, N. Noyan, D. Papp, and F. Alizadeh, Bilinear
        optimality constraints for the cone of positive polynomials,
        Mathematical Programming, Series B, 129 (2011) 5-31.
 
     EXAMPLES:
 
-    The nonnegative orthant in `\mathbb{R}^{n}` always has rank `n`::
+    The nonnegative orthant in `\mathbb{R}^{n}` always has rank `n`
+    [Rudolf et al.]_::
 
         sage: positives = Cone([(1,)])
         sage: lyapunov_rank(positives)
@@ -141,23 +186,25 @@ def lyapunov_rank(K):
         sage: quadrant = Cone([(1,0), (0,1)])
         sage: lyapunov_rank(quadrant)
         2
-        sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
+       sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
         sage: lyapunov_rank(octant)
         3
 
-    The `L^{3}_{1}` cone is known to have a Lyapunov rank of one::
+    The `L^{3}_{1}` cone is known to have a Lyapunov rank of one
+    [Rudolf et al.]_::
 
         sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
         sage: lyapunov_rank(L31)
         1
 
-    Likewise for the `L^{3}_{\infty}` cone::
+    Likewise for the `L^{3}_{\infty}` cone [Rudolf et al.]_::
 
         sage: L3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
         sage: lyapunov_rank(L3infty)
         1
 
-    The Lyapunov rank should be additive on a product of cones::
+    The Lyapunov rank should be additive on a product of cones
+    [Rudolf et al.]_::
 
         sage: L31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
         sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
@@ -165,8 +212,8 @@ def lyapunov_rank(K):
         sage: lyapunov_rank(K) == lyapunov_rank(L31) + lyapunov_rank(octant)
         True
 
-    Two isomorphic cones should have the same Lyapunov rank. The cone
-    ``K`` in the following example is isomorphic to the nonnegative
+    Two isomorphic cones should have the same Lyapunov rank [Rudolf et al.]_.
+    The cone ``K`` in the following example is isomorphic to the nonnegative
     octant in `\mathbb{R}^{3}`::
 
         sage: K = Cone([(1,2,3), (-1,1,0), (1,0,6)])
@@ -174,7 +221,7 @@ def lyapunov_rank(K):
         3
 
     The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
-    itself::
+    itself [Rudolf et al.]_::
 
         sage: K = Cone([(2,2,4), (-1,9,0), (2,0,6)])
         sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
@@ -182,7 +229,8 @@ def lyapunov_rank(K):
 
     TESTS:
 
-    The Lyapunov rank should be additive on a product of cones::
+    The Lyapunov rank should be additive on a product of cones
+    [Rudolf et al.]_::
 
         sage: K1 = random_cone(max_dim=10, max_rays=10)
         sage: K2 = random_cone(max_dim=10, max_rays=10)
@@ -191,12 +239,25 @@ def lyapunov_rank(K):
         True
 
     The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
-    itself::
+    itself [Rudolf et al.]_::
 
         sage: K = random_cone(max_dim=10, max_rays=10)
         sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
         True
 
+    The Lyapunov rank of a proper polyhedral cone in `n` dimensions can
+    be any number between `1` and `n` inclusive, excluding `n-1`
+    [Gowda/Tao]_ (by accident, this holds for the trivial cone in a
+    trivial space as well)::
+
+        sage: K = random_cone(max_dim=10, strictly_convex=True, solid=True)
+        sage: b = lyapunov_rank(K)
+        sage: n = K.lattice_dim()
+        sage: 1 <= b and b <= n
+        True
+        sage: b == n-1
+        False
+
     """
     V = K.lattice().vector_space()