Superfluous matrices in linear complementarity

Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices and establish that in superfluous matrices of any ordern 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.     

Win probabilities and simple majorities in probabilistic voting situations

This paper considers an election between candidatesA andB in which (1) voters may be uncertain about which candidate they will vote for, and (2) the winner is to be determined by a lottery betweenA andB that is based on their vote totals. This lottery is required to treat voters equally, to treat candidates equally, and to respond nonnegatively to increased support for a candidate. The set _n of all such lottery rules based on a total ofn voters is the convex hull of aboutn/2 basic lottery rules which include the simple majority rule. For odd values ofn 3 let , and for even values ofn 4 let . With the average of then voters probabilities of voting forA, it is shown that within _n the simple majority rule maximizes candidateA's overall win probability whenever , and that(n) is the smallest number for which this is true. Similarly, the simple majority rule maximizesB's overall win probability whenever (the average of the voters probabilities of voting forB) is as large as(n). This research was supported by the National Science Foundation, Grant SOC 75-00941.     

A modification of todd's triangulationJ 3

When we apply the fixed point computing method to mappings which are affine in some variables, we show that, to generate a sequence which converges to a fixed point, the mesh size need not be decreased in these coordinates. This paper modifies the triangulationJ ₃ with continuous refinement of mesh size to a triangulation such that the mesh size of in some given coordinates is constant and the mesh size in the other coordinates shrinks to zero.     

Operators of fibered groups

Let (G, ) denote a finite groupG with fibration . The group Aut (G, ) of operators of (G, ) is closely related to the group of collineations of (G, ). In this paper we investigate the geometric properties imposed on (G, ) by requiring that Aut (G, )=AutG. We find that in many instances this algebraic property restricts the geometry to a very special form.Dedicated to Professor Helmut Karzel on the occasion of his 60th birthday.     

Complétude des métriques lorentziennes de\mathbb{T}^2 et difféomorphismes du cercle

Let and the foliations by the null geodesics of some lorentzian metricg on the torus . We analyse how geodesic completeness properties ofg are related to the dynamics of and .     

Transvection free groups and invariants of polynomial tensor exterior algebras

Let :GGl(n, ) be a representation of a finite groupG over a field such that the ring of invariants is a polynomial algebra . It is known that in the nonmodular case (i.e., when the order of the group is not divisible by the characteristic of ), the invariants ofG acting on the tensor product of a polynomial and an exterior algebra are given by ,d denoting the exterior derivative. We show that in the modular case, the ring of invariants in is of this form if and only if is a polynomial algebra and all pseudoreflections in (G) are diagonalizable.     

On the isomorphisms and automorphism groups of circulants

Denote byC _n(S) the circulant graph (or digraph). LetM be a minimal generating element subset ofZ _n, the cyclic group of integers modulon, and In this paper, we discuss the problems about the automorphism group and isomorphisms ofC _n(S). When M S , we determine the automorphism group ofC _n(S) and prove that for any T if and only ifT = S, where is an integer relatively prime ton. The automorphism groups and isomorphisms of some other types of circulant graphs (or digraphs) are also considered. In the last section of this paper, we give a relation between the isomorphisms and the automorphism groups of circulants.     

Some proximity and sensitivity results in quadratic integer programming

We show that for any optimal solution for a given separable quadratic integer programming problem there exist an optimal solution for its continuous relaxation such that wheren is the number of variables and(A) is the largest absolute subdeterminant of the integer constraint matrixA. Also for any feasible solutionz, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution having greater objective function value and with . We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectorsb andb, respectively, depends linearly on b–b₁. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.This research was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998.     

Homogeneous algebraic varieties defined by Jordan pairs

Every Jordan pair defines an algebraic varietyX containing as a dense open subset.X is projective (affine) if and only if is separable (radical). The Picard group ofX is generated by the irreducible factors of the generic norm of . If is separable then the automorphism group ofX is the projective group of .     

Uneven distribution of ventilation—perfusion ratios in lungs estimated by a modified Newton method

The uneven distribution of ventilation—perfusion ratios ( ) in diseased lungs is the major cause of arterial hypoxemia. Farhi and Yokoyama (1967) and Yokoyama and Farhi (1967) were the first who used physiologically inert gases as indicator gases to assess the uneven distribution of Wagner and his coworkers in San Diego (1977b) extended the method and elaborated the multiple inert gas elimination technique in which blood flows in 50 compartments with different were estimated based on data for 6 indicator gases. They analyzed the indicator gas data through an enforced smoothing technique with the ridge regression. To get smooth distributions, they introduced a weighting function for compartments and an additional treatment for the non-negativity of the blood flow. The weighting function was empirically obtained. We analyzed the data without putting any weights on compartments nor any additional treatment for non-negativity of blood flow. The analytical method in the present study was a modified Newton method, which is one of the enforced smoothing method. Our method was capable of recovering all distribution patterns that were found through the method reported by Wagner et al. (1977b).     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Reliability bounds in DFRA class with known mean and variance

