Диссертация (1145311), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

., Am :xi Ai , где xi ∈ GF (2). Если через A обозначить матрицу соi=1столбцами A1 , A2 , . . . , Am , а через X столбец с элементами xi , т. е. положитьA = (A1 , A2 , . . . , Am ), X = (x1 , x2 , . . . , xm )T (используем обычные матричныеобозначения), то линейная комбинация запишется как AX. Равенство нулю линейной комбинации теперь запишется как AX = 0, т. е. как система n уравненийс m неизвестными xi , которые могут принимать только два значения: 0 или 1,или как одно матричное уравнение.Теперь определение линейной независимости и зависимости совокупности(0, 1)-столбцов A1 , A2 , .

. . , Am можно дать следующим образом: совокупность(0, 1)-столбцов A1 , A2 , . . . , Am будем называть линейно независимой, если матричное уравнение AX = 0 над GF (2) имеет только нулевое решение, в противном случае указанная совокупность называется линейно зависимой.Приведенные определения конструктивны в том смысле, что дают практический способ нахождения коэффициентов линейной зависимости, посколькутеория решений систем линейных уравнений излагается для произвольного поля, следовательно, и для поля по модулю два [38].

В частности, применяемаяв теории систем линейных уравнений теория определителей имеет место и дляполя по модулю два, с той особенностью, что здесь определитель совпадает сперманентом. Таким образом, для решения систем линейных уравнений над полем по модулю два можно пользоваться методом Гаусса, теоремами Кронекера— Капелли и Крамера, поскольку ранг (0, 1)-матрицы над полем по модулю два155находится как обычно.Однако пара особенностей решения систем над полем по модулю два всеже есть: во-первых, это простота (нет вычислительных трудностей); во-вторых,для некоторого класса матричных уравнений, как покажем в дальнейшем, возможна визуальная иллюстрация решений на графах.Воспользуемся сказанным выше применительно к теореме 55, сделав предварительно замечание.Пусть совокупность векторов A1 , A2 , .

. . , Am линейно независима, а совоmXкупность A1 , A2 , . . . , Am , Am+1 линейно зависима. Тогда Am+1 =xi Ai , илиi=1(A1 , A2 , . . . , Am )X = Am+1 . Последнее равенство можно рассматривать как матричное уравнение относительно определения коэффициентов линейной зависиmXмости Am+1 =x0i Ai (x0i – конкретное значение переменной xi , а именно 0i=1или 1). Заметим, что матричное уравнение (A1 , A2 , .

. . , Am )X = Am+1 , в силулинейной независимости столбцов A1 , A2 , . . . , Am имеет единственное решениеX = X 0 . Приведенное рассуждение, по сути, есть доказательство единственности разложения вектора Am+1 совокупности A1 , A2 , . . . , Am , Am+1 по базисуэтой совокупности A1 , A2 , . . ., Am .Изучим теперь 1-зависимую систему A1 , A2 , .

. . , Ak , . . . , Am и предложимконструктивный метод её разложения на минимальные 1-зависимые подсистемы. Для этого выделим некоторый базис такой системы. Не нарушая общностирассуждений, будем считать в качестве базиса подсистему A1 , A2 , . . . , Ak . Обозначим через Ã матрицу, построенную из столбцов базиса A1 , A2 , . . . , Ak .

Возьмем произвольный столбец A` , где ` ∈ {k + 1, . . . , m}, и рассмотрим единственное решение системы ÃX = A` . Ненулевые компоненты данного решения определяют некоторую подсистему системы A1 , A2 , . . . , Ak , вместе со столбцом A` составляющую минимальную 1-зависимую подсистему, которую обозначим как Ā,системы A1 , A2 , . . . , Ak , .

. . , Am . Тогда система {A1 , A2 , . . . , Ak , . . . , Am }− Ā = Aбудет 1-зависимой системой, из которой, если она не является минимальной,156можно вновь по той же схеме выделить минимальную 1-зависимую подсистему,и т. д. Очевидно, процесс выделения минимальных 1-зависимых систем конечен,проводя его и получим разбиение исходной 1-зависимой системы на минимальные 1-зависимые подсистемы.Пример 8.

Рассмотрим столбцы матрицы1 0 0 1 1 0 1A =  0 1 0 1 0 1 1 ,0 0 1 0 1 1 1которые составляют исходную 1-зависимую систему. Очевидно, что первыетри столбца являются линейно независимыми и составляют базис столбцов матрицы A. Также нетрудно видеть, что четвертый столбец есть линейнаякомбинацияпервых двух столбцов, т. е. столбцы подматрицы Ā =1 0 1 0 1 1  образуют минимальную 1-зависимую систему столбцов матри0 0 0цы A.

