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

В математике , особенно в теории матриц , матрица перестановок - это квадратная двоичная матрица, которая имеет ровно одну запись 1 в каждой строке и каждом столбце и нули в других местах. Каждая такая матрица, скажет P , представляет собой перестановку из т элементов , и, когда используется для умножения другой матрицы, скажет А , приводит к перестановке строк (при предварительно умножении, чтобы сформировать PA ) или столбцы (когда после умножения, к форме AP ) матрицы A .

Определение [ править ]

Учитывая перестановку π из m элементов,

${\ displaystyle \ pi: \ lbrace 1, \ ldots, m \ rbrace \ to \ lbrace 1, \ ldots, m \ rbrace}$

представлен в двухстрочной форме

${\ displaystyle {\ begin {pmatrix} 1 & 2 & \ cdots & m \\\ pi (1) & \ pi (2) & \ cdots & \ pi (m) \ end {pmatrix}},}$

есть два естественных способа связать перестановку с матрицей перестановок; а именно, начиная с единичной матрицы размера m × m , I _m , либо переставляют столбцы, либо переставляют строки в соответствии с π . Оба метода определения матриц перестановок появляются в литературе, и свойства, выраженные в одном представлении, могут быть легко преобразованы в другое представление. Эта статья в первую очередь будет иметь дело только с одним из этих представлений, а другое будет упоминаться только тогда, когда есть разница, о которой следует помнить.

М × м матрица перестановок P _π = ( р _IJ ) получают путем перестановки столбцов единичной матрицы I _м , то есть, для каждого I , р _IJ = 1 , если J = π ( я ) и р _Ij = 0 в противном случае, в этой статье мы будем называть столбцовым представлением . ^[1] Поскольку все записи в строке i равны 0, за исключением того, что 1 появляется в столбце π ( i ), мы можем написать

${\ displaystyle P _ {\ pi} = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ mathbf {e} _ {\ pi (2)} \\\ vdots \\\ mathbf {e} _ {\ pi (m)} \ end {bmatrix}},}$

где , А стандартный базис вектор , обозначает вектор - строку длиной м с 1 в J - м положении и 0 в любом другом положении. ^[2]${\ displaystyle \ mathbf {e} _ {j}}$

Например, матрица перестановок P _π, соответствующая перестановке, имеет вид${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}$

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.}$

Обратите внимание, что j- й столбец единичной матрицы I ₅ теперь появляется как π ( j ) -й столбец матрицы P _π .

Другое представление, полученное перестановкой строк единичной матрицы I _m , то есть для каждого j , p _ij = 1, если i = π ( j ) и p _ij = 0 в противном случае, будет называться строковым представлением .

Свойства [ править ]

В этом разделе используется столбцовое представление матрицы перестановок, если не указано иное.

Умножив раз в вектор - столбец г будет переставлять строки вектора:${\displaystyle P_{\pi }}$

${\displaystyle P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.}$

Повторное использование Этот результат показывает , что , если М представляет собой матрицу соответствующего размера, продукт, это просто перестановка строк M . Однако, учитывая, что ${\displaystyle P_{\pi }M}$

${\displaystyle P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T}}}$

для каждого k показывает, что перестановка строк задается π ⁻¹ . ( является транспонированной матрицей M. )${\displaystyle M^{\mathsf {T}}}$

Поскольку матрицы перестановок являются ортогональными матрицами (т.е. ), обратная матрица существует и может быть записана как${\displaystyle P_{\pi }P_{\pi }^{\mathsf {T}}=I}$

${\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}.}$

Умножение вектора-строки h раз переставит столбцы вектора:${\displaystyle P_{\pi }}$

${\displaystyle \mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}\;h_{2}\;\dots \;h_{n}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}={\begin{bmatrix}h_{\pi ^{-1}(1)}\;h_{\pi ^{-1}(2)}\;\dots \;h_{\pi ^{-1}(n)}\end{bmatrix}}}$

Опять же , повторное применение этого результата показывает , что после умножения матрицы M на матрицы перестановок P _П , то есть, МП _П , приводит к перестановке столбцов М . Заметьте также, что

${\displaystyle \mathbf {e} _{k}P_{\pi }=\mathbf {e} _{\pi (k)}.}$

Учитывая две перестановки л и σ из т элементов, соответствующие матрицы перестановки Р _π и P _сг , действующий на векторы - столбцы состоят с

${\displaystyle P_{\sigma }P_{\pi }\,\mathbf {g} =P_{\pi \,\circ \,\sigma }\,\mathbf {g} .}$

Те же матрицы, действующие на векторы-строки (то есть после умножения), составляются по одному и тому же правилу

