Permanent Determinant

/ mathcination

permanent_graphThe determinant and the permanent of a matrix are central characters in an endeavour to bring the powerful weapons of modern geometry to a battle in the epic war of computer science: the P vs. NP problem.

JM Landsberg has recently written a wonderful introduction to geometric complexity theory which is how the corresponding research field is called. This has inspired me to borrow some of it and write about the permanent and the determinant of a matrix.

In linear algebra, the determinant is a value associated to each square matrix. It has many particularly nice properties and interpretations. For example, it can help to decide whether a system of linear equations represented by the matrix has a unique solution and it computes the volume of the parallelepiped spanned by its rows. For an n\times n matrix A with entries a_{ij} it can be defined by the following formula:

\mathrm{det}(A) = \sum_{\sigma \in S_n} \mathrm{sign}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}.

The sum is taken over all permutations \sigma of the set \{1, 2, \ldots n\}. S_n denotes the symmetric group which comprises all these permutations and the sign of a permutation is +1 or -1 depending on whether the permutation has an even or odd number of transpositions.

At a first glance, the permanent looks like a simplification of the determinant because it is given by essentially the same formula without the sign function:

\mathrm{perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i,\sigma(i)}.

The permanent is very useful because it can be employed to find the answer to counting problems like finding the number of perfect matchings in a bipartite graph. However, where the determinant can be computed in polynomial time, e.g. by Gaussian elimination, computing the permanent is #P-hard.

Now, in the case of two by two matrices, the determinant can be used to compute the permanent:

\mathrm{perm}\left ( \begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} \right ) = a_{11}a_{22} + a_{12}a_{21} = \mathrm{det}\left ( \begin{matrix} a_{11} & -a_{12} \\ a_{21} & a_{22} \end{matrix} \right )

For larger matrices, however, computing the permanent by a determinant of the same size whose entries are given by linear forms of the entries of the original matrix is not possible. Then how about using the determinant of a matrix of a larger size? We would like to find a way to do this using determinants which are not too much larger. But the hardness result on computing the permanent means that using determinants with a size polynomial in the size of the matrix is winning the battle. A much more humble question is to find a representation using exponential size.

Bruno Grenet shows how to do this with an (2^n-1)\times (2^n-1) determinant in his paper An Upper Bound for the Permanent Versus Determinant Problem. The solution is sufficiently simply and I will therefore conclude by explaining how to do it using the example of three by three matrices. Another question is why this is correct and you can get the answer by going through the four pages of the paper.

Let’s start with a three by three matrix:

\mathrm{perm}\left ( \begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\a_{31}&a_{32}&a_{33}\end{matrix} \right ) = a_{11}a_{22}a_{33} + a_{11}a_{23}a_{32} + a_{12}a_{21}a_{33}+a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32}+a_{13}a_{22}a_{31}

In order to find a determinant representation for this permanent, we construct a graph from the subsets of the set \{1, 2, 3\} (we would use the set \{1, 2, \ldots, n\} for the general case).

change this

The graph of subsets of the set \{1, 2, 3\} together with auxiliary loops. The numbers in red give an ordering of the vertices.

This graph is constructed in a way such that the vertices (the subsets) are grouped by size such that all sets of the same cardinality form one layer of the graph. I will refer to the layer containing sets of cardinality i as the i-th layer. Now, edges are introduced between two vertices when inserting a single number into one of the respective sets yields the other. These edges are oriented from the smaller to the larger set and are labelled by a_{ij} if it ends in the i-th layer and the larger set is obtained by inserting the number j into the smaller set. For example, there is an edge labelled a_{23} from the node \{1\} to the node \{1, 3\} because the latter set is in layer 2 and was obtained by inserting 3. For each vertex representing a subset which is neither empty nor the whole set, we add an edge from this vertex to itself labelled by the number one. Finally, we identify the vertices representing the empty set and the whole set into one joint vertex (vertices 1 and 8 in the figure).

We can now order the vertices (for example as indicated by the red numbers in the figure) and represent the graph by its adjacency matrix:

\left ( \begin{matrix}0&a_{11}&a_{12}&a_{13}&0&0&0\\0&1&0&0&a_{22}&a_{23}&0\\0&0&1&0&a_{21}&0&a_{23}\\0&0&0&1&0&a_{21}&a_{22}\\a_{33}&0&0&0&1&0&0\\a_{32}&0&0&0&0&1&0\\a_{31}&0&0&0&0&0&1\end{matrix}\right )

This matrix has entry zero at position i, j if there is no edge between the i-th and the j-th vertex in our ordering. If there is an edge then its label is given at position i, j.

Now we can compute the determinant of this matrix and find that it is exactly the permanent of our matrix. You can use WolframAlpha to show that its determinant is indeed equal to the permanent. Why this is true is somewhat harder to see. It has to do with counting the number of cycle covers of the above graph. I invite you to have a look at the paper for more information.

Leave a comment