§ 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:с) исключают друг друга.

Комбинируя (16:18:а) и (16:18:с), с одной стороны, и (16:18:Ь) и (16:18:с), с другой, мы получаем более простое, однако более слабое утверждение ** 2):

->

(16:F) Либо существует вектор х = {хи ..., xm}£Sm, для которого

(16:19:а) 2 a(h 1) Xj=0 Для i= 1, ..., п,

либо существует вектор w = {w1, ..., wn}£Sn, для которого

(16:19:Ь) 2 a(h i)wt0 для ; = 1, яг.

16.4.4. Рассмотрим теперь кососимметрическую матрицу a(i, 7), т. е. такую матрицу, которая совпадает со своей отрицательно транспонированной в смысле п. 16.4.2; в этом случае должно быть п = т и

a(i, ])= - а(7, i), £,/=1, гс.

Тогда условия (16:19:а) и (16:19:Ь) из п. 16.4.3 выражают одно и то же. Действительно, (16:19:Ь) записывается как

2 a (i, 7) wt 0;

это можно переписать как

- 2 а (/ 0 = 0 ИЛИ 2 а (h /) = 0.

i=l i=l

Нам остается взять 7, £ вместо i, j 3), и мы получаем

2 я (£> /) wj = 0 а затем взять л: вместо о?, и мы получаем 2 а (U j) Xj =э 0=1 . 3=1

0. Мы установили (16:19:а). Таким образом, мы можем заменить дизъюнкцию неравенств (16:19:а) и (16:19:Ь) на одно из них, например на (16:19:Ь). В результате мы получаем:

(16:G) Если матрица a(i, 7) является кососимметрической (поэтому

п = т), то существует вектор w = {w1, ..., wn) mSn, для которого

2 a (U ]) ЩО для 7 = 1, ..., п.

г) Альтернативы (16:19:а), (16:19:Ь) не исключают друг друга: их конъюнкция равносильна (16:18:с).

2) Этот результат мог бы быть получен непосредственно из окончательного результата п. 16.4.1. Действительно, (16:19:а) равносильно (16:16:а), а (16:19:Ь) является слабой формой (16:16:Ь). Мы привели более подробный вывод, так как он проясняет общее положение дел.

3) Заметим, что теперь при п = т это просто изменение обозначений!