Jump to content

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

(Перенаправлено из матриц перестановок )

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

Каждая матрица перестановок P ортогональна равна , ее обратная матрица ее транспонированию : . [1] : 26  Действительно, матрицы перестановок можно охарактеризовать как ортогональные матрицы, все элементы которых неотрицательны . [2]

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

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

Соответствие на основе строк переводит перестановку π в матрицу в правом верхнем углу. Первый ряд имеет 1 в третьем столбце, потому что . В более общем плане мы имеем где когда и в противном случае.

Соответствие на основе столбцов переводит π в матрицу в левом нижнем углу. Первый столбец имеет 1 в третьей строке, потому что . В более общем плане мы имеем где равен 1, когда и 0 в противном случае. Поскольку два рецепта отличаются только заменой i на j , матрица это транспонирование ; и, поскольку является матрицей перестановок, мы имеем . Прослеживая две другие стороны большого квадрата, мы имеем и . [3]

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

Умножив матрицу M либо на или слева или справа переставит строки или столбцы M либо на π, либо на π. −1 . Детали немного сложны.

Начнем с того, что когда мы переставляем элементы вектора некоторой перестановкой π мы перемещаем вход входного вектора в слот выходного вектора. Какая запись тогда окажется, скажем, в первом слоте вывода? Ответ: Запись для чего , и, следовательно, . Рассуждая аналогичным образом о каждом из слотов, мы находим, что выходной вектор равен

хотя мы делаем перестановку , а не по . Таким образом, чтобы переставить записи по , мы должны переставить индексы на . [1] : 25  (Переставляя записи по иногда называют принятием точки зрения алиби при перестановке индексов на принял бы точку зрения псевдонима . [4] )

Теперь предположим, что мы предварительно умножаем некоторую из n строк матрицу по матрице перестановок . По правилу матриц умножения запись в продукте является

где равно 0, за исключением случаев, когда , когда оно равно 1. Таким образом, единственный член суммы, который выживает, - это член, в котором , и сумма уменьшается до . Поскольку мы переставили индекс строки на , мы переставили сами строки M на π . [1] : 25  Аналогичный аргумент показывает, что после умножения из n столбцов матрицы M на переставляет свои столбцы на π .

Два других варианта предварительно умножаются на или после умножения на , и они переставляют строки или столбцы соответственно на π −1 , а не на π .

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

Связанный с этим аргумент доказывает, что, как мы утверждали выше, транспонирование любой матрицы перестановок P также действует как ее инверсия, а это означает, что P обратима. (Артин оставляет это доказательство в качестве упражнения. [1] : 26  которое мы здесь решаем.) Если , тогда запись его транспонирования является . ввод продукта тогда

В любое время , член этой суммы является произведением двух разных записей в столбец P ; поэтому все члены равны 0, а сумма равна 0. Когда , мы суммируем квадраты записей в строка P , поэтому сумма равна 1. Произведение таким образом, является единичной матрицей. Симметричный аргумент показывает то же самое для , подразумевая, что P обратимо с .

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

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

где составная перестановка сначала применяется 𝜏, а затем 𝜎, работая справа налево:
Это следует из того, что предварительное умножение некоторой матрицы на C τ , а затем предварительное умножение полученного произведения на C σ дает тот же результат, что и предварительное умножение всего один раз на объединенную .

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

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

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

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

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

Матричная группа [ править ]

Когда π — тождественная перестановка, которая имеет для всех C i π и R π являются единичной матрицей .

Есть н ! матрицы перестановок, поскольку существует n ! перестановки и карта представляет собой взаимно однозначное соответствие между перестановками и матрицами перестановок. (Карта — еще одно такое соответствие.) По приведенным выше формулам эти матрицы перестановок размера n × n образуют группу порядка n ! при умножении матриц, с единичной матрицей в качестве единичного элемента , группа, которую мы обозначаем . Группа является подгруппой полной линейной группы обратимых n × n матриц действительных чисел размера . Действительно, для любого поля F группа также является подгруппой группы , где элементы матрицы принадлежат F . (Каждое поле содержит 0 и 1 с и и это все, что нам нужно для умножения матриц перестановок. Различные области расходятся во мнениях относительно того, является ли , но эта сумма не возникает.)

