Матрица перестановок

Матрица с ровно одной единицей в строке и столбце

В математике , особенно в теории матриц , матрица перестановок представляет собой квадратную двоичную матрицу , которая имеет ровно одну запись со значением 1 в каждой строке и каждом столбце, а все остальные записи равны 0. ^{[1] : 26  Матрица перестановок} размера n × n может представлять собой перестановку. из n элементов. Предварительное умножение n - строчной матрицы M на матрицу перестановок P , образуя PM , приводит к перестановке строк M , тогда как последующее умножение n -столбцовой матрицы M , образующей MP , переставляет столбцы M.

Каждая матрица перестановок P ортогональна , ее обратная матрица равна ее транспонированию : . ^{[1] : 26} Действительно, матрицы перестановок можно охарактеризовать как ортогональные матрицы, все элементы которых неотрицательны . ^[2] ${\displaystyle P^{-1}=P^{\mathsf {T}}}$

Два соответствия перестановки/матрицы

Между перестановками и матрицами перестановок существуют два естественных взаимно однозначных соответствия, одно из которых работает по строкам матрицы, другое — по ее столбцам. Вот пример, начинающийся с перестановки π в двухстрочной форме вверху слева:

${\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

Соответствие на основе строк переносит перестановку π в матрицу в правом верхнем углу. В первой строке в третьем столбце стоит 1, потому что . В более общем смысле, у нас есть где , когда и иначе. ${\displaystyle R_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle \pi (1)=3}$ ${\displaystyle R_{\pi }=(r_{ij})}$ ${\displaystyle r_{ij}=1}$ ${\displaystyle j=\pi (i)}$ ${\displaystyle r_{ij}=0}$

Соответствие на основе столбцов переносит π в матрицу в левом нижнем углу. В первом столбце в третьей строке стоит 1, потому что . В более общем смысле мы имеем где 1, когда и 0 в противном случае. Поскольку эти два рецепта отличаются только заменой i на j , матрица представляет собой транспонирование ; и, поскольку это матрица перестановок, мы имеем . Прослеживая две другие стороны большого квадрата, мы имеем и . ^[3] ${\displaystyle C_{\pi }}$ ${\displaystyle C_{\pi }}$ ${\displaystyle \pi (1)=3}$ ${\displaystyle C_{\pi }=(c_{ij})}$ ${\displaystyle c_{ij}}$ ${\displaystyle i=\pi (j)}$ ${\displaystyle C_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}$ ${\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}$ ${\displaystyle C_{\pi ^{-1}}=R_{\pi }}$

Матрицы перестановок переставляют строки или столбцы.

Умножение матрицы M либо на левую, либо на правую сторону приведет к перестановке строк или столбцов M либо на π , либо на π ⁻¹ . Детали немного сложны. ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }}$

Начнем с того, что когда мы переставляем элементы вектора некоторой перестановкой π , мы перемещаем элемент входного вектора в слот выходного вектора. Какая запись тогда окажется, скажем, в первом слоте вывода? Ответ: Запись, для которой , и, следовательно , . Рассуждая аналогичным образом о каждом из слотов, мы находим, что выходной вектор равен ${\displaystyle (v_{1},\ldots ,v_{n})}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle v_{i}}$ ${\displaystyle \pi (i)^{\text{th}}}$ ${\displaystyle v_{j}}$ ${\displaystyle \pi (j)=1}$ ${\displaystyle j=\pi ^{-1}(1)}$

${\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}$

хотя мы делаем перестановку на , а не на . Таким образом, чтобы переставить записи на , мы должны переставить индексы на . ^{[1] : 25} (Перестановка записей с помощью иногда называется принятием точки зрения алиби , тогда как перестановка индексов с помощью принимает точку зрения псевдонима . ^[4] ) ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$

Теперь предположим, что мы предварительно умножаем некоторую n -строчную матрицу на матрицу перестановок . По правилу умножения матриц запись в произведении равна ${\displaystyle M=(m_{i,j})}$ ${\displaystyle C_{\pi }}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle C_{\pi }M}$

$${\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}$$

где 0, кроме случаев , когда оно равно 1. Таким образом, единственный член суммы, который выживает, - это член, в котором , и сумма уменьшается до . Поскольку мы переставили индекс строки на , мы переставили сами строки M на π . ^{[1] : 25} Аналогичный аргумент показывает, что пост-умножение матрицы M с n столбцами на меняет местами ее столбцы на π . ${\displaystyle c_{i,k}}$ ${\displaystyle i=\pi (k)}$ ${\displaystyle k=\pi ^{-1}(i)}$ ${\displaystyle m_{\pi ^{-1}(i),j}}$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle R_{\pi }}$

Два других варианта — предварительное умножение на или последующее умножение на , и они переставляют строки или столбцы соответственно на π ⁻¹ вместо π . ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }}$

Транспонирование также является обратным

