Перманент

Эта статья о математическом понятии; о завивке волос см. Химическая завивка.

Пермане́нт в математике — числовая функция, определённая на множестве всех матриц; для квадратных матриц похожа на детерминант, и отличается от него лишь в том, что в разложении на перестановки (или на миноры) берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, определение перманента расширено и на неквадратные матрицы.

В литературе для обозначения перманента обычно используется одна из следующих нотаций: $\mathrm{P}\mathrm{e}\mathrm{r}(A)$$\mathrm {Per} (A)$, $\mathrm{p}\mathrm{e}\mathrm{r}A$$\mathrm {per} A$ или $\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{m}A$$\mathrm {perm} A$.

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

Перманент квадратной матрицыПравить

Пусть $A$$A$  — квадратная матрица размера $n\times <!--\; \times \; -->n$$n\times n$ , элементы $a_{i,j}$$a_{i,j}$  которой принадлежат некоторому полю $K$$K$ . Перманентом матрицы $A$$A$  называется число:

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{a}_{i,{\mathrm{\pi <!--\; \pi \; -->}}_i}=\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}{a}_{1,{\mathrm{\pi <!--\; \pi \; -->}}_1}{a}_{2,{\mathrm{\pi <!--\; \pi \; -->}}_2}\cdots <!--\; \cdots \; -->a_{n,{\mathrm{\pi <!--\; \pi \; -->}}_n}$$\mathrm {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}}$ ,

где сумма берётся по всем перестановкам $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  чисел от 1 до $n$$n$ .

Например, для матрицы размера $2\times <!--\; \times \; -->2$$2\times 2$ :

$\mathrm {Per} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc$ .

Это определение отличается от аналогичного определения детерминанта лишь тем, что в детерминанте некоторые члены суммы имеют отрицательный знак, в зависимости от знака перестановки $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ .

Перманент прямоугольной матрицыПравить

Понятие перманента иногда расширяют на случай произвольной прямоугольной матрицы $A$$A$  размера $m\times <!--\; \times \; -->n$$m\times n$  следующим способом. Если $m<n$ , то:

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\underset{\mathrm{\pi <!--\; \pi \; -->}}{\sum <!--\; \sum \; -->}\underset{i=1}{\overset{m}{\prod <!--\; \prod \; -->}}{a}_{i,{\mathrm{\pi <!--\; \pi \; -->}}_i}$$\mathrm {Per} (A)=\sum _{\pi }\prod _{i=1}^{m}a_{i,\pi _{i}}$ ,

где сумма берётся по всем $m$$m$ -элементным размещениям из множества чисел от 1 до $n$$n$ .

Если же $m>n$$m>n$ , то:

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\mathrm{P}\mathrm{e}\mathrm{r}(A^T)$$\mathrm {Per} (A)=\mathrm {Per} (A^{T})$ .

Или, что эквивалентно, перманент прямоугольной матрицы можно определить как сумму перманентов всех её квадратных подматриц порядка $min\{n,m\}$$\min\{\,n,m\,\}$ .

СвойстваПравить

Перманент любой диагональной или треугольной матрицы равен произведению элементов на её диагонали. В частности, перманент нулевой матрицы равен нулю, а перманент единичной матрицы — единице.

Перманент не изменяется при транспонировании: $\mathrm{P}\mathrm{e}\mathrm{r}(A^T)=\mathrm{P}\mathrm{e}\mathrm{r}(A)$$\mathrm {Per} (A^{T})=\mathrm {Per} (A)$ . В отличие от детерминанта, перманент матрицы не изменяется от перестановки строк или столбцов матрицы.

Перманент является линейной функцией от строк (или столбцов) матрицы, то есть:

• если умножить любую одну строку (столбец) на некоторое число $c$$c$ , то и значение перманента увеличится в $c$$c$  раз;
• перманент суммы двух матриц, отличающихся лишь одной строкой (столбцом), равен сумме их перманентов.

Аналог разложения Лапласа по первой строке матрицы для перманента:

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_{1,j}{B}_{1,j}$$\mathrm {Per} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j}$ ,

где $B_{i,j}$$B_{i,j}$  — перманент матрицы, получающейся из $A$$A$  удалением $i$$i$ -й строки и $j$$j$ -го столбца. Так, например, для матрицы размера $3\times <!--\; \times \; -->3$$3 \times 3$ , имеет место:

$\mathrm {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}\mathrm {Per} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}}+a_{12}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}$ .

Перманент матрицы порядка $n$$n$  — однородная функция порядка $n$$n$ :

$\mathrm{P}\mathrm{e}\mathrm{r}(c\cdot <!--\; \cdot \; -->A)=c^n\cdot <!--\; \cdot \; -->\mathrm{P}\mathrm{e}\mathrm{r}(A)$$\mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)$ , где $c\in <!--\; \in \; -->K$$c\in K$  — скаляр.

Если $P$$P$  — перестановочная матрица, то:

$\mathrm{P}\mathrm{e}\mathrm{r}(P)=1$$\mathrm {Per} (P)=1$ ;

$\mathrm{P}\mathrm{e}\mathrm{r}(AP)=\mathrm{P}\mathrm{e}\mathrm{r}(PA)=\mathrm{P}\mathrm{e}\mathrm{r}(A)$$\mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)$  для любой матрицы $A$$A$  того же порядка.

Если матрица $A$$A$  состоит из неотрицательных действительных чисел, то $\mathrm{P}\mathrm{e}\mathrm{r}(A)⩾<!--\; ⩾\; -->detA$$\mathrm {Per} (A)\geqslant \det A$ .

Если $A$$A$  и $B$$B$  — две верхние (или нижние) треугольные матрицы, то:

$\mathrm{P}\mathrm{e}\mathrm{r}(AB)=\mathrm{P}\mathrm{e}\mathrm{r}(BA)=\mathrm{P}\mathrm{e}\mathrm{r}(A)\cdot <!--\; \cdot \; -->\mathrm{P}\mathrm{e}\mathrm{r}(B)$$\mathrm {Per} (AB)=\mathrm {Per} (BA)=\mathrm {Per} (A)\cdot \mathrm {Per} (B)$ ,

(в общем случае равенство не выполняется для произвольных $A$$A$  и $B$$B$ , в отличие от аналогичного свойства детерминантов).

Перманент дважды стохастической матрицы порядка $n$$n$  не менее, чем $n!/n^n$$n!/n^{n}$  (гипотеза ван дер Вардена, доказанная в 1980 году).

Вычисление перманентаПравить

В отличие от детерминанта, который может быть легко вычислен, например методом Гаусса, вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к классу сложности #P-полных задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц.

В настоящее время^{[уточнить]} неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением, чем знаменитое P=NP.

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

Формула РайзераПравить

Вычисление перманента по определению обладает сложностью $O(n!)$$O(n!)$  (или даже $O(n\cdot <!--\; \cdot \; -->n!)$$O(n\cdot n!)$  при «грубой» реализации). Оценку можно значительно улучшить, воспользовавшись формулой Райзера:

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=(-<!--\; -\; -->1{)}^n\underset{S\subseteq <!--\; \subseteq \; -->\{1,\dots <!--\; \dots \; -->,n\}}{\sum <!--\; \sum \; -->}(-<!--\; -\; -->1{)}^{|S|}\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}\underset{j\in <!--\; \in \; -->S}{\sum <!--\; \sum \; -->}{a}_{ij}$$\mathrm {Per} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}$ ,

с ней перманент может быть вычислен за время $O(2^n{n}^2)$$O(2^{n}n^{2})$  или даже $O(2^{n}n)$$O(2^{n}n)$ , если перечислять подмножества по коду Грея.

ПриложенияПравить

Перманент практически не используется в линейной алгебре, но находит применение в дискретной математике и комбинаторике.

Перманент матрицы $A$$A$ , состоящей из нулей и единиц, можно интерпретировать, как число полных паросочетаний в двудольном графе с матрицей смежности $A$$A$  (то есть ребро между $i$$i$ -й вершиной одной доли и $j$$j$ -й вершиной другой доли существует, если $a_{ij}=1$$a_{{ij}}=1$ ).

Перманент произвольной матрицы можно рассматривать как сумму весов всех полных паросочетаний в полном двудольном графе, где под весом паросочетания понимается произведение весов его рёбер, а веса рёбер записаны в элементах матрицы смежности $A$$A$ .

ЛитератураПравить

• Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.

СсылкиПравить

• Weisstein, Eric W. Permanent (англ.) на сайте Wolfram MathWorld.
• Permanent (англ.) на сайте PlanetMath.