ＲＥＬＩＡＢＩＬＩＴＹＢＯＵＮＤＳＩＮＤＦＲＡＣＬＡＳＳＷＩＴＨＫＮＯＷＮＭＥＡＮ　ＡＮＤ　ＶＡＲＩＡＮＣＥＣＨＥＮＧＫＡＮ（程侃）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ,ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ,Ｂ...     

Rings of regular functions on nilpotent orbits and their covers

Summary LetG be a complex semisimple algebraic group with Lie algebra . Let be a nilpotentG-orbit, its ring of regular functions. We derive a formula for as aG-module and prove some partial results on a cover of . We then relate this formula to various existing multiplicity formulas forK-types in Harish-Chandra bimodules ofG.Supported by National Science Foundation Grant DMS-8505550     

Near boundary behavior of primal—dual potential reduction algorithms for linear programming

This paper is concerned with selection of the-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + , ), the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close ton + . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that can be sometimes chosen in a wide range [n + , ) while still guaranteeing the currently best convergence rate of O( L) iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.Research supported in part by NSF Grant DDM-8922636.     

Gray codes from antimatroids

We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.For antimatroid (E, ), letJ( ) denote the graph whose vertices are the sets of , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( ;k) to be the subgraph ofJ( )² induced by the sets in with exactlyk elements. Both graphsJ( ) andJ( ;k) are connected, and the former is bipartite.We show that there is a Hamiltonian cycle inJ( )×K ₂. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( ;k) has a Hamilton path if (E, ) is the poset antimatroid of a series-parallel poset.Similarly, we show thatG( )×K ₂ is Hamiltonian, whereG( ) is the basic word graph of a language antimatroid (E, ). This result was known previously for poset antimatroids.Research supported in part by NSERC.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.     

Extensions of abelian 2-groups byL 2(q) under irreducible action

We study groups . which are nonsplit extensions of elementary Abelian 2-groups A by H ∼ L₂(q), with H acting on A irreducibly and A ≠ Z₂. Related cohomology groups are computed. Groups are given a complete regimentation for odd q. Moreover, there is only one, up to isomorphism, group for q ≡ −1 (mod 4) and there is none for q ≡ 1 (mod 4). We also present an explicit construction of treated as automorphism groups of some loops close to extraspecial groups, the so-called “code loops” brought in sight by Griess and Parker. Supported by Byelorus Republican Foundation for Fundamental Research grant No. F97M-02. Translated fromAlgebra i Logika, Vol. 39, No. 3, pp. 280–319, May–June, 2000.     

Packing two graphs of ordern having total size at most 2n − 2

Two graphsG andH of the same order are packable ifG can be embedded in the complement ofH. In this paper we give a complete characterization of two graphs of ordern having total size at most 2n – 2 which are packable. This result extends an earlier result of B. Bollobás and S.E. Eldridge.     

A new product of algebras and a type reduction theorem

A construction is defined which associates, to every algebra of a fixed but arbitrary finite similarity type, a groupoidF . The identities ofF are finitely based if and only if those of are, andF is finite if and only if is finite. Up to isomorphism,F has the same endomorphism monoid and subalgebra lattice as , but the congruence lattice ofF is the result of adjoining a new 1 to the congruence lattice of .F is functorial, preserves the satisfaction (and the non-satisfaction) of most Mal'cev conditions, and produces, by composition with the operation of forming the generated variety, an isomorphism of the lattice of varieties of fixed type to an interval in the lattice of varieties of groupoids.The construction makes use of a new product operation, applicable to two algebras of differing similarity types, which is introduced and studied in this paper.Research supported by National Science Foundation grant MCS-8103455.Presented by K. A. Baker.     

The number oft-wise balanced designs

We prove that the number oft-wise balanced designs of ordern is asymptotically , provided that blocks of sizet are permitted. In the process, we prove that the number oft-profiles (multisets of block sizes) is bounded below by and above by for constants c₂>c₁>0.     

Common invariant subspaces for collections of operators

Let be a collection of bounded operators on a Banach spaceX of dimension at least two. We say that is finitely quasinilpotent at a vectorx ₀X whenever for any finite subset of the joint spectral radius of atx ₀ is equal 0. If such collection contains a non-zero compact operator, then and its commutant have a common non-trivial invariant, subspace. If in addition, is a collection of positive operators on a Banach lattice, then has a common non-trivial closed ideal. This result and a recent remarkable theorem of Turovskii imply the following extension of the famous result of de Pagter to semigroups. Let be a multiplicative semigroup of quasinilpotent compact positive operators on a Banach lattice of dimension at least two. Then has a common non-trivial invariant closed ideal.This work was supported by the Research Ministry of Slovenia.