(мы заменили tu ..., tp на tu .... tm, s4, sn). В покомпонентной записи это равносильна
Jjtja(h /)+ 2*-0.
j=i z=i
Второе слагаемое слева равно st, так что можно написать
(16:7) Sa(i, -5,.
Если бы имело место 2 tj" 0, то были бы справедливы равенства f4 -
= ...=-0и, следовательно, из (16:7) вытекало бы, что s4 - . . . = 5Л=0.
Это, однако, противоречит (16:6). Следовательно, 2/>0- Заменим
равенство (16:7) его следствием
(16:8) 2а(£, j)tj0.
т i т
Положим теперь Xj= tjl 2 tj Для 7 = 1» • • •» Тогда мы получим 2 #7 = 1»
j=l i=l
и (16:5) дает нам #42г0, #mi0. Следовательно,
(16:9) х = {хи . . ., л:т}6т,
и (16:8) приводит к условию
(16:10) J\a(i9j)xj0 для / = 1, п.
Рассмотрим, с другой стороны, случай, когда С не содержит 0. Теорема (16:В) из п. 16.3 позволяет нам сделать вывод о существо-
вании такой содержащей у гиперплоскости (см. (16:2:а) из п. 16.2.1), что множество С содержится в полупространстве, порожденном этой гиперплоскостью (см. (16:2:Ь) из п. 16.2.1). Обозначим эту гиперплоскость через
2 dtXi = ъ.
Поскольку 0 принадлежит ей, то 6 = 0. Таким образом, рассматриваемое полупространство имеет вид
(16:11) 2>0.
-»• ->•-» ->
Векторы х1, хт, б1, бп принадлежит этому полупространству.
При записи этого факта для 6* неравенство (16:11) принимает вид
2а*г>0, т. е. ai>0. Таким образом, мы получаем г=1
(16:12) а4>0, ап>0.
§ 16]
ЛИНЕЙНОСТЬ и выпуклость
При аналогичной записи для xJ мы получаем
(16:13) 2а(*, /)а.>0.
Положим теперь Wiaijat для £=1, п. Тогда мы получаем
2 м>$ = 1, и (16:12) дает нам м;1>0, . . ., ы>0.
Следовательно,
->
(16:14) = {1!, Wn}£Sn.
Неравенство (16:13) дает нам
(16:15) a(U ])u>i>0 для / = 1, ..., т.
Объединяя соотношения (16:9), (16:10), (16:14), (16:15), мы можем утверждать следующее:
(16:С) Пусть задана прямоугольная матрица с т столбцами и п стро-
ками. Обозначим элементы этой матрицы через а (&, /), i = = 1, . . ., п; 7 = 1, . . иг. Тогда либо существует такой вектор
х = {а?!, . . ., хт) е Sm, что
(16:16:а) 2 а (*> /) ж7 = 0 Для * = 1> • • •» п,
либо такой вектор w = {и, . . ., £ £л, что
(16:16:b) 2a(*» j)wi>0 для / = 1, «г.
Заметим, далее, следующее:
Альтернативы (16:16:а) и (16:6:Ь) исключают друг друга.
Доказательство. Предположим, что (16:6:а) и (16:16:Ь) имеют место одновременно. Умножим каждое из неравенств (16:6:а) на u?i и просуммируем по всем i = 1, . . ., п; это дает нам
п т
2 2а (*"» /) = о.
i=l j=l
Умножим, далее, каждое из неравенств (16:16:Ь) на xt и просуммируем по / = 1, т; это дает нам
п т
2 2*(*i О1).
г=1 j=l
Таким образом, мы получаем противоречие.
16.4.2. Заменим матрицу a (i, j) отрицательно транспонированной к ней матрицей; это значит, что мы обозначим столбцы (а не строки,
*) Здесь >0, а не просто > 0. Действительно, из =0 мы получили бы xt = . . . =
= хт - 0, что невозможно, так как 2 xi - !•
как раньше) через i = 1, . . ., п и строки (а не столбцы, как раньше) через f*= 1, . . ., т. Пусть, далее, элементами матрицы будут - а (£, ;) (а не а (£, /), как раньше). (Таким образом, числа пит также поменялись ролями.)
Сформулируем окончательный результат п. 16.4.1 для новой матрицы
в терминах первоначальной матрицы. Пусть при этом х = {xiy . . ., хт}
t -> ->
играет роль w = {wl9 . . ., wn}, a w = {wv . . ., wn} играет роль
X - {#1? * * * #7n}*
Мы получим следующее:
(16:D) Пусть прямоугольная матрица с п строками и т столбцами
задана. Обозначим элементы этой матрицы через а(£, /), i = 1, п,
/ = 1, . . ., т. Тогда либо существует вектор х = {х[, . .., хт) £ Sm,
для которого выполняется
(16:17:а) 2 a(i, j) х-<0, i = l, л,
либо существует вектор м? = {, wn}£Sn, для которого выполняется
(16:17:Ь) 2 /)0.
Эти две альтернативы исключают одна другую.
16.4.3. Объединим результаты пп. 16.4.1 и 16.4.2. Из них следует,
что выполняются либо (16:17:а), либо (16:16:Ь), либо, наконец, (16:16:а)
и (16:17:Ь) одновременно; эти три возможности исключают друг друга.
->->->• ->
Используя ту же самую матрицу a(i, j) и переобозначая х, ш, xf, w из пп. 16.4.1, 16.4.2 через х, w, х, и?, мы получаем следующее:
(16:Е) Либо существует вектор x = {xi9 xm}£Sm, для которого
(16:18:а) a(i, j) xj<.0 Для i=l, п,
либо вектор w - {wu wn}£Sn, Для которого
(16:18:Ь) 2 a(U ])т<0 для 7 = 1, т,
-> ->
либо два вектора: жг = {, a:m}m и w = {wv WnJgiSn, для которых
2 л (i, у) xj 0 для i = l, . . ., /г,
(16:18:с)
2 а (г, у) 0 для 7 = 1, ..., т.
Три альтернативы (16:18:а), (16:18:Ь) и (16:18:с) исключают друг друга.