Binary relations as single primitive notions for hyperbolic three-space and the inversive plane

By interpreting J.A. Lester's [9] result on inversive-distance-preserving mappings as an axiomatizability statement, and by using the Liebmann isomorphism between the inversive plane and hyperbolic three-space, we point out that hyperbolic three-spaces (and inversive geometry) coordinatized by Euclidean fields can be axiomatized with planes (or circles) as variables, by using only the plane-orthogonality (or circle-orthogonality) predicate _p (or _c), or by using only the predicate δ′ (or δ), where δ′(p,p′) (or δ(A, B)) is interpreted as ‘the distance between the planes p and p′ is equal to the length of the segment s whose angle of parallelism is (i. e. II(s) = )’ (or as ‘the numerical distance between the disjoint circles A and B has the value , which corresponds to s via Liebmann's isomorphism’).     

Transposition invariant string matching

Given strings A=a₁a₂…a_m and B=b₁b₂…b_n over an alphabet , where is some numerical universe closed under addition and subtraction, and a distance function d(A,B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is , where A+t=(a₁+t)(a₂+t)…(a_m+t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, including Hamming distance, longest common subsequence (LCS), Levenshtein distance, and their versions where the exact matching condition is replaced by an approximate one. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance, and for some we achieve these upper bounds. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems, and its connection with multidimensional range-minimum search. As a byproduct, we give improved sparse dynamic programming algorithms to compute LCS and Levenshtein distance.     

An inverse theorem for the restricted set addition in Abelian groups

Let A be a set of k5 elements of an Abelian group G in which the order of the smallest nonzero subgroup is larger than 2k−3. Then the number of different elements of G that can be written in the form a+a^′, where a,a^′A, a≠a^′, is at least 2k−3, as it has been shown in [Gy. Károlyi, The Erdős–Heilbronn problem in Abelian groups, Israel J. Math. 139 (2004) 349–359]. Here we prove that the bound is attained if and only if the elements of A form an arithmetic progression in G, thus completing the solution of a problem of Erdős and Heilbronn. The proof is based on the so-called ‘Combinatorial Nullstellensatz.’     

到三定点相对距离的和等于定数的点的轨迹

本文研究了相对测度空间中的距离问题. 利用质点几何的理论方法获得如下结果:对任意给定的实数, 满足条件dT (P,A) + dT (P,B) + dT (P,C) =τ的点P的轨迹是凸十二边形或九边形(其中T:=ABC 是由给定的不同三点A, B, C构成的三角形), 所得结果丰富了相对距离研究领域的内容.     

Some extensions of the Kantorovich inequality and statistical applications

Kantorovich gave an upper bound to the product of two quadratic forms, (X′AX) (X′A⁻¹X), where X is an n-vector of unit length and A is a positive definite matrix. Bloomfield, Watson and Knott found the bound for the product of determinants |X′AX| |X′A⁻¹X| where X is n × k matrix such that X′X = I_k. In this paper we determine the bounds for the traces and determinants of matrices of the type X′AYY′A⁻¹X, X′B²X(X′BCX)⁻¹ X′C²X(X′BCX)⁻¹ where X and Y are n × k matrices such that X′X = Y′Y = I_k and A, B, C are given matrices satisfying some conditions. The results are applied to the least squares theory of estimation.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

An exact algorithm for solving the vertex separator problem

Given G = (V, E) a connected undirected graph and a positive integer β(|V|), the vertex separator problem is to find a partition of V into no-empty three classes A, B, C such that there is no edge between A and B, max{|A|, |B|} ≤ β(|V|) and |C| is minimum. In this paper we consider the vertex separator problem from a polyhedral point of view. We introduce new classes of valid inequalities for the associated polyhedron. Using a natural lower bound for the optimal solution, we present successful computational experiments.     

Some properties of BLUE in a linear model and canonical correlations associated with linear transformations

Let (x, Xβ, V) be a linear model and let A′ = (A′₁, A′₂) be a p × p nonsingular matrix such that A₂X = 0, Rank A₂ = p − Rank X. We represent the BLUE and its covariance matrix in alternative forms under the conditions that the number of unit canonical correlations between y₁ ( = A₁x) and y₂ ( = A₂x) is zero. For the second problem, let x′ = (x′₁, x′₂) and let a g-inverse V⁻ of V be written as (V⁻)′ = (A′₁, A′₂). We investigate the reations (if any) between the nonzero canonical correlations {1 ₁ … ₁ > 0} due to y₁ ( = A₁x) and y₂ ( = A₂x), and the nonzero canonical correlations {1 λ₁ … λ_v+r > 0} due to x₁ and x₂. We answer some of the questions raised by Latour et al. (1987, in Proceedings, 2nd Int. Tampere Conf. Statist. (T. Pukkila and S. Puntanen, Eds.), Univ. of Tampere, Finland) in the case of the Moore-Penrose inverse V⁺ = (A′₁, A′₂) of V.     

The set of values of b for which there exist block designs with b blocks

Let B denote the set of values of b for which there exists a block design with b blocks and for k3, let B_k denote the subset of B determined by the designs with block size k. We present some information about B and the sets B_k. In particular, we discuss, for certain integers h, the question as to whether there exist integers k and k^′ such that the equation b^′=b+h has infinitely many solutions b,b^′ satisfying bB_k and b^′B_k^′. The study is restricted to the case λ=1.     

Deadbeat control: A special inverse eigenvalue problem

In this paper we give a numerical method to construct a rankm correctionBF (where then ×m matrixB is known and them ×n matrixF is to be found) to an ×n matrixA, in order to put all the eigenvalues ofA +BF at zero. This problem is known in the control literature as deadbeat control. Our method constructs, in a recursive manner, a unitary transformation yielding a coordinate system in which the matrixF is computed by merely solving a set of linear equations. Moreover, in this coordinate system one easily constructs the minimum norm solution to the problem. The coordinate system is related to the Krylov sequenceA ^–1 B,A ^–2 B,A ^–3 B, .... Partial results of numerical stability are also obtained.Dedicated to Professor Germund Dahlquist: on the occasion of his 60th birthday     

An asymptotic minimax risk bound for estimation of a linear functional relationship

We consider estimation of the parameter B in a multivariate linear functional relationship X_i=ξ_i+ξ_1i, Y_i=Bξ_i+ξ_2i, i=1,…,n, where the errors (ζ_1i^′, ζ_2i^′) are independent standard normal and (ξ_i, i ) is a sequence of unknown nonrandom vectors (incidental parameters). If there are no substantial a priori restrictions on the infinite sequence of incidental parameters then asymptotically the model is nonparametric but does not fit into common settings presupposing a parameter from a metric function space. A special result of the local asymptotic minimax type for the m.1.e. of B is proved. The accuracy of the normal approximation for the m.l.e. of order n^−1/2 is also established.     

Noisy colored point set matching

We propose a process for determining approximated matches, in terms of the bottleneck distance, under color preserving rigid motions, between two colored point sets A,B∈R², |A|≤|B|. We solve the matching problem by generating all representative motions that bring A close to a subset B^′ of set B and then using a graph matching algorithm. We also present an approximate matching algorithm with improved computational time. In order to get better running times for both algorithms we present a lossless filtering preprocessing step. By using it, we determine some candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B^′ of S. Then, we solve the matching problem between A and every candidate zone. Experimental results using both synthetic and real data are reported to prove the effectiveness of the proposed approach.     

Generating orthogonal matrix polynomials satisfying second order differential equations from a trio of triangular matrices

The method developed in [A.J. Durán, F.A. Grünbaum, Orthogonal matrix polynomials satisfying second order differential equations, Int. Math. Res. Not. 10 (2004) 461–484] led us to consider matrix polynomials that are orthogonal with respect to weight matrices W(t) of the form , , and (1−t)^α(1+t)^βT(t)T^*(t), with T satisfying T^′=(2Bt+A)T, T(0)=I, T^′=(A+B/t)T, T(1)=I, and T^′(t)=(−A/(1−t)+B/(1+t))T, T(0)=I, respectively. Here A and B are in general two non-commuting matrices. We are interested in sequences of orthogonal polynomials (P_n)_n which also satisfy a second order differential equation with differential coefficients that are matrix polynomials F₂, F₁ and F₀ (independent of n) of degrees not bigger than 2, 1 and 0 respectively. To proceed further and find situations where these second order differential equations hold, we only dealt with the case when one of the matrices A or B vanishes.The purpose of this paper is to show a method which allows us to deal with the case when A, B and F₀ are simultaneously triangularizable (but without making any commutativity assumption).     

Lie Triple Derivable Mappings on Rings

Let ? be a ring containing a nontrivial idempotent. In this article, under a mild condition on ?, we prove that if δ is a Lie triple derivable mapping from ? into ?, then there exists a Z _{A, B} (depending on A and B) in its centre 𝒵(?) such that δ(A + B) = δ(A) + δ(B) + Z _{A, B} . In particular, let ? be a prime ring of characteristic not 2 containing a nontrivial idempotent. It is shown that, under some mild conditions on ?, if δ is a Lie triple derivable mapping from ? into ?, then δ = D + τ, where D is an additive derivation from ? into its central closure T and τ is a mapping from ? into its extended centroid 𝒞 such that τ(A + B) = τ(A) + τ(B) + Z _{A, B} and τ([[A, B], C]) = 0 for all A, B, C ∈ ?.     

The vertex separator problem: a polyhedral investigation

The vertex separator (VS) problem in a graph G=(V,E) asks for a partition of V into nonempty subsets A, B, C such that there is no edge between A and B, and |C| is minimized subject to a bound on max{|A|,|B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Necessary and sufficient conditions are given for the VSP to be full dimensional. Central to our investigation is the relationship between separators and dominators. Several classes of valid inequalities are investigated, along with the conditions under which they are facet defining for the VSP. Some of our proofs combine in new ways projection with lifting.In a companion paper we develop a branch-and-cut algorithm for the (VS) problem based on the inequalities discussed here, and report on computational experience with a wide variety of (VS) problems drawn from the literature and inspired by various applications.Research supported by the National Science Foundation through grant #DMI-0098427 and by the Office of Naval Research through contract N00014-97-1-0196Research supported by the Brazilian agencies FAPESP (grant 01/14205–6), CAPES (grant BEX 04444/02–2) and CNPq (grants 302588/02–7 and Pronex 664107/97–4)     

Common Best Proximity Points: Global Optimal Solutions

Let S:A→B and T:A→B be given non-self mappings, where A and B are non-empty subsets of a metric space. As S and T are non-self mappings, the equations Sx=x and Tx=x do not necessarily have a common solution, called a common fixed point of the mappings S and T. Therefore, in such cases of non-existence of a common solution, it is attempted to find an element x that is closest to both Sx and Tx in some sense. Indeed, common best proximity point theorems explore the existence of such optimal solutions, known as common best proximity points, to the equations Sx=x and Tx=x when there is no common solution. It is remarked that the functions x→d(x,Sx) and x→d(x,Tx) gauge the error involved for an approximate solution of the equations Sx=x and Tx=x. In view of the fact that, for any element x in A, the distance between x and Sx, and the distance between x and Tx are at least the distance between the sets A and B, a common best proximity point theorem achieves global minimum of both functions x→d(x,Sx) and x→d(x,Tx) by stipulating a common approximate solution of the equations Sx=x and Tx=x to fulfill the condition that d(x,Sx)=d(x,Tx)=d(A,B). The purpose of this article is to elicit common best proximity point theorems for pairs of contractive non-self mappings and for pairs of contraction non-self mappings, yielding common optimal approximate solutions of certain fixed point equations. Besides establishing the existence of common best proximity points, iterative algorithms are also furnished to determine such optimal approximate solutions.     

Algorithms and Methods for Solving Scheduling Problems and Other Extremum Problems on Large-Scale Graphs

We consider a large-scale directed graph G = (V, E) whose edges are endowed with a family of characteristics. A subset of vertices of the graph, V′ ⊂ V, is selected and some additional conditions are imposed on these vertices. An algorithm for reducing the optimization problem on the graph G to an optimization problem on the graph G′ = (V′, E′) of a lower dimension is developed. The main steps of the solution and some methods for constructing an approximate solution to the problem on the transformed graph G′ are presented.__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 235–251, 2003.     

A Pair in a Crowd of Unit Balls

Let F be a family of mutually nonoverlapping unit balls in the n -dimensional Euclidean space Rⁿ. The distance between the centres of A,B   F is denoted by d(A, B). We prove, among others, that if d(A, B)  <  4 and n ≥  5, then A andB are always visible from each other, that is, a light ray emanating from the surface of A reaches B without being blocked by other unit balls. Furthermore, if d(A, B)  < 2n / 2, then any small “shake’ of F can make A, B visible from each other.     

Solutions to Operator Equations on Hilbert C*-Modules II

In this paper, we study the solvability of the operator equations A*X + X*A = C and A*XB + B*X*A = C for general adjointable operators on Hilbert C*-modules whose ranges may not be closed. Based on these results we discuss the solution to the operator equation AXB = C, and obtain some necessary and sufficient conditions for the existence of a real positive solution, of a solution X with B*(X* + X)B ≥ 0, and of a solution X with B*XB ≥ 0. Furthermore in the special case that R(B) í [`(R(A*))]{R(B)\subseteq\overline{R(A*)}} we obtain a necessary and sufficient condition for the existence of a positive solution to the equation AXB = C. The above results generalize some recent results concerning the equations for operators with closed ranges.     

C-Cosine Functions and the Abstract Cauchy Problem, II

For a bounded linear injectionCon a Banach spaceXand a closed linear operatorA : D(A) X → Xwhich commutes withCwe prove that (1) the abstract Cauchy problem,u″(t) = Au(t),t R,u(0) = Cx,u′(0) = Cy, has a unique strong solution for everyx,y D(A) if and only if (2)A₁ = AD(A²) generates aC₁-cosine function onX₁(D(A) with the graph norm), if (and only if, in caseAhas nonempty resolvent set) (3)Agenerates aC-cosine function onX. HereC₁ = CX₁. Under the assumption thatAis densely defined andC⁻¹AC = A, statement (3) is also equivalent to each of the following statements: (4) the problemv″(t) = Av(t) + C(x + ty) + ∫^t₀ Cg(r) dr,t R,v(0) = v′(0) = 0, has a unique strong solution for everyg L¹_locandx, y X; (5) the problemw″(t) = Aw(t) + Cg(t),t R,w(0) = Cx,w′(0) = Cy, has a unique weak solution for everyg L¹_locandx, y X. Finally, as an application, it is shown that for any bounded operatorBwhich commutes withCand has range contained in the range ofC,A + Bis also a generator.