On the permanent of a random symmetric matrix

Two of the most basic matrix parameters are the determinant and the permanent: for an $n\times n$ matrix $M=(x_{i,j})_{i,j}$, define

A central direction of research in probabilistic combinatorics and random matrix theory is to understand the determinant and permanent of different types of random matrices. For example, let $A_{n}$ be an $n\times n$ matrix whose entries are i.i.d. Rademacher-distributed random variables, taking values $\pm 1$ with probability $1/2$ each (this is often called a random Bernoulli matrix). A classical theorem of Komlós [19] (perhaps the foundational theorem in discrete random matrix theory) is that $\Pr(\det A_{n}=0)=o(1)$ as $n\to\infty$. That is to say, $A_{n}$ is asymptotically almost surely nonsingular. Since then, there has been intensive effort to refine our understanding of the singularity probability (see [18, 31, 32, 28, 5]), culminating in a recent breakthrough of Tikhomirov [36] proving that $\Pr(\det A_{n}=0)=2^{-n+o(n)}$. The problem of estimating the order of magnitude of $\det A_{n}$ has also received significant attention: Tao and Vu [31] proved that with probability $1-o(1)$ we have $\mathopen{}\mathclose{{}\left|\det A_{n}}\right|=n^{n/2+o(n)}$, and later Nguyen and Vu [26] proved a central limit theorem for $\log|\det A_{n}|$ (see also [15, 16]).

Most of the above-mentioned results generalise readily to more general types of random matrices, where the entries are independently sampled from any subgaussian distribution. There has also been intensive interest in random matrices with dependence between the entries. Perhaps the most prominent examples are symmetric random matrices. Let $M_{n}$ be the random matrix whose entries on and above the diagonal are independent Rademacher random variables, and the entries below the diagonal are chosen to make the matrix symmetric (equivalently, we can choose a random matrix $A_{n}$ as above and condition on the event that $A_{n}$ is symmetric). The study of random symmetric matrices has necessitated the development of new tools, but by now there is a fairly complete understanding of the determinant of a random symmetric matrix with Rademacher entries. The fact that $\Pr(\det M_{n}=0)=o(1)$ was first proved by Costello, Tao and Vu [10] (see also [12]), and stronger estimates on $\Pr(\det M_{n}=0)$ were obtained by several authors [24, 38, 13, 9]. It is also known that with probability $1-o(1)$ we have $|\det M_{n}|=n^{n/2+o(n)}$ (this follows from work on the least singular value of $M_{n}$ due to Nguyen [25] and Rudelson [38], together with Wigner’s celebrated semicircle law [43, 44]), and a central limit theorem for $\log|\det M_{n}|$ was proved by Bourgade and Mody [4] (see also [34]).

It is widely believed that for all the above-mentioned theorems concerning determinants of random matrices (symmetric or not), there should be analogous theorems for permanents. However, the permanent appears to be a much more challenging parameter to study. For example, while the determinant encodes information about linear dependence and can be interpreted as the (signed) volume of a certain parallelepiped, it only seems possible to attack the permanent from a “combinatorial” point of view, directly considering the formal definition in Equation 1.1. The fact that the permanent is harder to study is maybe not surprising, since (in contrast to the determinant) the permanent of a matrix is $\#$P-hard to compute (as was famously proved by Valiant [37]). Even the analogue of the singularity problem, to show that $\Pr(\operatorname{per}A_{n}=0)=o(1)$, was open for a long time. In 2009, Tao and Vu [33] finally resolved this problem and also estimated the typical magnitude of $\operatorname{per}A_{n}$: namely, they proved that asymptotically almost surely $\mathopen{}\mathclose{{}\left|\operatorname{per}A_{n}}\right|=n^{n/2+o(n)}$. Perhaps surprisingly, permanents of random matrices turn out to be of interest in quantum computing: Aaronson and Arkhipov [2] proved that quantum computers cannot be efficiently simulated by classical computers, conditional on a conjecture which strengthens the aforementioned Tao–Vu permanent theorem (see also [1, 11, 22]).

