On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

Siegel’s Lemma and Sum-Distinct Sets

Let L(x)=a ₁ x ₁+a ₂ x ₂+???+a _n x _n , n≥2, be a linear form with integer coefficients a ₁,a ₂,…,a _n which are not all zero. A basic problem is to determine nonzero integer vectors x such that L(x)=0, and the maximum norm ‖x‖ is relatively small compared with the size of the coefficients a ₁,a ₂,…,a _n . The main result of this paper asserts that there exist linearly independent vectors x ₁,…,x _n?1∈? ⁿ such that L(x _i )=0, i=1,…,n?1, and $$\|{\mathbf{x}}_{1}\|\cdots\|{\mathbf{x}}_{n-1}\|<\frac{\|{\mathbf{a}}\|}{\sigma_{n}},$$ where a=(a ₁,a ₂,…,a _n ) and $$\sigma_{n}=\frac{2}{\pi}\int_{0}^{\infty}\left(\frac{\sin t}{t}\right)^{n}\,dt.$$ This result also implies a new lower bound on the greatest element of a sum-distinct set of positive integers (Erdös–Moser problem). The main tools are the Minkowski theorem on successive minima and the Busemann theorem from convex geometry.     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

Contraction mappings in interval analysis

Under certain conditions, the contraction mapping fixed point theorem guarantees the convergence of the iterationx _i+1=f(x _i ) toward a fixed point of the functionf:R ⁿ →R ⁿ. When an interval extensionF off is used in a similar iteration scheme to obtain a sequence of interval vectors these conditions need not provide convergence to a degenerate interval vector representing the fixed point, even if the width of the initial interval vector is chosen arbitrarily small. We give a sufficient condition on the extensionF in order that the convergence is guaranteed. The centered form of Moore satisfies this condition.     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

Variational Inequalities: an Elementary Approach

We will deal with the following problem: Let M be an n×n matrix with real entries. Under which conditions the family of inequalities: x∈? ⁿ ;x?0;M·x?0has non–trivial solutions? We will prove that a sufficient condition is given by m_i,j+m_j,i?0 (1?i,j?n); from this result we will derive an elementary proof of the existence theorem for Variational Inequalities in the framework of Monotone Operators.     

A functional equation having monomials as solutions

For each n=1,2,3, we obtain the general solution and the stability of the functional equation

f(2x+y)+f(2x-y)=2^n-2[f(x+y)+f(x-y)+6f(x)].     

On the classification of conditionally integrable evolution systems in (1 + 1) dimensions

We generalize earlier results of Fokas and Liu and find all locally analytic (1 + 1)-dimensional evolution equations of order n that admit an N-shock-type solution with N ≤ n + 1. For this, we develop a refinement of the technique from our earlier work, where we completely characterized all (1+1)-dimensional evolution systems u _t = F (x, t, u, ?u/?x,..., ?ⁿ u/? x ⁿ) that are conditionally invariant under a given generalized (Lie-Bäcklund) vector field Q(x, t, u, ?u/?x,..., ?^k u/?x ^k)?/?u under the assumption that the system of ODEs Q = 0 is totally nondegenerate. Every such conditionally invariant evolution system admits a reduction to a system of ODEs in t, thus being a nonlinear counterpart to quasi-exactly solvable models in quantum mechanics.     

Existence and nonuniqueness of solutions to a functional-differential equation

We examine the functional-differential equation Δu(x) — div(u(H(x))f (x)) = 0 on a torus which is a generalization of the stationary Fokker-Planck equation. Under sufficiently general assumptions on the vector field f and the map H, we prove the existence of a nontrivial solution. In some cases the subspace of solutions is established to be multidimensional.     

Fractal functions and interpolation

Let a data set {(x _i,y _i) ∈I×R;i=0,1,?,N} be given, whereI=[x ₀,x _N]?R. We introduce iterated function systems whose attractorsG are graphs of continuous functionsf∶I→R, which interpolate the data according tof(x _i)=y _i fori ε {0,1,?,N}. Results are presented on the existence, coding theory, functional equations and moment theory for such fractal interpolation functions. Applications to the approximation of naturally wiggly functions, which may show some kind of geometrical self-similarity under magnification, such as profiles of cloud tops and mountain ranges, are envisaged.     

A strongly polynomial algorithm for linear systems having a binary solution

