Linear systems with a quadratic integral

It is shown that a linear system of n differential equations with constant coefficients, at least one of whose integrals is a non-degenerate quadratic form, may be reduced to a canonical system of Hamiltonian equations. In particular, n is even and the phase flow preserves the standard measure; if the index of the quadratic integral is odd, the trivial solution is unstable, and so on. For the case n = 4 the stability conditions are given a geometrical form. The general results are used to investigate small oscillations of non-holonomic systems, and also the problem of the stability of invariant manifolds of non-linear systems that have Morse functions as integrals.     

Controllability and observability in the problem of stabilizing mechanical systems with cyclic coordinates

An approach based on linear control theory is used to solve the problem of stabilizing the steady motions of holonomic mechanical systems in which only cyclic coordinates are controllable [1–3]. The most general structure of forces acting on the system is considered and it is assumed that the constraints imposed are time-independent. The set of new criteria of controllability and observability based on the reduction of the problem under consideration is obtained. The reduction enables one to reduce the investigation of these problems to an analysis of a problem of less dimensions.     

On an optimal stopping problem of Gusein-Zade

We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t^*)^r, where t^*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ_r,n lets approximately t^*n arrivals go by and then stops ‘almost immediately’, in the sense that τ_r,n/n→t^* in probability as n→∞, r→∞     

Binary set functions and parity check matrices

We consider the possibility of extending to a family of sets a binary set function defined on a subfamily so that the extension is, in fact, uniquely determined. We place in this context the problem of finding the least integer n(r) such that every linear code of length n with n n(r), dimension n-r and minimum Hamming distance at least 4 has a parity check matrix composed entirely of odd weight columns and answer this problem by showing that n(r) = 5.2^{r − 4} + 1, r4. This result is applied to yield new constructions and bounds for unequal error protection codes with minimum distances 3 and 4.     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

Stabilization of the stationary motions of non-holonomic mechanical systems

The possible stabilization of the unstable stationary motions of a non-holonomic system is studied from the standpoint of general control theory /1, 2/. As distinct from the case previously considered /3/, when forces of a certain structure are applied with respect to both positional and cyclical coordinates, the stabilization is obtained here by applying control forces only with respect to the cyclical coordinates /4/; the control forces may be applied with respect to some or all of the cyclical coordinates, and depend on the positional coordinates, the velocities, and the corresponding cyclical momenta. It is shown that, just as in the case of holonomic systems /5, 6/, depending on the control properties of the corresponding linear subsystem, the stationary motions, whether stable or unstable, can be stabilized, up to asymptotic stability with respect to all the phase variables, or asymptotic stability with respect to some of the phase variables and stability with respect to the remaining variables. The type of stabilization with respect to the given phase variables depends on the Lyapunov transformations which are needed in order to reduce the critical cases obtained to singular cases /7, 8/.     

On the problem op n-stationary centers

Among the various problems of celestial mechanics related to the n-body problem, a certain amount of interest attaches to the specific situation wherein a passive gravitational point mass M moves under the assumption that the relative disposition of the other active gravitational masses experiences no large changes.

If the attracting masses are regarded as points and if changes in the relative disposition of the attracting bodies are neglected, one arrives at the problem of the motion of the point M in a field produced by n-stationary attracting centers (the point M here represents the (n+l)-th body).

In addition to the problem of central motion (n = 1), soluble dynamics problems of this category include Euler's case [1] of two (n= 2) stationary Newtonian attracting centers.

This problem, which for a long time was of solely theoretical Interest as an example of an integrable Liouville system [2], has recently been attracting attention in connection with the mechanics of artificial satellites, particularly after it was shown that the potential of an oblate spheroid can be approximated by the potential of two specifically chosen stationary Newtonian attracting centers [3 and 4].

The solution of the problem for n-attracting centers for n ≥ 3 is unknown, except for a single special case of three centers pointed out by Lagrange and considered In greater detail by J.A. Serre [5].

We shall concern ourselves here with problems on the existence of periodic trajectories in the case of n-attracting centers. An arbitrary and not necessarily Newtonian gravitational law will be assumed.

Our analysis is based on the theory of quasiindices of singular force field points as set forth in [60].     

Hermitian quadratic eigenvalue problems of restricted rank

We consider a quadratic eigenvalue problem such that the second order term is a Hermitian matrix of rank r, the linear term is the identity matrix, and the constant term is an arbitrary Hermitian matrix . Of the n+r solutions that this problem admits, we show at least n-r to be real and located in specific intervals defined by the eigenvalues of A, whence at most 2r are nonreal occuring in possibly repeated conjugate pairs.     

Adaptive control of uncertain coupled mechanical systems with application to base-isolated structures

