Determinant vs Permanent

The determinant and the permanent are famous polynomials in the world of maths (some say the determinant is the most famous in the world). We are unable to compare the complexity of the determinant with the permanent, and this is an important hurdle in complexity theory. A google search for “determinant vs. permanent” returns 432,000 results, which amounts to a very big hurdle. It is closely related to the P vs. NP problem.

Given a 2 \times 2 matrix M = \left( \begin{matrix} a & b \\ c & d \end{matrix} \right), the determinant is ad - bc. The less familiar permanent is ad + bc. Both are polynomials in the entries, a, b, c and d, of the matrix.

In general, the permanent is what we get when we put a “+” sign everywhere we see a “-” in the expression for the determinant.

Despite this apparent similarity, the two polynomials behave very differently.

Gaussian Elimination is an algorithm that allows us to calculate the determinant quickly. In the UK, you learn at school aged 17. The algorithm might seem laborious: a 3 \times 3 matrix requires about 30 operations. But, at O(n^3) operations for a matrix of size n, it is a very fast algorithm for matrices.

In contrast, there is no known polynomial-time algorithm for calculating the permanent; there is no known O(n^r) algorithm for any r. An active line of research is to try to write the permanent of a smaller matrix as the determinant of a much larger matrix. Here is an example in the case of a 3 \times 3 matrix:

Permanental Adjacency Matrix
Expressing the permanent as the determinant of a larger matrix, using adjacency matrices of graphs.

This picture is taken from Jan Draisma’s article on “Geometry, Invariants and the Search for Elusive Complexity Bounds” from the March 2nd SIAM news. It depicts a method by Bruno Grenet to find the permanent of a smaller matrix as the determinant of a larger matrix.

The method shows that we can find the permanent of a matrix of size n by finding the determinant of a matrix of size 2^n -1. It works as follows:

  1. We make the partially ordered set (poset) formed from all possible subsets of the numbers \{ 1, 2, \cdots, n \}. Its graph it the diagram shown on the left hand side of the above picture.
  2. We make paths in our poset by starting with the empty set, and adding in elements one at a time until we have all the numbers \{ 1, 2, \cdots, n \}.
  3. Next we make the matrix, on the right hand side of the picture. First, we label the rows and columns of the matrix by the 2^n - 1 non-empty subsets of \{ 1, 2, \cdots, n \}.
  4. The entries of the matrix are given by the weighting of the edge of the graph that goes from the column’s index to the row’s index in the poset picture.
  5. Each term in the determinant of the matrix corresponds to a path in the graph.

Here is Bruno Grenet’s paper from 2012.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s