-def _rho(K, K2=None):
+def _restrict_to_space(K, W):
r"""
- Restrict ``K`` into its own span, or the span of another cone.
+ Restrict this cone a subspace of its ambient space.
INPUT:
- - ``K2`` -- another cone whose lattice has the same rank as this
- cone.
+ - ``W`` -- The subspace into which this cone will be restricted.
OUTPUT:
- A new cone in a sublattice.
+ A new cone in a sublattice corresponding to ``W``.
- EXAMPLES::
+ EXAMPLES:
+
+ When this cone is solid, restricting it into its own span should do
+ nothing::
sage: K = Cone([(1,)])
- sage: _rho(K) == K
+ sage: _restrict_to_space(K, K.span()) == K
True
+ A single ray restricted into its own span gives the same output
+ regardless of the ambient space::
+
sage: K2 = Cone([(1,0)])
- sage: _rho(K2).rays()
+ sage: K2_S = _restrict_to_space(K2, K2.span()).rays()
+ sage: K2_S
N(1)
in 1-d lattice N
sage: K3 = Cone([(1,0,0)])
- sage: _rho(K3).rays()
+ sage: K3_S = _restrict_to_space(K3, K3.span()).rays()
+ sage: K3_S
N(1)
in 1-d lattice N
- sage: _rho(K2) == _rho(K3)
+ sage: K2_S == K3_S
True
TESTS:
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim = 8)
- sage: K_S = _rho(K)
- sage: K_S.is_solid()
+ sage: _restrict_to_space(K, K.span()).is_solid()
True
And the resulting cone should live in a space having the same
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim = 8)
- sage: K_S = _rho(K, K.dual() )
- sage: K_S.lattice_dim() == K.dual().dim()
+ sage: K_P = _restrict_to_space(K, K.dual().span())
+ sage: K_P.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_ambient_dim = 8)
- sage: K.dim() == _rho(K).dim()
+ sage: K.dim() == _restrict_to_space(K,K.span()).dim()
True
Nor should it affect the lineality of a cone::
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim = 8)
- sage: K.lineality() == _rho(K).lineality()
+ sage: K.lineality() == _restrict_to_space(K, K.span()).lineality()
True
No matter which space we restrict to, the lineality should not
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim = 8)
- sage: K.lineality() >= _rho(K).lineality()
+ sage: S = K.span(); P = K.dual().span()
+ sage: K.lineality() >= _restrict_to_space(K,S).lineality()
True
- sage: K.lineality() >= _rho(K, K.dual()).lineality()
+ sage: K.lineality() >= _restrict_to_space(K,P).lineality()
True
If we do this according to our paper, then the result is proper::
sage: set_random_seed()
- sage: K = random_cone(max_ambient_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_ambient_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_ambient_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_ambient_dim = 8,
- ....: strictly_convex=True,
- ....: solid=True)
- sage: K_S = _rho(K)
- sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K = random_cone(max_ambient_dim = 8)
+ sage: K_S = _restrict_to_space(K, K.span())
+ sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
sage: K_SP.is_proper()
True
- sage: K_SP = _rho(K_S, K_S.dual())
+ sage: K_SP = _restrict_to_space(K_S, K_S.dual().span())
sage: K_SP.is_proper()
True
- Test Proposition 7 in our paper concerning the duals and
+ Test the proposition 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_ambient_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
-
- ::
+ it. The operation of dual-taking should then commute with
+ _restrict_to_space::
sage: set_random_seed()
- sage: J = random_cone(max_ambient_dim = 8,
- ....: solid=True,
- ....: strictly_convex=False)
+ sage: J = random_cone(max_ambient_dim = 8)
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_ambient_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_ambient_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: K_W_star = _restrict_to_space(K, J.span()).dual()
+ sage: K_star_W = _restrict_to_space(K.dual(), J.span())
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()
+ # First we want to intersect ``K`` with ``W``. The easiest way to
+ # do this is via cone intersection, so we turn the subspace ``W``
+ # into a cone.
+ W_cone = Cone(W.basis() + [-b for b in W.basis()], lattice=K.lattice())
+ K = K.intersection(W_cone)
# 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() ]
+ K_W_rays = [ W.coordinate_vector(r) for r in K.rays() ]
- L = ToricLattice(K2.dim())
- return Cone(W_rays, lattice=L)
+ L = ToricLattice(W.dimension())
+ return Cone(K_W_rays, lattice=L)
def discrete_complementarity_set(K):
r"""
- Compute the 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.
+ Compute a discrete complementarity set of this cone.
- 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:
def lyapunov_rank(K):
r"""
- Compute the Lyapunov (or bilinearity) rank of this cone.
+ Compute the Lyapunov rank (or bilinearity rank) of this cone.
The Lyapunov rank of a cone can be thought of in (mainly) two ways:
An integer representing the Lyapunov rank of the cone. If the
dimension of the ambient vector space is `n`, then the Lyapunov rank
will be between `1` and `n` inclusive; however a rank of `n-1` is
- not possible (see the first reference).
-
- .. note::
-
- In the references, the cones are always assumed to be proper. We
- do not impose this restriction.
-
- .. seealso::
-
- :meth:`is_proper`
+ not possible (see [Orlitzky/Gowda]_).
ALGORITHM:
sage: lyapunov_rank(K1) == lyapunov_rank(K2)
True
- Just to be sure, test a few more::
-
- sage: K1 = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=True)
- sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
- sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
- sage: lyapunov_rank(K1) == lyapunov_rank(K2)
- True
-
- ::
-
- sage: K1 = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=False)
- sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
- sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
- sage: lyapunov_rank(K1) == lyapunov_rank(K2)
- True
-
- ::
-
- sage: K1 = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=True)
- sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
- sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
- sage: lyapunov_rank(K1) == lyapunov_rank(K2)
- True
-
- ::
-
- sage: K1 = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=False)
- sage: A = random_matrix(QQ, K1.lattice_dim(), algorithm='unimodular')
- sage: K2 = Cone( [ A*r for r in K1.rays() ], lattice=K1.lattice())
- sage: lyapunov_rank(K1) == lyapunov_rank(K2)
- True
-
The dual cone `K^{*}` of ``K`` should have the same Lyapunov rank as ``K``
itself [Rudolf et al.]_::
sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
True
- Make sure we exercise the non-strictly-convex/non-solid case::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=False)
- sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
- True
-
- Let's check the other permutations as well, just to be sure::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=True)
- sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
- True
-
- ::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=False)
- sage: lyapunov_rank(K) == lyapunov_rank(K.dual())
- True
-
- ::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=True)
- 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, the `n-1` restriction will hold for the
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim=8)
sage: actual = lyapunov_rank(K)
- sage: K_S = _rho(K)
- sage: K_SP = _rho(K_S.dual()).dual()
+ sage: K_S = _restrict_to_space(K, K.span())
+ sage: K_SP = _restrict_to_space(K_S.dual(), K_S.dual().span()).dual()
sage: l = K.lineality()
sage: c = K.codim()
sage: expected = lyapunov_rank(K_SP) + K.dim()*(l + c) + c**2
sage: actual == expected
True
- The Lyapunov rank of a proper cone is just the dimension of ``LL(K)``::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=True)
- sage: lyapunov_rank(K) == len(LL(K))
- True
-
- In fact the same can be said of any cone. These additional tests
- just increase our confidence that the reduction scheme works::
+ The Lyapunov rank of any cone is just the dimension of ``LL(K)``::
sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=True,
- ....: solid=False)
- sage: lyapunov_rank(K) == len(LL(K))
- True
-
- ::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=True)
- sage: lyapunov_rank(K) == len(LL(K))
- True
-
- ::
-
- sage: set_random_seed()
- sage: K = random_cone(max_ambient_dim=8,
- ....: strictly_convex=False,
- ....: solid=False)
+ sage: K = random_cone(max_ambient_dim=8)
sage: lyapunov_rank(K) == len(LL(K))
True
- Test Theorem 3 in [Orlitzky/Gowda]_::
+ We can make an imperfect cone perfect by adding a slack variable
+ (a Theorem in [Orlitzky/Gowda]_)::
sage: set_random_seed()
sage: K = random_cone(max_ambient_dim=8,
if m < n:
# K is not solid, restrict to its span.
- K = _rho(K)
+ K = _restrict_to_space(K, K.span())
- # Lemma 2
- beta += m*(n - m) + (n - m)**2
+ # Non-solid reduction lemma.
+ beta += (n - m)*n
if l > 0:
# K is not pointed, restrict to the span of its dual. Uses a
# proposition from our paper, i.e. this is equivalent to K =
# _rho(K.dual()).dual().
- K = _rho(K, K.dual())
+ K = _restrict_to_space(K, K.dual().span())
- # Lemma 3
- beta += m * l
+ # Non-pointed reduction lemma.
+ beta += l * m
beta += len(LL(K))
return beta