permanentPermanent2003-12-05 16:14:052006-12-15 13:40:59Definition\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% portions from
% makra.sty 1989-2005 by Marijke van Gans %
% ^ ^
\catcode`\@=11 % o o
% ->*<-
% ~
%%%% CHARS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% code char frees for
%let\Para\S % \Para ç \S \scriptstyle
%let\Pilcrow\P % \Pilcrow ö \P
%mathchardef\pilcrow="227B
\mathchardef\lt="313C % \lt < < bra
\mathchardef\gt="313E % \gt > > ket
%let\bs\backslash % \bs \
%let\us\_ % \us _ \_ ...
%%%% DIACRITICS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%let\udot\d % under-dot (text mode), frees \d
%let\odot\. % over-dot (text mode), frees \.
%let\hacek\v % hacek (text mode), frees \v
%let\makron\= % makron (text mode), frees \=
%let\tilda\~ % tilde (text mode), frees \~
%let\uml\" % umlaut (text mode), frees \"
%def\ij/{i{\kern-.07em}j}
%def\trema#1{\discretionary{-}{#1}{\uml #1}}
%%%% amssymb %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\le\leqslant
\let\ge\geqslant
%let\prece\preceqslant
%let\succe\succeqslant
%%%% USEFUL MISC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\C++{C$^{_{++}}$}
%let\writelog\wlog
%def\wl@g/{{\sc wlog}}
%def\wlog{\@ifnextchar/{\wl@g}{\writelog}}
%def\org#1{\lower1.2pt\hbox{#1}}
% chem struct formulae: \bs, --- / \org{C} etc.
%%%% USEFUL INTERNAL LaTeX STUFF %%%%%%%%%%%%%%%%%%%%%%%%
%let\Ifnextchar=\@ifnextchar
%let\Ifstar=\@ifstar
%def\currsize{\@currsize}
%%%% KERNING, SPACING, BREAKING %%%%%%%%%%%%%%%%%%%%%%%%%
%def\qqquad{\hskip3em\relax}
%def\qqqquad{\hskip4em\relax}
%def\qqqqquad{\hskip5em\relax}
%def\qqqqqquad{\hskip6em\relax}
%def\qqqqqqquad{\hskip7em\relax}
%def\qqqqqqqquad{\hskip8em\relax}
%%%% LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%let\addtoreset\@addtoreset
%{A}{B} adds A to list of counters reset to 0
% when B is \refstepcounter'ed (see latex.tex)
%
%def\numbernext#1#2{\setcounter{#1}{#2}\addtocounter{#1}{\m@ne}}
%%%% EQUATIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% LEMMATA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% DISPLAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% MATH LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\D\displaystyle
\let\T\textstyle
\let\S\scriptstyle
\let\SS\scriptscriptstyle
% array:
%def\<#1:{\begin{array}{#1}}
%def\>{\end{array}}
% array using [ ] with rounded corners:
%def\[#1:{\left\lgroup\begin{array}{#1}}
%def\]{\end{array}\right\rgroup}
% array using ( ):
%def\(#1:{\left(\begin{array}{#1}}
%def\){\end{array}\right)}
%def\hh{\noalign{\vskip\doublerulesep}}
%%%% MATH SYMBOLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\d{\mathord{\rm d}} % d as in dx
%def\e{{\rm e}} % e as in e^x
%def\Ell{\hbox{\it\char`\$}}
\def\sfmath#1{{\mathchoice%
{{\sf #1}}{{\sf #1}}{{\S\sf #1}}{{\SS\sf #1}}}}
\def\Stalkset#1{\sfmath{I\kern-.12em#1}}
\def\Bset{\Stalkset B}
\def\Nset{\Stalkset N}
\def\Rset{\Stalkset R}
\def\Hset{\Stalkset H}
\def\Fset{\Stalkset F}
\def\kset{\Stalkset k}
\def\In@set{\raise.14ex\hbox{\i}\kern-.237em\raise.43ex\hbox{\i}}
\def\Roundset#1{\sfmath{\kern.14em\In@set\kern-.4em#1}}
\def\Qset{\Roundset Q}
\def\Cset{\Roundset C}
\def\Oset{\Roundset O}
\def\Zset{\sfmath{Z\kern-.44emZ}}
% \frac overwrites LaTeX's one (use TeX \over instead)
%def\fraq#1#2{{}^{#1}\!/\!{}_{\,#2}}
\def\frac#1#2{\mathord{\mathchoice%
{\T{#1\over#2}}
{\T{#1\over#2}}
{\S{#1\over#2}}
{\SS{#1\over#2}}}}
%def\half{\frac12}
\mathcode`\<="4268 % < now is \langle, \lt is <
\mathcode`\>="5269 % > now is \rangle, \gt is >
%def\biggg#1{{\hbox{$\left#1\vbox %to20.5\p@{}\right.\n@space$}}}
%def\Biggg#1{{\hbox{$\left#1\vbox %to23.5\p@{}\right.\n@space$}}}
\let\epsi=\varepsilon
\def\omikron{o}
\def\Alpha{{\rm A}}
\def\Beta{{\rm B}}
\def\Epsilon{{\rm E}}
\def\Zeta{{\rm Z}}
\def\Eta{{\rm H}}
\def\Iota{{\rm I}}
\def\Kappa{{\rm K}}
\def\Mu{{\rm M}}
\def\Nu{{\rm N}}
\def\Omikron{{\rm O}}
\def\Rho{{\rm P}}
\def\Tau{{\rm T}}
\def\Ypsilon{{\rm Y}} % differs from \Upsilon
\def\Chi{{\rm X}}
%def\dg{^{\circ}} % degrees
%def\1{^{-1}} % inverse
\def\*#1{{\bf #1}} % boldface e.g. vector
%def\vi{\mathord{\hbox{\bf\i}}} % boldface vector \i
%def\vj{\mathord{\,\hbox{\bf\j}}} % boldface vector \j
%def\union{\mathbin\cup}
%def\isect{\mathbin\cap}
%let\so\Longrightarrow
%let\oso\Longleftrightarrow
%let\os\Longleftarrow
% := and :<=>
%def\isdef{\mathrel{\smash{\stackrel{\SS\rm def}{=}}}}
%def\iffdef{\mathrel{\smash{stackrel{\SS\rm def}{\oso}}}}
\def\isdef{\mathrel{\mathop{=}\limits^{\smash{\hbox{\tiny def}}}}}
%def\iffdef{\mathrel{\mathop{\oso}\limits^{\smash{\hbox{\tiny %def}}}}}
%def\tr{\mathop{\rm tr}} % tr[ace]
%def\ter#1{\mathop{^#1\rm ter}} % k-ter[minant]
%let\.=\cdot
%let\x=\times % ÃÂÃÂ (direct product)
%def\qed{ ${\S\circ}\!{}^\circ\!{\S\circ}$}
%def\qed{\vrule height 6pt width 6pt depth 0pt}
%def\edots{\mathinner{\mkern1mu
% \raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu % .shorter
% \raise4pt\hbox{.}\mkern1mu % .
% \raise1pt\hbox{.}\mkern1mu}} % .
%def\fdots{\mathinner{\mkern1mu
% \raise7pt\vbox{\kern7pt\hbox{.}} % . ~45ð
% \raise4pt\hbox{.} % .
% \raise1pt\hbox{.}\mkern1mu}} % .
\def\mod#1{\allowbreak \mkern 10mu({\rm mod}\,\,#1)}
% redefines TeX's one using less space
%def\int{\intop\displaylimits}
%def\oint{\ointop\displaylimits}
%def\intoi{\int_0^1}
%def\intall{\int_{-\infty}^\infty}
%def\su#1{\mathop{\sum\raise0.7pt\hbox{$\S\!\!\!\!\!#1\,$}}}
%let\frakR\Re
%let\frakI\Im
%def\Re{\mathop{\rm Re}\nolimits}
%def\Im{\mathop{\rm Im}\nolimits}
%def\conj#1{\overline{#1\vphantom1}}
%def\cj#1{\overline{#1\vphantom+}}
%def\forAll{\mathop\forall\limits}
%def\Exists{\mathop\exists\limits}
%%%% PICTURES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\cent{\makebox(0,0)}
%def\node{\circle*4}
%def\nOde{\circle4}
%%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\opcit{[{\it op.\,cit.}]}
\def\bitem#1{\bibitem[#1]{#1}}
\def\name#1{{\sc #1}}
\def\book#1{{\sl #1\/}}
\def\paper#1{``#1''}
\def\mag#1{{\it #1\/}}
\def\vol#1{{\bf #1}}
\def\isbn#1{{\small\tt ISBN\,\,#1}}
\def\seq#1{{\small\tt #1}}
%def\url<{\verb>}
%def\@cite#1#2{[{#1\if@tempswa\ #2\fi}]}
%%%% VERBATIM CODE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\"{\verb"}
%%%% AD HOC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% WORDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \hyphenation{pre-sent pre-sents pre-sent-ed pre-sent-ing
% re-pre-sent re-pre-sents re-pre-sent-ed re-pre-sent-ing
% re-fer-ence re-fer-ences re-fer-enced re-fer-encing
% ge-o-met-ry re-la-ti-vi-ty Gauss-ian Gauss-ians
% Des-ar-gues-ian}
%def\oord/{o{\trema o}rdin\-ate}
% usage: C\oord/s, c\oord/.
% output: co\"ord... except when linebreak at co-ord...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ^ ^
\catcode`\@=12 % ` '
% ->*<-
% ~\def\per{\mathop{\rm per}\nolimits}
\PMlinkescapeword{column}
\PMlinkescapeword{columns}
\PMlinkescapeword{differences}
\PMlinkescapeword{enumerating}
\PMlinkescapeword{odd}
\PMlinkescapeword{matching}
\PMlinkescapeword{properties}
\PMlinkescapeword{property}
\PMlinkescapeword{relation}
\PMlinkescapeword{row}
\PMlinkescapeword{rows}
\PMlinkescapeword{sum}
\PMlinkescapeword{theory}
\PMlinkescapeword{time}
\PMlinkescapeword{times}
\subsubsection*{Definition of the permanent}
Let $M$ be an $n\times n$ matrix over a field (or even a commutative ring)
$\Fset$, and $M_{ij}$ its entries (with $i$ ranging over a set $I$ and $j$
over a set $J$, each of $n$ elements).
The {\bf permanent} of $M$, denoted by $\per M$, is given by
$$
\per M \;\isdef\;
\sum_{\pi\,\in\,S} \; \prod_{i\,\in\,I} \; M_{i\;\pi(i)}
$$
where $S$ is the set of all $n!$ bijections $\pi : I\to J$. Usually $I$ and $J$ are identified with each other (and with the set of the first $n$ natural numbers, traditionally skipping 0) so that $S$ consists of the elements of the symmetric group $S_n$, the group of permutations of $n$ objects.
In words: we want products of each time $n$ matrix elements chosen
such that there's one from each row $i$ and also one from each column $j$.
There are $n!$ ways to pick those elements (for any permutation of the
column indices relative to the row indices take the elements that end
up in diagonal position). The permanent is the sum of those $n!$ products.
E.g.\ ($n=3$)
$\hbox{\verb" @ O O O @ O O O @ @ O O O @ O O O @"}$\\
$\hbox{\verb" O @ O + O O @ + @ O O + O O @ + @ O O + O @ O"}$\\
$\hbox{\verb" O O @ @ O O O @ O O @ O O O @ @ O O"}$
\clearpage
\subsubsection*{Comparison with the determinant}
It is closely related to one of the ways to define the determinant,
$$
\det M \;\isdef\;
\sum_{\pi\,\in\,S_I} \pm \prod_{i\,\in\,I} \; M_{i\;\pi(i)}
$$
where $S_I$ is the symmetry group of $I$ (isomorphic to $S_n$); the sign is $+$ for even permutations and $-$ for odd ones.
E.g.\ ($n=3$)
$\hbox{\verb" @ O O O @ O O O @ @ O O O @ O O O @"}$\\
$\hbox{\verb" O @ O + O O @ + @ O O - O O @ - @ O O - O @ O"}$\\
$\hbox{\verb" O O @ @ O O O @ O O @ O O O @ @ O O"}$
Note two important differences though.
%
\begin{itemize}
\item While the determinant enjoys the property that $(\det A)(\det B)
= \det(AB)$, the permanent has no such nice arithmetic properties.
\item In the definition of the determinant, we must have $I=J$ i.e.\ we must
have a particular way in mind of matching rows to columns. A matrix
to transform from one basis to another would be an example where this
match is arbitrary. Different conventions which row goes with which
column give two different values (one $-1$ times the other) for the
determinant. By contrast, the permanent is well defined for any $I$
and $J$.
\end{itemize}
%
In the representation theory of groups (where the field $\Fset$ is $\Cset$) determinant and permanent are special cases of the {\bf immanent} (there is an immanent for every character of $S_n$).
\clearpage
\subsubsection*{Some properties of the permanent}
These follow immediately from the definition:
\begin{itemize}
\item The permanent is ``multilinear'' in the rows and columns (i.e.\
linear in every one of them).
\item It is ``homogeneous of degree $n$'', i.e.\ $\per(kA) = k^n\per(A)$,
where $k$ is a scalar (i.e.\ element of $\Fset$).
\item When $P$ and $Q$ are permutation matrices, $\per(PAQ) = \per(PA)
= \per(AQ) = \per(A)$.
\item $\per(A^\top) = \per(A)$.
\item $\D\per\big({A\;\;0\,\atop\,0\;\;D}\big) = \per(A)\per(D)$.
\item If $M$ only has nonnegative entries, then
$$
\per M \ge \det M
$$
Equality is attained
\begin{itemize}
\item (with value 0) when the products (of entries, one from each row
and from each column) that contribute to det and per are all zero.
This happens whenever a whole column or row is zero, but also for
instance in
$$
\left\lgroup
\begin{array}{rrr}
12 & 0 & 0 \\
13 & 0 & 0 \\
14 & 15 & 16
\end{array}
\right\rgroup
$$
\item when the permutations used are all even (which implies only
one is used). This happens in a diagonal matrix, but also
for instance in
$$
\left\lgroup
\begin{array}{cccc}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}
\right\rgroup
$$
\end{itemize}
\end{itemize}
Permanents find application in combinatorics, e.g.\ in enumerating Latin
squares.
See also Van der Waerden's permanent conjecture (now a theorem) for doubly
stochastic matrices (where $\Fset$ is $\Rset$).
Note: some authors define something for non-square matrices they also call ``permanent''.