You are currently browsing the tag archive for the ‘permanent’ tag.

Van Vu and I have just uploaded to the arXiv our preprint “On the permanent of random Bernoulli matrices“, submitted to Adv. Math. This paper establishes analogues of some recent results on the determinant of random $n \times n$ Bernoulli matrices (matrices in which all entries are either +1 or -1, with equal probability of each), in which the determinant is replaced by the permanent.

More precisely, let M be a random $n \times n$ Bernoulli matrix, with n large. Since every row of this matrix has magnitude $n^{1/2}$, it is easy to see (by interpreting the determinant as the signed volume of a parallelopiped) that $|\det(M)|$ is at most $n^{n/2}$, with equality being satisfied exactly when M is a Hadamard matrix. In fact, it is known that the determinant $\det(M)$ has magnitude $n^{(1/2 - o(1)) n}$ with probability $1-o(1)$; for a more precise result, see my earlier paper with Van. (There is in fact believed to be a central limit theorem for $\log |\det(M)|$; see this paper of Girko for details.) These results are based upon the elementary “base times height” formula for the volume of a parallelopiped; the main difficulty is to understand what the distance is from one row of M to a subspace spanned by several other rows of M.

The permanent $\hbox{per}(M)$ looks formally very similar to the determinant, but does not have a geometric interpretation as a signed volume of a parallelopiped and so can only be analysed combinatorially; the main difficulty is to understand the cancellation that can arise from the various signs in the matrix. It can be somewhat larger than the determinant; for instance, the maximum value of $\hbox{per}(M)$ for a Bernoulli matrix M is $n! = n^{(1 - o(1)) n}$, attaned when M consists entirely of +1’s. Nevertheless, it is not hard to see that $\hbox{per}(M)$ has the same mean and standard deviation as $\det(M)$, namely 0 and $\sqrt{n!}$ respectively, which shows that $|\hbox{per}(M)|$ is at most $n^{(1/2-o(1))n}$ with probability 1-o(1). Our main result is to show that one also has that $|\hbox{per}(M)|$ is at least $n^{(1/2-o(1))n}$ with probability 1-o(1), thus obtaining the analogue of the previously mentioned result for the determinant (though our o(1) bounds are significantly weaker).

In particular, this shows that the probability that the permanent vanishes completely is o(1) (in fact, we get a bound of $O(n^{-c})$ for some absolute constant $c > 0$). This result appears to be new (although there is a cute observation of Alon (see e.g. this paper of Wanless for a proof) that if $n=2^m-1$ is one less than a power of 2, then every Bernoulli matrix has non-zero permanent). In contrast, the probability that the determinant vanishes completely is conjectured to equal $(1/2 + o(1))^n$ (which is easily seen to be a lower bound), but the best known upper bound for this probability is $(1/\sqrt{2 }+ o(1))^n$, due to Bourgain, Vu, and Wood.

Avi Wigderson‘s final talk in his Distinguished Lecture Series on “Computational complexity” was entitled “Arithmetic computation“; the complexity theory of arithmetic circuits rather than boolean circuits.