On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

Syzygies of Veronese Embeddings

We prove that the Veronese embedding _O ⁿ (d): ^{n N} with n2, d3 does not satisfy property N _p (according to Green and Lazarsfeld) if p3d–2. We make the conjecture that also the converse holds. This is true for n=2 and for n=d=3.     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.     

The Higher K-Theory of Real Curves

If X is a smooth curve defined over the real numbers , we show that K _n (X) is the sum of a divisible group and a finite elementary Abelian 2-group when n 2. We determine the torsion subgroup of K _n (X), which is a finite sum of copies of and 2, only depending on the topological invariants of X() and X(), and show that (for n 2) these torsion subgroups are periodic of order 8.     

Rates of convergence for the stability of large order statistics

Forr1 and eachnr, letM _nr be therth largest ofX ₁,X ₂, ...,X _n , where {X _n ,n1} is an i.i.d. sequence. Necessary and sufficient conditions are presented for the convergence of for all >0 and some –1, where {a _n } is a real sequence. Furthermore, it is shown that this series converges for all >–1, allr1 and all >0 if it converges for some >–1, somer1 and all >0.     

Resolution of the Symmetric Nonnegative Inverse Eigenvalue Problem for Matrices Subordinate to a Bipartite Graph

There is a symmetric nonnegative matrix A, subordinate to a given bipartite graph G on n vertices, with eigenvalues _{12 n} if and only if, ₁ + _n 0, ₂ + _n-10,..., _m + _{n - m + 1}0, _{m + 1}0,..., _{n - m} 0, in which m is the matching numberof G. Other observations are also made about the symmetric nonnegative inverse eigenvalue problem with respect to a graph     

Invariance Principles for Paced Record Times and Applications

Let {Y_n:n0} be a sequence of independent and identically distributed random variables with continuous distribution function, and let {N(t):t0} be a point process. In this paper, making use of strong invariance principles, we establish limit laws for the paced record process {X(t):t0} based on {Y_n:n0} and {N(t):t0}. We consider as applications of our main results, the case of the classical and paced record models. We conclude by extensions of our theorems to non-homogeneous record processes.     

Approximation of the Distribution of the Supremum of a Centered Random Walk. Application to the Local Score

Let (X _n ) _{n 0} be a real random walk starting at 0, with centered increments bounded by a constant K. The main result of this study is: |P(S _n n x)–P( sup_{0 u 1} B _u x)| C(n,K) n/n, where x 0, ² is the variance of the increments, S _n is the supremum at time n of the random walk, (B _u ,u 0) is a standard linear Brownian motion and C(n,K) is an explicit constant. We also prove that in the previous inequality S _n can be replaced by the local score and sup₀ u 1 B _u by sup₀ u 1|B _u |.     

A finite characterization ofK-matrices in dimensions less than four

The class of realn × n matricesM, known asK-matrices, for which the linear complementarity problemw – Mz = q, w 0, z 0, w ^T z =0 has a solution wheneverw – Mz =q, w 0, z 0 has a solution is characterized for dimensionsn <4. The characterization is finite and practical. Several necessary conditions, sufficient conditions, and counterexamples pertaining toK-matrices are also given. A finite characterization of completelyK-matrices (K-matrices all of whose principal submatrices are alsoK-matrices) is proved for dimensions <4.Partially supported by NSF Grant MCS-8207217.Research partially supported by NSF Grant No. ECS-8401081.     

Triangles in arrangements of lines

Givenn lines in the real projective plane, Grünbaum conjectures that, for n16, the numberp ₃ of triangular regions determined by the lines is at most 1/3n(n–1). We show that ifn7 thenp ₃ 8/21n(n–1)+2/7, we also point out that if no vertex is a point of intersection of exactly three of the lines, thenp ₃1/3n(n–1).Professor Gu died while on a visit to Poland in April 1997     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.     

A recursive construction of asymmetric 1-factorizations

W. D. Wallis has recently shown that forn 4, the complete graph on 2n points (denotedK _2n ) has two non-isomorphic 1-factorizations. In this paper we prove that forn 5,K _2n has a 1-factorization with no symmetry at all and that as n increases without bound, the number of pairwise non-isomorphic asymmetric 1-factorizations ofK _2n also increases without bound.The work of B. A. Anderson was partially supported by an Arizona State University Summer Faculty Fellowship.     

Infinitesimal obstructions to weakly mixing

