# Expected value of determinant of simple infinite random matrix

Suppose we have a matrix $$A \in \mathbb{R}^{n\times n}$$ where

$$A_{ij} = \begin{cases} 1 & \text{with probability} \quad p\\ 0 &\text{with probability} \quad1-p\end{cases}$$

I would like to know the following expected value

$$\lim_{n \rightarrow \infty} \mathbb E(| \det (A) |)$$

i.e., the asymptotic behavior as $$n$$ becomes large.

### What I tried so far

It feels like this has been done already, but after searching for quite a while I performed simulations and it looks like

$$\mathbb E(|\det(A)|) \propto e^{n f(p) }$$

where $$f$$ is some function of the probability $$p$$. $p$." />

I would be very happy if someone knows the result or a good reference where I could look it up.

Edit: I changed the figure and added plots of the solutions

$$\text{log} \mathbb E(|\det(A)|) \propto \frac{n}{2} \text{log} \frac{n p (1-p)}{e}$$ given by Richard Stanley and RaphaelB4 which coincide up to multiplicative terms if the factorial in Richard Stanleys solution is replaced by stirlings formula.

• Math experiment done with Maple produces $E(\det A)=0$ for $n=1,…,4$ and $$p,-2\,{p}^{4}+2\,{p}^{2},12\,{p}^{9}-36\,{p}^{8}+36\,{p}^{7}-18\,{p}^ {5}+6\,{p}^{3},-528\,{p}^{16}+3456\,{p}^{15}-10080\,{p}^{14}+17280\,{p }^{13}-19152\,{p}^{12}+13824\,{p}^{11}-5760\,{p}^{10}+576\,{p}^{9}+504 \,{p}^{8}-144\,{p}^{6}+24\,{p}^{4}$$ for $E(|\det A|)$. In view of it your hypothesis does not seem to be true. Apr 6 '18 at 10:57
• Thanks for your response. In the simulations I performed, the scaling relationship $E(|det A|) \propto e^{Nf(p)}$ is only valid for large $n$. Therefore, it could be that for small $n$ the expectation value behaves differently and maybe even decrease with increasing $n$. Apr 6 '18 at 11:44
• I added a figure showing simulation results for $p=0.5$. Apr 6 '18 at 11:59
• Hadamard inequality, implies $\mathbb{E}(|\mathrm{det}(A)|) \leq (pn)^{n/2}.$ Apr 6 '18 at 13:49
• It can be shown that the expected value of $\mathrm{det}(A)^2$ is exactly $n!p^n(p-1)^{n-1}(1+(n-1)p)$. Apr 7 '18 at 20:48

Here is a solution to Hipstpaka's question about $\det(A)^2$. I don't have enough space to answer in a comment. I don't know where a statement appears in the literature, but the proof uses a standard technique discussed for instance in Enumerative Combinatorics, vol. 2, Exercise 5.64.

Write $\varepsilon_w$ for the sign of the permutation $w\in S_n$. Then \begin{eqnarray*} \sum_A \det(A)^2 & = & \sum_{i,j=1}^n\sum_{a_{ij}=0,1} \left(\sum_{w\in S_n} \varepsilon_w a_{1,w(1)}\cdots a_{n,w(n)}\right)^2\\ & = & \sum_{i,j=1}^n\sum_{a_{ij}=0,1} \sum_{u,v\in S_n} \varepsilon_u\varepsilon_v a_{1,u(1)}\cdots a_{n,u(n)} a_{1,v(1)}\cdots a_{n,v(n)}. \end{eqnarray*} Let $f(u,v)$ be the number of distinct variables occurring among $a_{1,u(1)},\dots, a_{n,u(n)},a_{1,v(1)},\dots, a_{n,v(n)}$. The product $a_{1,u(1)}\cdots a_{n,u(n)}a_{1,v(1)}\cdots a_{n,v(n)}$ is 1 with probability $p^{f(u,v)}$ and is otherwise 0. Moreover, $f(u,v)= 2n-\mathrm{fix}(uv^{-1})$, where $\mathrm{fix}(uv^{-1})$ denotes the number of fixed points of $uv^{-1}$. If $E$ denotes expectation, then we get $$E(\det(A)^2) = \sum_{u,v\in S_n}\varepsilon_u\varepsilon_v p^{2n-\mathrm{fix}(uv^{-1})}.$$ Setting $w=uv^{-1}$ and noting that $\varepsilon_u\varepsilon_{wu^{-1}} = \varepsilon_w$, we get \begin{eqnarray*} E(\det(A)^2) & = & \sum_{w\in S_n} p^{2n-\mathrm{fix(w)}} \sum_u\varepsilon_u\varepsilon_{wu^{-1}}\\ & = & n!p^{2n}\sum_{w\in S_n}p^{-\mathrm{fix(w)}}\varepsilon_w. \end{eqnarray*} Let $g(n)=\sum_{w\in S_n}p^{-\mathrm{fix(w)}}\varepsilon_w$. By standard generating function techniques (Enumerative Combinatorics, vol. 2, Section 5.2) we have \begin{eqnarray*} \sum_{n\geq 0} g(n)\frac{x^n}{n!} & = & \exp\left( \frac 1p x-\frac{x^2}{2}+\frac{x^3}{3} -\frac{x^4}{4}+\cdots\right)\\ & = & (1+x)\exp \left( \frac 1p-1\right)x. \end{eqnarray*} It is now routine to extract the coefficient of $x^n$ and then compute $$E(\det(A)^2)= n!\,p^n(p-1)^{n-1}(1+(n-1)p).$$

In general we don't have $E(\det(A)^2)=E(|\det(A)|)^2$, so this does not directly answer the original question.

