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

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

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

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

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где составная перестановка $\sigma \circ \tau$ сначала применяется 𝜏, а затем 𝜎, работая справа налево:

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

Это следует из того, что предварительное умножение некоторой матрицы на C _τ , а затем предварительное умножение полученного произведения на C _σ дает тот же результат, что и предварительное умножение всего один раз на объединенную $C_{\sigma \,\circ \,\tau }$.

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

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

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

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

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

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

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

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

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

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

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

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

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

Двойно стохастические матрицы

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

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

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

${\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 как $\kappa$ и обратный R как $\rho$. Затем мы можем вычислить линейно-алгебраические свойства P на основе некоторых комбинаторных свойств, которые являются общими для двух перестановок. $\kappa _{P}$ и $\rho _{P}=\kappa _{P}^{-1}$.

Точка фиксируется ​ $\kappa _{P}$ только тогда, когда это исправлено $\rho _{P}$ а след P , — это количество таких общих неподвижных точек. целое число k является одним из них, то стандартный базисный вектор ek _Если является собственным вектором P .

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

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

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

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

См. также

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

Ссылки

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