Позволять обозначают симметричную группу или группу перестановок на {1,2,..., n }, где групповая операция представляет собой стандартную композицию справа налево" "; и пусть обозначаем противоположную группу , которая использует композицию слева направо» ". Карта который переводит π в матрицу на основе столбцов является точным представлением , и аналогично для карты что переводит π в .

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

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

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

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

Поэтому мы здесь обозначаем инверсию C как и обратный R как . Затем мы можем вычислить линейно-алгебраические свойства P на основе некоторых комбинаторных свойств, которые являются общими для двух перестановок. и .

Точка фиксируется только тогда, когда это исправлено а след P , — это количество таких общих неподвижных точек. [1] : 322  целое число k является одним из них, то стандартный базисный вектор ek Если является собственным вектором P . [1] : 118 

Чтобы вычислить комплексные , напишите собственные значения P перестановку как композиция непересекающихся циклов , скажем . (Перестановки непересекающихся подмножеств коммутируют, поэтому здесь не имеет значения, составляем ли мы справа налево или слева направо.) Ибо , пусть длина цикла быть , и пусть — множество комплексных решений , эти решения являются корни единства . Мультимножественное объединение тогда является мультимножеством собственных значений P . С момента написания поскольку произведение циклов даст одинаковое количество циклов одинаковой длины, анализируя дало бы тот же результат. Кратность — это любого собственного значения v число i , для которого содержит В. [6] (Поскольку любая матрица перестановок нормальна , а любая нормальная матрица диагонализуема по комплексным числам, [1] : 259  алгебраическая и геометрическая кратности собственного значения v одинаковы.)

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

Ограниченные формы [ править ]

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

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

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

  1. Перейти обратно: Перейти обратно: а б с д и ж г час я Артин, Майкл (1991). Алгебра . Прентис Холл. стр. 24–26, 118, 259, 322.
  2. ^ Завланос, Майкл М.; Паппас, Джордж Дж. (ноябрь 2008 г.). «Динамический системный подход к сопоставлению взвешенных графов» . Автоматика . 44 (11): 2817–2824. CiteSeerX   10.1.1.128.6870 . дои : 10.1016/j.automatica.2008.04.009 . S2CID   834305 . Проверено 21 августа 2022 г. Позволять обозначим множество ортогональные матрицы и обозначим множество поэлементные неотрицательные матрицы. Затем, , где это набор матрицы перестановок.
  3. ^ Эта терминология не является стандартной. Большинство авторов используют только одно из двух соответствий, выбирая то, которое соответствует другим их соглашениям. Например, Артин использует соответствие на основе столбцов. Мы придумали здесь два названия, чтобы обсудить оба варианта.
  4. ^ Конвей, Джон Х.; Бургель, Хайди; Гудман-Штраус, Хаим (2008). Симметрии вещей . АК Петерс. п. 179. Перестановку, скажем, имен нескольких людей, можно рассматривать как перемещение либо имен, либо людей. Точка зрения псевдонима рассматривает перестановку как присвоение нового имени или псевдонима каждому человеку (от латинского alias = иначе). Альтернативно, с точки зрения алиби, мы перемещаем людей в места, соответствующие их новым именам (от латинского алиби = в другое место).
  5. ^ Бруальди (2006) стр.19
  6. ^ Дж. Наджнудель, А. Никехбали, 2010, стр.4.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0cc7d2aaec1f7a65a1880b94ea5a4fea__1715881440
URL1:https://arc.ask3.ru/arc/aa/0c/ea/0cc7d2aaec1f7a65a1880b94ea5a4fea.html
Заголовок, (Title) документа по адресу, URL1:
Permutation matrix - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)