Матрицы с положительными главными минорами

из "Введение в теорию, методы и экономические предложения задач о дополнительности "

Обратимся к другому важному матричному классу — классу матриц, все главные миноры которых положительны. [c.26]
Доказанная лемма и ее следствие позволяют установить конечность метода Лемке для Р-матриц. [c.27]
Теорема 7.1. Если все главные миноры матрицы М положительны, то метод Лемке при любом q завершается на допустимом базисном решении (5.1), удовлетворяющем условиям дополнительности, т. е. дает решение L P(q,M). [c.27]
Доказательство. Мы уже видели, что завершение на луче подразумевает существование ненулевого вектора z 0, удовлетворяющего неравенствам (6.1). Однако по только что доказанной лемме в случае Р-матриц это невозможно. Значит, для Р-матриц невозможно и завершение метода Лемке на луче. [c.27]
Приведем еще одну важную характеризацию Р-матриц, для чего нам потребуется два вспомогательных утверждения. [c.27]
Пусть векторы z, w связаны соотношением w = Mz. Будем говорить, что М меняет знак z, если гу 0 для всех г = 1,. .., и. [c.27]
Лемма 7.2. Матрица М принадлежит классу Р в том и только в том случае, когда она не меняет знак ни у одного вектора, кроме нулевого. [c.27]
Доказательство. Прежде всего, доказывая необходимость, заметим, что можно ограничиться случаем z 0. В самом деле, если L = г Zi 0 7 0, определим D — диагональную матрицу, получаемую из единичной матрицы сменой знака у тех ее строк, номера которых входят в L. Матрица М = DMD снова оказывается Р-матрицей, поскольку мы просто сменили знаки у строк и столбцов М, номера которых входят в L. Кроме того, матрица М1 меняет знак у вектора Dz 0. [c.28]
пусть 0 z О и М меняет знак z. Определим множество К = г 0 . Предполагая, что К 0, выделим М — главную подматрицу М, получаемую из нее удалением тех строк и столбцов, номера которых не входят в К. Пусть также z — вектор, получаемый из z аналогичным образом. Матрица М — также Р-матрица и меняет знак z. Поскольку все Zi 0, то должно выполняться неравенство М z 0. В силу леммы 7.1 это отвергает гипотезу о принадлежности М классу Р. Необходимость доказана. [c.28]
Перейдем к обоснованию достаточности. Пусть М = (а ) — произвольная главная подматрица матрицы М, К — множество номеров входящих в нее строк и столбцов. Если ее определитель не положителен, М должна иметь хотя бы одно неположительное вещественное собственное значение и соответствующий ему ненулевой вещественный собственный вектор z (это следует из того, что определитель матрицы есть произведение всех ее собственных значений, причем комплексные значения образуют сопряженные пары). Если теперь дополнить вектор z до размерности п нулями в позициях вне К, мы получим вектор z, знак которого меняется над действием матрицы М. Полученное противоречие доказывает достаточность. [c.28]
Напомним, что элементарным преобразованием системы линейных уравнений называют разрешение ее относительно одной из своих неизвестных (т. е. операцию исключения этой неизвестной из всех уравнений, кроме некоторого). Поскольку элементарное преобразование не меняет множества решений системы, простым следствием доказанной леммы является следующий факт. [c.28]
Такое преобразование возможно, так как все тц 0( 0). [c.28]
Теорема 7.2. Линейная задача о дополнительности L P(q,M) имеет единственное решение при всех q тогда и только тогда, когда М — Р-матрица. [c.28]
Доказательство. Пусть М — Р-матрица. По теореме 7.1 задача L P(q, М) разрешима при всех q, причем ее решение является некоторым допустимым базисным решением системы ее уравнений. Переходя в случае необходимости к преобразованной задаче, матрица которой также Р-матрица, можно, не ограничивая общности, считать, что q О и решение, получаемое методом Лемке, имеет вид (q Q) (т. е. z = 0, w = q 0). Пусть оно не единственно и (w,z) — другое решение. Тогда не трудно видеть, что М меняет знак z, т. е. по лемме 7.2 не может принадлежать Р. [c.28]
Обратно, пусть L P(q, М) имеет единственное решение при всех q, но М — не Р-матрица. Тогда по лемме 7.2 существует ненулевой вектор z такой, что все Zi Wi О, где w = Mz. [c.29]
Определим q = (w)+ — M(z)+, где плюс над вектором означает его положительную срезку, т. е. замену отрицательных координат нулями. Поскольку z w = О, пара (w+, z+) 0 является, очевидно, решением L P(q,M). Другим очевидным решением L P(q,M) будет пара (w ,z ) 0, где минус над вектором означает положительную срезку противоположного ему вектора. При проверке всех условий опираемся на равенства w = Mz, w = w+ — w , z = z+ — z , z w = 0. [c.29]
В общем случае линейная задача о дополнительности не всегда разрешима, даже если ее ограничения совместны. [c.29]

Вернуться к основной статье