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

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

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

Тогда последовательность соответствующих элементарных операций над столбцами — это умножение данной матрицысправа на матрицу P T .Для любой элементарной операции над полем GF (2) существует обратнаяэлементарная операция, причем элементарные матрицы для прямой и обратнойопераций совпадают.Определение 29. Две квадратные (0, 1)-матрицы n-го порядка A и C будемназывать конгруэнтными над полем GF (2) если существует невырожденная(0, 1)-матрица P такая, что C = P T AP .Теорема 61.

Любая симметричная (0, 1)-матрица A конгруэнтна блочно-диагональной матрице видаAe = diag(L1 , L2 , . . . , Lq , l1 , l2 , . . . , lp , 0, 0, . . . , 0)где lj (j = 1, 2, . . . , p) единичный блок размерности 1 × 1, Lk (k = 1, 2, . . . , q)0 1, и p + 2q = rank A.— матрица 2 × 2 вида 1 0Доказательство. Если на главной диагонали матрицы A стоит хотя быодна единица, тогда с помощью двойных элементарных операций мы можем поставить эту единицу в левый верхний угол матрицы.

Затем применим двойныеэлементарные операции для обнуления всех остальных элементов, стоящих впервой строке и в первом столбце. В результате мы сведем рассматриваемуюзадачу к такой же задаче, но уже для матрицы размерности на единицу меньше,(n − 1) × (n − 1).Теперь рассмотрим случай, когда все элементы, стоящие на главной диагонали матрицы A, нулевые. Если хотя бы один элемент матрицы отличен отнуля, с помощью двойной элементарной операции поместим этот элемент напересечение первой строки и второго столбца матрицы. Поскольку матрица A173симметричная, то во второй строке в первом столбце полученной матрицы также будет стоять единица.

Далее с помощью двойных элементарных операцийобнулим все элементы, стоящие в первых двух строках и первых двух столбцах.Опять-таки мы свели рассматриваемую задачу к такой же задаче для матрицыразмерности (n − 2) × (n − 2), т. е. на 2 меньше. Повторяя конечное число разуказанные действия, мы получим требуемую матрицу Ae .Напомним, что невырожденная (0, 1)-матрица C в равенстве Ae = CAC Tтакая, что C −1 = C.

Отсюда следует, что равенство A = CAe C T также выполнено.В работах [46, 102, 125, 130] приводятся различные доказательства следующего результата (теорема 62). Здесь мы приводим его более простое и короткоедоказательство. Также мы предлагаем метод получения минимальной факторизации, основанный на методе исключения Гаусса.Теорема 62.

Число столбцов в матрице B в минимальной факторизацииматрицы A равноrank A + δ(A),где 1,δ(A) = 0,если aii = 0 для всех i = 1, 2, . . . , n,в противном случае.Доказательство.Еслина главной диагонали матрицы Ae находтся толь0 1, тогда мы можем записатько q блоков вида 1 0Ae = QQT ,174гдеQ=IO...OOH H ...

H H J I H ... H H J .O O ... I H J O O ... O L JЗдесьI=1 00 1,L = 0 11 0,H = 1 11 1,J = 11и число столбцов в Q равно 2q + 1. Если r = rank A < n, добавим к матрице Qn − r нулевых строк.Если на главной диагонали матрицы Ae стоят q блоков вида 0 11 0иpединиц, тогдаAe = QQT ,гдеQ=IO...OOOO...OH H ... H H J 0 0 ... 0I H ...

H H J 0 0 ... 0 O O ... I H J 0 0 ... 0 O O ... O L J 0 0 ... 0 O O ... O O 1 0 0 ... 0 O O ... O O 0 1 0 ... 0 O O ... O O 0 0 0 ... 1o2q − 2 строк2 строк.p строкЗдесь O = (0, 0) и 0 = (0, 0)T . Если r < n, добавим к матрице Q всего n − rнулевых строк.175В обоих случаях равенство Ae = QQT проверяется непосредственным вычислением, и мы получаем следующее равенство:A = CAe C T = CQQT C T .Это означает, что матрица A представима в виде A = BB T , где B = CQ.

Теперьдокажем, что полученная факторизация A = BB T является минимальной.Очевидно, что число столбцов матрицы B не может быть меньше r. Действительно, r = rank A ≤ rank B. Следовательно, нам требуется рассмотретьтолько случай, когда Ae = diag(L1 , L2 , . . . , Lq ).Предположим, что найдутся 2q векторов X1 , X2 , . . .

, X2q ∈ G2q таких, чтоG(X1 , X2 , . . . , X2q ) = Ae . Так как det G(X1 , X2 , . . . , X2q ) 6= 0, эти векторы линейно независимы. Это значит, что они образуют базис G2q . С одной стороны,все эти векторы четные (все элементы, стоящие на главной диагонали матрицы Ae — нули), и их линейная оболочка состоит только из четных векторов.С другой стороны, нечетный вектор (1, 0, . .

. , 0)T принадлежит линейному пространству G2q . Это значит, что число столбцов матрицы Q, удовлетворяющейравенству Ae = QQT , больше 2q.Замечание 33. Задача матричной факторизации может быть обобщена ирассмотрена не только над полем GF (2). Например, в статьях [53] и [181],изучена задача двоичной факторизации для матриц с целыми неотрицательными элементами, в работе [133] рассмотрена аналогичная задача для булевых матриц.3.2.

