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

5 Answers 5

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$
4
  • $\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, 2019 at 20:02
  • $\begingroup$ It is possible to do a similar derivation of the expected value for higher even powers of detA? $\endgroup$
    – Machinato
    Jan 31, 2021 at 16:32
  • $\begingroup$ @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. $\endgroup$ Feb 1, 2021 at 19:37
  • $\begingroup$ @Stanley After more than a year of (from time to time) trying to tackle the poblem, I have finally concluded it cannot be done this way. It is, however, rather strange. Nyquist (1954) derived an almost general formula for E[det^4 A]. However, his entries are symetrical random variables (the case of all $\pm 1$ matrices belongs here! you can even assign some probability $p$ that the entries are zero). Somehow, however, there is no such formula for the case when the A's entries are general iid random variables. $\endgroup$
    – Machinato
    Jun 10, 2022 at 21:08
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$
2
  • 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$ Apr 7, 2018 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, 2018 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
  • 1
    $\begingroup$ The matrix $A/pn$ on average is a stochastic matrix , not $A/p$. $\endgroup$
    – Mahdi
    Apr 6, 2018 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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