Resolution of the Symmetric Nonnegative Inverse Eigenvalue Problem for Matrices Subordinate to a Bipartite Graph

There is a symmetric nonnegative matrix A, subordinate to a given bipartite graph G on n vertices, with eigenvalues _{12 n} if and only if, ₁ + _n 0, ₂ + _n-10,..., _m + _{n - m + 1}0, _{m + 1}0,..., _{n - m} 0, in which m is the matching numberof G. Other observations are also made about the symmetric nonnegative inverse eigenvalue problem with respect to a graph     

Some Criteria for Multivalently Starlikeness

Let S_n(p)(p, n N) be the class of functions f() = ^p + a_p+n^p+n + which are p-valently starlike in the unit disk. Some sufficient conditions for a function f() to be in the class S_n(p) are given.AMS Subject Classification (2000): primary 30C45     

Interior-point algorithms for monotone affine variational inequalities

Given ann×n matrixM, a vectorq in ⁿ , a polyhedral convex setX={x|Axb, Bx=d}, whereA is anm×n matrix andB is ap×n matrix, the affinne variational inequality problem is to findxX such that (Mx+q) ^T (y–x)0 for allyX. IfM is positive semidefinite (not necessarily symmetric), the affine variational inequality can be transformeo to a generalized complementarity problem, which can be solved in polynomial time using interior-point algorithms due to Kojima et al. We develop interior-point algorithms that exploit the particular structure of the problem, rather than direictly reducing the problem to a standard linear complemntarity problem.This work was partially supported by the Air Force Office of Scientific Research, Grant AFOSR-89-0410 and the National Science Foundation, Grant CCR-91-57632.The authors acknowledge Professor Osman Güler for pointing out the valoidity of Theorem 2.1 without further assumptions and the proof to that effect. They are also grateful for his comments to improve the presentation of this paper.     

Formulas for best extrapolation

We considern-point Lagrange-Hermite extrapolation forf(x), x>1, based uponf(x _i ),i=1(1)n, –1x _i 1, including non-distinct pointsx _i in confluent formulas involving derivatives. The problem is to find the pointsx _i that minimize the factor in the remainderP _n (x)f ⁽ⁿ⁾()/n, –1<<x subject to the condition|P _n (x)|M, –1x1,2^–n+1M2 ⁿ . The solution is significant only when a single set of pointsx _i suffices for everyx>1. The problem is here completely solved forn=1(1)4. Forn>4 it may be conjectured that there is a single minimal , 0 rn, whererr(M) is a non-decreasing function ofM, P _n (–1)=(–1) ⁿ M, and for 0rn–2, thej-th extremumP _n (x _{e, j} )=(–1) ^n–j M,j=1(1)n–r–1 (except forM=M _r ,r=1(1)n–1, whenj=1(1)n–r).     

Maximum and minimum sets for some geometric mean values

Ifv _r is ther-dimensional volume of ther-simplex formed byr+1 points taken at random from a compact setK in ⁿ , withrn, andh is a (strictly) increasing function, then the (unique) compact set that gives the minimum expected value ofh o v _r, is proved to be the ellipsoid (whenr=n) and the ball (whenr) almost everywhere. This result is established by using a single integral inequality for centrally symmetric quasiconvex functions integrated over compact rectangles.     

Free-knot Splines Approximation of s-monotone Functions

