A variational principle for eigenvalues of pencils of Hermitian matrices

LetH=(A, B) be a pair of HermitianN×N matrices. A complex number is an eigenvalue ofH ifdet(A–B)=0 (we include = ifdetB=0). For nonsingularH (i.e., for which some is not an eigenvalue), we show precisely which eigenvalues can be characterized as _k ⁺ =sup{inf{*A:*B=1,S},SS _k},S _k being the set of subspaces of C ^N of codimensionk–1.Dedicated to the memory of our friend and colleague Branko NajmanResearch supported by NSERC of Canada and the I.W.Killam FoundationProfessor Najman died suddenly while this work was at its final stage. His research was supported by the Ministry of Science of CroatiaResearch supported by NSERC of Canada     

∈-Weak Minimal Solutions of Vector Optimization Problems with Set-Valued Maps

In this paper, we consider cone-subconvexlike vector optimization problems with set-valued maps in general spaces and derive scalarization results, -saddle point theorems, and -duality assertions using -Lagrangian multipliers.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

On the distribution of sequences connected with digit-representation

Let N=e(s)b(s)+e(s–1)b(s–1)+...+e(1)b(1)+e(0) be the digit representation of the integer N to base b or to -scale, that is with respect to the best approximation denominators of an irrational number . Let f:N₀ Z with f(0)=0 be an arbitrary function and r(0),r(1),... be an arbitrary sequence of integers and F(N):=f(e(s))r(s)+...+f(e (1))r(1)+f(e(0))r(0). Conditions for the uniform distribution modulo one of the sequence {F(N)x}_NN, x are given.     

Joint convergence of conditional expectations

Let P_n, nIN{0}, be probability measures on a-fieldA; f_n, nIN{0}, be a family of uniformly boundedA-measurable functions andA _n, nIN, be a sequence of sub--fields ofA, increasing or decreasing to the-fieldA _o. It is shown in this paper that the conditional expectations converge in P_o-measure to with k, n, m , if P_n|A, nIN, converges uniformly to P_n|A and f_n, nIN, converges in P_o-measure to f_o.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Pseudo-mesures p- adiques associées aux fonctions L deQ

It is shown that some standard results concerning the p-adic L- functions, L_p(), ofQ(p-divisibilities of 1/2L_p(, s), and congruences for 1/2L_p(, t)–1/2L_p(, s), s, t_p) are direct consequences of a general structural theorem, based only on the functional properties of the p-adic pseudo-measures and distributions attached to these L_p-functions (essentially the eulerian ones). The method suggests that all such divisibilities and congruences are obtained systematically by this way, and are the best possible (in a standard point of view). In particular, these results improve significantly all the known ones.     

Singular perturbations in foliations

Summary We define a constraint system , [0,₀), which is a kind of family of vector fields on a manifold. This is a generalized version of the family of the equations , [0,₀),x ^m ,y ⁿ . Finally, we prove a singular perturbation theorem for the system , [0,₀).Dedicated to Professor Kenichi Shiraiwa on his 60th birthday     

Approximation by Reciprocals of Polynomials with Positive Coefficients in L p Spaces

