Positive block matrices and numerical ranges

Any positive matrix M partitioned in four n-by-n blocks satisfies the unitarily invariant norm inequality $6M6\le 6M_{1,1}+M_{2,2}+\omega I6$, where ω is the width of the numerical range of $M_{1,2}$. Some related inequalities and a reverse Lidskii majorization are given.     

Reachability analysis of linear systems using support functions

This work is concerned with the algorithmic reachability analysis of continuous-time linear systems with constrained initial states and inputs. We propose an approach for computing an over-approximation of the set of states reachable on a bounded time interval. The main contribution over previous works is that it allows us to consider systems whose sets of initial states and inputs are given by arbitrary compact convex sets represented by their support functions. We actually compute two over-approximations of the reachable set. The first one is given by the union of convex sets with computable support functions. As the representation of convex sets by their support function is not suitable for some tasks, we derive from this first over-approximation a second one given by the union of polyhedrons. The overall computational complexity of our approach is comparable to the complexity of the most competitive available specialized algorithms for reachability analysis of linear systems using zonotopes or ellipsoids. The effectiveness of our approach is demonstrated on several examples.     

A construction of commutative nilsemigroups

All commutative nilsemigroups are constructed from congruences on free commutative semigroups.     

Maximal Elements Under Reference-Dependent Preferences with Applications to Behavioral Traps and Games

We study reference-dependent preference relations defined by a real-valued bivariate function and prove an existence criterion for maximal elements. Then we formulate a generalized version of the well-known Brondsted maximum principle and apply it to behavioral traps and Nash equilibrium in games with preference relations that are not necessarily partial orders.     

On the solitaire cone and its relationship to multi-commodity flows

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:?1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;?2. a related NP-completeness result;?3. a method of generating large classes of facets;?4. a complete characterization of 0-1 facets;?5. exponential upper and lower bounds (in the dimension) on the number of facets;?6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;?7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards. Received: July 1996 / Accepted: February 2000?Published online February 22, 2001     

Homogenization of divergence-form operators with lower-order terms in random media

The probabilistic machinery (Central Limit Theorem, Feynman-Kac formula and Girsanov Theorem) is used to study the homogenization property for PDE with second-order partial differential operator in divergence-form whose coefficients are stationary, ergodic random fields. Furthermore, we use the theory of Dirichlet forms, so that the only conditions required on the coefficients are non-degeneracy and boundedness. Received: 27 August 1999 / Revised version: 27 October 2000 / Published online: 26 April 2001