Q-matrices and boundedness of solutions to linear complementarity problems

This paper is concerned with the existence and boundedness of the solutions to the linear complementarity problemw=Mz+q,w0,z0,w ^T z=0, for eachq ⁿ . It has been previously established that, ifM is copositive plus, then the solution set is nonempty and bounded for eachq ⁿ iffM is aQ-matrix. This result is shown to be valid also forL ₂-matrices,P ₀-matrices, nonnegative matrices, andZ-matrices.     

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).     

Degeneracy in linear complementarity problems: a survey

Given a square matrixM of ordern and a vectorq ⁿ , the linear complementarity problem is the problem of either finding aw ⁿ and az ⁿ such thatw–Mz=q,w0,z0 andw ^T z=0 or showing that no such (w, z) exists. This problem is denoted asLCP(q, M). We say that a solution (w, z) toLCP(q, M) is degenerate if the number of positive coordinates in (w, z) is less thann. As in linear programming, degeneracy may cause cycling in an adjacent vertex following methods like Lemke's algorithm. Moreover, ifLCP(0,M) has a nontrivial solution, a condition related to degeneracy, then unless certain other conditions are satisfied, the algorithm may not be able to decide about the solvability of the givenLCP(q, M). In this paper we review the literature on the implications of degeneracy to the linear complementarity theory.     

Some classes of matrices in linear complementarity theory

The linear complementarity problem is the problem of finding solutionsw, z tow = q + Mz, w0,z0, andw ^T z=0, whereq is ann-dimensional constant column, andM is a given square matrix of dimensionn. In this paper, the author introduces a class of matrices such that for anyM in this class a solution to the above problem exists for all feasibleq, and such that Lemke's algorithm will yield a solution or demonstrate infeasibility. This class is a refinement of that introduced and characterized by Eaves. It is also shown that for someM in this class, there is an even number of solutions for all nondegenerateq, and that matrices for general quadratic programs and matrices for polymatrix games nicely relate to these matrices.Research partially supported by National Science Foundation Grant NSF-GP-15031.     

On the parametric linear complementarity problem: A generalized solution procedure

This paper presents a solution procedure for the parametric linear complementarity problemIw–Mz=q+sp,w ^T z=0,w0, andz0, whereM is a positive semidefinite matrix or aP-matrix. This procedure is different from existing ones in the way it handles initialization. By exploiting special relationships between the vectorsq andp, it can reduce computational effort. Sinceq is an arbitrary vector, the procedure can be used for the ordinary linear complementarity problem. In that case, it produces pivots exactly analogous to those of Lemke's algorithm.This paper is based on the author's doctoral dissertation at Johns Hopkins University, 1977. The author wishes to thank her advisors, Professors C. S. ReVelle and D. J. Elzinga. During the last year of her graduate studies, the author held an AAUW-IBM dissertation fellowship.     

A short proof of finiteness of Murty's principal pivoting algorithm

We give a short proof of the finiteness of Murty's principal pivoting algorithm for solving the linear complementarity problemy = Mz + q, y ^T z = 0,y 0,z 0 withP-matrixM.     

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.     

Editorial Policy

Consider the parametric linear complementarity problem w=Mz+q+p, w0, z0, w ^T z=0, where p0, 0q0, and 0. We show that a necessary condition for every complementary map z() to be isotone for every nonzero q0 and every p is that M be either a P-matrix or a -matrix. The Cottle necessary and sufficient conditions for strong and uniform isotonicity for P-matrices are restated, with slight modifications, for -matrices.     

On the gradient-projection method for solving the nonsymmetric linear complementarity problem

The Levitin-Poljak gradient-projection method is applied to solve the linear complementarity problem with a nonsymmetric matrixM, which is either a positive-semidefinite matrix or aP-matrix. Further-more, if the quadratic functionx ^T(Mx + q) is pseudoconvex on the feasible region {x R ⁿ |Mx + q 0,x0}, then the gradient-projection method generates a sequence converging to a solution, provided that the problem has a solution. For the case when the matrixM is aP-matrix and the solution is nondegenerate, the gradient-projection method is finite.This work is based on the author's PhD Dissertation, which was supported by NSF Grant No. MCS-79-01066 at the University of Wisconsin, Madison, Wisconsin.The author would like to thank Professor O. L. Mangasarian for his guidance of the dissertation.     

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.     

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.     

Total Scalar Curvature and L 2 Harmonic 1-Forms on a Minimal Hypersurface in Euclidean Space

Let M ⁿ , n 3, be a complete oriented immersed minimal hypersurface in Euclidean space R ⁿ⁺¹. We show that if the total scalar curvature on M is less than the n/2 power of 1/C _s , where C _s is the Sobolev constant for M, then there are no L ² harmonic 1-forms on M. As corollaries, such a minimal hypersurface contains no nontrivial harmonic functions with finite Dirichlet integral and so it has only one end. This implies finally that M is a hyperplane.     