${\displaystyle \mathbf {h} P_{\sigma }P_{\pi }=\mathbf {h} P_{\pi \,\circ \,\sigma }.}$

Для ясности, приведенные выше формулы используют префиксную нотацию для композиции перестановок, то есть

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

Позвольте быть матрица перестановки, соответствующая π в его строчном представлении. Свойства этого представления могут быть определены из свойств представления столбца, поскольку, в частности, ${\displaystyle Q_{\pi }}$${\displaystyle Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.}$

${\displaystyle Q_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=P_{{\pi }^{-1}}\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{(\pi ^{-1})^{-1}(k)}^{\mathsf {T}}=\mathbf {e} _{\pi (k)}^{\mathsf {T}}.}$

Из этого следует, что

${\displaystyle Q_{\sigma }Q_{\pi }\,\mathbf {g} =Q_{\sigma \,\circ \,\pi }\,\mathbf {g} .}$

По аналогии,

${\displaystyle \mathbf {h} \,Q_{\sigma }Q_{\pi }=\mathbf {h} \,Q_{\sigma \,\circ \,\pi }.}$

Группа матриц [ править ]

Если (1) обозначает единичную перестановку, то P ₍₁₎ - единичная матрица .

Пусть S _n обозначает симметрическую группу или группу перестановок на {1,2, ..., n }. Поскольку есть n ! перестановок, есть n ! матрицы перестановок. Согласно приведенным выше формулам матрицы перестановок n × n образуют группу при матричном умножении с единичной матрицей в качестве единичного элемента .

Отображение S _n → A ⊂ GL ( n , Z ₂ ) является точным представлением . Таким образом, | А | = п ! .

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

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

Линейные алгебраические свойства [ править ]

След матрицы перестановок является числом неподвижных точек перестановки. Если перестановка имеет неподвижные точки, поэтому ее можно записать в форме цикла как π = ( a ₁ ) ( a ₂ ) ... ( a _k ) σ, где σ не имеет неподвижных точек, тогда e _{a 1} , e _{a 2} , ..., e _{a k} - собственные векторы матрицы перестановок.

Для вычисления собственных значений матрицы перестановок , записи в виде произведения циклов , скажем, . Пусть соответствующие длины этих циклов равны , и пусть - множество комплексных решений . Объединение всех s - это набор собственных значений соответствующей матрицы перестановок. Геометрическая кратность каждого собственного значения равно числу х , которые содержат его. ^[4]${\displaystyle P_{\sigma }}$${\displaystyle \sigma }$${\displaystyle \sigma =C_{1}C_{2}\cdots C_{t}}$${\displaystyle l_{1},l_{2}...l_{t}}$${\displaystyle R_{i}(1\leq i\leq t)}$${\displaystyle x^{l_{i}}=1}$${\displaystyle R_{i}}$${\displaystyle R_{i}}$

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

Примеры [ править ]

Перестановка строк и столбцов [ править ]

Когда матрица перестановок P умножается слева на матрицу M, чтобы получить PM, она переставляет строки M (здесь элементы вектора-столбца),
когда P умножается справа на M, чтобы получить MP, он переставляет столбцы M (здесь элементы вектора-строки):

Перестановки строк и столбцов представляют собой, например, отражения (см. Ниже) и циклические перестановки (см. Матрицу циклических перестановок ).

Перестановка строк [ править ]

Матрица перестановок P _π , соответствующая перестановка: есть${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},}$

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.}$

Учитывая вектор g ,

${\displaystyle P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.}$

Объяснение [ править ]

Матрица перестановок всегда будет иметь вид

${\displaystyle {\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{j}}\\\end{bmatrix}}}$

где e _{a i} представляет i- й базисный вектор (в виде строки) для R ^j , и где

${\displaystyle {\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}}$

является перестановка формы матрицы перестановок.

Теперь, выполняя умножение матриц , по существу формируют скалярное произведение каждой строки первой матрицы с каждым столбцом второй. В этом случае мы будем формировать скалярное произведение каждой строки этой матрицы с вектором элементов, которые мы хотим переставить. То есть, например, v  = ( g ₀ , ..., g ₅ ) ^T ,

е _{а я} · v  =  г _{а я}

Таким образом, произведение матрицы перестановок на вектор v выше будет вектором в форме ( g _{a 1} , g _{a 2} , ..., g _{a j} ), и что тогда это перестановка v, поскольку мы сказали, что форма перестановки

${\displaystyle {\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.}$

Таким образом, матрицы перестановки действительно меняют порядок элементов в векторах, умноженных на них.

Запрещенные формы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

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