5
$\begingroup$

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. :)

$\endgroup$
4
  • 2
    $\begingroup$ Your intuition is sensible. What difference would someone else's "intuition" make? What would make one intuition better than another? If you were asking about applications of permanents, then there would be a more objective meaning to the Question. $\endgroup$
    – hardmath
    Apr 10, 2016 at 2:51
  • 1
    $\begingroup$ I think the main point of the permanent is that it looks naively similar to the determinant (exactly in the sense of your decription), but is much more difficult to compute. So it is not really expected to have an intutive "meaning". $\endgroup$ Apr 10, 2016 at 10:33
  • 2
    $\begingroup$ @Hardmath I think that someone else's intuition can make a big difference in terms of understanding a concept deeply, if their intuitive explanation helps to motivate a concept and explain why it is simple and easy, even though it might look daunting and strange at first sight. One of the difficulties of learning math, in my experience, is that textbooks sometimes don't bother to explain the intuition. For example, I didn't feel I had grokked the dual problem in convex optimization until I learned the perturbation viewpoint, which is frequently omitted. $\endgroup$
    – littleO
    Apr 11, 2016 at 1:24
  • $\begingroup$ Well, @littleO, you have exactly summed up my expiriences. And that is why I ask such question. $\endgroup$
    – user320254
    Apr 12, 2016 at 9:04

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.