On the maximum of r-Stirling numbers

Determining the location of the maximum of Stirling numbers is a well-developed area. In this paper we give the same results for the so-called r-Stirling numbers which are natural generalizations of Stirling numbers.     

On r-quick limit sets for empirical and related processes based on mixing random variables

The r-quick limit points of normalized sample paths and empirical distribution functions of mixing processes are characterized. An r-quick version of Bahadur-Kiefer-type representation for sample quantiles is established, which yields the r-quick limit points of quantile processes. These results are applied to linear functions of order statistics. Some results on r-quick convergence of certain Gaussian processes are also established.     

On the connectedness of the solution set to linear complementarity systems

This paper establishes sufficient conditions for the connectedness of nontrivial subsets of the solution set to linear complementarity systems with special structure. Connectedness may be important to investigate stability and sensitivity questions, parametric problems, and for extending a Lemke-type method to a new class of problems. Such a property may help in analyzing the structure of the feasible region by checking the explicitly given matrices of the resulting conditions. From the point of view of geometry, the question is how to analyze the combined geometrical object consisting of a Riemannian manifold, a pointed cone, and level sets determined by linear inequalities.This paper has been mainly prepared while the author was visiting the Department of Mathematics at the University of Pisa. This research was partialy supported by the Hungarian National Research Foundation, Grant No. OTKA-2568.     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

On the torsion of linear higher order connections

For a linear r-th order connection on the tangent bundle we characterize geometrically its integrability in the sense of the theory of higher order G-structures. Our main tool is a bijection between these connections and the principal connections on the r-th order frame bundle and the comparison of the torsions under both approaches.     

Solvable infinite-dimensional linear groups with restrictions on the nonabelian subgroups of infinite rank

Under study are the solvable nonabelian linear groups of infinite central dimension and sectional p-rank, p ≥ 0, in which all proper nonabelian subgroups of infinite sectional p-rank have finite central dimension. We describe the structure of the groups of this class.     

On the asymptotic number of non-equivalent q-ary linear codes

Let be the group of monomial matrices, i.e., the group generated by all permutation matrices and diagonal matrices in . The group acts on the set of all subspaces of . The number of orbits of this action, denoted by N_n,q, is the number of non-equivalent linear codes in . It was conjectured by Lax that as n→∞. We confirm this conjecture in this paper.     

A note on solvability of a class of linear complementarity problems

We give a characterization of unique solvability of an infinite family of linear complementarity problems of a special form by means of a finite subset of this family.     

Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

Existence and uniqueness of solutions for the generalized linear complementarity problem

Cottle and Dantzig (Ref. 1) showed that the generalized linear complementarity problem has a solution for anyqR ^m ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). They also extended known characterizations of squareP-matrices to vertical blockP-matrices.Here we show, using a technique similar to Murty's (Ref. 2), that there exists a unique solution for anyqR ^m if and only ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). To obtain this characterization, we employ a generalization of Tucker's theorem (Ref. 3) and a generalization of a theorem initially introduced by Gale and Nikaido (Ref. 4).     

Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

Exact and stable least squares solution to the linear programming problem

A linear programming problem is transformed to the finding an element of polyhedron with the minimal norm. According to A. Cline [6], the problem is equivalent to the least squares problem on positive ortant. An orthogonal method for solving the problem is used. This method was presented earlier by the author and it is based on the highly developed least squares technique. First of all, the method is meant for solving unstable and degenerate problems. A new version of the artifical basis method (M-method) is presented. Also, the solving of linear inequality systems is considered.     

Characterizations of multivariate normality II. Through linear regressions

It is established that a vector (X′₁, X′₂, …, X′_k) has a multivariate normal distribution if (i) for each X_i the regression on the rest is linear, (ii) the conditional distribution of X₁ about the regression does not depend on the rest of the variables, and (iii) the conditional distribution of X₂ about the regression does not depend on the rest of the variables, provided that the regression coefficients satisfy some more conditions that those given by [4]J. Multivar. Anal. 6 81–94].     