Связанный с этим аргумент доказывает, что, как мы утверждали выше, транспонирование любой матрицы перестановок P также действует как ее инверсия, а это означает, что P обратима. (Артин оставляет это доказательство в качестве упражнения, ^{[1] : 26} , которое мы здесь решаем.) Если , то запись его транспонирования равна . Затем происходит поступление продукта ${\displaystyle P=(p_{i,j})}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle P^{\mathsf {T}}}$ ${\displaystyle p_{j,i}}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle PP^{\mathsf {T}}}$

$${\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}$$

Всякий раз , когда член этой суммы является произведением двух разных записей в столбце P ; поэтому все члены равны 0, а сумма равна 0. Когда мы суммируем квадраты элементов в строке P , поэтому сумма равна 1. Таким образом, произведение является единичной матрицей. Симметричный аргумент показывает то же самое для , подразумевая, что P обратим с . ${\displaystyle i\neq j}$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle i=j}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle PP^{\mathsf {T}}}$ ${\displaystyle P^{\mathsf {T}}P}$ ${\displaystyle P^{-1}=P^{\mathsf {T}}}$

Умножение матриц перестановок

Учитывая две перестановки из n элементов 𝜎 и 𝜏, произведение соответствующих матриц перестановок на основе столбцов C _σ и C _τ определяется как ^{[1] ​​: 25} , как и следовало ожидать, по формуле

$${\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}$$

${\displaystyle \sigma \circ \tau }$

$${\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}$$

C _τC _σ ${\displaystyle C_{\sigma \,\circ \,\tau }}$

Для матриц на основе строк есть особенность: произведение R _σ и R _τ определяется выражением

${\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}$

с 𝜎, примененным перед 𝜏 в составной перестановке. Это происходит потому, что мы должны выполнить предварительное умножение, чтобы избежать инверсий при варианте на основе строк, поэтому мы должны выполнить предварительное умножение сначала на R _σ , а затем на R _τ .

Некоторые люди, применяя функцию к аргументу, пишут функцию после аргумента ( постфиксная запись ), а не перед ним. При выполнении линейной алгебры они работают с линейными пространствами векторов-строк и применяют линейное отображение к аргументу, используя матрицу отображения для последующего умножения вектора-строки аргумента. Они часто используют оператор композиции слева направо, который мы здесь обозначаем точкой с запятой; поэтому композиция определяется либо ${\displaystyle \sigma \,;\,\tau }$

${\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}$

или, более элегантно,

${\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}$

с 𝜎, примененным первым. Это обозначение дает нам более простое правило умножения матриц перестановок на основе строк:

${\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}$

Матричная группа

Когда π — тождественная перестановка, которая для всех i имеет место , C _π и R _π являются единичной матрицей . ${\displaystyle \pi (i)=i}$

Нет ! _ матрицы перестановок, поскольку существует n ! перестановки и карта представляют собой взаимно однозначное соответствие между перестановками и матрицами перестановок. (Карта — еще одно такое соответствие.) По приведенным выше формулам эти матрицы перестановок размера n × n образуют группу порядка n ! при умножении матриц, с единичной матрицей в качестве ее единичного элемента , группы, которую мы обозначаем . Группа является подгруппой общей линейной группы обратимых матриц действительных чисел размера n × n . Действительно , для любого поля F группа также является подгруппой группы , где элементы матрицы принадлежат F. (Каждое поле содержит 0 и 1 с и и это все, что нам нужно для умножения матриц перестановок. Разные поля расходятся во мнениях относительно того, является ли , но эта сумма не возникает.) ${\displaystyle C\colon \pi \mapsto C_{\pi }}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle GL_{n}(\mathbb {R} )}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle GL_{n}(F)}$ ${\displaystyle 0+0=0,}$ ${\displaystyle 0+1=1,}$ ${\displaystyle 0*0=0,}$ ${\displaystyle 0*1=0,}$ ${\displaystyle 1*1=1;}$ ${\displaystyle 1+1=0}$

Пусть обозначает симметричную группу или группу перестановок на {1,2,..., n }, где групповая операция представляет собой стандартную композицию справа налево " "; и пусть обозначает противоположную группу , которая использует композицию слева направо " ". Карта , которая переводит π в свою матрицу на основе столбцов, является точным представлением , и аналогично для карты , которая переводит π в . ${\displaystyle S_{n}^{\leftarrow }}$ ${\displaystyle \circ }$ ${\displaystyle S_{n}^{\rightarrow }}$ ${\displaystyle \,;\,}$ ${\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}$ ${\displaystyle C_{\pi }}$ ${\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}$ ${\displaystyle R_{\pi }}$

Дважды стохастические матрицы

Любая матрица перестановок является дважды стохастической . Набор всех дважды стохастических матриц называется многогранником Биркгофа , и матрицы перестановок играют в этом многограннике особую роль. Теорема Биркгофа – фон Неймана утверждает, что каждая дважды стохастическая действительная матрица представляет собой выпуклую комбинацию матриц перестановок одного и того же порядка, причем матрицы перестановок являются в точности крайними точками (вершинами) многогранника Биркгофа. Таким образом, многогранник Биркгофа представляет собой выпуклую оболочку матриц перестановок. ^[5]

