один вектор виду з
коефіцієнтом. Перенісши його в праву чатсть рівності (1.22), отримаємо
, (1.23)
де. Але оскільки, компонента з номером правою частини (1.23) відмінна від нуля. Тому серед векторів лівої частини (1.23) знайдеться хоча б один вектор виду, для якого. Переносячи його в праву частину (1.23), знаходимо
(1.24)
де
Цей процес перенесення векторів в праву частину можна продовжити аналогічним чином і далі. Припустимо, що вже проведено (2k-1) кроків. Тоді має місце співвідношення
(1.25)
де
Можливі два випадки:
1) при деякому
2).
У першому випадку процес перенесення закінчується, причому з векторів у правій частині (1.25) можна утворити замкнуте маршрут. Таким маршрутом є
В
У другому випадку процес перенесення триває, і оскільки, серед векторів Р ij , де (i, j) обов'язково знайдеться вектор з коефіцієнтом.
Описаний процес перенесення не може триває безкінечно, так як всі вектора, що переносяться вправо, різні. Тому через кінцеве число кроків ми обов'язково зіткнемося з випадком 1, який, як показано вище, веде до утворення замкнутого маршруту.
Отже, допустивши, що система векторів лінійно залежна, ми прийшли до протиріччя з умовою теореми, згідно з яким з комунікацій системи R не можна скласти замкнутий маршрут. Залишається прийняти, що система R складається з лінійно незалежних векторів.
Достатність умов теореми доведена.
Назвемо комунікацію Т-задачі основний комунікацією плану Х , якщо Тоді, використовуючи теорему 3.4, можна сформулювати наступний ознака перевірки довільного плану на опорность.
План Т-завдання є опорним (базисним), якщо з його основних комунікацій не можна скласти замкнутий маршрут.
Теорема 5. Вектор є лінійною комбінацією векторів системи R тоді і тільки тоді, коли з векторів цієї системи можна скласти маршрут, що з'єднує пункти A k і. Якщо цей маршрут має вигляд
В
то
. (1.26)
Доказ цієї теореми грунтується на теоремі 3.4. Нехай виражений у вигляді лінійної комбінації векторів системи R. Додавши до неї вектор, отримаємо систему лінійно залежних векторів. Тоді в силу теореми 3.4 з'являється замкнутий маршрут. Це замкнене маршрут повинен містити комунікацію і, отже, всі інші комунікації повинні з'єднати і.
Тоді
.
Перенісши в праву частину, отримаємо вираз (1.26), що й потрібно було довести. br/>
1
2
3
4
5
6
i/J
В
1
В
+
1
1
1
2
X = /Td>
1
1
3
1
1
4
1
1
1
5
Рис. 3.3.
Розглянемо довільну матрицю. Між позиціями матриці Х і векторамиВ можна встановити наступне відповідність. Вектор відповідає елементу матриці Х. Тоді можна задати систему з векторів, виділивши одиницями відповідні елементи матриці Х. Розглянемо матрицю на Рис3. Тут одиницями відзначена система векторів R:
.
При використанні матриці Х критерій перевірки лінійної незалежності формулюється так: для лінійної ...