Let ^t be the flow (parametrized with respect to arc length) of a smooth unit vector field v on a closed Riemannian manifold M ⁿ , whose orbits are geodesics. Then the (n-1)-plane field normal to v, v, is invariant under d ^t and, for each x M, we define a smooth real function _x (t) : (1 + _i (t)), where the _i(t) are the eigenvalues of AA ^T, A being the matrix (with respect to orthonormal bases) of the non-singular linear map d^2t , restricted to v at the point _x ^-t M ⁿ.Among other things, we prove the Theorem (Theorem II, below). Assume v is also volume preserving and that _x ^' (t) 0 for all x M and real t; then, if _x ^t : M M is weakly missng for some t, it is necessary that vx 0 at all x M.     

A New Law of the Iterated Logarithm in Rd with Application to Matrix-Normalized Sums of Random Vectors

Let (X _n , n1) be a sequence of independent centered random vectors in R ^d . We study the law of the iterated logarithm lim sup _n(2 log log B _n )^–1/2 B ^–1/2 _n S _n =1 a.s., where B _n is the covariance matrix of S _n = ⁿ _i=1 X _i , n1. Application to matrix-normalized sums of independent random vectors is given.     

Covering a convex body by smaller homothetic copies

Let a convex bodyAE ⁿ be covered bys smaller homothetic copies with coefficients ₁, ..., _s , respectively. It is conjectured that ₁ + ...+ _s n. This conjecture is confirmed in two cases:n is arbitrary ands=n+1;s is arbitrary andn=2.     

Some Applications of Critical Point Theory of Distance Functions on Riemannian Manifolds

In this paper, we use the theory of critical points of distance functions to study the rigidity and topology of Riemannian manifolds with sectional curvature bounded below. We prove that an n-dimensional complete connected Riemannian manifold M with sectional curvature K _M 1 is isometric to an n-dimensional Euclidean unit sphere if M has conjugate radius bigger than /2 and contains a geodesic loop of length 2. We also prove that if M is an n(3)-dimensional complete connected Riemannian manifold with K _M 1 and radius bigger than /2, then any closed connected totally geodesic submanifold of dimension not less than two of M is homeomorphic to a sphere.     

A parametric linear complementarity problem involving derivatives

The problem considered in this paper is given by the conditions:w = q + tp + Mz, w 0, 0,w ^T = 0, where a dot denotes the derivative with respect to the scalar parametert 0. In this problem,q, p aren-vectors withq 0 andM is an byn P-matrix. This problem arises in a certain basic problem in the field of structural mechanics. The main result in this paper is the existence and uniqueness theorem of a solution to this problem. The existence proof is constructive providing a computational method of obtaining the solution asymptotically.This research is in part supported by the National Science Foundation under Grant No. ENG77-11136.     

A preconditioner for constrained and weighted least squares problems with Toeplitz structure

We study methods for solving the constrained and weighted least squares problem min _x by the preconditioned conjugate gradient (PCG) method. HereW = diag (₁, , _m ) with _{1 m} 0, andA ^T = [T ₁ ^T , ,T _k ^T ] with Toeplitz blocksT _l R ^{n × n} ,l = 1, ,k. It is well-known that this problem can be solved by solving anaugmented linear 2 × 2 block linear systemM +Ax =b, A ^T = 0, whereM =W ^–1. We will use the PCG method with circulant-like preconditioner for solving the system. We show that the spectrum of the preconditioned matrix is clustered around one. When the PCG method is applied to solve the system, we can expect a fast convergence rate.Research supported by HKRGC grants no. CUHK 178/93E and CUHK 316/94E.     

Covering a Finite Abelian Group by Subset Sums

Let G be an abelian group of order n. The critical number c(G) of G is the smallest s such that the subset sums set (S) covers all G for eachs ubset SG\{0} of cardinality |S|s. It has been recently proved that, if p is the smallest prime dividing n and n/p is composite, then c(G)=|G|/p+p–2, thus establishing a conjecture of Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing n, n/p is composite and n7p²+3p.We also extend a result of Diderrichan d Mann by proving that, for n67, |S|n/3+2 and S=G imply (S)=G. Sets of cardinality for which (S) =G are also characterized when n183, the smallest prime p dividing n is odd and n/p is composite. Finally we obtain a necessary and sufficient condition for the equality (G)=G to hold when |S|n/(p+2)+p, where p5, n/p is composite and n15p².* Work partially supported by the Spanish Research Council under grant TIC2000-1017 Work partially supported by the Catalan Research Council under grant 2000SGR00079