Линейно-алгебраические свойства

Точно так же, как каждая перестановка связана с двумя матрицами перестановок, каждая матрица перестановок связана с двумя перестановками, как мы можем видеть, переименовав пример в большом квадрате выше, начиная с матрицы P в правом верхнем углу:

${\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

Поэтому здесь мы обозначаем инверсию C как и инверсию R как . Затем мы можем вычислить линейно-алгебраические свойства P на основе некоторых комбинаторных свойств, которые являются общими для двух перестановок и . ${\displaystyle \kappa }$ ${\displaystyle \rho }$ ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}=\kappa _{P}^{-1}}$

Точка фиксируется только тогда , когда она фиксируется , а след P — это количество таких общих фиксированных точек. ^{[1] : 322} Если целое число k является одним из них, то стандартный базисный вектор ek является собственным вектором _P . ^{[1] : 118} ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}}$

Чтобы вычислить комплексные собственные значения P , запишите перестановку как композицию непересекающихся циклов , скажем . (Перестановки непересекающихся подмножеств коммутируют, поэтому здесь не имеет значения, составляем ли мы справа налево или слева направо.) Для пусть длина цикла равна , и пусть – множество комплексных решений , эти решения являются корнями единства . Тогда объединение мультимножеств является мультимножеством собственных значений P . Поскольку запись как произведение циклов дала бы одинаковое количество циклов одинаковой длины, анализ дал бы тот же результат. Кратность любого собственного значения v — это число i , для которого содержится v . ^[6] (Поскольку любая матрица перестановок нормальна , а любая нормальная матрица диагонализуема по комплексным числам, ^{[1] : 259} , алгебраическая и геометрическая кратности собственного значения v одинаковы.) ${\displaystyle \kappa _{P}}$ ${\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}$ ${\displaystyle 1\leq i\leq t}$ ${\displaystyle c_{i}}$ ${\displaystyle \ell _{i}}$ ${\displaystyle L_{i}}$ ${\displaystyle x^{\ell _{i}}=1}$ ${\displaystyle \ell _{i}^{\,{\text{th}}}}$ ${\displaystyle L_{i}}$ ${\displaystyle \rho _{P}}$ ${\displaystyle \rho _{p}}$ ${\displaystyle L_{i}}$

Из теории групп мы знаем, что любую перестановку можно записать как композицию транспозиций . Следовательно, любая матрица перестановки разлагается как произведение элементарных матриц переключения строк , каждая из которых имеет определитель -1. Таким образом, определитель матрицы перестановки P является знаком перестановки , который также является знаком . ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}}$

Ограниченные формы

• Массив Костаса — матрица перестановок, в которой все векторы смещения между элементами различны.
• головоломка с n ферзями — матрица перестановок, в которой имеется не более одной записи на каждой диагонали и антидиагонали.

Смотрите также

• Матрица знакопеременных знаков
• Матрица обмена
• Обобщенная матрица перестановок
• Полином Ладьи
• Постоянный

Рекомендации

1. Артин, Майкл (1991). Алгебра . Прентис Холл. стр. 24–26, 118, 259, 322.
2. Завланос, Майкл М.; Паппас, Джордж Дж. (ноябрь 2008 г.). «Динамический системный подход к сопоставлению взвешенных графов». Автоматика . 44 (11): 2817–2824. CiteSeerX 10.1.1.128.6870 . doi : 10.1016/j.automatica.2008.04.009. S2CID  834305 . Проверено 21 августа 2022 г. Обозначим через множество ортогональных матриц и через множество поэлементных неотрицательных матриц. Тогда , где – набор матриц перестановок.  ${\displaystyle O_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle N_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle P_{n}=O_{n}\cap N_{n}}$ ${\displaystyle P_{n}}$ ${\displaystyle n\times n}$
3. Эта терминология не является стандартной. Большинство авторов используют только одно из двух соответствий, выбирая то, которое соответствует другим их соглашениям. Например, Артин использует соответствие на основе столбцов. Мы придумали здесь два названия, чтобы обсудить оба варианта.
4. Конвей, Джон Х.; Бургель, Хайди; Гудман-Штраус, Хаим (2008). Симметрии вещей . АК Петерс. п. 179. Перестановку, скажем, имен нескольких людей, можно рассматривать как перемещение либо имен, либо людей. Точка зрения псевдонима рассматривает перестановку как присвоение нового имени или псевдонима каждому человеку (от латинского alias = иначе). Альтернативно, с точки зрения алиби, мы перемещаем людей в места, соответствующие их новым именам (от латинского алиби = в другое место).
5. Бруальди (2006) стр.19
6. Дж. Наджнудель, А. Никехбали, 2010, стр.4.

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том. 108. Кембридж: Издательство Кембриджского университета . ISBN 0-521-86565-4. Збл  1106.05001.
• Джозеф, Наджнудель; Ашкан, Никегбали (2010), Распределение собственных значений рандомизированных матриц перестановок , arXiv : 1005.0402 , Bibcode : 2010arXiv1005.0402N