Classes of matrices associated with the optimal assignment problem

Let E=[e_ij] be a matrix with integral elements, and let x be an indeterminate defined over the rational field Q. We investigate matrices of the form X=[x^e_ij] (i = 1,…, m; j = 1,…, n; m ⩽ n). We may multiply the lines (rows or columns) of the matrix X by suitable integral powers of x in various ways and thereby transform X into a matrix Y=[x^f_ij] such that the f_ij are nonnegative integers and each line of Y contains at least one element x⁰ = 1. We call Y a normalized form of X, and we denote by S(X) the class of all normalized forms associated with a given matrix X. The classes S(X) have a fascinating combinatorial structure, and the present paper is a natural outgrowth and extension of an earlier study. We introduce new concepts such as an elementary transformation called an interchange. We prove, for example, that two matrices in the same class are transformable into one another by interchanges. Our analysis of the class S(X) also yields new insights into the structure of the optimal assignments of the matrix E by way of the diagonal products of the matrix X.     

A note on reflexivity in Banach spaces

For any normed spaceX, the unit ball ofX is weak *-dense in the unit ball ofX ^**. This says that for any ε>0, for anyF in the unit ball ofX ^**, and for anyf ₁,…,f _n inX ^*, the system of inequalities |f _i(x)?F(f _i)|≤ε can be solved for somex in the unit ball ofX. The author shows that the requirement that ε be strictly positive can be dropped only ifX is reflexive.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

Zeros of analytic functions and norms of inverse matrices

Letk _n be the smallest constant such that for anyn-dimensional normed spaceX and any invertible linear operatorT ∈L(X) we have $|\det (T)| \cdot ||T^{ - 1} || \le k_n |||T|^{n - 1} $ . LetA ₊ be the Banach space of all analytic functionsf(z)=Σ _k≥0 a _kz^k on the unit diskD with absolutely convergent Taylor series, and let ‖f‖A ₊=σ _k≥0 |ακ|; define ? _n on $\overline D ^n $ by $ \begin{array}{l} \varphi _n \left( {\lambda _1 ,...,\lambda _n } \right) \\ = inf\left\{ {\left\| f \right\|_{A + } - \left| {f\left( 0 \right)} \right|; f\left( z \right) = g\left( z \right)\prod\limits_{i = 1}^n {\left( {\lambda _1 - z} \right), } g \in A_ + , g\left( 0 \right) = 1 } \right\} \\ \end{array} $ . We show thatk _n=sup {? _n(λ₁,…, λ _n ); (λ₁,…, λ _n )∈ $\overline D ^n $ }. Moreover, ifS is the left shift operator on the space ?∞:S(x ₀,x ₁, …,x _p, …)=(x ₁,…,x _p,…) and if J_n(S) denotes the set of allS-invariantn-dimensional subspaces of ?∞ on whichS is invertible, we have $k_n = \sup \{ |\det (S|_E )|||(S|_E )^{ - 1} ||E \in J_n (S)\} $ . J. J. Schäffer (1970) proved thatk _n≤√en and conjectured thatk _n=2, forn≥2. In factk ₃>2 and using the preceding results, we show that, up to a logarithmic factor,k _n is of the order of √n whenn→+∞.     

Characterization of a class of bivariate distribution functions

Let F_X,Y(x,y) be a bivariate distribution function and P_n(x), Q_m(y), n, m = 0, 1, 2,…, the orthonormal polynomials of the two marginal distributions F_X(x) and F_Y(y), respectively. Some necessary conditions are derived for the co-efficients c_n, n = 0, 1, 2,…, if the conditional expectation E[P_n(X) ∥ Y] = c_nQ_n(Y) holds for n = 0, 1, 2,…. Several examples are given to show the application of these necessary conditions.     

The rate of the normal approximation for jackknifingU-statistics

Let U_n be a U-statistic with symmetric kernel h(x,y) such that Eh(X_1,X_2)=θ and Var E[h(X_1,X_2)-θ|X_j]>0.Let f(x) be a function defined on R and f″ be bounded.If f(θ) is the parameterof interest,a natural estimator is f(U_n).It is known that the distribution function of z_n=(n~(1/2){Jf(U_n)-f(θ)})/(S_n~*) converges to the standard normal distribution Φ(x) as n→∞,where Jf(U_n) isthe jackknife estimator of f(U_n),and S_n~(*2) is the jackknife estimator of the asymptotic variance ofn~(1/2) Jf(U_n).It is of theoretical value to study the rate of the normal approximation of the statistic.In this paper,assuming the existence of fourth moment of h(X_1,X_2),we show that(?)|P{z_n≤x}-Φ(x)|=O(n~(-1/2)log n).This improves the earlier results of Cheng(1981).     

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

Fixed point theory and product,sub-, super-spaces

In this paper, we definen-segmentwise metric spaces and then we prove the following results:

1. (i)|Let (X, d) be ann-segmentwise metric space. ThenX ⁿ has the fixed point property with respect to uniformly continuous bounded functions if and only if, for any continuous functionF: C ^*(X) → C^*(X) and for anyn-tuple of distinct points x₁, x₂, ?, x_n ∈X, there exists anh ∈C ^*(X) such that $$F(h)(x_1 ) = h(x_1 ),i = 1,2,...,n;$$ whereC ^*(X) has either the uniform topology or the subspace product (Tychonoff) topology \((C^ * (X) \subseteq X^X )\) .
2. LetX _i (i = 1, 2, ?) be countably compact Hausdorff spaces such thatX ₁ × ? × X_n has the fixed point property for alln ∈N Then the product spaceX ₁ × X₂ × ? has the fixed point property. We shall also discuss several problems in the Fixed Point Theory and give examples if necessary. Among these examples, we have:
3. There exists a connected metric spaceX which can be decomposed as a disjoint union of a closed setA and an open setB such thatA andB have the fixed point property andX does not have.
4. There exists a locally compact metrizable spaceX which has the fixed point property but its one-point compactificationX ⁺ does not have the fixed point property.

Other relevant results and examples will be presented in this paper.     

A limit theorem for order preserving nonexpansive operators inL 1

We prove the following theorem:Let T be an order preserving nonexpansive operator on L ₁ (μ) (or L ₁ ⁺ ) of a σ-finite measure, which also decreases theL _∞-norm, and let S=tI+(1?t)T for 0<t<1. Then for everyf ∈ L_p (1<p<∞),the sequence S ⁿf converges weakly in L_p. (The assumptions do not imply thatT is nonexpansive inL _p for anyp>1, even ifμ is finite.) For the proof we show that ∥S ⁿ⁺¹ f?S ⁿf∥ _p → 0 for everyf ∈L _p, 1<p<∞, and apply toS the following theorem:Let T be order preserving and nonexpansive in L ₁ ⁺ , and assume that T decreases theL _∞-norm. Then forg ∈L _p (1<p<∞) Tⁿg is weakly almost convergent. If forf ∈ L_p we have T ⁿ⁺¹ f?T ⁿ f → 0weakly, then T ⁿf converges weakly in L_p (1<p<∞).     

Nonparametric estimation of mixed partial derivatives of a multivariate density

On the basis of a random sample of size n on an m-dimensional random vector X, this note proposes a class of estimators f_n^(p) of f^(p), where f is a density of X w.r.t. a σ-finite measure dominated by the Lebesgue measure on R^m, p = (p₁,…,p_m), p_j ≥ 0, fixed integers, and for x = (x₁,…,x_m) in R^m, f^(p)(x) = ?^p₁+…+p_m f(x)/(?^p₁x₁ … ?^p_mx_m). Asymptotic unbiasedness as well as both almost sure and mean square consistencies of f_n^(p) are examined. Further, a necessary and sufficient condition for uniform asymptotic unbisedness or for uniform mean square consistency of f_n^(p) is given. Finally, applications of estimators of this note to certain statistical problems are pointed out.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

Increasing and decreasing operators on complete lattices

The (isotone) map f: X → X is an increasing (decreasing) operator on the poset X if f(x) ? f²(x) (f²(x) ? f(x), resp.) holds for each x ∈ X. Properties of increasing (decreasing) operators on complete lattices are studied and shown to extend and clarify those of closure (resp. anticlosure) operators. The notion of the decreasing closure, $\text{f}$, (the increasing anticlosure, $\text{f}$,) of the map f: X → X is introduced extending that of the transitive closure, $\text{f}\text{?}$, of f. $\text{f}\text{f}$, and $\text{f}$ are all shown to have the same set of fixed points. Our results enable us to solve some problems raised by H. Crapo. In particular, the order structure of H(X), the set of retraction operators on X is analyzed. For X a complete lattice H(X) is shown to be a complete lattice in the pointwise partial order. We conclude by claiming that it is the increasing-decreasing character of the identity maps which yields the peculiar properties of Galois connections. This is done by defining a u-v connection between the posets X and Y, where u: X → X (v: Y → Y) is an increasing (resp. decreasing) operator to be a pair f, g of maps f; X → Y, g: Y → X such that gf ? u, fg ? v. It is shown that the whole theory of Galois connections can be carried over to u-v connections.     

Multiobjective programming and penalty functions

This paper generalizes the penalty function method of Zang-will for scalar problems to vector problems. The vector penalty function takes the form $$g(x,\lambda ) = f(x) + \lambda ^{ - 1} P(x)e,$$ wheree ?R ^m, with each component equal to unity;f:R ⁿ →R ^m, represents them objective functions {f ⁱ} defined onX \( \subseteq \) R ⁿ; λ ∈R ¹, λ>0;P:R ⁿ →R ¹ X \( \subseteq \) Z \( \subseteq \) R ⁿ,P(x)≦0, ∨x ∈R ⁿ,P(x) = 0 ?x ∈X. The paper studies properties of {E (Z, λ _r )} for a sequence of positive {λ _r } converging to 0 in relationship toE(X), whereE(Z, λ _r ) is the efficient set ofZ with respect tog(·, λ_r) andE(X) is the efficient set ofX with respect tof. It is seen that some of Zangwill's results do not hold for the vector problem. In addition, some new results are given.     