The study of the permanent of a random symmetric matrix seems to have first been explicitly suggested by Tao and Vu (see [33, Remark 1.6]). They observed that their arguments for the permanent of a (not necessarily symmetric) random matrix “do not seem to easily yield any non-trivial result for the permanent of a random symmetric Bernoulli matrix”. The statement of Theorem 1.1 has been conjectured by Vu in 2009 (see [39]). He also mentioned the conjecture in a recent survey [40, Conjecture 6.11], and described it as “the still missing piece of the picture” regarding determinants and permanents of random discrete matrices.

Theorem 1.1 is actually a combination of two different results. First, the following proposition gives an upper bound on $|\operatorname{per}M_{n}|$.

Proposition 1.2 is easily proved using an estimate for $\mathbb{E}[(\operatorname{per}M_{n})^{2}]$ and Markov’s inequality; see Section 2. The main role of this paper is to prove the following lower bound on $|\operatorname{per}M_{n}|$.

We remark that the constant $c$ in Theorem 1.3 can be made explicit. For example, $c=1/150$ certainly suffices, though this can be improved substantially simply by optimising constants throughout the proof. However, without new ideas our methods do not seem to be capable of proving the statement of Theorem 1.3 with any $c\geq 1/2$. This state of affairs is essentially the same as for the non-symmetric case previously considered by Tao and Vu [33].

Of course, Theorem 1.3 also shows that the probability of having $\operatorname{per}M_{n}=0$ is polynomially small. Before this paper no nontrivial bounds for this probability were known, except when $n=2^{m}-1$ with $m\in\mathbb{N}$, where for elementary number-theoretic reasons it is actually impossible to have $\operatorname{per}M_{n}=0$ (see [30]¹¹1Actually, this result is part of an extensive body of research concerning permanents of (non-random) matrices with $\pm 1$ entries; see for example [41, 6, 7, 8, 30, 42, 20, 29, 21].).

Finally, we remark that the methods used to prove Theorem 1.1 are quite robust, and analogous theorems can be proved for much more general distributions. For example, consider any fixed real probability distributions $\mu$ and $\nu$, and let $M_{n}^{\mu,\nu}$ be the random symmetric matrix whose diagonal entries have distribution $\nu$ and whose off-diagonal entries have distribution $\mu$ (and whose entries on and above the diagonal are mutually independent). With some fairly mild assumptions on $\mu$ and $\nu$ it is a routine matter to prove an analogue of Proposition 1.2 for $M_{n}^{\mu,\nu}$, and in Section 8 we sketch how to make some minor adaptations to the proof of Theorem 1.3 to obtain a version that holds for very general distributions (we only require that $\mu$ has nontrivial support). In particular, one can prove an analogue of Theorem 1.1 for random symmetric Gaussian matrices such as the Gaussian Orthogonal Ensemble (GOE).

Notation. In this paper, we use the notation $\mathbb{N}=\{1,2,\dots\}$ for the positive integers. All logarithms are to base $e$. For functions $f:\mathbb{N}\to\mathbb{R}$ and $g:\mathbb{N}\to\mathbb{R}_{>0}$, we write $f=o(g)$ if $f(n)/g(n)\to 0$ as $n\to\infty$.

In this section we provide the simple proof of Proposition 1.2. It will be an immediate consequence of Markov’s inequality and the following lemma.

The rest of this paper is devoted to the proof of Theorem 1.3. In this section we outline the high-level strategy of the proof, stating two key lemmas and deducing Theorem 1.3 from them.

We couple the distributions of the matrices $M_{n}$ for all $n\in\mathbb{N}$ by viewing each $M_{n}$ as containing the first $n$ rows and columns of an infinite random symmetric matrix (with Rademacher entries). Say that subsets of a given ground set are complement-disjoint if their complements are disjoint. For $A,B\subseteq\{1,\dots,n\}$, let $M_{n}[A,B]$ be the submatrix of $M_{n}$ consisting of the rows in $A$ and the columns in $B$. For $\lambda\geq 0$, we say that a matrix is $\lambda$-heavy if its permanent has absolute value at least $\lambda$.