Столбцы матрицыA, не входящие в подматрицу Ā, т. е. столбцы0 1 0 1подматрицы A =  0 0 1 1 , будут составлять 1-зависимую подсисте1 1 1 1му и, более того, минимальную 1-зависимую подсистему.Если бы на первом шаге мы взяли не четвертый, а пятыйстолбец мат1 0 1рицы A, то получили бы следующие матрицы Ā и A: Ā =  0 0 0  и0 1 10 1 0 1A =  1 1 1 1  соответственно, столбцы которых определяют две дру0 0 1 1гие минимальные 1-зависимые подсистемы, на которые разбивается множество столбцов матрицы A.157Таким образом, с помощью приведенного примера мы не только продемонстрировали процесс разбиения 1-зависимой системы на минимальные 1-зависимые подсистемы, но и показали неоднозначность такого разбиения.Покажем теперь особенности векторных подпространств над GF (2), т. е.особенности подпространств (0, 1)-столбцов.Начнем с линейной оболочки произвольной совокупности n-столбцов A1 ,A2 , .

. ., Ak , . . ., Am над GF (2) как типичного примера подпространства. Обозначать линейную оболочку будем как [A1 , A2 , . . . , Ak , . . . , Am ]. Число возможныхлинейных комбинаций, которые можно составить из столбцов этой совокупности, равно 2m , число различных линейных комбинаций не превосходит такоечисло и совпадает с ним тогда и только тогда, когда столбцы данной совокупности линейно независимы.

Потому если столбцы A1 , A2 , . . . , Ak составляют базиссовокупности A1 , A2 , . . . , Ak , . . . , Am , то, во-первых, [A1 , A2 , . . . , Ak , . . . , Am ] =[A1 , A2 , . . . , Ak ], а, во-вторых, число различных элементов линейной оболочкиA1 , A2 , . . . , Ak , .

. . , Am равно 2k . Таким образом, число разных элементов любого конечномерного векторного пространства V над GF (2) не просто четноечисло, а это число является степенью двойки, а именно, |V | = 2dim V .Линейная оболочка n-столбцов [A1 , A2 , . . ., Ak , .

. ., Am ] с базисом A1 , A2 ,. . ., Ak изоморфна над GF (2) векторному пространству k-столбцов с базисом,составленным из столбцов единичной матрицы k-го порядка. Данное замечание позволяет “отождествлять” линейные подпространства размерности k изn-столбцов, где k ≤ n, с пространством k-столбцов.Нетрудно видеть, что n-мерное пространство n-столбцов содержит в себе(n − 1)-мерное векторное подпространство четных n-столбцов. Действительно,базисом в таком подпространстве могут служить столбцы матрицы, полученнойиз единичной матрицы (n − 1)-го порядка приписыванием к последней строкииз единиц.Сумма S и пересечение Q двух векторных подпространств L1 и L2 пространства n-столбцов V определяются обычным образом, они также являются158векторными подпространствами пространства V , при этом справедливо равенство dim S = dim L1 + dim L2 − dim Q.Однако при определении ортогонального дополнения к подпространствуL пространства (0, 1)-столбцов V (т.

е. еще одного подпространства пространства V ) мы тотчас же сталкиваемся с особенностями, вытекающими из свойствполя по модулю два. Дело в том, что в пространстве (0, 1)-столбцов над GF (2)можно получить скалярное произведение столбцов как сумму произведений соответствующих элементов столбцов над GF (2). Называя, как обычно, столбцыортогональными, если их скалярное произведение равно нулю, мы тотчас жеобнаруживаем, что все четные столбцы ортогональны сами себе. Скалярноеже произведение нечетного столбца на себя всегда равно 1. Это показывает,что скалярное произведение над GF (2) отличается от привычного скалярногопроизведения в векторных пространствах, например от скалярного произведения над полем вещественных чисел.

Роднит их то, что скалярные произведенияв указанных пространствах линейны по обоим своим аргументам. Скалярноепроизведение в пространствах над GF (2) нашло большое применение в теорииобыкновенных графов [32], что не позволяет оставить его без внимания.Вернемся к ортогональному дополнению подпространства L, которое, какобычно, будем обозначать через L⊥ , пространства столбцов V . Над GF (2) сумма подпространств L и L⊥ , вообще говоря, не совпадает с V , что становитсяочевидным, если в качестве L взять линейную оболочку [v] ненулевого четногостолбца v ∈ V .

В этом случае L ⊂ L⊥ или L ∩ L⊥ = L. Чтобы рассмотретьситуацию в общем случае, когда L ∩ L⊥ 6= 0, напомним определение матрицыГрама G совокупности векторов (столбцов) v1 , v2 , . . . , vm ∈ V .Определение 21. Матрицей Грама совокупности векторов (столбцов) v1 ,v2 , . . ., vm ∈ V называется матрица G = G(v1 , v2 , . .

Характеристики

Список файлов диссертации