The Choquet integral representation in the affine vector-valued case

LetX be any compact convex subset of a locally convex Hausdorff space andE be a complex Banach space. We denote byA(X, E) the space of all continuous and affineE-valued functions defined onX. In this paper we prove thatX is a Choquet simplex if and only if the dual ofA(X, E) is isometrically isomorphic by a selection map toM _m (X, E*), the space ofE*-valued,w*-regular boundary measures onX. This extends and strengthens a result of G. M. Ustinov. To do this we show that for any compact convex setX, each element of the dual ofA(X, E) can be represented by a measure inM _m (X, E*) with the same norm, and this representation is unique if and only ifX is a Choquet simplex. We also prove that ifX is metrizable andE is separable then there exists a selection map from the unit ball of the dual ofA(X, E) into the unit ball ofM _m (X, E*) which is weak* to weak*-Borel measurable.This work will constitute a portion of the author's Ph.D. Thesis at the University of Illinois.     

Chaos caused by a strong-mixing measure-preserving transformation

The chaos caused by a strong-mixing preserving transformation is discussed and it is shown that for a topological spaceX satisfying the second axiom of countability and for an outer measurem onX satisfying the conditions: (i) every non-empty open set ofX ism-measurable with positivem-measure; (ii) the restriction ofm on Borel σ-algebra ℬ(X) ofX is a probability measure, and (iii) for everyY⊂X there exists a Borel setB⊂ℬ(X) such thatB⊃Y andm(B) =m(Y), iff:X→X is a strong-mixing measure-preserving transformation of the probability space (X, ℬ(X),m), and if {m}, is a strictly increasing sequence of positive integers, then there exists a subsetC⊂X withm (C) = 1, finitely chaotic with respect to the sequence {m _i}, i.e. for any finite subsetA ofC and for any mapF:A→X there is a subsequencer _i such that lim_i→∞ f ^r i(a) =F(a) for anya ∈A. There are some applications to maps of one dimension. the National Natural Science Foundation of China.     

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Playing with admissibility spectra

Jensen showed that any countable sequenceA ofA-admissibles is the initial part of the admissibility spectrum of a realR. His construction generalizes straightforwardly to Σ _n -admissibles. This adaptation makes admissibles not inA R-inadmissible. We strengthen Jensen’s theorem by requiring that Σ _n (A)-admissibles not inA be Σ _m (R)-admissible or Σ _m (R)-non-projectible, form <n. The contents of this paper formed part of the author’s doctoral thesis. He would like to thank Professor Sy Friedman for his capable advising, and the NSF and MIT for their financial support.     

On subgroups containing non-trivial normal subgroups

We prove that ifA≠1 is a subgroup of a finite groupG and the order of an element in the centralizer ofA inG is strictly larger (larger or equal) than the index [G:A], thenA contains a non-trivial characteristic (normal) subgroup ofG. Consequently, ifA is a stabilizer in a transitive permutation group of degreem>1, thenexp(Z(A))<m. These theorems generalize some recent results of Isaacs and the authors.     

Krylov sequences of maximal length and convergence of GMRES

In most practical cases, the convergence of the GMRES method applied to a linear algebraic systemAx=b is determined by the distribution of eigenvalues ofA. In theory, however, the information about the eigenvalues alone is not sufficient for determining the convergence. In this paper the previous work of Greenbaum et al. is extended in the following direction. It is given a complete parametrization of the set of all pairs {A, b} for which GMRES(A, b) generates the prescribed convergence curve while the matrixA has the prescribed eigenvalues. Moreover, a characterization of the right hand sidesb for which the GMRES(A, b) converges exactly inm steps, wherem is the degree of the minimal polynomial ofA, is given. This work was supported by AS CR Grant A2030706. Part of the work was performed while the third author visited Instituto di Analisi Numerica (IAN CNR).     

A-stable block implicit one-step methods

A class of methods for solving the initial value problem for ordinary differential equations is studied. We developr-block implicit one-step methods which compute a block ofr new values simultaneously with each step of application. These methods are examined for the property ofA-stability. A sub-class of formulas is derived which is related to Newton-Cotes quadrature and it is shown that for block sizesr=1,2,..., 8 these methods areA-stable while those forr=9,10 are not. We constructA-stable formulas having arbitrarily high orders of accuracy, even stiffly (strongly)A-stable formulas.     

