Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I would like to know what is your intuition behind permanent of a matrix.
For me, it looks like someone came and saw determinant, deleted permutation sign and voila, we have permanent and it counts the number of perfect matchings. But I am sure that is not how it was. :)
Representation-theoretic explanations as to why the permanent is an intuitive and natural matrix function may be found in the article Group Characters and Algebra.
For me, the permanent is a very intuitive and natural matrix function because the permanent of a matrix often encodes enumerative properties concerning permutations in a natural and elegant way. This is not just true for permanents of binary matrices: there are many elegant and intuitive combinatorial properties associated with permanents of non-binary matrices.
For example, I have previously noted a connection between the series coefficients for $\frac{\cos x}{1+x}$ and $\frac{\sin x}{1-x}$ and permanents of matrices with $(1+i)$s along the main diagonal and ones everywhere else, where $i = \sqrt{-1}$ denotes the imaginary unit, as indicated in the OEIS sequence A009551 and in the OEIS sequence A009102. This connection between permanents of matrices of this form and the series expansions for $\frac{\cos x}{1+x}$ and $\frac{\sin x}{1-x}$ may be explained in a natural way using rencontres numbers. The rencontre number $T(n, k)$ is the number of permutations of $n$ elements with $k$ fixed points.
In general, we have that the permanent of the $n \times n$ matrix with $x$'s on the diagonal and $1$s everywhere else equals $$ \sum_{k=0}^{n} T(n, k) x^{k}, $$ and there are natural and intuitive combinatorial interpretations of this summation.
The permanent of a binary matrix also nicely illustrates why the permanent is a natural and intuitive matrix function. For example, consider the following combinatorial problem due to Dan Dima described in the OEIS sequence A000316:
"$n$ couples meet for a party and they exchange gifts. Each of the $2n$ writes their name on a piece of paper and puts it into a hat. They take turns drawing names and give their gift to the person whose name they drew. If anyone draws either their own name or the name of their partner, everyone puts the name they have drawn back into the hat and everyone draws anew." What is the number A000316$(n)$ of different permissible drawings?
I have previously noted that A000316$(n)$ equals the permanent of the $(2n) \times (2n)$ matrix $1_{n} - I_{n} - J_{n}$ with zeroes along the main diagonal and the antidiagonal, and ones everywhere else. For example, in the case whereby $n = 4$, the total number of different permissible drawings is equal to:
\begin{equation*} \text{perm} \left(\begin{matrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \end{matrix}\right) = 4752 \end{equation*}
Letting $\{a, a' \}$, $\{b, b'\}$, etc. denote the $n=4$ couples at this party, and letting the $2n = 8$ people at this party be ordered as indicated in the tuple $$( a, b, c, d, d', c', b', a' ),$$ let permissible drawings be denoted using "two-line notation" for permutations as illustrated in the below example:
\begin{equation*} \left(\begin{matrix} a & b & c & d & d' & c' & b' & a' \\ c & a' & b' & a & b & d & d' & c' \end{matrix}\right). \end{equation*}
So it is clear that the permanent of $1_{4} - I_{4} - J_{4}$ encodes or "encrypts" the number A000316$(n)$ of different permissible drawings (which is equal to the number of permutations $\sigma \in S_{2n}$ such that $\sigma_{1} \neq 8$, $\sigma_{2} \neq 7$, etc.) in a natural way.
