Перманент
В математике, пермане́нт — числовая функция, определённая для матриц, для квадратных матриц похожая на детерминант, и отличающаяся от него лишь в том, что в разложении на перестановки (или на миноры) берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, перманент может быть определён и для не квадратных матриц.
В литературе для обозначения перманента обычно используется одна из следующих нотаций: <math>\mbox{Per}(A)</math>, <math>\mbox{per } A</math> или <math>\mbox{perm } A</math>.
Содержание
Определение
Пусть <math>A</math> — квадратная матрица размера <math>n \times n</math>, элементы <math>a_{i, j}</math> которой принадлежат некоторому полю <math>K</math>. Перманентом матрицы <math>A</math> называется число:
- <math>\mbox{Per}(A) = \sum_{\pi \in S_n} \prod_{i=1}^n a_{i, \pi_i} = \sum_{\pi \in S_n} a_{1, \pi_1} a_{2, \pi_2} \cdots a_{n, \pi_n},</math>
где сумма берётся по всем перестановкам <math>\pi</math> чисел от 1 до <math>n</math>.
Например, для матрицы размера <math>2 \times 2</math>:
- <math>\mbox{Per} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad + bc.</math>
Это определение отличается от аналогичного определения детерминанта лишь тем, что в детерминанте некоторые члены суммы имеют отрицательный знак, в зависимости от знака перестановки <math>\pi</math>.
Перманент прямоугольной матрицы
Понятие перманента иногда расширяют на случай произвольной прямоугольной матрицы <math>A</math> размера <math>m \times n</math> следующим способом. Если <math>m < n</math>, то:
- <math>\mbox{Per}(A) = \sum_{\pi} \prod_{i=1}^m a_{i, \pi_i},</math>
где сумма берётся по всем <math>m</math>-элементным размещениям из множества чисел от 1 до <math>n</math>.
Если же <math>m > n</math>, то:
- <math>\mbox{Per}(A) = \mbox{Per}(A^T)</math>.
Или, что эквивалентно, перманент прямоугольной матрицы можно определить как сумму перманентов всех её квадратных подматриц порядка <math>\min(n, m)</math>;
Свойства
- Перманент любой диагональной или треугольной матрицы равен произведению элементов на её диагонали. В частности, перманент нулевой матрицы равен нулю, а перманент единичной матрицы — единице.
- Перманент не изменяется при транспонировании:
- <math>\mbox{Per}(A^T) = \mbox{Per}(A)</math>
- Перманент матрицы не изменяется от перестановки строк или столбцов матрицы (в отличие от детерминанта).
- Перманент является линейной функцией от строк (или столбцов) матрицы, то есть:
- Если умножить любую одну строку (столбец) на некоторое число <math>c</math>, то и значение перманента увеличится в <math>c</math> раз;
- Перманент суммы двух матриц, отличающихся лишь одной строкой (столбцом) равен сумме их перманентов.
- Аналог разложения Лапласа по первой строке матрицы для перманента:
- <math>\mbox{Per}(A) = \sum_{j=1}^{n} a_{1,j} B_{1,j}</math>, где <math>B_{i,j}</math> — перманент матрицы, получающейся из <math>A</math> удалением <math>i</math>-й строки и <math>j</math>-го столбца.
- Так, например, для матрицы размера <math>3 \times 3</math>, имеем:
- <math>
\mbox{Per} \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} =
a_{11} \mbox{Per} \begin{pmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{pmatrix}
+ a_{12} \mbox{Per} \begin{pmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{pmatrix}
+ a_{13} \mbox{Per} \begin{pmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{pmatrix}.</math>
- Перманент матрицы порядка <math>n</math> — однородная функция порядка <math>n</math>:
- <math>\mbox{Per}(c \cdot A) = c^n \cdot \mbox{Per}(A)</math>, где <math>c \in K</math> — скаляр.
- Если <math>P</math> — перестановочная матрица, то:
- <math>\mbox{Per}(P) = 1;</math>
- <math>\mbox{Per}(AP) = \mbox{Per}(PA) = \mbox{Per}(A)</math> для любой матрицы <math>A</math> того же порядка.
- Если матрица <math>A</math> состоит из неотрицательных действительных чисел, то <math>\mbox{Per}(A) \geq \det A</math>.
- Если <math>A</math> и <math>B</math> — две верхние (или нижние) треугольные матрицы, то:
- <math>\mbox{Per}(AB) = \mbox{Per}(BA) = \mbox{Per}(A) \cdot \mbox{Per}(B).</math>
- Однако необходимо заметить, что, в общем случае, предыдущее равенство не выполняется для произвольных <math>A</math> и <math>B</math>, в отличие от аналогичного свойства детерминантов.
Вычисление перманента
В отличие от детерминанта, который может быть легко вычислен, например методом Гаусса, вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к классу сложности #P-полных задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц.[1]
В настоящее время неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением чем знаменитое P=NP.
В декабре 2012 четыре независимые группы исследователей предложили прототип квантового фотонного устройства, вычисляющее перманент матрицы.[2]
Формула Райзера
Вычисление перманента по определению занимает <math>O(n!)</math> времени. Его можно значительно улучшить, воспользовавшись формулой Райзера:[3][4]
- <math>\mbox{Per}(A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.</math>
Формула Райзера может быть вычислена за время <math>O(2^nn^2)</math> или даже <math>O(2^nn)</math>, если перечислять подмножества по коду Грея.
Приложения
Перманент практически не используется в линейной алгебре, но находит применение в дискретной математике и комбинаторике.
Перманент матрицы <math>A</math>, состоящей из нулей и единиц, можно интерпретировать, как число полных паросочетаний в двудольном графе с матрицей смежности <math>A</math> (то есть ребро между <math>i</math>-й вершиной одной доли и <math>j</math>-й вершиной другой доли существует, если <math>a_{ij} = 1</math>).
Перманент произвольной матрицы можно рассматривать как сумму весов всех полных паросочетаний в полном двудольном графе, где под весом паросочетания понимается произведение весов его рёбер, а веса рёбер записаны в элементах матрицы смежности <math>A</math>.
Напишите отзыв о статье "Перманент"
Примечания
- ↑ Leslie G. Valiant (1979). «The Complexity of Computing the Permanent». Theoretical Computer Science (Elsevier) 8: 189–201. DOI:10.1016/0304-3975(79)90044-6.
- ↑ [lenta.ru/news/2012/12/24/photoncomp/ Физики разработали фотонный квантовый компьютер] (рус.). Лента.ру (24 декабря 2012). Проверено 25 декабря 2012. [www.webcitation.org/6DDwOB6Gw Архивировано из первоисточника 27 декабря 2012].
- ↑ Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/RyserFormula.html Ryser Formula] (англ.) на сайте Wolfram MathWorld.
Литература
- Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.
Ссылки
- Weisstein, Eric W. [mathworld.wolfram.com/Permanent.html Permanent] (англ.) на сайте Wolfram MathWorld.
- [planetmath.org/encyclopedia/Permanent.html Permanent] (англ.) на сайте PlanetMath.
Отрывок, характеризующий Перманент
Moscou, le 3 Octobre, 1812. Signe:Napoleon».
[Князь Кутузов, посылаю к вам одного из моих генерал адъютантов для переговоров с вами о многих важных предметах. Прошу Вашу Светлость верить всему, что он вам скажет, особенно когда, станет выражать вам чувствования уважения и особенного почтения, питаемые мною к вам с давнего времени. Засим молю бога о сохранении вас под своим священным кровом.
Москва, 3 октября, 1812.
Наполеон. ]
«Je serais maudit par la posterite si l'on me regardait comme le premier moteur d'un accommodement quelconque. Tel est l'esprit actuel de ma nation», [Я бы был проклят, если бы на меня смотрели как на первого зачинщика какой бы то ни было сделки; такова воля нашего народа. ] – отвечал Кутузов и продолжал употреблять все свои силы на то, чтобы удерживать войска от наступления.
В месяц грабежа французского войска в Москве и спокойной стоянки русского войска под Тарутиным совершилось изменение в отношении силы обоих войск (духа и численности), вследствие которого преимущество силы оказалось на стороне русских. Несмотря на то, что положение французского войска и его численность были неизвестны русским, как скоро изменилось отношение, необходимость наступления тотчас же выразилась в бесчисленном количестве признаков. Признаками этими были: и присылка Лористона, и изобилие провианта в Тарутине, и сведения, приходившие со всех сторон о бездействии и беспорядке французов, и комплектование наших полков рекрутами, и хорошая погода, и продолжительный отдых русских солдат, и обыкновенно возникающее в войсках вследствие отдыха нетерпение исполнять то дело, для которого все собраны, и любопытство о том, что делалось во французской армии, так давно потерянной из виду, и смелость, с которою теперь шныряли русские аванпосты около стоявших в Тарутине французов, и известия о легких победах над французами мужиков и партизанов, и зависть, возбуждаемая этим, и чувство мести, лежавшее в душе каждого человека до тех пор, пока французы были в Москве, и (главное) неясное, но возникшее в душе каждого солдата сознание того, что отношение силы изменилось теперь и преимущество находится на нашей стороне. Существенное отношение сил изменилось, и наступление стало необходимым. И тотчас же, так же верно, как начинают бить и играть в часах куранты, когда стрелка совершила полный круг, в высших сферах, соответственно существенному изменению сил, отразилось усиленное движение, шипение и игра курантов.
Русская армия управлялась Кутузовым с его штабом и государем из Петербурга. В Петербурге, еще до получения известия об оставлении Москвы, был составлен подробный план всей войны и прислан Кутузову для руководства. Несмотря на то, что план этот был составлен в предположении того, что Москва еще в наших руках, план этот был одобрен штабом и принят к исполнению. Кутузов писал только, что дальние диверсии всегда трудно исполнимы. И для разрешения встречавшихся трудностей присылались новые наставления и лица, долженствовавшие следить за его действиями и доносить о них.
Кроме того, теперь в русской армии преобразовался весь штаб. Замещались места убитого Багратиона и обиженного, удалившегося Барклая. Весьма серьезно обдумывали, что будет лучше: А. поместить на место Б., а Б. на место Д., или, напротив, Д. на место А. и т. д., как будто что нибудь, кроме удовольствия А. и Б., могло зависеть от этого.
В штабе армии, по случаю враждебности Кутузова с своим начальником штаба, Бенигсеном, и присутствия доверенных лиц государя и этих перемещений, шла более, чем обыкновенно, сложная игра партий: А. подкапывался под Б., Д. под С. и т. д., во всех возможных перемещениях и сочетаниях. При всех этих подкапываниях предметом интриг большей частью было то военное дело, которым думали руководить все эти люди; но это военное дело шло независимо от них, именно так, как оно должно было идти, то есть никогда не совпадая с тем, что придумывали люди, а вытекая из сущности отношения масс. Все эти придумыванья, скрещиваясь, перепутываясь, представляли в высших сферах только верное отражение того, что должно было совершиться.
«Князь Михаил Иларионович! – писал государь от 2 го октября в письме, полученном после Тарутинского сражения. – С 2 го сентября Москва в руках неприятельских. Последние ваши рапорты от 20 го; и в течение всего сего времени не только что ничего не предпринято для действия противу неприятеля и освобождения первопрестольной столицы, но даже, по последним рапортам вашим, вы еще отступили назад. Серпухов уже занят отрядом неприятельским, и Тула, с знаменитым и столь для армии необходимым своим заводом, в опасности. По рапортам от генерала Винцингероде вижу я, что неприятельский 10000 й корпус подвигается по Петербургской дороге. Другой, в нескольких тысячах, также подается к Дмитрову. Третий подвинулся вперед по Владимирской дороге. Четвертый, довольно значительный, стоит между Рузою и Можайском. Наполеон же сам по 25 е число находился в Москве. По всем сим сведениям, когда неприятель сильными отрядами раздробил свои силы, когда Наполеон еще в Москве сам, с своею гвардией, возможно ли, чтобы силы неприятельские, находящиеся перед вами, были значительны и не позволяли вам действовать наступательно? С вероятностию, напротив того, должно полагать, что он вас преследует отрядами или, по крайней мере, корпусом, гораздо слабее армии, вам вверенной. Казалось, что, пользуясь сими обстоятельствами, могли бы вы с выгодою атаковать неприятеля слабее вас и истребить оного или, по меньшей мере, заставя его отступить, сохранить в наших руках знатную часть губерний, ныне неприятелем занимаемых, и тем самым отвратить опасность от Тулы и прочих внутренних наших городов. На вашей ответственности останется, если неприятель в состоянии будет отрядить значительный корпус на Петербург для угрожания сей столице, в которой не могло остаться много войска, ибо с вверенною вам армиею, действуя с решительностию и деятельностию, вы имеете все средства отвратить сие новое несчастие. Вспомните, что вы еще обязаны ответом оскорбленному отечеству в потере Москвы. Вы имели опыты моей готовности вас награждать. Сия готовность не ослабнет во мне, но я и Россия вправе ожидать с вашей стороны всего усердия, твердости и успехов, которые ум ваш, воинские таланты ваши и храбрость войск, вами предводительствуемых, нам предвещают».
