Order isomorphisms in cones and a characterization of duality for ellipsoids

We study order isomorphisms in finite-dimensional ordered vector spaces. We generalize theorems of Alexandrov, Zeeman, and Rothaus (valid for ??non-angular?? cones) to wide classes of cones, including in particular polyhedral cones, using a different and novel geometric method. We arrive at the following result: whenever the cone has more than n generic extremal vectors, an order isomorphism must be affine. In the remaining case, of precisely n extremal rays, the transform has a restricted diagonal form. To this end, we prove and use a new version of the well-known Fundamental theorem of affine geometry. We then apply our results to the cone of positive semi-definite matrices and get a characterization of its order isomorphisms. As a consequence, the polarity mapping is, up to a linear map, the only order-reversing isomorphism for ellipsoids.     

Maximal exponents of polyhedral cones (II)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rⁿ. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that the maximum value of γ(K) as K runs through all n-dimensional minimal cones (i.e., cones having n+1 extreme rays) is n²-n+1 if n is odd, and is n²-n if n is even, the maximum value of the exponent being attained by a minimal cone with a balanced relation for its extreme vectors. The K-primitive matrices A such that γ(A) attain the maximum value are identified up to cone-equivalence modulo positive scalar multiplication.     

Maximal exponents of polyhedral cones (I)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rn. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that if K is an n-dimensional polyhedral cone with m extreme rays then for any K-primitive matrix A, γ(A)?(mA−1)(m−1)+1, where mA denotes the degree of the minimal polynomial of A, and the equality holds only if the digraph (E,P(A,K)) associated with A (as a cone-preserving map) is equal to the unique (up to isomorphism) usual digraph associated with an m×m primitive matrix whose exponent attains Wielandt's classical sharp bound. As a consequence, for any n-dimensional polyhedral cone K with m extreme rays, γ(K)?(n−1)(m−1)+1. Our work answers in the affirmative a conjecture posed by Steve Kirkland about an upper bound of γ(K) for a polyhedral cone K with a given number of extreme rays.     

Polyhedral cones and positive operators

Some results are obtained relating topological properties of polyhedral cones to algebraic properties of matrices whose columns are the extremal vectors of the cone. In addition, several characterizations of positive operators on polyhedral cones are given.     

Projection onto polyhedra in outer representation

The projection of the origin onto an n-dimensional polyhedron defined by a system of m inequalities is reduced to a sequence of projection problems onto a one-parameter family of shifts of a polyhedron with at most m + 1 vertices in n + 1 dimensions. The problem under study is transformed into the projection onto a convex polyhedral cone with m extreme rays, which considerably simplifies the solution to an equivalent problem and reduces it to a single projection operation. Numerical results obtained for random polyhedra of high dimensions are presented.     

Polyhedral combinatorics of UPGMA cones

Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm. The partition lattice informs the study of UPGMA trees. We give a closed form for the extreme rays of UPGMA cones on n taxa, and compute the spherical volumes of the UPGMA cones for small n.     

On the geometry of complete intersection toric varieties

In this paper we give a geometric characterization of the cones of toric varieties that are complete intersections. In particular, we prove that the class of complete intersection cones is the smallest class of cones which is closed under direct sum and contains all simplex cones. Further, we show that the number of the extreme rays of such a cone, which is less than or equal to 2n − 2, is exactly 2n − 2 if and only if the cone is a bipyramidal cone, where n > 1 is the dimension of the cone. Finally, we characterize all toric varieties whose associated cones are complete intersection cones. Received: 4 July 2005     

Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

Locally minimal topological groups 2

We continue in this paper the study of locally minimal groups started in Außenhofer et al. (2010) [4]. The minimality criterion for dense subgroups of compact groups is extended to local minimality. Using this criterion we characterize the compact abelian groups containing dense countable locally minimal subgroups, as well as those containing dense locally minimal subgroups of countable free-rank. We also characterize the compact abelian groups whose torsion part is dense and locally minimal. We call a topological group G almost minimal if it has a closed, minimal normal subgroup N such that the quotient group G/N is uniformly free from small subgroups. The class of almost minimal groups includes all locally compact groups, and is contained in the class of locally minimal groups. On the other hand, we provide examples of countable precompact metrizable locally minimal groups which are not almost minimal. Some other significant properties of this new class are obtained.     