The following lemma shows that with high probability there exists a heavy submatrix of $M_{n}$ consisting of almost all the rows and columns of $M_{n}$, and moreover we have some control over which rows and columns are not included. Roughly speaking, it is proved by studying how permanents of submatrices evolve in the sequence of random matrices $M_{1},\dots,M_{n}$.

By applying Lemma 3.1 with various different choices of $X$ and $Y$, we can obtain many heavy submatrices $M_{n}[A_{1},B_{1}],\dots,M_{n}[A_{m},B_{m}]$ such that the sets $A_{1},\dots,A_{m},B_{1},\dots,B_{m}$ are complement-disjoint. The next lemma states that in such a situation, if we sample $M_{n+1}$ by adding a random row and column to $M_{n}$, then a large proportion of our submatrices can be transformed into larger submatrices without losing much of their heaviness. We will apply this lemma repeatedly, each step decreasing by 1 the number of rows and columns that our submatrices are missing.

We now show how to deduce Theorem 1.3 from Lemmas 3.1 and 3.2.

We remark that the overall structure of our proof is similar to the work of Tao and Vu [33] on permanents of (not necessarily symmetric) random matrices. Indeed, Tao and Vu’s proof can also be broken up into two parts analogous to Lemmas 3.1 and 3.2. However, in Tao and Vu’s setting, all entries of the random matrix are independent, allowing them to expose the entries row by row. After exposing $k$ rows, they consider $k\times k$ submatrices that consist of all the $k$ exposed rows (and of $k$ of the $n$ columns). When exposing the $k$-th row, the permanent of any such $k\times k$ submatrix can be described as a linear polynomial in some of the entries of the new row, where the coefficients are given by the permanents of certain $(k-1)\times(k-1)$ submatrices in the first $k-1$ rows. In contrast, in our setting with the random symmetric matrix $M_{n}$, we are forced to expose the entries of our matrix in a different way: at the $k$-th step we reveal the entries in $M_{k}$ that are not present in $M_{k-1}$ (that is, we add a new random row and column, with equal entries, to the matrix considered so far²²2This type of exposure is standard in the study of symmetric random matrices (see for example [10]).). Since there is only one $k\times k$ submatrix in $M_{k}$ (namely $M_{k}$ itself), in our setting we also need to consider the permanents of (substantially) smaller submatrices of $M_{k}$.

This more intricate strategy introduces significant challenges. Most notably, the permanents of the submatrices of $M_{k}$ are described by quadratic polynomials in the new matrix entries, where the coefficients depend on the permanents of certain submatrices of $M_{k-1}$ (this is in contrast to Tao and Vu’s setting, where the permanents are described by linear polynomials in the entries of the new row). This necessitates the use of some more sophisticated probabilistic tools. Furthermore, there can be certain types of cancellations within these quadratic polynomials, which are not possible for the linear polynomials in the Tao–Vu setting. For example, even if all submatrices of $M_{k-1}$ have non-zero permanent, it can happen that the polynomial describing the permanent of some submatrix of $M_{k}$ has only very few nonzero coefficients. Handling these types of cancellations requires key new ideas.

Organization of the rest of the paper. Lemma 3.1 will be proved in Section 6, and Lemma 3.2 will be proved in Section 7. As preparation, in Section 4 we collect some probabilistic tools that we will use in the proofs, and in Section 5 we collect some lemmas that can be obtained by studying permanent expansion formulas.

It is more delicate to generalise the Erdős–Littlewood–Offord inequality to quadratic polynomials. For a multilinear quadratic polynomial $f$ in the variables $x_{1},\dots,x_{n}$ and for a real number $r>0$, let $G^{(r)}(f)$ be the graph with vertex set $\{1,\dots,n\}$ having an edge $ij$ whenever the coefficient of $x_{i}x_{j}$ in $f$ has absolute value at least $r$. Let $\nu(G)$ be the matching number³³3The matching number of a graph $G$ is the largest number $\nu$ such that one can find $\nu$ disjoint edges in $G$. of a graph $G$. The following is a special case of a theorem proved by Meka, Nguyen and Vu [23, Theorem 1.6].

