О необходимых и достаточных условиях Р-подобия одного класса (0, 1)- матриц

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 512. 643.8 А. А. Беспалов
Вестник СПбГУ. Сер. 10, 2006, вып. 2
О НЕОБХОДИМЫХ И ДОСТАТОЧНЫХ УСЛОВИЯХ Р-ПОДОВИЯ ОДНОГО КЛАССА (0,1)-МАТРИЦ
Определение 1. *) Матрицы, А и В будем называть Р-подобными, если выполняется соотношение В — РАР'-, причем Р — матрица перестановок.
Другими словами, будем говорить, что квадратные матрицы, А и В P-подобны (перестановочно подобны), если от одной матрицы к другой можно перейти с помощью перестановки рядов, т. е. перестановки строк и такой же перестановки столбцов.
Нетрудно видеть, что P-подобие является частным случаем подобия матриц.
Обозначим через sa и sb столбцы строчных сумм, а через qa и qs — столбцы столбцовых сумм матриц, А и В соответственно**). Тогда sa — Ае, sb — Be, qA = А'-е и qs — В'-е, где е — столбец из единиц.
Будем в дальнейшем считать, что матрицы, А и В — квадратные (0,1)-матрицы одинаковой размерности.
Утверждение 1. Матрицы, А и В, у которых столбцы как строчных, так и столбцовых сумм состоят из различных элементов, будут перестановочно подобны тогда и только тогда, когда существует такое Р, что Psa = sb и Pqa — Чв-
Доказательство. Доказательство необходимости предварим следующим очевидным замечанием: квадратная (ОД)-матрица Р будет матрицей перестановки тогда и только тогда, когда Ре — Р'-е = е.
Пусть, А P-подобна В, т. е. существует такая матрица перестановки Р, что РАР1 — В. Из этого равенства тотчас следует, что РАР'-е = Be =& gt- РАе — Be, или Psa — sb-Аналогично, из РАР'- - В =& gt- РА'-Р'- - В1 =& gt-¦ РА'-е = В'-е, или PqA — qe- Тем самым необходимость доказана.
Достаточность. Пусть выполнено Psa — sb и PqA — qe- Нетрудно видеть, что, в силу требования различности элементов в столбцах как строчных, так и столбцовых сумм матриц, А и В соответственно, матрица Р будет определяться единственным образом. Поэтому, не нарушая общности рассуждений, будем считать, что матрица Р совпадает с единичной матрицей. В этом случае исходное предположение можно записать как sa = sb и Ча — Чв-
Будем также предполагать, что матрицы, А и В имеют размерность п и элементы в столбце sa — sb упорядочены по убыванию.
Поскольку рассматриваемые в дальнейшем свойства матриц, А и В аналогичны, то ограничимся рассмотрением только матрицы А.
Максимальная строчная сумма у матрицы, А может быть равна или п, или п — 1. Число различных возможных столбцов строчных сумм с различными элементами равно п: начинающихся с п равно п — 1, и один столбец начинается с п — 1. Максимальная сумма элементов столбца строчных сумм (максимальная сумма всех элементов у матриц А) в данном случае равна половине произведения п (п + 1). Таким свойством обладает один столбец (п, п — 1,…, 2,1)'-. Аналогичная минимальная сумма равна половине
*) Беспалое А. А. Матричный метод проверки изоморфизма графов // Вести. С. -Петерб. унта. Сер. 10: Прикладная математика и информатика, процессы управления. 2004. Вып. 3. С. 6, определение 1.2.
'*) Там же, с. 8.
© А. А. Беспалов, 2006
произведения п (п — 1). Таким свойством обладает только столбец (п — 1,…, 1,0)'-. У матриц со столбцами строчных сумм, начинающихся с я, за исключением матрицы со столбцом с максимальной суммой элементов, последняя строка нулевая.
Рассмотрим теперь матрицу АН, где Н — матрица перестановки, которая упорядочивает элементы в столбце столбцовых сумм. В соответствии с утверждением будем считать, что столбец столбцовых сумм матрицы АН состоит из различных элементов и элементы в столбце столбцовых сумм упорядочены по тому же правилу, что и элементы в столбце строчных сумм. Очевидно, что в рассматриваемом случае матрица Н определяется единственным образом. Нетрудно вйдеть, что матриц, А с таким условием всего две — это матрицы со столбцами строчных сумм (п, п — 1,…, 2,1)'- и (п — 1,…, 1,0)'-. Дело в том, что у матриц, А со столбцами строчных сумм, начинающихся спи имеющих нулевую строку, упорядоченные столбцы матриц АН начинаются сп — 1. Как отмечено выше, матрица с таким условием имеет сумму элементов, равную половине произведения п (п — 1). Матрицы, у которых упорядоченные столбцы строчных (столбцовых) сумм начинаются с п, имеют сумму элементов большую, чем половина произведения гг (п — 1).
Таким образом, с точностью до перестановки столбцов есть всего две матрицы с упорядоченными столбцами строчных сумм, состоящих из разных элементов, и со столбцами столбцовых сумм, также содержащих различные элементы. С точностью до перестановки столбцов эти матрицы равны треугольным матрицам с единицами над диагональю, идущей из правого верхнего угла в левый нижний. У одной из матриц указанная диагональ состоит из единиц, у другой — из нулей.
Итак, условие, что как столбец строчных сумм, так и столбец столбцовых сумм состоят из различных элементов, в случае когда один из них задан, определяет (0,^-матрицу единственным образом. Этим завершается доказательство достаточности утверждения.
Замечание1. Если Psa — sb, a PqA ф qe, то матрицы Аи В не будут перестановочно подобными, и, следовательно, класс (ОД)-матриц, определяемых условием, что у них столбцы как строчных сумм, так и столбцовых сумм состоят из разных элементов, состоит из 2п различных подмножеств перестановочно подобных внутри подмножеств матриц.
Замечание2. Поскольку на квадратные (0,1)-матрицы можно смотреть как на матрицы смежности графов, то доказываемое утверждение можно сформулировать в терминах изоморфизма графов.
Утверждение 2. Два графа с матрицами смежности, А и В, у которых столбцы как строчных, так и столбцовых сумм состоят из различных элементов, будут изоморфными тогда и только тогда, когда существует такая матрица перестановки Р, что PsA = sb и PqA = qe-
По нашему мнению, утверждение, содержащееся в замечании 2, может быть интересно для специалистов по теории графов.
Summary
Bespalov A. A. Necessary and sufficient conditions of P-similarity in special class (0,l)-matrices.
Necessary and sufficient conditions of permutation similarity in special class (0,l)-matrices are shown.
Статья поступила в редакцию 11 декабря 2005 г.

ПоказатьСвернуть
Заполнить форму текущей работой