The cone of nonnegative polynomials with nonnegative coefficients and linear operators preserving this cone

Let be the cone of real univariate polynomials of degree ≤ 2n which are nonnegative on the real axis and have nonnegative coefficients. We describe the extremal rays of this convex cone and the class of linear operators, acting diagonally in the standard monomial basis, preserving this cone.     

Critical angles in random polyhedral cones

This work concerns the angular structure of random polyhedral cones generated by p stochastically independent vectors uniformly distributed on the unit sphere of Rn. We comment on the expected number of critical angles and the mathematical expectation of the extremal angles.     

Tropical polar cones, hypergraph transversals, and mean payoff games

We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.     

Quasisymmetrically minimal uniform Cantor sets

The uniform Cantor set E(n,c) of Hausdorff dimension 1, defined by a bounded sequence n of positive integers and a gap sequence c, is shown to be minimal for 1-dimensional quasisymmetric maps.     

On a cone covering problem

Given a set of polyhedral cones C₁,…,Ck⊂Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computational complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi.     

On the stability of minimal cones in warped products

In a seminal paper published in 1968, J. Simons proved that, for n ≤ 5, the Euclidean (minimal) cone CM, built on a closed, oriented, minimal and non totally geodesic hypersurface M ⁿ of \(\mathbb{S}^{n + 1} \) is unstable. In this paper, we extend Simons’ analysis to warped (minimal) cones built over a closed, oriented, minimal hypersurface of a leaf of suitable warped product spaces. Then, we apply our general results to the particular case of the warped product model of the Euclidean sphere, and establish the unstability of CM, whenever 2 ≤ n ≤ 14 and M ⁿ is a closed, oriented, minimal and non totally geodesic hypersurface of \(\mathbb{S}^{n + 1} \) .     

Generalized inverses of cone preserving maps

Let K₁ and K₂ be solid cones in Rⁿ and R^m respectively, and let A be a linear operator such that AK₁?K₂. Necessary and sufficient conditions for the existence of various kinds of generalized inverses of A taking K₂ into K₁ are given. Projections which belong to π(K), the set of all linear operators that preserve a are studied. In particular, it is proved that a projection P in π(K) is a simplicial nonnegative linear combination of its rank-one operators iff Im P∩K is a simplical cone. An open question of Burns, Fiedler, and Haynsworth concerning minimal generating matrices of polyhedral cones is also extended and answered affirmatively.     

Locating minimal sets using polyhedral cones

In this paper, we develop a theory of localization for minimal sets of a family S of nonempty subsets of Rⁿ by considering polyhedral cones. To this end, we consider the first method to locate all efficient points of a nonempty set A⊂Rⁿ introduced by Yu (1974) [10].     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.     

Normal Fans of Polyhedral Convex Sets

The normal fan of a polyhedral convex set in ? ⁿ is the collection of its normal cones. The structure of the normal fan reflects the geometry of that set. This paper reviews and studies properties about the normal fan. In particular, it investigates situations in which the normal fan of a polyhedral convex set refines, or is a subfan of, that of another set. It then applies these techniques in several examples. One of these concerns the face structure and normal manifold of the critical cone of a polyhedral convex set associated with a point in ? ⁿ . Another concerns how perturbation of the right hand side of the linear constraints defining such a set affects the normal fan and the face structure.     

Additive representation of symmetric inverse M-matrices and potentials

In this article we characterize the closed cones respectively generated by the symmetric inverse M-matrices and by the inverses of symmetric row diagonally dominant M-matrices. We show the latter has a finite number of extremal rays, while the former has infinitely many extremal rays. As a consequence we prove that every potential is the sum of ultrametric matrices.