Дискретная математика: графы и автоматы. Альпин Ю.А - 29 стр.

§ 2. Нормальная форма матрицы смежности                приводимого графа            29


    Теперь пусть граф приводим и V1 , V2 , . . . , Vs — нормальная ну-
мерация компонент. Перенумеруем вершины графа, придав первые
номера вершинам из V1 , а остальные вершины — произвольно. При
такой нумерации, очевидно, матрица смежности примет форму (1)
и тем самым доказана её приводимость. Если же продолжить ну-
мерацию, придав очередные номера вершинам из V2 , и так далее
(то есть, произвести нормальную нумерацию), то получим желаемую
форму (2). ¤
    Как видно из предложения 1, при “правильной” нумерации вер-
шин матрица графа наглядно отражает его строение. А именно, её
диагональные блоки являются по существу матрицами смежности
компонент, а блоки, лежащие левее диагонали, содержат информацию
о дугах, идущих из компоненты с бо́льшим номером в компоненты с
меньшим номером.
    Любая квадратная булева матрица A может рассматриваться как
матрица смежности орграфа. Учитывая, что при новой нумерации
вершин графа его матрица смежности A заменяется перестановочно
подобной матрицей P AP T , замечаем, что второе утверждение пред-
ложения 1 принимает следующий вид:
   Следствие 1. Любая приводимая булева матрица некоторым
перестановочным подобием приводится к нормальной форме.
     Полученные выше сведения об орграфах и их матрицах смежно-
сти можно применять для анализа матриц над полем. Пусть C = (cij )
— комплексная матрица порядка n. Графом матрицы C называют
нумерованный орграф с n вершинами, в котором i → j ⇔ aij 6= 0.
Портретом комплексной матрицы C в вычислительной линейной
алгебре называют (0,1)-матрицу A = (aij ) такую, что aij = 1 ⇔
cij 6= 0. Ясно, что булевский портрет A матрицы можно понимать
как матрицу смежности графа матрицы C.
     Поскольку перестановочное подобие P лишь переставляет стро-
ки и столбцы, то нули в матрицах P AP −1 и P CP −1 стоят на одних и
тех же местах.1) Следовательно, комплексная матрица неприводима в
точности тогда, когда неприводим её портрет. А если она приводима,
то перестановочное подобие P , преобразующее её портрет к нормаль-
ному виду, преобразует и саму комплексную матрицу к нормальному
виду. Поэтому следствие 1 распространяется и на комплексные мат-
рицы.
  1)
     Разумеется, в первом случае перестановочную матрицу P нужно считать булевой, а во
втором — комплексной матрицей, но мы не применяем разных обозначений, поскольку в обоих
случаях производится одинаковая перестановка рядов.