On the convergence of finite linear predictors of stationary processes

It is shown that the finite linear least-squares predictor of a multivariate stationary process converges to its Kolmogorov-Wiener predictor at an exponential rate, provided that the entries of its spectral density matrix are smooth functions. Also, the same rate of convergence holds for the partial sums of the Kolmogorov-Wiener predictor.     

On p-norm linear discrimination

We consider a p-norm linear discrimination model that generalizes the model of Bennett and Mangasarian (1992) and reduces to a linear programming problem with p-order cone constraints. The proposed approach for handling linear programming problems with p-order cone constraints is based on reformulation of p-order cone optimization problems as second order cone programming (SOCP) problems when p is rational. Since such reformulations typically lead to SOCP problems with large numbers of second order cones, an “economical” representation that minimizes the number of second order cones is proposed. A case study illustrating the developed model on several popular data sets is conducted.     

The order of a zero of a Wronskian and the theory of linear dependence

Every root of the top Wronskian of a Wronskian matrix whose rank at the root is equal to the number of columns, is of integer order even if the highest derivatives exist only at the root. If the rank of a Wronskian matrix is constant and smaller than the number of rows, then the number of independent linear relations between the functions in the first row is equal to the number of functions minus the rank. These results were proved under additional assumptions by Bôcher, Curtiss, and Moszner. Their proofs are simplified.     

On the average number of steps of the simplex method of linear programming

The goal is to give some theoretical explanation for the efficiency of the simplex method of George Dantzig. Fixing the number of constraints and using Dantzig's self-dual parametric algorithm, we show that the number of pivots required to solve a linear programming problem grows in proportion to the number of variables on the average. Supported in part by NSF Grant #MCS-8102262.     

On weak generalized positive subdefinite matrices and the linear complementarity problem

In this article, we present a weaker version of the class of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi [J.P. Crouzeix and S. Komlósi, The Linear Complementarity Problem and the Class of Generalized Positive Subdefinite Matrices, Applied Optimization, Vol. 59, Kluwer, Dordrecht, 2001, pp. 45–63], which is new in the literature, and obtain some properties of weak generalized positive subdefinite (WGPSBD) matrices. We show that this weaker class of matrices is also captured by row-sufficient matrices introduced by Cottle et al. [R.W. Cottle, J.S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114/115 (1989), pp. 231–249] and show that for WGPSBD matrices under appropriate assumptions, the solution set of a linear complementarity problem is the same as the set of Karush–Kuhn–Tucker-stationary points of the corresponding quadratic programming problem. This further extends the results obtained in an earlier paper by Neogy and Das [S.K. Neogy and A.K. Das, Some properties of generalized positive subdenite matrices, SIAM J. Matrix Anal. Appl. 27 (2006), pp. 988–995].     

Representing the space of linear programs as the Grassmann manifold

Each linear program (LP) has an optimal basis. The space of linear programs can be partitioned according to these bases, so called the basis partition. Discovering the structures of this partition is our goal. We represent the space of linear programs as the space of projection matrices, i.e., the Grassmann manifold. A dynamical system on the Grassmann manifold, first presented in Sonnevend et al. (Math Program 52:527–553), is used to characterize the basis partition as follows: From each projection matrix associated with an LP, the dynamical system defines a path and the path leads to an equilibrium projection matrix returning the optimal basis of the LP. We will present some basic properties of equilibrium points of the dynamical system and explicitly describe all eigenvalues and eigenvectors of the linearized dynamical system at equilibrium points. These properties will be used to determine the stability of equilibrium points and to investigate the basis partition. This paper is only a beginning of the research towards our goal. Research is supported in part by NUS Academic Research Grant R-146-000-084-112. The author wishes to thank Josef Stoer for his valuable comments on the paper and to thank Wingkeung To, Jie Wu, Xingwang Xu, Deqi Zhang and Chengbo Zhu for providing consultations on Differential Geometry and Grassmann manifolds and pointing out useful literature. The author is certainly responsible to all faults in the paper.