The following concentration inequality is a special case of the Azuma–Hoeffding martingale concentration inequality, and is sometimes known as McDiarmid’s inequality (see for example [35, Lemma 1.34]).

The next inequality is a one-sided version of the Azuma–Hoeffding inequality for supermartingales (see [33, Lemma 2.3]).

Recall that for $0<p<1$, a Bernoulli random variable $\chi\sim\operatorname{Ber}(p)$ is a random variable taking values $0$ and $1$ with $\Pr(\chi=1)=p$ and $\Pr(\chi=0)=1-p$. The following lemma is a version of the Chernoff concentration bound for sums of Bernoulli random variables (see for example [3, Theorem A.1.4]).

Sometimes we will encounter random variables that stochastically dominate a sum of Bernoulli random variables (we say that a random variable $X$ stochastically dominates another random variable $Y$ if there is a coupling of $X$ and $Y$ such that we always have $X\geq Y$). For example, consider a random process with $n$ steps where each step satisfies a certain property with probability at least $1/2$, even when conditioning on any outcome of the previous steps. Then the number $X$ of steps with this property stochastically dominates a sum of $n$ independent $\operatorname{Ber}(1/2)$ random variables. Denoting this sum by $Y$, we therefore have $\Pr\mathopen{}\mathclose{{}\left(X-(n/2)<-t}\right)\leq\Pr\mathopen{}\mathclose{{}\left(Y-(n/2)<-t}\right)<e^{-2t^{2}/n}$ for any $t>0$ by Lemma 4.7. Hence we can use Lemma 4.7 to show that a random variable is very likely reasonably large if it stochastically dominates a sum of Bernoulli random variables.

Finally, the following lemma is an easy consequence of Markov’s inequality (see, for example, [33, Lemma 2.1]).

We will use Fact 5.1 in combination with the linear anti-concentration inequalities in Fact 4.2 and Theorem 4.1, and we will use Fact 5.2 in combination with the quadratic anti-concentration inequalities in Fact 4.3 and Theorem 4.4

Observe in particular that the formula in Fact 5.2 gives an expression for the permanent of a $(k+1)\times(k+1)$ matrix in terms of permanents of $(k-1)\times(k-1)$ submatrices (and one $k\times k$ submatrix). This means that, for example, when we add a new row and column to a matrix, the size of the largest submatrix with nonzero permanent can increase by two. This observation will be crucial for the proof of Lemma 3.2.

In the proof of Lemma 3.2, we will apply Fact 5.2 with the symmetric matrices $M=M_{n}$ and $M^{\prime}=M_{n+1}$. That is to say, $(x_{1},\dots,x_{n},z)=(y_{1},\dots,y_{n},z)$, so the formula in Fact 5.2 can be interpreted as a quadratic polynomial in $x_{1},\dots,x_{n}$ (after conditioning on the value of $z$). In order to apply Fact 4.3 to this polynomial, we need this polynomial to have a multilinear degree-2 coefficient with large absolute value. For this, it suffices that $\operatorname{per}M[A,B]^{(i,j)}+\operatorname{per}M[A,B]^{(j,i)}$ has large absolute value for some $i\neq j$ (with $i,j\in A\cap B$). The following lemma will be useful for ensuring this condition.

We end this section with two simple lemmas that illustrate how to apply Facts 5.1, 5.2 and 5.3 to “grow” heavy minors in a random symmetric matrix. Recall that $M_{n}$ is a random symmetric matrix, and that $M_{n-1}$ contains the first $n-1$ rows and columns of $M_{n}$.

In this section we prove Lemma 3.1. Recall that $L=\lfloor(\log n)/10\rfloor$ and that $X,Y\subseteq\{1,\dots,n\}$ are disjoint subsets with $|X|=L$ and $|Y|=3L$. By reordering the rows and columns, we can assume without loss of generality that $X=\{1,\dots,L\}$ and $Y=\{n-3L+1,\dots,n\}$.