Equivalence of the Generalized Vertical Block Linear Complementarity Problems and Linear Complementarity Problems

In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices, one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property.     

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

Sign reversing and matrix classes

The concept of sign reversing is a useful tool to characterize certain matrix classes in linear complementarity problems. In this paper, we characterize the sign-reversal set of an arbitrary square matrixM in terms of the null spaces of the matricesI–⁁+⁁M, where ⁁ is a diagonal matrix such that 0⁁I. These matrices are used to characterize the membership ofM in the classes P₀, P, and the class of column-sufficient matrices. A simple proof of the Gale and Nikaido characterization theorem for the membership in P is presented.We also study the class of diagonally semistable matrices. We prove that this class is contained properly in the class of sufficient matrices. We show that to characterize the diagonally semistable property is equivalent to solving a concave Lagrangian dual problem. For 2×2 matrices, there is no duality gap between a primal problem and its Lagrangian problem. Such a primal problem is motivated by the definition of column sufficiency.The author would like to thank Professor Richard W. Cottle for his helpful comments on earlier versions of this paper. The author would also like to thank an anonymous referee for numerous helpful comments on this paper.     

On strongly degenerate complementary cones and solution rays

In this paper we show that ifA is a matrix in the class of matricesE(d), for ad R ⁿ ,d > 0, introduced by Garcia, then the boundary of the set ofq R ⁿ for which the linear complementarity problem (q, A) has a solution is equal to the union of all strongly degenerate cones of (I, -A). This is a generalization of a similar result for copositive plus matrices observed by Cottle. We also study some related questions.On leave from Indian Statistical Service, Government of India.     

Characterizations of optimal scalings of matrices

A scaling of a non-negative, square matrixA ≠ 0 is a matrix of the formDAD ^?1, whereD is a non-negative, non-singular, diagonal, square matrix. For a non-negative, rectangular matrixB ≠ 0 we define a scaling to be a matrixCBE ^?1 whereC andE are non-negative, non-singular, diagonal, square matrices of the corresponding dimension. (For square matrices the latter definition allows more scalings.) A measure of the goodness of a scalingX is the maximal ratio of non-zero elements ofX. We characterize the minimal value of this measure over the set of all scalings of a given matrix. This is obtained in terms of cyclic products associated with a graph corresponding to the matrix. Our analysis is based on converting the scaling problem into a linear program. We then characterize the extreme points of the polytope which occurs in the linear program.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

Completely- matrices

A matrix is a real square matrixM such that for everyq the linear complementarity problem: Findw andz satisfyingw = q + Mz, w ≥ 0, z ≥ 0, w ^T z = 0, has a solution. We characterize the class of completely- matrices, defined here as the class of -matrices all of whose nonempty principal submatrices are also -matrices.     

An algorithm for computing all solutions of an absolute value equation

Presented is an algorithm which in a finite (but exponential) number of steps computes all solutions of an absolute value equation Ax + B|x| = b (A, B square), or fails. Failure has never been observed for randomly generated data. The algorithm can also be used for computation of all solutions of a linear complementarity problem.     

Characterizing Q-Matrices beyond L-Matrices

The characterization of Q-matrices, within the class of P₀ matrices due to Aganagič and Cottle, is well known. Afterward, Pang proved a similar characterization for the class L which does not contain class P₀. In this note, we establish furher the same result of Pang for a new class of matrices which properly contains class L. Furthermore, the equivalence between a Q-matrix and a Q_b-matrix, which consists of matrices such that the linear complementarity problem LCP(q,M) has a nonempty and compact solution set for all , is discussed within such a new class. Positive subdefinite matrices with rank one are specially analyzed. This work was supported by CONICYT-Chile through FONDECYT 104-0610, FONDAP-Matemáticas Aplicadas II, and Proyecto MECESUP UCO 9907.     

A conforming decomposition theorem,a piecewise linear theorem of the alternative,and scalings of matrices satisfying lower and upper bounds

A scaling of a nonnegative matrixA is a matrixXAY ^?1, whereX andY are nonsingular, nonnegative diagonal matrices. Some condition may be imposed on the scaling, for example, whenA is square,X=Y or detX=detY. We characterize matrices for which there exists a scaling that satisfies predetermined upper and lower bound. Our principal tools are a piecewise linear theorem of the alternative and a theorem decomposing a solution of a system of equations as a sum of minimal support solutions which conform with the given solutions.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Linear complementarity problems with an invariant number of solutions

This paper studies the class INS of all realn × n matricesM for which the linear complementarity problem (q, M) has exactlyk solutions—k depending only onM—for all realn-vectorsq interior to the coneK(M) of vectors for which (q, M) has any solution at all. This generalizes the results in Cottle and Stone (1983) which deal with the subclassU in INS wherek equals one.After the first two sections of this paper, which introduce the problem and background material, we move on to examine necessary conditions for a matrixM to be in INS (Section 3) and sufficient conditions under whichM will be in INS (Section 4). Section 5 deals with the possible values whichk may have. Section 6 discusses related results concerning the geometry of linear complementarity problems. Finally, Section 7 deals with some known and new matrix classes which are in INS.     

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.     

Backward stability of a pivoting strategy for sign-regular linear systems

A matrixA issign-regular if, for each orderk, allk×k submatrices ofA have determinant with the same sign. In this paper, a pivoting strategy ofO(n) operations for the Gaussian elimination of linear systems whose coefficient matrices are sign-regular is proposed. Backward error analysis of this pivoting strategy is performed and small error bounds are obtained. Our results can also be applied to linear systems whose coefficient matrices have sign-regular inverses.     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

On monotonicity in parametric linear complementarity problems

This paper generalizes the answers that were given by R.W. Cottle to questions that were originally raised by G. Maier.Essentially, we give necessary and sufficient conditions for some notions of monotonicity of solutions for the parametric linear complementarity problem. Our proofs are direct ones and not algorithmic, as Cottle's proofs are, and also cover a broader class of matrices.     

A classification of upper equivalent matrices the generic case

Two square matricesA andB are called upper equivalent iff there exists an invertible lower triangular matrixL such thatL ^–1 AL andB have the same upper triangular parts. In this paper we obtain a set of invariants for this equivalence relation. In the case when any minor of a matrixA, in the intersection of its last columns and first rows and contained in its upper triangular part is different from zero, it is shown that the above mentioned set of invariants completely determines the upper triangular parts of the matrices from the equivalence class ofA. Simple representatives for this class are also given.     

Making sparse matrices sparser: Computational results

Many optimization algorithms involve repeated processing of a fixed set of linear constraints. If we pre-process the constraint matrixA to be sparser, then algebraic operations onA will become faster. We consider the problem of making a given matrix as sparse as possible, theSparsity Problem (SP). In a companion paper with S. Frank Chang, we developed some theoretical algorithms for SP under a non-degeneracy assumption (McCormick and Chang, 1988). Here we investigate what must be done to make those algorithms applicable in practice. We report encouraging computational results in making linear programming constraint matrices sparser. We also find that the Simplex Algorithm can solve the reduced LPs faster. Comparisons are made to a heuristic algorithm for SP of Adler et al. (1989).This work was partially supported by NSF Grants ECS-84-04350 and CDR-84-21402, and by ONR Contract N0014-87-K0214.     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10