A Nim-like Game and Dynamic Recurrence Relations

The nim-like game 〈n, f; X, Y〉 is defined by an integer n ≥ 2 a constraint function f, and two players and X and Y. Players X and Y alternate taking coins from a pile of n coins, with X taking the first turn. The winner is the one who takes the last coin. On the kth turn, a player may remove t_k coins, where 1 ≤ t₁ ≤ n ? 1 and 1 ≤ t_k ≤ max{1, f(t_k?1) for k > 1. Let the set S_f = {1} ∪ {n| there is a winning strategy for Y in the nim-like game 〈n, f; X, Y〉}. In this paper, an algorithm is provided to construct the set S_f = {a₁, a₂,…} in an increasing sequence when the function f(x) is monotonic. We show that if the function f(x) is linear, then there exist integers n₀ and m such that a_n+1 = a_n + a_n?m for n > n₀ and we give upper and lower bounds for m (dependent on f. A duality is established between the asymptotic order of the sequence of elements in S_f and the degree of the function f(x). A necessary and sufficient condition for the sequence {a₀, a₁, a₂,…} of elements in S_f to satisfy a regular recurrence relation is described as well.     

On dimensionally exotic maps

We call a value y = f(x) of a map f: X → Y dimensionally regular if dimX ≤ dim(Y × f ^?1(y)). It was shown in [6] that if a map f: X → Y between compact metric spaces does not have dimensionally regular values, then X is a Boltyanskii compactum, i.e., a compactum satisfying the equality dim(X × X) = 2dim X ? 1. In this paper we prove that every Boltyanskii compactum X of dimension dim X ≥ 6 admits a map f: X → Y without dimensionally regular values. We show that the converse does not hold by constructing a 4-dimensional Boltyanskii compactum for which every map has a dimensionally regular value.     

Isometric factorization of weakly compact operators and the approximation property

Using an isometric version of the Davis, Figiel, Johnson, and Pe?czyński factorization of weakly compact operators, we prove that a Banach spaceX has the approximation property if and only if, for every Banach spaceY, the finite rank operators of norm ≤1 are dense in the unit ball ofW(Y,X), the space of weakly compact operators fromY toX, in the strong operator topology. We also show that, for every finite dimensional subspaceF ofW(Y,X), there are a reflexive spaceZ, a norm one operatorJ:Y→Z, and an isometry Φ :F →W(Y,X) which preserves finite rank and compact operators so thatT=Φ(T) oJ for allT∈F. This enables us to prove thatX has the approximation property if and only if the finite rank operators form an ideal inW(Y,X) for all Banach spacesY.     

Sequences of contractions on L1-spaces

Let T_n, n = 1,2,… be a sequence of linear contractions on the space where is a finite measure space. Let M be the subspace of L¹ for which T_ng → g weakly in L¹ for g?M. If T_n1 → 1 strongly, then T_nf → f strongly for all f in the closed vector sublattice in L¹ generated by M.This result can be applied to the determination of Korovkin sets and shadows in L¹. Given a set G ? L¹, its shadow S(G) is the set of all f?L¹ with the property that T_nf → f strongly for any sequence of contractions T_n, n = 1, 2,… which converges strongly to the identity on G; and G is said to be a Korovkin set if S(G) = L¹. For instance, if 1 ?G, then, where M is the linear hull of G and $\text{B}$_M is the sub-σ-algebra of $\text{B}$ generated by {x?X: g(x) > 0} for g?M. If the measure algebra is separable, has Korovkin sets consisting of two elements.     

Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions

A function f(x) defined on $\text{X}$ = $\text{X}$₁ × $\text{X}$₂ × … × $\text{X}$_n where each $\text{X}$_i is totally ordered satisfying f(x ∨ y) f(x ∧ y) ≥ f(x) f(y), where the lattice operations ∨ and ∧ refer to the usual ordering on $\text{X}$, is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies ?DΣ^?1D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

Conditional limit theorems for exponential families and finite versions of de Finetti's theorem

Consider an exponential familyP _λ which is maximal, smooth, and has uniformly bounded standardized fourth moments. Consider a sequenceX ₁,X ₂,... of i.i.d. random variables with parameter λ. LetQ _nsk be the law ofX ₁,...,X _k given thatS _n=X ₁+...+X _n=s. Choose λ so thatE _λ(X ₁)=s/n. Ifk andn→∞ butk/n→0, then $$\parallel Q_{nsk} - P_\lambda ^k \parallel = \gamma \frac{k}{n} + o\left( {\frac{k}{n}} \right)$$ where γ=1/2E{|1?Z ²|} andZ isN(0,1). The error term is uniform ins, the value ofS _n. Similar results are given fork/n→θ and for mixtures of theP _λ ^k . Versions of de Finetti's theorem follow.