We prove that, if f(x) L ^p _[0,1], 1 < p < , f(x) 0, x [0,1], f 0, then there is a polynomial p(x) ⁺ _n such that f - 1/p _LP C(p)(f,n ^-1/2) _LP where ⁺ _n indicates the set of all polynomials of degree n with positive coeficients (see the definition (1) in the text).     

Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ ₁ (x) subject toQ _i (x) 0,i M ₁ {2,...,m},x P R ⁿ, whereQ _i (x), i M {1} M ₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R ^m;u 0, u _i= l}be fixed;then the problem:iM minimize u _iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e. u C₁ {u S;Q _i (x (u)) 0,i M ₁} or unfeasible, i.e. there exists ani M ₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC _i C_i S _i withS _i {u S; u _i=0}, i M. A constructive method is used to prove that C _i is not empty and thatx (û) withiM û C _i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ _i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ _i (x) 0, iM ₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R ^m;u 0, u _i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u _i Q_i (x (u)) über dem durch die lineareniM Restriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP R ⁿ, immer eine Optimallösungx (u), die entweder zulässig ist: u C₁ {u S;Q ₁ (x (u)) 0,i M ₁} oder unzulässig ist, d.h. es existiert eini M ₁ mitu C_i {u S;Q _i (x(u))0}.Es seien folgende MengenC _i C_i S _i definiert, mitS _i {u S;u _i=0}, i M. Es wird konstruktiv bewiesen, daß C _i 0 undx (û) mitû C _i eine Optimallösung voniM iM (QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.     

A note on the addition of residues

LetA andB be two proper subsets of _n such thatA + B _n .The Cauchy-Davenport Theorem states that|A + B| |A| + |B| – 1 for a primen. As mentioned by Cauchy the inequality may not hold for a compositen. Chowla generalized the Cauchy-Davenport as follows.Suppose 0 B andgcd(x, n) = 1 for allx B0, then|A + B| |A| + |B| – 1. We show that if 0 B and for allx, y B0 such thatx y gcd(x,y,n) = 1, then|A + B| |A| + |B| – 2. Moreover|A + B| |A| + |B| – 1 unless |B| = 2 or b B such thatB {0, b} is a union of cosets modulo the cyclic group generated byb.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

Quasisimilarity of model contractions with unequal defects

Let T and T be C₁₀ contractions with characteristic functions H (ⁿⁿ⁺¹), H (^mm+1). The fundamental result is: T and T are quasisimilar if and only if The paper contains an analysis of this condition; examples are given.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 149, pp. 24–37, 1986.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

On Tabor's problem concerning a certain quasi-ordering of iterative roots of functions

Summary Using the Isaacs-Zimmermann's theory of iterative roots of functions, we prove a theorem concerning the problemP 250 posed by J. Tabor:Letf: E E be a given mapping. Denote byF the set of all iterative roots off. InF we define the following relation: if and only if is an iterative root of. The relation is obviously reflexive and transitive. The question is: Is it also antisymmetric? If we consider iterative roots of a monotonic function the answer is yes. But in general the question is open.Here we prove that there exists a three-element decomposition { _i ;i = 1, 2, 3} of the setE ^E with blocks _i of the same cardinality 2^cardE such that the functions from ₁ do not possess any proper iterative root, the quasi-ordering is not antisymmetric onF(f) for anyf ₂, and is an ordering onF(f) for anyf ₃. Iff is a strictly increasing continuous self-bijection ofE, then the relation is an ordering onF(f) ifff is different from the identity mapping of the setE.     

On the existence of wave operators for the Klein-Gordon equation

The problem of existence of wave operators for the Klein-Gordon equation ( _t ² –+²+iV_1t+V₂)u(x,t)=0 (x R ⁿ,t R, n3, >0) is studied where V₁ and V₂ are symmetric operators in L₂(R ⁿ) and it is shown that conditions similar to those of Veseli-Weidmann (Journal Functional Analysis 17, 61–77 (1974)) for a different class of operators are also sufficient for the Klein-Gordon equation.     

Asymptotics of Eigenvalues of a Plate with Small Clamped Zone

Different types of asymptotic expansions are constructed and justified for eigenvalues of the Dirichlet problem for the biharmonic operator in a plane domain with a small hole of the diameter (the Kirchhoff-Love plate clamped at ). Depending on properties of an eigenfunction of the limiting problem, the expansions happen either to be series in powers of , or to contain terms, holomorphic in | ln |^–1     

On the type of spectral operators and the non-spectrality of several differential operators on Lp

A spectral operator, not necessarily bounded, which is the infinitesimal generator of a strongly continuous group of operators {U(t)|t} where U(t) = (|t|^K), is of type k N_o, i.e. T = S + N, where S is spectral of scalar type, N is bounded, N^k+1 = O and S and N are commuting. This result yields a simple proof of the non-spectrality of certain differential operators on L^p, p 2, which are known to be selfadjoint for p = 2.     

Counting Bumps

The number of modes of a density f can be estimated by counting the number of 0-downcrossings of an estimate of the derivative f, but this often results in an overestimate because random fluctuations of the estimate in the neighbourhood of points where f is nearly constant will induce spurious counts. Instead of counting the number of 0-downcrossings, we count the number of "significant" modes by counting the number of downcrossings of an interval [-, ]. We obtain consistent estimates and confidence intervals for the number of "significant" modes. By letting converge slowly to zero, we get consistent estimates of the number of modes. The same approach can be used to estimate the number of critical points of any derivative of a density function, and in particular the number of inflection points.