Let I be a finite interval and r,sN. Given a set M, of functions defined on I, denote by ₊ ^s M the subset of all functions yM such that the s-difference ^s y() is nonnegative on I, >0. Further, denote by ₊ ^s W _p ^r , the class of functions x on I with the seminorm x ^(r)L _p 1, such that ^s x0, >0. Let M _n (h _k ):={ _i=1 ⁿ c _i h _k (w _i t– _i )c _i ,w _i , _i R, be a single hidden layer perceptron univariate model with n units in the hidden layer, and activation functions h _k (t)=t ₊ ^k , tR, kN ₀. We give two-sided estimates both of the best unconstrained approximation E( ₊ ^s W _p ^r ,M _n (h _k ))L _q , k=r–1,r, s=0,1,...,r+1, and of the best s-monotonicity preserving approximation E( ₊ ^s W _p ^r , ₊ ^s M _n (h _k ))L _q , k=r–1,r, s=0,1,...,r+1. The most significant results are contained in theorem 2.2.     

On integer points in polyhedra: A lower bound

Given a polyhedronP we writeP _I for the convex hull of the integral points inP. It is known thatP _I can have at most135-2 vertices ifP is a rational polyhedron with size . Here we give an example showing thatP _I can have as many as ( ^n–1) vertices. The construction uses the Dirichlet unit theorem.The results of the paper were obtained while this author was visiting the Cowles Foundation at Yale University     

The asymptotic distribution of magnitude trimmed sums for distributions in the Feller class

LetX, X ₁,X ₂,... be i.i.d. with common distribution functionF. Rather than study limit behavior of the sum,S _n =X ₁++X _n , under constant normalizations, we consider the sum with ther _n summands largest in magnitude removed from the sumS _n , wherer _n andr _n n ^–10. This is known as an intermediate magnitude trimmed sum. LetF be such that lim inf_t lim inf _t EX ² I(|X|t/)t ² P((|X|>t)>0. The collection of suchF is known as the Feller class, a large class of distributions which includes all domains of attraction (in particular the stable laws). Pruitt(¹³) showed that asymptotic normality always holds for the trimmed sums ifF is in the Feller class and ifF is symmetric. Here, for anyF in the Feller class, we obtain complete results including the form of the possible limit laws and their convergence criteria, thus generalizing Pruitt's result to the asymmetric setting.This paper forms a portion of the author's Ph.D. dissertation under the supervision of Daniel C. Weiner.     

Head of the line processor sharing for many symmetric queues with finite capacity

In this paper the steady-state behavior of many symmetric queues, under the head of the line processor-sharing discipline, is investigated. The arrival process to each of n queues is Poisson, with rateA, and each queue hasr waiting spaces. A job arriving at a full queue is lost. The queues are served by a single exponential server, which has a mean raten, and splits its capacity equally amongst the jobs at the head of each nonempty queue. The normal traffic casep=/< 1 is considered, and it is assumed thatn1 andr= 0(1). A 2-term asymptotic approximation to the loss probabilityL is derived, and it is found thatL = 0(n ^–r ), for fixedp. If6=(1–p)/p 1, then the approximation is valid if n² 1 and (r+ 1)²n, and in this caseL r!/(n)^r. Numerical values ofL are obtained forr = 1,2,3,4 and 5,n = 1000,500 and 200, and various values ofp< 1. Very small loss probabilities may be obtained with appropriate values of these parameters.     

The Problem of the Pawns

In this paper we study the number M _m;n of ways to place nonattacking pawns on an m x n chessboard. We find an upper bound for M _m;n and consider a lower bound for M _m;n by reducing this problem to that of tiling an (m+1)x(n+1) board with square tiles of size 1x1 and 2x2. Also, we use the transfer-matrix method to implement an algorithm that allows us to get an explicit formula for M _m;n for given m. Moreover, we show that the double limit := lim _m;n (M _m;n ) ^1/mn exists and 2.25915263 n 2.26055675. Also, the true value of n is around 2.2591535382327...AMS Subject Classification: 05A16, 05C50, 52C20, 82B20.     

Weakly Associated Prime Filtration

Let R be a (not necessarily Noetherian) commutative ring and let M be a (not necessarily finitely generated) R-module. We characterize the modules with only finitely many weakly associated primes as those modules M admitting a chain 0 = M ₀ M ₁ ... M _n = M of submodules together with prime ideals p₁, p₂,...,p _n such that the set of weakly associated primes of M _i /M _i-1 is equal to {p _i } for all 1 i n. Let M = gr_a(M) = _n0a ⁿ M/a ⁿ⁺¹ M be the corresponding graded module over the graded ring R = gr_a(R) = _n0a ⁿ /a ⁿ⁺¹. It is shown that the union of the set of weakly associated primes of.....     

Orlik-Solomon Algebras and Tutte Polynomials

The OS algebra A of a matroid M is a graded algebra related to the Whitney homology of the lattice of flats of M. In case M is the underlying matroid of a hyperplane arrangement A in ^r , A is isomorphic to the cohomology algebra of the complement ^r A. Few examples are known of pairs of arrangements with non-isomorphic matroids but isomorphic OS algebras. In all known examples, the Tutte polynomials are identical, and the complements are homotopy equivalent but not homeomorphic.We construct, for any given simple matroid M ₀, a pair of infinite families of matroids M _n and M _n , n 1, each containing M ₀ as a submatroid, in which corresponding pairs have isomorphic OS algebras. If the seed matroid M ₀ is connected, then M _n and M _n have different Tutte polynomials. As a consequence of the construction, we obtain, for any m, m different matroids with isomorphic OS algebras. Suppose one is given a pair of central complex hyperplane arrangements A ₀ and A ₁ . Let S denote the arrangement consisting of the hyperplane {0} in ₁ . We define the parallel connection P(A ₀, A ₁), an arrangement realizing the parallel connection of the underlying matroids, and show that the direct sums A ₀ A ₁ and S P (A ₀, A ₁) have diffeomorphic complements.     

On One Counterexample in Convex Approximation

We prove the existence of a function fcontinuous and convex on [–1, 1] and such that, for any sequence {p _n} _{n= 1} of algebraic polynomials p _nof degree nconvex on [–1, 1], the following relation is true: , where ₄(t, f) is the fourth modulus of continuity of the function fand . We generalize this result to q-convex functions.     

Very tight embeddings of subspaces ofLp, 1 =p< 2, intolp n

We prove that for 1 p < r < 2, every n-dimensional subspace E of L _r, in particular l _r ⁿ , well-embeds into l _p ^m for some m (1 + $$\epsilon$$)n, where well depends on p, r, and the arbitrary $$\epsilon$$ > 0, but not on n.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

Integral Formulas for the r-Mean Curvature Linearized Operator of a Hypersurface

For a normal variation of a hypersurface M ⁿ in a space form Q _c ⁿ⁺¹ by a normal vector field fN, R. Reilly proved:

On Jordan Angles and the Triangle Inequality in Grassmann Manifolds

Let L, M and N be p-dimensional subspaces in ⁿ . Let { _j } be the angles between L and M, let { _j } be the angles between M and N, and let { _j } be the angles between L and M. Consider the orbit of the vector = (₁,...., _n ) ^p with respect to permutations of coordinates and inversions of axes. Let Z be the convex hull of this orbit. Then + Z. We discuss similar theorems for other symmetric spaces. We also obtain formula for geodesic distance for arbitrary invariant convex Finsler metrics on classical symmetric spaces.     

Beurling-Lax representations using classical Lie groups with many applications II: GL(n,©) and Wiener-Hopf factorization

The classical Beurling-Lax-invariant subspace theorem characterizes the full range simply invariant subspacesM of L _n ² as being of the formM=H _n ² where L _n×n is a phase function. Here L _n ² is the Hilbert space of measurable ⁿ-valued functions on the unit circle {e^it|0t2} which are square-integrable in norm, H _n ² is the subspace of functions in L _n ² with analytic continuation to the interior of the disk {zz|<1}, L _n×n ² is the space of measurable essentially bounded n×n matrix functions on the unit circle, and a phase function is one whose values (e^it) are unitary for a.e. t (i.e., (e^it) is in the Lie group U(n) a.e.). Halmos extended this to L ² . A subspace ML _n ² is said to beinvariant if e^it MM,simply invariant if in addition e^ikt M=(0), andfull range if 0} $$ " align="middle" border="0"> e^–iNt M is dense in L _n ² . In the Beurling-Lax representationM=H _n ² ,M uniquely determines up to a unitary constant factor on the right if one insists that (e^it)U(n). If one demands only that (e^it) GL(n,) (the group of invertible n×n complex matrices), however, there is considerably more freedom; in fact H _n ² =₁H _n ² where ₁ F and FL _n×n is outer with inverse F^–1L _n×n . More generally, we have H _n ² =[₁H _n ]^– whenever ₁=F and F is outer with F and F^–1 in L _n×n ² . (An FL _n×n ² will be said to beouter if FH _n is a dense subset of H _n ² .) In particular one can use this freedom to obtain representationsM=[H _n ]^– where the representor has values (e^it) in other matrix Lie groups. This program was carried out in accompanying work of the authors [B-H1-4] for the classical simple Lie groups U(m,n), O(p,q), O^*(2n), Sp(n,C), Sp(n,R), Sp(p,q), O(n,C), GL(n,R), U^*(2n), GL(n,R) and SL(n,C) and many applications were given. In this paper we give a natural theorem for GL(n,), by introducing the extra structure of preassigning the spaceM ^x=[H _n ]^– as well asM=[H _n ]^–. The theorems in [B-H1-4] can be derived by specializing our main result here for GL(n,) to the various subgroups which we listed.Both authors are partially supported by the National Science Foundation.     

Quantum Poisson processes and dilations of dynamical semigroups

Summary The notion of a quantum Poisson process over a quantum measure space is introduced. This process is used to construct new quantum Markov processes on the matrix algebraM _n with stationary faithful state . If (, ) is the quantum measure space in question ( a von Neumann algebra and a faithful normal weight), then the semigroupe ^tL of transition operators on (M _n , ) has generator whereu is an arbitrary unitary element of the centraliser of (M _n ,).Supported by the Netherlands Organization for Scientific Research NWO     

The eigenvalues of the Sinyukov mapping for geodesically equivalent metrics are globally ordered

Suppose all geodesics of two Riemannian metrics g and defined on a (connected, geodesically complete) manifold M ⁿ coincide. At each point x M ⁿ , consider the common eigenvalues ₁, ₂, ... , _n of the two metrics (we assume that _{1 2 n}) and the numbers . We show that the numbers _i are ordered over the entire manifold: for any two points x and y in M the number _k(x) is not greater than _k+1(y). If _k(x)= _k+1(y), then there is a point z M _n such that _k(z)= _k+1(z). If the manifold is closed and all the common eigenvalues of the metrics are pairwise distinct at each point, then the manifold can be covered by the torus.Translated from Matematicheskie Zametki, vol. 77, no. 3, 2005, pp. 412–423.Original Russian Text Copyright © 2005 by V. S. Matveev.This revised version was published online in April 2005 with a corrected issue number.