Графы как линейные отображенияРассмотрим конечное множество Q, состоящее из q элементов. Обозначимчерез Q0 множество всех подмножеств множества Q. На данном множестве,176состоящем из 2q элементов, рассмотрим две алгебраические операции: умножение элементов множества на элементы поля GF (2) (т. е. 0 и 1) и симметрическую разность элементов. Множество Q0 с рассмотренными операциями является линейным пространством над полем GF (2). При этом стандартный базисэтого линейного пространства состоит из элементов множества Q. Это линейное пространство WQ0 изоморфно линейному пространству WQ , состоящему изq-мерных векторов, компоненты которых — элементы GF (2), имеющих видX = (x1 , x2 , . . . , xq )T ,где xj ∈ {0, 1} при j = 1, 2, .

. . , q, с покомпонентным сложением и умножением на элементы GF (2). Сложение (0, 1)-векторов над GF (2) соответствуетсимметрической разности двух соответствующих подмножеств множества Q,а умножение вектора на 0 или 1 соответствует умножению соответствующегоподмножества Q на это же число.Пусть дан граф G.

Обозначим через E и V множества его ребер и вершинсоответственно. Согласно изложенному выше, имеем два линейных пространства WE0 и WV0 . Следовательно, граф G может быть определен как линейноеотображение WE0 → WV0 , которое каждому ребру ставит в соответствие вершины, которые оно соединяет. Матрица данного линейного отображения в стандартном базисе — это матрица инцидентности графа G (мы будем обозначатьее через B).Аналогично, граф G может быть определен как линейное отображениеWV0 → WE0 , которое каждой вершине ставит в соответствие множество ребер,инцидентных этой вершине. Очевидно, что матрица этого линейного отображения в стандартном базисе — это матрица B T . Мы имеем также два линейныхпространства WE и WV , состоящих из (0, 1)-векторов, которые изоморфны WE0и WV0 соответственно.Пусть (0, 1)-вектор Y является образом вектора X при отображении WE →WV .

Тогда имеем BX = Y (здесь мы рассматриваем умножение над полем177GF (2)). Линейное пространство WC0 = ker B — это пространство циклов графа G. В линейном пространстве WE получаем пространство решений системыуравнений BX = 0 соответственно. Каждое решение этой системы соответствует циклу или сумме циклов, не имеющих общих ребер, в пространстве WE0 .

Длякаждого (0, 1)-столбца Y , в котором ровно две единицы, решение системы уравнений BX = Y соответствует пути из одной вершины, которая соответствуетединице, в другую такую вершину и возможно, включает несколько циклов безобщих ребер. У этих циклов также нет общих ребер с путем.Рассмотрим теперь свойства матрицы реберной инцидентности B, котораяявляется (0, 1)-матрицей.

Каждый столбец B соответствует ребру графа G сn вершинами, таким образом, он содержит ровно две единицы. Все столбцыматрицы B различны. Очевидно, что rank B ≤ n−1. Граф G является связнымтогда и только тогда, когда rank B = n − 1. Ребра, соответствующие n − 1линейно независимым столбцам B, образуют остов графа G. Для графа G, укоторого p ребер, число k = p − n + 1 называется цикломатическим числом.В рассматриваемом случае k равно размерности линейного пространства WC0(или WC ).Имеется еще два линейных отображения, связанных с графом G. Одно изних — это отображение WV0 → WV0 , которое каждой вершине ставит в соответствие вершины, с ней смежные.

Матрица этого отображения в стандартномбазисе — это матрица смежности графа G (мы будем обозначать ее через A).Второе линейное отображение — это отображение WE0 → WE0 , которое каждомуребру ставит в соответствие множество ребер, которые с ним смежны. Матрицей данного отображения является матрица смежности реберного графа L(G),построенного для данного графа G (будем обозначать эту матрицу через D).3.3. Паросочетания и реберные покрытияСначала дадим необходимые определения.178Определение 30. Реберное покрытие графа G — это множество ребер графа, такое, что каждая вершина графа инцидентна по крайней мере одномуребру из этого множества. Подмножество данного покрытия, само являющееся покрытием и содержащее минимальное число ребер этого покрытия,называется минимальным покрытием.

Наименьшее реберное покрытие — этореберное покрытие, состоящее из наименьшего числа ребер. Число реберногопокрытия β(G) — количество ребер в наименьшем реберном покрытии графа G.Определение 31. Паросочетание, или независимое множество ребер в графе— это множество ребер, никакие два из которых не имеют общих вершин.Подмножество данного паросочетания, само являющееся паросочетанием исодержащее максимальное число ребер данного паросочетания, называетсямаксимальным паросочетанием.

Наибольшее паросочетание — это паросочетание, состоящее из наибольшего числа ребер. Число паросочетания α(G) —количество ребер в наибольшем паросочетании графа G.Рассмотрим теперь одно свойства матрицы B, характеризующее наибольшее паросочетание.Теорема 63.

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

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