For a related question (and answer) see Expected determinant of a random NxN matrix.

• Just a comment to say that the sum $g(n)=\sum_{w\in S_n}p^{-\mathrm{fix(w)}}\varepsilon_w$ can be computed directly by considering e.g. the number of fixed points of $w$: $$g(n)=\sum_{k=0}^n p^{-k}\binom{n}{k}\sum_{\substack{w\in S_{n-k}\\ \text{no fixed points}}}\varepsilon_w.$$ The last sum is the determinant of the identity matrix where one replaces the main diagonal with zeros, which is easily seen to be $(n-k-1)(-1)^{n-k-1}$, so that $$g(n)=\sum_{k=0}^n p^{-k}\binom{n}{k}(n-k-1)(-1)^{n-k-1}=\frac{1}{p^n}(1-p)^{n-1}(1+(n-1)p).$$ May 4 '19 at 20:02
• It is possible to do a similar derivation of the expected value for higher even powers of detA? Jan 31 at 16:32
• @Machinato It might be possible to do fourth powers using the idea in the solution to Exercise 5.64(b) of my book Enumerative Combinatorics, vol. 2. I think that higher powers will be hopeless using this method. Feb 1 at 19:37

Very nice problem!

Let me recall you that the determinant of $n \times n$ matrices with entries in $\{0,1\}$ is related to the one of $n+1 \times n+1$ matrices with entries in $\{-1,+1\}$: replace the zeros by $-1$'s and add a row of $-1$'s on the top and a column of ones on the right (you may want to read this arXiv).

I can now tell you that, besides the trivial cases $p=0$ and $p=1,$ your problem is solved for $p=\frac{1}{2}$.

Indeed it was studied by T. Tao and V. Vu in arXiv. They proved that for the matrix $M_n$ of size $n \times n$ where the entries are i.i.d. Bernoulli random variables in $\{-1,+1\},$ the probability that $|\det(M_n)|$ is close to $\sqrt{n!}$ tends to one:

$$P \left(|\det (M_n)|\geq \sqrt{n!}\exp(-29n^{1/2}\ln^{1/2}n)\right)=1-o(1).$$

I agree with user39115!

I will give a heuristic from random matrix theory because we know the global behaviour of the eigenvalue. First $$A=p 1 +\sqrt{N(p-p^2)}\frac{B}{\sqrt{N}}$$ where $1$ is the matrix with only 1 entries and $$B_{i,j}=\begin{cases} \frac{1-p}{\sqrt{(p-p^2)}} &\text{with probability } p\\ \frac{-p}{\sqrt{(p-p^2)}} &\text{ with probability }1-p \end{cases}$$ $B$ is a random matrices independent entries with zero mean and variance 1 so we are exactly in set up of generalise Wigner Matrices https://terrytao.files.wordpress.com/2011/02/matrix-book.pdf. The eigenvalue of $B/\sqrt{N}$ converge to the Uniform law on the unit circle. $$\mu_n = \frac{1}{N}\sum_{\lambda\in \sigma(B/\sqrt{N})}\delta_\lambda \rightarrow \frac{1}{\pi}\mathcal{U}_{x^2+y^2\leq 1}$$ $A$ is just a rank one perturbation of $B$ so it does not change the global distribution of the eigenvalue of $B$ only add the larger eigenvalue $\lambda_1\sim pN$. $$\log(|det(A)|)\sim \log(pN)+N\log(\sqrt{N(p-p^2)})+\log(|det(B/\sqrt{N})|)$$ and we believe that $$\frac{1}{N}\log(|det(B/\sqrt{N})|=\frac{1}{N}\sum_{\lambda\in\sigma(B/\sqrt{N})} \log(|\lambda|)\sim \frac{1}{\pi}\int_{x^2+y^2\leq 1}\log(\sqrt{x^2+y^2})dxdy$$ and the last integral is equal to $-1/2$.Therefore we should get $$\log(|det(A)|)\sim N\log(\sqrt{\frac{N(p-p^2)}{e}})$$ note that we recover $\sqrt{N!}$ of user39115.

So this is my heuristic (which rigourous proof is probably extremly hard.)

• The logarithm of the determinant of your $B$ matrix is normally distributed, with mean $\frac{1}{2} (n-1)!$. This was originally stated by Girko (mathscinet.ams.org/mathscinet-getitem?mr=1453330 ), but his proof is opaque and seems to skirt some technical steps. Later more transparent proofs were given by Nguyen and Vu (arxiv.org/pdf/1112.0752.pdf ) and by Bao, Pan, and Zhou (arxiv.org/pdf/1208.5823.pdf ) Apr 7 '18 at 0:00
• @RaphaelB4: This solution seems to be correct (see plot) and coincides with the one stated by Richard Stanley. Apr 8 '18 at 7:09

$$\mathbb{E}(|\mathrm{det}(A)|) \leq (pn)^{n/2} =e ^{\frac {n}2\log pn}.$$
If we divide by $pn$, the matrix $B=\frac{1}{pn}A$ is, on average, a stochastic matrix. In the generic case, the Perron-Frobenius theorem says $B$ has one eigenvalue equal to $1$ and all the others have modulus smaller than $1$.
Therefore, it would be reasonable to expect there exists some $0<b(p)<1$ such that $\langle |{\rm det}(B)|\rangle\sim b(p)^n$. The function $b(p)$ is probably decreasing with $p$ since as $p\to 1$ the lines of $B$ become equal and the determinant must vanish.
This would give $\langle |{\rm det}(A)|\rangle\sim (pnb(p))^n=e^{n{\rm log}(pnb(p))}$.
• The matrix $A/pn$ on average is a stochastic matrix , not $A/p$. Apr 6 '18 at 13:53