A problem of feedback stabilization is addressed for a class of uncertain nonlinear mechanical systems with n degrees of freedom and n_c < n control inputs. Each system of the class has the structure of two coupled subsystems with n_c and n_r degrees of freedom, respectively, a prototype being an uncertain base isolated building structure with n degrees of freedom actively controlled via actuators applying forces to specific degrees of freedom of the base movement, n_c < n in number. A nonlinear adaptive feedback strategy is described, which, under appropriate assumptions on the system uncertainties, guarantees a form of practical stability of the zero state. Numerical simulations are also presented to illustrate the application of the control strategy to a base isolated building.     

Integral estimation and adaptive stabilization of non-holonomic controlled systems

A method for the programmed stabilization of non-holonomic dynamic systems is proposed. The original problem is reduced to a constrained adaptive control problem with unknown perturbations, which are represented by the reactions of linear (not necessarily ideal) non-holonomic constraints. Effective control and parameter estimation algorithms are constructed for the exponential stabilization of the system. The method can be extended to non-holonomic systems whose parameters are not known in advance or undergo an unknown bounded drift with time.     

Bounds on the error of fejer and clenshaw-curtis type quadrature for analytic functions

We consider the problem of integrating a function f : [-1,1] → R which has an analytic extension to an open disk D^r of radius r and center the origin, such that for any . The goal of this paper is to study the minimal error among all algorithms which evaluate the integrand at the zeros of the n-degree Chebyshev polynomials of first or second kind (Fejer type quadrature formulas) or at the zeros of (n-2)-degree Chebyshev polynomials jointed with the endpoints -1,1 (Clenshaw-Curtis type quadrature formulas), and to compare this error to the minimal error among all algorithms which evaluate the integrands at n points. In the case r > 1, it is easy to prove that Fejer and Clenshaw-Curtis type quadrature are almost optimal. In the case r = 1, we show that Fejer type formulas are not optimal since the error of any algorithm of this type is at least about n^-2. These results hold for both the worst-case and the asymptotic settings.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.     

Manifolds of idemopotent matrices

Let M_n be the set of n×n matrices and r a nonnegative integer with r ≤ n. It is known,from Lie groups, that the rank r idempotent matrices in M_n form an arcwise connected 2n (n-r)-dimensional analytic manifold. This paper provides an elementary proof of this result making it accessible to a larger audience.     

On-line construction of the upper envelope of triangles and surface patches in three dimensions

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions. This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log nΣ_r=1ⁿτ(r)/r²) and depends on the expected size τ(r) of an intermediate result for r triangles. Since τ(r) can be Θ(r²(r)) in the worst case, this cost is bounded in the worst case by O(n(n) log n). (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice. It extends to surfaces and surface patches of fixed maximum algebraic degree.     

The harmonic means of diagonals of doubly-stochastic matrices

It is shown that every doubly-stochastic n × n matrix with precisely r positive elements possesses a positive diagonal whose harmonic mean is at least equal to n/r.     

On the quasi-stationary distribution of a stochastic Ricker model

We model the evolution of a single-species population by a size-dependent branching process Z_t in discrete time. Given that Z_t = n the expected value of Z_t+1 may be written nexp(r − γn) where r> 0 is a growth parameter and γ > 0 is an (inhibitive) environmental parameter. For small values of γ the short-term evolution of the normed process γZ_t follows the deterministic Ricker model closely. As long as the parameter r remains in a region where the number of periodic points is finite and the only bifurcations are the period-doubling ones (r in the beginning of the bifurcation sequence), the quasi-stationary distribution of γZ_t is shown to converge weakly to the uniform distribution on the unique attracting or weakly attracting periodic orbit. The long-term behavior of γZ_t differs from that of the Ricker model, however: γZ_t has a finite lifetime a.s. The methods used rely on the central limit theorem and Markov's inequality as well as dynamical systems theory.     

Whittaker方程对非完整力学系统的推广

1904年Whittaker利用能量积分将一个完整保守力学系统问题降阶为一个带有较少自由度系统问题.并得到了Whittaker方程[1].本文推导对于非完整力学系统的这类方程.并称之为广义Whittaker方程;然后把这些方程变换为Nielsen形式;最后举例说明新方程的应用.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Chapter 3:inertia preservers

Let Vdenote either the space of n×n hermitian matrices or the space of n×nreal symmetric matrices, Given nonnegative integers r,s,t such that r+S+t=n, let G( r,s,r) denote the set of all matrices in V with inertia (r,s,t). We consider here linear operators on V which map G(r,s,t) into itself.     

Bondage number of strong product of two paths

The bondage number b(G) of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. In this paper, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m≥2 and n≥2, b(P_m?P_n) = 7 - r(m) - r(n) if (r(m), r(n)) = (1, 1) or (3, 3), 6 - r(m) - r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t ≡ 1 (mod 3), r(t) = 2 if t ≡ 2 (mod 3), and r(t) = 3 if t ≡ 0 (mod 3).