This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax?=?b, 0 ≤?x?≤?1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.     

Linear maps preserving M–P inverses of matrices between matrix spaces over fields

Suppose F is a field of characteristic not 2. Let n and m be two arbitrary positive integers with n≥2. We denote by M _n (F) and S _n (F) the space of n×n full matrices and the space of n×n symmetric matrices over F, respectively. All linear maps from S _n (F) to M _m (F) preserving M–P inverses of matrices are characterized first, and thereby all linear maps from S _n (F) (M _n (F)) to S _m (F) (M _m (F)) preserving M–P inverses of matrices are characterized, respectively.     

Additive operators preserving rank-additivity on symmetry matrix spaces

We characterize the additive operators preserving rank-additivity on symmetry matrix spaces. LetS _n(F) be the space of alln×n symmetry matrices over a fieldF with 2,3 ∈F ^*, thenT is an additive injective operator preserving rank-additivity onS _n(F) if and only if there exists an invertible matrixU∈M _n(F) and an injective field homomorphism ? ofF to itself such thatT(X)=cUX ^?U^T, ?X=(x_ij)∈S_n(F) wherec∈F ^*,X ^?=(?(x _ij)). As applications, we determine the additive operators preserving minus-order onS _n(F) over the fieldF.     

On solvability of derivative dependent doubly singular boundary value problems

In this paper we establish existence of solutions of singular boundary value problem ?(p(x)y ^′(x))^′=q(x)f(x,y,py′) for 0<x≤b and $\lim_{x\rightarrow0^{+}}p(x)y^{\prime}(x)=0$ , α ₁ y(b)+β ₁ p(b)y ^′(b)=γ ₁ with p(0)=0 and q(x) is allowed to have integrable discontinuity at x=0. So the problem may be doubly singular. Here we consider $\lim_{x\rightarrow0^{+}}\frac{q(x)}{p'(x)}\neq0$ therefore $\lim_{x\rightarrow0^{+}}p(x)y'(x)=0$ does not imply y′(0)=0 unless $\lim_{x\rightarrow0^{+}}f(x,y(x),p(x)y'(x))=0$ .     

Difference Sets in {\mathbb{Z}}_4^m and {\mathbb{F}}_2^{2m}

Let R=GR(4,m) be the Galois ring of cardinality 4^m and let T be the Teichmüller system of R. For every map λ of T into { -1,+1} and for every permutation Π of T, we define a map φ _λ ^Π of Rinto { -1,+1} as follows: if x∈R and if x=a+2b is the 2-adic representation of x with x∈T and b∈T, then φ _λ ^Π (x)=λ(a)+2Tr(Π(a)b), where Tr is the trace function of R . For i=1 or i=-1, define D _i as the set of x in R such thatφ _λ ^Π =i. We prove the following results: 1) D _i is a Hadamard difference set of (R,+). 2) If φ is the Gray map of R into ${\mathbb{F}}_2^{2m}$ , then (D _i) is a difference set of ${\mathbb{F}}_2^{2m}$ . 3) The set of D _i and the set of φ(D _i) obtained for all maps λ and Π, both are one-to-one image of the set of binary Maiorana-McFarland difference sets in a simple way. We also prove that special multiplicative subgroups of R are difference sets of kind D _i in the additive group of R. Examples are given by means of morphisms and norm in R.     

Stability problem for the Go?a?b-Schinzel type functional equations

Let X be a vector space over a field K of real or complex numbers, n∈N and λ∈K?{0}. We study the stability problem for the Go?a?b-Schinzel type functional equations

f(x+fn(x)y)=λf(x)f(y)     

Some matrix functional equations

We investigate the pair of matrix functional equations G(x)F(y) = G(xy) and G(x)G(y) = F(y/x), featuring the two independent scalar variables x and y and the two N×N matrices F(z) andG(z) (with N an arbitrary positive integer and the elements of these two matrices functions of the scalar variable z). We focus on the simplest class of solutions, i.e., on matrices all of whose elements are analytic functions of the independent variable. While in the scalar (N = 1) case this pair of functional equations only possess altogether trivial constant solutions, in the matrix (N > 1) case there are nontrivial solutions. These solutions satisfy the additional pair of functional equations F(x)G(y) = G(y/x) andF(x)F(y) = F(xy), and an endless hierarchy of other functional equations featuring more than two independent variables.