Диссертация (1145311), страница 22
Текст из файла (страница 22)
. , vm ) с элементами gij(i = 1, 2, . . . , m; j = 1, 2, . . . , m), где gij = (vi , vj ) – скалярное произведениестолбцов vi и vj .159Если обозначим через A = (v1 , v2 , . . . , vm ) матрицу, построенную из столбцов v1 , v2 , . . . , vm ∈ V (dim V = n), то, очевидно, что G = AT A.Пусть теперь v1 , v2 , . . . , vm ∈ V базис линейной оболочки L = [v1 , v2 , .
. . , vm ].Следовательно, m ≤ n.Теорема 56. L ∩ L⊥ 6= 0 тогда и только тогда, когдаdet G(v1 , v2 , . . . , vm ) = 0.Доказательство. Необходимость. Пусть u ∈ L ∩ L⊥ и u 6= 0. Так какu ∈ L, то u раскладывается по базису L, т. е. u = x1 v1 + x2 v2 + . . . + xm vm , гдеxi ∈ {0, 1}, i = 1, 2, . . . , m, — координаты вектора u в базисе подпространства L.Пусть X = (x1 , x2 , .
. . , xm )T – координатный столбец вектора u. Очевидно, чтоu 6= 0 тогда и только тогда, когда X 6= 0. Поскольку u кроме подпространства Lпринадлежит также подпространству L⊥ , то (u, vi ) = 0 для всех i = 1, 2, . . . , m.То есть (x1 v1 + x2 v2 + .
. . + xm vm , vi ) = 0, i = 1, 2, . . . , m. Последние m равенствможно рассматривать как одно матричное равенство GX = 0, где X 6= 0. Наполученное матричное равенство можно смотреть как на систему m линейныходнородных уравнений с m неизвестными, имеющую ненулевое решение. Следовательно, определитель матрицы коэффициентов этой системы должен бытьравен нулю. То есть det G = 0, что и требовалось доказать.Достаточность. Пусть det G = 0.
Тогда уравнение GX = 0 имеет решениеX 6= 0. Подставляя решение в уравнение, получим равенство GX = 0. Расписывая данные равенства поэлементно и делая необходимые преобразования,получим m равенств: (x1 v1 + x2 v2 + . . . + xm vm , vi ) = 0, i = 1, 2, . . . , m, которыеговорят о том, что вектор u = x1 v1 + x2 v2 + .
. . + xm vm , во-первых, принадлежитподпространству L, во-вторых, не равен нулю и, в-третьих, принадлежит L⊥ .Следовательно, L ∩ L⊥ 6= 0, что и требовалось доказать.160Следствие 15. Пространство V является прямой суммой подпространстваL и его ортогонального дополнения L⊥ , т. е. V = L ⊕ L⊥ , тогда и толькотогда, когда det G 6= 0.Следствие 16.
Пусть Xi = (xi1 , xi2 , . . . , xim )T – i-й координатный столбец(i = 1, 2, . . . , k) фундаментальной системы решений X1 , X2 , . . . , Xk уравненияGX = 0. Тогда вектора ui = xi1 v1 + xi2 v2 + . . . + xim vm , i = 1, 2, . . . , k образуютбазис подпространства L ∩ L⊥ .Следствие 17. dim(L ∩ L⊥ ) = m − rank G.Доказательство сразу же следует из следствия 16.Следствие 18.
Если det G(v1 , v2 , . . . , vm ) 6= 0, то векторы v1 , v2 , . . . , vm линейно независимы.Доказательство. Если векторы v1 , v2 , . . . , vm линейно зависимы, тоdet G(v1 , v2 , . . . , vm ) = 0.Следствие 19. Пусть det G(X1 , X2 , . . . , Xm ) 6= 0; тогда векторы X1 , X2 , . . .,Xm линейно независимы.Замечание 27. Частный случай следствия 19, когда G — единичная матрица, рассмотрен в книге [48].Особенностью векторных пространств над полем по модулю 2 являетсято, что утверждение, обратное доказанному в следствии 4, не является верным.Так, векторы (1, 1, 1, 1, 1)T и (1, 0, 1, 0, 1)T линейно независимы, а определительматрицы Грама этих векторов равен нулю.161Кроме перечисленных выше способов построения подпространств пространства n-столбцов V : линейная оболочка, сумма и пересечение подпространств,ортогональное дополнение подпространства, можно рассмотреть еще подпространства решений систем линейных однородных уравнений AX = 0, где матрица A имеет n столбцов.Если обозначим подпространство решений через L, то, очевидно, что L =[X1 , X2 , .
. . , Xk ], где X1 , X2 , . . . , Xk – фундаментальная система решений уравнения AX = 0. К особенностям базиса подпространства L (уравнение решаетсянад полем по модулю два) следует отнести тот факт, что вектора фундаментальной системы решений, построенной стандартным способом, будут “выделять” вмножестве столбцов матрицы A минимальные 1-зависимые подсистемы (т. е.линейные комбинации AXi после удаления в них нулевых столбцов будут минимальными 1-зависимыми совокупностями).Особый интерес подпространство решений уравнения AX = 0 может представлять в случае, когда столбцы матрицы A 1-зависимы.
Особенностью такого случая является то, что уравнение AX = 0 имеет решение X = I, где I –столбец из единиц (следует из определения 1-зависимости). На основании теоремы 55 столбцы матрицы A разбиваются на минимальные 1-зависимые подсистемы столбцов: A1 , A2 , . . .
, Ak – обозначения подсистем. Тогда существуеттакая матрица перестановки P , что AP = (A1 , A2 , . . . , Ak ) = Ã. ПосколькуAX = (AP )(P T X) = ÃY , то вместо уравнения AX = 0 можно рассматриватьэквивалентное ему уравнение ÃY = 0. Причем уравнение ÃY = 0 также допускает решение Y = I, так как P T I = I. В соответствии со структурой матрицыà решение Y = I может быть представлено в виде I T = (I1T , I2T , . .
. , IkT ), гдеAj Ij = 0 (j = 1, 2, . . . , k; Ij – столбец из единиц соответствующей размерности). Если ввести столбцы Y1 = (I1T , 0T2 , . . . , 0Tk )T , Y2 = (0T1 , I2T , . . . , 0Tk )T , . . . ,Yk = (0T1 , . . . , 0Tk−1 , IkT )T , то очевидно, что столбцы Y1 , Y2 , . . . , Yk будут решениями уравнения ÃY = 0, так как ÃYj = Aj Yj = 0. Рассмотрим вопрос, когдарешения Y1 , Y2 , . . . , Yk образуют фундаментальную систему решений уравнения162ÃY = 0. Ответив на него, мы фактически ответим и на более общий вопрос:когда система уравнений AX = 0, допускающая решение X = I, имеет фундаментальную систему решений, число решений в которой совпадает с числомминимальных 1-зависимых подсистем, на которые разбивается совокупностьстолбцов матрицы A.Теорема 57. Пусть столбцыY1 = (I1T , 0T2 , .
. . , 0Tk )T , Y1 = (0T1 , I2T , . . . , 0Tk )T , . . . ,Yk = (0T1 , . . . , 0Tk−1 , IkT )T(3.1)являются решениями уравнения ÃY = 0. Они образуют фундаментальнуюсистему решений уравнения ÃY = 0 тогда и только тогда, когда определяемое этими решениями разбиение столбцов матрицы Ã = (A1 , A2 , . . . , Ak ) на1-зависимые подсистемы A1 , A2 , . . .
, Ak единственно и сами подсистемы минимальные.Доказательство. Необходимость. Пусть Y1 , Y2 , . . . , Yk – фундаментальная система решений. Она решений определяет разбиение множества столбцов матрицы Ã на минимальные 1-зависимые совокупности. Предположим, чтоимеется еще одно разбиение множества столбцов матрицы Ã на минимальные1-зависимые подсистемы столбцов, отличное от A1 , A2 , . .
. , Ak . Тогда этому разбиению соответствует хотя бы одно решение системы уравнений ÃY = 0, не являющееся линейной комбинацией Y1 , Y2 , . . . , Yk . Действительно, поскольку дварассматриваемых разбиения различны, то хотя бы одна подсистема столбцоввторого разбиения не совпадает ни с одной из подсистем A1 , A2 , . . .
, Ak , т. е. врешении, которое соответствует данной подсистеме столбцов, в каждой из k частей есть нули и единицы. Тем самым оно не может быть линейной комбинациейвекторов Y1 , Y2 , . . . , Yk , что противоречит условию.Достаточность. Пусть разбиение A1 , A2 , . . . , Ak столбцов матрицы A наминимальные 1-зависимые системы единственно (с точностью до перестановки163столбцов в каждой из совокупностей, составляющих разбиение).
Предположим,что векторы (1), соответствующие данному разбиению столбцов матрицы Ã, необразуют фундаментальной системы решений уравнения ÃY = 0. Такое предположение эквивалентно утверждению, что уравнение ÃY = 0 имеет решениеỸ , не являющееся линейной комбинацией совокупности векторов (3.1). Компоненты вектора Ỹ определяют выбор 1-зависимой системы столбцов матрицы Ã.Так как Ỹ не выражается через векторы (1), то соответствующая 1-зависимаяподсистема не есть объединение никаких подсистем из A1 , A2 , . . . , Ak .
Отталкиваясь от этой 1-зависимой подсистемы, на основании теоремы 55 можно получить разбиение множества столбцов матрицы Ã на минимальные 1-зависимыеподсистемы, отличное от A1 , A2 , . . . , Ak . Данное противоречие завершает доказательство теоремы.Замечание 28. Столбцы 1-зависимой совокупности можно всегда считатьразличными. Действительно, после удаления из 1-зависимой совокупностичетного числа одинаковых столбцов она снова будет 1-зависимой совокупностью. Далее, любую ненулевую совокупность различных столбцов можно превратить в 1-зависимую совокупность различных столбцов добавлением илиудалением одного столбца, если, конечно, она изначально не является таковой.
Действительно, пусть нам дана совокупность ненулевых различныхстолбцов A1 , A2 , . . . , Am . Построим из этих столбцов матрицу A и столбецAm+1 следующим образом: в столбце Am+1 поставим единицы на тех местах,где соответствующие строки матрицы A нечетные. Тогда, если в искомойсовокупности нет столбца, равного столбцу Am+1 , добавляя к совокупностистолбец Am+1 , получим 1-зависимую совокупность A1 , A2 , . . . , Am , Am+1 . Если в искомой совокупности оказался столбец, равный Am+1 (таким можетоказаться только один столбец), то удаляем его. Оставшаяся совокупностьm − 1 столбцов будет 1-зависимой совокупностью.164Замечание 29. На множестве всевозможных (0, 1)-столбцов одинаковой длины мы можем задать три бинарные ассоциативные операции, результатомдействия которых будет снова (0, 1)-столбец этого же множества: суммастолбцов по модулю два, булева сумма столбцов и адамарово (поэлементное)умножение столбцов. Если обозначим указанное множество через V , операцию сложения по модулю 2 знаком +, операцию булева сложения знаком+̇, операцию адамарова умножения знаком ◦, то для любых u, v ∈ V будемиметь (u + v) + (u+̇v) + (u ◦ v) = 0.Замечание 30.
Множество n-столбцов из нулей и единиц с операциями сложения + и умножения ◦, упомянутыми в замечании 29, образует конечноеассоциативное коммутативное кольцо с единицей. Роль единицы в этом кольце выполняет n-столбец I (столбец из единиц).3.1.1. Теорема о циклах и разрезахПриведем сначала необходимые сведения из теории графов.Определение 22. Графом G будем называть упорядоченную пару (V, E), гдеV — множество вершин, или узлов графа, и E — множество его ребер.Далее мы будем рассматривать только графы, ребра которых являютсянеупорядоченными парами {vi , vj }, где vi и vj — вершины из V , и нет ребер,соединящих одну и ту же вершину, т. е., неориентированные простые графы.Определение 23.
Граф называется помеченным, если его вершинам и ребрам в соответствии с определенными правилами, зависящими от задачи, сопоставлены какие-либо метки (обычно различные натуральные числа).В дальнейшем мы будем рассматривать только помеченные графы.Понятие инцидентности сопоставляет каждое ребро вершинам, которыеэто ребро соединяет. Например, ребро {vi , vj } инцидентно вершинам vi и vj .165Если существует ребро, соединяющее две вершины, то говорят, что эти вершиныявляются смежными. Более формально, вершины vi , vj ∈ V смежные, если{vi , vj } ∈ E.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
