کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4602339 1631167 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generalizations of the hidden Minkowski property
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Generalizations of the hidden Minkowski property
چکیده انگلیسی

The linear complementarity problem whose defining feature is the extended n-step property is known to be solvable in polynomial time. This paper focuses on the investigation of the subclass of P0-matrices that possess this particular property. We present a necessary condition and a (separate) sufficient condition for membership in the class. It is shown that each of the conditions defines a set of matrices that properly contains the (transposed) hidden Minkowski set, thus generalizing previous work developed in Ref. [J.-S. Pang, R. Chandrasekaran, Linear complementarity problems solvable by a polynomially bounded pivoting algorithm, Math. Program. Study 25 (1985) 13–27] and in Ref. [W.D. Morris, Jr., J. Lawrence, Geometric properties of hidden Minkowski matrices, SIAM J. Matrix Anal. Appl. 10 (1989) 229–232]. To prove the necessity result we use a matrix-analytical approach instead of a geometric argument as in the previous case. To prove the sufficiency result we first establish two characterizations of singular irreducible K0-matrices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 429, Issues 8–9, 16 October 2008, Pages 2076-2088