Some relationships between implicit Runge-Kutta,collocation and Lanczosτ methods,and their stability properties

In this paper relationships between various one-step methods for the initial value problem in ordinary differential equations are discussed and a unified treatment of the stability properties of the methods is given. The analysis provides some new results on stability as well as alternative derivations for some known results. The term stability is used in the sense ofA-Stability as introduced by Dahlquist. Conditions for any polynomial collocation method or its equivalent to beA-Stable are derived. These conditions may be easily checked in any particular case.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

A problem of Dyer,Porcelli, and Rosenfeld

In this paper, we will demonstrate that a conjecture of Dyer, Porcelli, and Rosenfeld is correct. In fact, we will show that ifM is any finite von Neumann factor andA is any non-zero element ofM, then there exists aT inM such that the spectrum ofT+A is disjoint from the spectrum ofT, i.e. such thatσ(T+A) ∩ σ(T)=φ.     

A probabilistic analysis of the set covering problem

A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e.The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.     

A short zero-one law proof of a result of Abian

Summary In this note a new and very short zero-one law proof of the following theorem of Abian is presented. The subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use a given basis element of a prescribed Hamel basis, has outer Lebesgue measure one and inner measure zero.Let {a, b, c, ...} be a Hamel basis for the real numbers. LetA be the subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use the basis elementa. Sierpinski [4, p. 108] has shown thatA is nonmeasurable in the sense of Lebesgue. Abian [1] has improved Sierpinski's result by showing thatm* (A), the outer measure ofA, is one and thatm _* (A), the inner measure ofA, is zero. In this note a very short proof, using a zero-one law, of Abian's result will be presented.The following zero-one law is an immediate consequence of the Lebesgue Density Theorem [2, p. 290].     

On the number of popular differences

We prove that there exists an absolute constant c > 0 such that for any finite set A ⊆ ℤ with |A| ≥ 2 and any positive integer m < c|A|/ ln |A| there are at most m integers b > 0 satisfying |(A + b) \ A| ≤ m; equivalently, there are at most m positive integers possessing |A| −m (or more) representations as a difference of two elements of A.     

The Padé-Rayleigh-Ritz method for solving large hermitian eigenproblems

We make use of the Padé approximants and the Krylov sequencex, Ax,,...,A ^m–1 x in the projection methods to compute a few Ritz values of a large hermitian matrixA of ordern. This process consists in approaching the poles ofR _x()=((I–A)^–1 x,x), the mean value of the resolvant ofA, by those of [m–1/m]_Rx(), where [m–1/m]_Rx() is the Padé approximant of orderm of the functionR _x(). This is equivalent to approaching some eigenvalues ofA by the roots of the polynomial of degreem of the denominator of [m–1/m]_Rx(). This projection method, called the Padé-Rayleigh-Ritz (PRR) method, provides a simple way to determine the minimum polynomial ofx in the Krylov subspace methods for the symmetrical case. The numerical stability of the PRR method can be ensured if the projection subspacem is sufficiently small. The mainly expensive portion of this method is its projection phase, which is composed of the matrix-vector multiplications and, consequently, is well suited for parallel computing. This is also true when the matrices are sparse, as recently demonstrated, especially on massively parallel machines. This paper points out a relationship between the PRR and Lanczos methods and presents a theoretical comparison between them with regard to stability and parallelism. We then try to justify the use of this method under some assumptions.     

Equivalence of Hadamard matrices

Supposem is a square-free odd integer, andA andB are any two Hadamard matrices of order 4m. We will show thatA andB are equivalent over the integers (that is,B can be obtained fromA using elementary row and column operations which involve only integers).     

A combinatorial interior point method for network flow problems

For solving minimum cost flow problems, we develop a combinatorial interior point method based on a variant of the algorithm of Karmarkar, described in Gonzaga [3, 4]. Gonzaga proposes search directions generated by projecting certain directions onto the nullspace ofA. By the special combinatorial structure of networks any projection onto the nullspace ofA can be interpreted as a flow in the incremental graph ofG. In particular, to evaluate the new search direction, it is sufficient to choose a negative circuit subject to costs on the arcs depending on the current solution. That approach results in an O(mn ² L) algorithm wherem denotes the number of vertices,n denotes the number of arcs, andL denotes the total length of the input data.     

Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.