From d0b846c67811a7e7f09ccf817b8637cdb09de6a3 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Tue, 1 Jul 2025 00:03:45 -0400 Subject: [PATCH] mjo/cone/isomorphism.py: update docs/names, add is-isomorphic method Rename the isomorphism generator to linear_isomorphisms(), since "linear isomorphism" is as good of a distinguishing name as I can think of. Then add the is_linearly_isomorphic() function to check that at least one isomorphism exists. --- mjo/cone/isomorphism.py | 134 ++++++++++++++++++++++++++++++---------- 1 file changed, 103 insertions(+), 31 deletions(-) diff --git a/mjo/cone/isomorphism.py b/mjo/cone/isomorphism.py index eefd796..f746914 100644 --- a/mjo/cone/isomorphism.py +++ b/mjo/cone/isomorphism.py @@ -1,38 +1,69 @@ -def rational_isomorphism_generator(K1, K2): +def linear_isomorphisms(K1, K2): r""" Generate invertible linear transformations mapping ``K1`` onto ``K2``. - If ``K1`` and ``K2`` are both pointed and solid in - ``n``-dimensional space, then they have extreme rays, and we - construct isomorphisms (over the rationals) by mapping size-``n`` - subsets of ``K1``'s extreme rays to size-``n`` subsets of ``K2``'s - extreme rays. The resulting isomorphisms are unique only up to - scalar multiples; it may be possible to scale some rows of the - isomorphism by different positive multiples, and it is always - possible to scale the entire isomorphism by a single positive - amount. For example, the automorphism group of the nonnegative - orthant is allowed to scale each extreme ray by a different - multiple, but the automorphisms of the little-l1 cone (a square - raised to height one in ``RR^3``) must be scaled as a whole. In - general this comes down to the number of extreme rays being - greater than the dimension of the cone. - - If ``K1`` and ``K2`` are not pointed, then in addition to the - procedure above, we also map a basis for the lineality space of - ``K1`` to a basis of the lineality space for ``K2``. Similarly, - when ``K1`` or ``K2`` are not solid, we map bases for their - orthogonal complements to one another. This procedure is not - unique, since there are many isomorphisms (corresponding to many - choices of bases) between two vector subspaces of the same - size. As a result you should expect a greater degree of - non-uniqueness in the isomorphisms when your cones are not pointed - or not solid. (If, say, only ``K1`` is not pointed, then we know - immediately that ``K2`` cannot be isomorphic to it.) + In general, if ``K1`` and ``K2`` are isomorphic, there will be an + infinite number of isomorphisms between them. For example, any + positive scalar multiple of a cone isomorphism is itself a cone + isomorphism. As such we do not return *every* isomorphism, only a + "generating set." For the precise meaning of this, please see the + description of the algorithm below. + + INPUT: + + - ``K1`` -- the first cone + + - ``K2`` -- the second cone + + OUTPUT: + + A generator that yields linear isomorphisms between ``K1`` and + ``K2``, one at a time. The isomorphisms consist of invertible + matrices ``A`` whose entries are rational numbers and satisfy + ``Cone(r*A for r in K1).is_equivalent(K2)``. In other words, they + map the cone ``K1`` onto ``K2``, acting on the rays of ``K1`` from + the right. The right-action is mainly for compatibility with the + basis matrix of a vector space, which in SageMath contains the + basis vectors as rows. The returned matrices are immutable so that they may be hashed, and, for example, de-duplicated using ``set()``. + ALGORITHM: + + It is well-known that the linear automorphisms of a cone that + :meth:`is_strictly_convex` must map extreme rays of the original + cone (which exist, because it is strictly convex) to extreme rays + of the target cone (which had better exist, otherwise the cones + are not isomorphic). If moreover ``K1`` meth:`is_solid`, then it + has at least `n` extreme rays, where `n` is the dimension of its + ambient space, and likewise for ``K2`` (otherwise, again, they are + not isomorphic). As a result, if ``K1`` is both strictly convex + and solid, any isomorphism must map a basis consisting of its + extreme rays to a basis of extreme rays for ``K2``. In this + scenario we generate all such maps, and yield the ones that turn + out to be isomorphisms when we check them explicitly. + + If the cones are both solid and strictly convex, the generated + isomorphisms are unique up to positive row scalings. When there + are exactly `n` extreme rays (that is, when the cone + :meth:`is_simplicial`), each row of an isomorphism can be scaled + independently without destroying the isomorphism property. But + when there are more than `n` extreme rays, it is typically only + safe to scale the entire isomorphism by a single positive amount. + + If ``K1`` and ``K2`` are *not* pointed, then in addition to the + procedure above, we map a basis for the :meth:`linear_subspace` of + ``K1`` to a basis of the :meth:`linear_subspace` of + ``K2``. Similarly, if ``K1`` and ``K2`` are not solid, we map + bases for their orthogonal complements to one another. There are + many isomorphisms (corresponding to many choices of bases) between + two vector subspaces of the same dimension, so in this case, the + cone isomorphisms we generate should be considered unique only up + to vector-space isomorphisms of the lineality spaces and othogonal + complements. + EXAMPLES: In this example, the lower half-space is obtained from the upper @@ -40,7 +71,7 @@ def rational_isomorphism_generator(K1, K2): sage: K1 = Cone([(0,1),(1,0),(-1,0)]) sage: K2 = Cone([(0,-1),(1,0),(-1,0)]) - sage: next(rational_isomorphism_generator(K1,K2)) + sage: next(linear_isomorphisms(K1,K2)) [ 1 0] [ 0 -1] @@ -50,7 +81,7 @@ def rational_isomorphism_generator(K1, K2): sage: K2 = Cone([(1,1), (-1,1), (0,-1)]) sage: K1.is_equivalent(K2) True - sage: next(rational_isomorphism_generator(K1,K2)) + sage: next(linear_isomorphisms(K1,K2)) [1 0] [0 1] @@ -65,7 +96,7 @@ def rational_isomorphism_generator(K1, K2): ....: [ 2, 6, 9, 58], ....: [ -1, -7, -16, -90]]) sage: K2 = Cone([r*A for r in K1]) - sage: g = next(rational_isomorphism_generator(K1,K2)) + sage: g = next(linear_isomorphisms(K1,K2)) sage: Cone(r*g for r in K1.rays()).is_equivalent(K2) True @@ -74,7 +105,7 @@ def rational_isomorphism_generator(K1, K2): only the unique automorphisms:: sage: K1 = Cone([(1,0,1), (-1,0,1), (0,1,1), (0,-1,1)]) - sage: set(rational_isomorphism_generator(K1,K1)) + sage: set(linear_isomorphisms(K1,K1)) {[-1 0 0] [ 0 -1 0] [ 0 0 1], @@ -100,6 +131,16 @@ def rational_isomorphism_generator(K1, K2): [0 1 0] [0 0 1]} + TESTS: + + Every cone should be isomorphic to itself under (at least) the + identity transformation:: + + sage: K = random_cone(max_ambient_dim=5) + sage: I = matrix.identity(QQ, K.lattice_dim()) + sage: I in linear_isomorphisms(K,K) + True + """ # There are no invertible maps between lattices of different # dimensions. @@ -196,3 +237,34 @@ def rational_isomorphism_generator(K1, K2): if Cone(r*X for r in K1.rays()).is_equivalent(K2): X.set_immutable() yield X + + +def is_linearly_isomorphic(K1,K2): + r""" + Return ``True`` if ``K1`` and ``K2`` are linearly isomorphic + over the rationals, and ``False`` otherwise. + + TESTS: + + Every cone is isomorphic to itself:: + + sage: K = random_cone(max_ambient_dim=5) + sage: is_linearly_isomorphic(K,K) + True + + Isomorphism is symmetric:: + + sage: K = random_cone(max_ambient_dim=5) + sage: J = random_cone(min_ambient_dim=K.lattice_dim(), + ....: max_ambient_dim=K.lattice_dim(), + ....: min_rays=K.nrays(), + ....: max_rays=K.nrays()) + sage: K.is_isomorphic(J) == J.is_isomorphic(K) + True + + """ + try: + next(linear_isomorphisms(K1,K2)) + return True + except StopIteration: + return False -- 2.49.0