16
$\begingroup$

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$.

Comparison of simulation results and solutions described below for different values of $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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user64494 Apr 6 '18 at 10:57
  • $\begingroup$ 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$. $\endgroup$ – Hipstpaka Apr 6 '18 at 11:44
  • $\begingroup$ I added a figure showing simulation results for $p=0.5$. $\endgroup$ – Hipstpaka Apr 6 '18 at 11:59
  • 2
    $\begingroup$ Hadamard inequality, implies $\mathbb{E}(|\mathrm{det}(A)|) \leq (pn)^{n/2}.$ $\endgroup$ – Mahdi Apr 6 '18 at 13:49
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Richard Stanley Apr 7 '18 at 20:48
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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).$$ $\endgroup$ – Gagar May 4 at 20:02
22
$\begingroup$

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).$$

$\endgroup$
10
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ 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 ) $\endgroup$ – Kevin P. Costello Apr 7 '18 at 0:00
  • $\begingroup$ @RaphaelB4: This solution seems to be correct (see plot) and coincides with the one stated by Richard Stanley. $\endgroup$ – Hipstpaka Apr 8 '18 at 7:09
3
$\begingroup$

Hadamard inequality , implies

$$ \mathbb{E}(|\mathrm{det}(A)|) \leq (pn)^{n/2} =e ^{\frac {n}2\log pn}. $$

$\endgroup$
2
$\begingroup$

What follows is very heuristic [and updated according to first comment].

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))}$.

$\endgroup$
  • 1
    $\begingroup$ The matrix $A/pn$ on average is a stochastic matrix , not $A/p$. $\endgroup$ – Mahdi Apr 6 '18 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.