Оглавление
- 1 Матрица перестановок
- 1.1 Матрицы перестановок
- 1.2 Соответствие перестановок и матриц
- 1.3 Умножение матриц перестановок
- 1.4 Матричная группа
- 1.5 Дважды стохастические матрицы
- 1.6 Теорема Биркгофа–фон Неймана
- 1.7 Линейно-алгебраические свойства
- 1.8 Вычисление комплексных собственных значений
- 1.9 Алгебраическая и геометрическая кратности
- 1.10 Определитель матрицы перестановок
- 1.11 Формы с ограниченным доступом
- 1.12 Полный текст статьи:
- 2 Матрица перестановок
Матрица перестановок
-
Матрицы перестановок
- Матрицы перестановок имеют ровно одну запись, равную 1, в каждой строке и столбце.
- Матрицы перестановок ортогональны и их обратная величина равна транспонированию.
-
Соответствие перестановок и матриц
- Существует два взаимно однозначных соответствия между перестановками и матрицами перестановок: на основе строк и на основе столбцов.
- Матрица на основе строк переводит перестановку в матрицу на основе столбцов и наоборот.
-
Умножение матриц перестановок
- Умножение матрицы на матрицу перестановок переставляет строки или столбцы матрицы.
- Транспонирование матрицы перестановок также является её инверсией.
-
Матричная группа
- Матрицы перестановок образуют группу порядка n! при матричном умножении.
- Группа матриц перестановок является подгруппой общей линейной группы.
-
Дважды стохастические матрицы
- Каждая матрица перестановок вдвойне стохастична.
- Совокупность всех дважды стохастических матриц называется многогранником Биркгофа.
-
Теорема Биркгофа–фон Неймана
- Каждая дважды стохастическая вещественная матрица является выпуклой комбинацией матриц перестановок.
- Матрицы перестановок являются крайними точками многогранника Биркгофа.
-
Линейно-алгебраические свойства
- Каждая перестановка связана с двумя матрицами перестановок.
- Каждая матрица перестановок связана с двумя перестановками.
- Точка фиксируется с помощью κP тогда и только тогда, когда это исправлено с помощью ρP.
- След P равен числу общих фиксированных точек.
- Если целое число k является фиксированной точкой, ek является собственным вектором P.
-
Вычисление комплексных собственных значений
- Запишите κP как совокупность непересекающихся циклов.
- Для каждого цикла определите длину и набор комплексных решений для xℓi = 1.
- Объединение множеств Lя является мультимножеством собственных значений P.
- Кратность собственного значения v равна числу i, для которого Lя содержит v.
-
Алгебраическая и геометрическая кратности
- Любая матрица перестановок является нормальной и диагонализуема по комплексным числам.
- Алгебраическая и геометрическая кратности собственного значения v одинаковы.
-
Определитель матрицы перестановок
- Определитель матрицы перестановок P равен знаку перестановки κP.
- Знак перестановки κP также является признаком ρP.
-
Формы с ограниченным доступом
- Массив Costas: матрица перестановок с различными векторами смещения между элементами.
- Головоломка из n ферзей: матрица перестановок с не более одной записью в каждой диагонали и антидиагонали.