Abstract
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 P0, 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Murty, K. G.,Linear Complementarity, Linear and Nonlinear Programming, Helderman Verlag, Berlin, Germany, 1988.
Cottle, R. W., Pang, J. S., andStone, R. E.,The Linear Complementarity Problem, Academic Press, Boston, Massachusetts, 1992.
Cottle, R. W., Giannessi, F., andLions, J. L., Editors,Variational Inequalities and Complementarity Problems: Theory and Applications, Wiley, New York, New York, 1980.
Harker, P. T., andPang, J. S.,Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms, and Applications, Mathematical Programming, Vol. 48, pp. 161–220, 1990.
Sandberg, I. W., andWillson, A. N., Jr.,Some Theorems on Properties of DC-Equations of Nonlinear Networks, Bell System Technical Journal, Vol. 48, pp. 1–34, 1969.
Ramamurthy, K. G., andMohan, S. R.,Nonnegativity of Principal Minors of Generalized Inverses of P O-Matrices, Linear Algebra and Its Applications, Vol. 65, pp. 125–131, 1985.
Eagambabrm, N.,Generalized Inverses with Nonnegative Principal Minors, Linear Algebra and Its Applications, Vol. 111, pp. 293–312, 1988.
Aganagić, M., andCottle, R. W.,A Constructive Characterization of Q 0-Matrices with Nonnegative Principal Minors, Mathematical Programming, Vol. 37, pp. 223–231, 1987.
Eaves, B. C.,The Linear Complementarity Problem, Management Science, Vol. 17, pp. 612–634, 1971.
Samelson, H., Thrall, R. M., andWesler, O.,A Partition Theorem for Euclidean n-Space, Proceedings of the American Mathematical Society, Vol. 9, pp. 805–807, 1958.
Ingleton, A. W.,A Problem in Linear Inequalities, Proceedings of the London Mathematical Society, Vol. 16, pp. 519–536, 1966.
Murty, K. G.,On the Number of Solutions to the Complementarity Problem and the Spanning Properties of Complementary Cones, Linear Algebra and Its Applications, Vol. 5, pp. 65–108, 1972.
Cottle, R. W., Pang, J. S., andVenkateswaran, V.,Sufficient Matrices and the Linear Complementarity Problem, Linear Algebra and Its Applications, Vol. 114, pp. 231–249, 1989.
Cottle, R. W., andChang, Y. Y.,Least Index Resolution of Degeneracy in Linear Complementarity Problems with Sufficient Matrices, SIAM Journal on Matrix Analysis and Applications, Vol. 13, pp. 1131–1141, 1992.
Kojima, M., Megiddo, N., Noma, T., andYoshise, A.,A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems, Springer Verlag, Berlin, Germany, 1991.
Pang, J. S.,Iterative Descent Algorithm for a Row Sufficient Linear Complementarity Problem, SIAM Journal on Matrix Analysis and Applications, Vol. 12, pp. 611–624, 1991.
Gale, D., andNikaido, H.,The Jacobian Matrix and Global Univalence of Mappings, Mathematische Annalen, Vol. 159, pp. 81–93, 1965.
Bazaraa, M. S., Sherali, H. D., andShetty, C. M.,Nonlinear Programming: Theory and Algorithms, 2nd Edition, John Wiley and Sons, New York, New York, 1993.
Fiedler, M., andPták, V.,On Matrices with Nonpositive Off-Diagonal Elements and Positive Principal Minors, Czechoslovak Mathematical Journal, Vol. 12, pp. 382–400, 1962.
Aganagić, M.,Contributions to Complementarity Theory, Stanford University, PhD Thesis, 1978.
Strang, G.,Linear Algebra and Its Applications, 3rd Edition, Harcourt Brace Jovanovich, Orlando, Florida, 1988.
Cottle, R. W., andGuu, S. M.,Two Characterizations of Sufficient Matrices, Linear Algebra and Its Applications, Vol. 170, pp. 65–74, 1992.
Author information
Authors and Affiliations
Additional information
Communicated by D. G. Luenberger
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.
Rights and permissions
About this article
Cite this article
Guu, S.M. Sign reversing and matrix classes. J Optim Theory Appl 89, 373–387 (1996). https://doi.org/10.1007/BF02192535
Issue Date:
DOI: https://doi.org/10.1007/BF02192535