Codimension 2 subvarieties of projective space

The motivation for the present paper is theHartshorne Conjecture on complete intersections inP ⁿ , forn6, and in the codimension 2 case: Any smooth codimension 2 subvarietyX ofP ⁿ is conjectured to be a complete intersection forn6. We prove this conjecture for all varieties with degree below a certain bound, which represents an improvement of the numerical information available untill now.This research has been supported by a grant from theStefi andLars Fylkesaker Foundation     

A Note on a Paper by P. Amodio and F. Mazzia

In 1999 Amodio and Mazzia presented a new backward error analysis for LU factorization and introduced a new growth factor _n . Their very interesting approach allowed them to obtain sharp error bounds. In particular, they derive nice results assuming that partial pivoting is used. However, the forward error bound for the solution of a linear system whose coefficient matrix A is an M-atrix given in Theorem 4.1 of that paper is not correct. They first obtain a bound for the condition number (U) assuming that one has the LU factorization of an M-matrix and then they apply the bounds obtained when partial pivoting is used. But if P is the permutation associated with partial pivoting then PA = LU can fail to be an M-atrix and the bound for (U) can be false, as shown in our Example 1.1. We also prove that, for a pivoting strategy presented in the paper, the growth factor of an M-matrix A is _n(A) = 1 and (U) (A), where U is the upper triangular matrix obtained after applying such a pivoting strategy.This revised version was published online in October 2005 with corrections to the Cover Date.     

On a characterization of complete matrix rings

Peter R. Fuchs established in 1991 a new characterization of complete matrix rings by showing that a ringR with identity is isomorphic to a matrix ringM _n (S) for some ringS (and somen 2) if and only if there are elementsx andy inR such thatx ^n–1 0,x ⁿ=0=y ²,x+y is invertible, and Ann(x ^n–1)Ry={0} (theintersection condition), and he showed that the intersection condition is superfluous in casen=2. We show that the intersection condition cannot be omitted from Fuchs' characterization ifn3; in fact, we show that if the intersection condition is omitted, then not only may it happen that we do not obtain a completen ×n matrix ring for then under consideration, but it may even happen that we do not obtain a completem ×m matrix ring for anym2.     

A sharp form of Poincaré type inequalities on balls and spheres

Summary Letu be a real valued function on ann-dimensional Riemannian manifoldM ⁿ. We consider an inequality between theL ^q-norm ofu minus its mean value overM ⁿ and theL ^p-norm of the gradient ofu.The best constant in such inequality is exhibited in the following cases: i)M ⁿ is an open ball inIR ⁿ andp=1, 0<qn/(n–1); ii)M ⁿ is a sphere inIR ⁿ +1 and eitherp=1, 0<qn/(n–1) orp>n,q=.

---

Sunto Siau una funzione a valori reali dafinita su una varietà riemannianan-dimensionaleM ⁿ. Si considera una disuguaglianza tra la normaL ^q diu meno il suo valor medio suM ⁿ e la normaL ^p del gradiente diu.Si determina la costante ottimale in tale disuguaglianza nei seguenti casi: i)M ⁿ è un disco aperto inIR ⁿ ep=1, 0<qn/(n–1); ii)M ⁿ è una sfera inIR ⁿ +1 ep=1, 0<qn/(n–1) oppurep>n,q=.

     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

On the number of solutions to the linear comple-mentarity problem

Given ann × n matrixA and ann-dimensional vectorq letN(A, q) be the cardinality of the set of solutions to the linear complementarity problem defined byA andq. It is shown that ifA is nondegenerate thenN(A, q) + N(A, –q) 2 ⁿ , which in turn impliesN(A, q) 2 ⁿ – 1 ifA is also aQ-matrix.It is then demonstrated that min _q0 N(A, q) 2 ^n–1 – 1, which concludes that the complementary cones cannot spanR ⁿ more than 2 ^n–1 – 1 times around. For anyn, an example of ann × n nondegenerateQ-matrix spanning allR ⁿ , but a subset of empty interior, 2^[n/3] times around is given.     

Approximation in the mean by rational functions

In this paper we proved that for a large class of compact subsetsK in the complex plane,R(K) is dense inL ^q () if and only if the set of analytic bounded point evaluations forR ^q (K, ) is empty. As a consequence, we showed that this result is true for allK ifR(K) is replaced byA(K). Our main result includes the corresponding result of James Thomson for polynomials approximation as such a special case thatK is a disk.     

Rational approximation to Lipschitz and Zygmund classes

In this paper, characterizations for lim _n(R _n (f)/(n ^–1)=0 inH and for lim _n(n ^r+ R _n (f)=0 inW ^r Lip ,r1, are given, while, forZ, a generalization to a related result of Newman is established.Communicated by Ronald A. DeVore.