-2
$\begingroup$

Let $A \in \mathbb{R}^{11 \times 11}$ and it's elements are form set $\{ -1,1 \}$. $\mathbb{P}(-1) = \mathbb{P}(1) = 0.5$. What is a probability to get such a matrix, that $\det A > 4000$?

I have such an idea:

It's better to find the $\mathbb{P}(\det A \leq 4000)$:

$F_{\det A} = \mathbb{P}(\det A \leq 4000) = \mathbb{P} \left( \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{11})} (-1)^{\sigma(\alpha)}a_{1\alpha_1}a_{2\alpha_2}...a_{11\alpha_{11}} \leq 4000 \right)$.

But I have several problems:

  1. $a_{ij}$ is a random value, but not all of $a_{1\alpha_1}a_{2\alpha_2}...a_{11\alpha_{11}}$ are random values.

  2. How to calculate $\mathbb{P}(\xi_1+...+\xi_{11} \leq 4000)$? I realize that $\xi_1+...+\xi_{11}$ is a hyperplane...

P.S. Is there any programm that can make N trials generating random matrixes?

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ This question appears to be off-topic because it is essentially the same as your question from yesterday. $\endgroup$
    – Anthony Quas
    Nov 14, 2014 at 15:33
  • 4
    $\begingroup$ I didn't see the question from yesterday: what's the link? Depending on what's there, the downvoters might reconsider, because $(11,4000)$ seems to be in or near the range where the problem is quite nontrivial. For a random $\pm1$ matrix $A$ of size $n \times n$, the distribution of $\;\det A$ is symmetric with ${\mathbb E}(\det^2 A) = n!$. For $n=11$, this makes the standard deviation $\sqrt{11!} \simeq 6318$, so it's not at all obvious what one should expect for the probability that $\det A > 4000$. $\endgroup$
    – Noam D. Elkies
    Nov 14, 2014 at 15:38
  • 3
    $\begingroup$ @Noam If you put it this way, it surely becomes interesting. But otherwise there are several parts of the question which make it likely that it is just homework. (for example: Why 11 and 4000? What is $\xi$? The fact that the OP thinks he has to add the by-definition approach) If the question would be something reasonable about the distribution of $det(A)$ for $n\times n$ matrices it would certainly be of interest. In its current form, only your comment makes it interesting. $\endgroup$
    – Daniel Soltész
    Nov 14, 2014 at 16:31
  • 2
    $\begingroup$ In fact, the original version of the question just asked whether or not there exists an 11-by-11 (+1,-1)-matrix with determinant above 4000, albeit it was stated in a way that suggested that the desired proof would use probabilistic methods (i.e., show that the probability that its determinant is > 4000 is non-zero). Anyway, the link is here (not sure what amount of reputation is needed before you can view deleted questions (or if such an amount of reputation exists)). $\endgroup$
    – Nathaniel Johnston
    Nov 14, 2014 at 18:37
  • 4
    $\begingroup$ There's no Hadamard matrix of order $11$. (Though removing a row and column from $H_{12}$ yields a square $\pm 1$ matrix of order $11$ and determinant $\pm 12^5$ which is more than sufficient.) $\endgroup$
    – Noam D. Elkies
    Nov 14, 2014 at 19:42

3 Answers 3

Reset to default
3
$\begingroup$

A recent paper of Nguyen and Vu shows that the logarithm of the determinant is asymptotically normal. You could use this to estimate the probability that you are looking for. However, the result is an asymptotic result for $n$ large and it's not clear that $n=11$ is large enough to get a good approximation. They actually get an error bound of $(\log n)^{-1/3+o(1)}$ in general. I don't know if the proof gives something that is explicit of the $o(1)$ term in the error bound, however. In any case, $(\log 11)^{-1/3} \approx 0.747...$ isn't a very good error bound, so the asymptotic normal approximation might not be very good when $n=11$.

Improve this answer
$\endgroup$
2
$\begingroup$

I did $10^5$ trials in Maple and found a probability of $0.35313$ for $|\det(A)|>4000$, or half that for $\det(A)>4000$. The calculation took a couple of minutes, so you could easily do $10^7$ trials or more if you care. Code is as follows:

with(LinearAlgebra):
r0 := rand(0..1):
r := () -> 2 * r0() - 1:
rM := () -> Matrix(11,11,[seq(r(),i=1..121)]):
SS := [seq(Determinant(rM()),i=1..100000)]:
evalf(nops(select(u -> abs(u)>4000,SS))/nops(SS));
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The determinant will be a multiple of $2^{10}.$ Add/subtract the first row from the rest to reduce the determinant calculation (up to sign) to $2^{10}$ times the determinant of a $10 \times 10$ matrix with entries $0,1$ with equal probabilities. That should run somewhat faster. $\endgroup$
    – Aaron Meyerowitz
    Nov 14, 2014 at 18:30
  • 1
    $\begingroup$ Yes, though $\{0,1\}$ determinants of order $10$ aren't all that much faster than $\pm 1$ determinants of order $11$. FWIW here's equivalent gp code: p(N)=sum(d=1,N,abs(matdet(matrix(11,11,i,j,1-2*random(2))))>4000)/N (I also get 35+ percent from p(10^5), in about six seconds). $\endgroup$
    – Noam D. Elkies
    Nov 14, 2014 at 20:51
  • $\begingroup$ Using Noam's code, I obtained probability 0.354798 for p(10^6), and 0.3548666 for p(10^7). $\endgroup$
    – Vladimir Dotsenko
    Nov 14, 2014 at 22:04
1
$\begingroup$

Thank you, @Noam, for your idea!

Statement 1: Let $A \in \mathbb{R}^{n \times n}$ and $a_{ij} \in \{-1, 1\}$, then $\mathbb{E}(\det A) = 0$

Proof: It's easy to see, that because of every $a_{ij}$ is a random value: $ \mathbb{E}(\det A) = \mathbb{E} \left( \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} (-1)^{\sigma(\alpha)} a_{1\alpha_1}a_{2\alpha_2}...a_{n\alpha_{n}} \right) = \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} (-1)^{\sigma(\alpha)} \mathbb{E}a_{1\alpha_1} \mathbb{E}a_{2\alpha_2} ... \mathbb{E}a_{n\alpha_{n}} = 0,$ as $\displaystyle \mathbb{E}a_{ij} = (-1) \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} = 0.$ $\square$

Statement 2: Let $A \in \mathbb{R}^{n \times n}$ and $a_{ij} \in \{-1, 1\}$, then $\mathbb{E}((\det A)^2) = n!$

Proof: $ \mathbb{E}(\det A)^2 = \mathbb{E} \left( \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} (-1)^{\sigma(\alpha)} a_{1\alpha_1}a_{2\alpha_2}...a_{n\alpha_{n}} \right)^2 = \mathbb{E} \left( \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} (-1)^{\sigma(\alpha)} a_{1\alpha_1}a_{2\alpha_2}...a_{n\alpha_{n}} \sum\limits_{\beta=(\beta_1,\beta_2,...,\beta_{n})} (-1)^{\sigma(\beta)} a_{1\beta_1}a_{2\beta_2}...a_{n\beta_{n}} \right) = \mathbb{E} \left( \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} \sum\limits_{\beta=(\beta_1,\beta_2,...,\beta_{n})} (-1)^{\sigma(\alpha) + \sigma(\beta)} a_{1\alpha_1}a_{2\alpha_2}...a_{n\alpha_{n}} \cdot a_{1\beta_1}a_{2\beta_2}...a_{n\beta_{n}} \right) $

If permutations $\alpha$ and $\beta$ are not the same, then there is $a_{ij}$ which have power 1, and its $\mathbb{E}a_{ij} = 0$. Then equation above can be rewritten:

$ \mathbb{E}(\det A)^2 = \sum\limits_{\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})} (-1)^{2\sigma(\alpha)} \mathbb{E}a^2_{1\alpha_1} \mathbb{E}a^2_{2\alpha_2}... \mathbb{E}a^2_{n\alpha_{n}} = n!, $

as $\displaystyle \mathbb{E}a_{ij} = (-1)^2 \cdot \frac{1}{2} + 1^2 \cdot \frac{1}{2} = 1$, and the number of permutations $\alpha=(\alpha_1,\alpha_2,...,\alpha_{n})$ is equal to $A_n^n=n!$ $\square$

Then from the statements 1 and 2, we have that there are matrixes with determinant greter than 0 and $\mathbb{E}((\det A)^2) = 11!$, and correspondingly we have an assesment:

$\exists A: \det A \geq \sqrt{11!} \approx 6317.9 > 4000.$

The generator for matrixes in Wolfram Mathematica:

While[True,
 A = Table[RandomInteger[]*2 - 1, {i, 11}, {j, 11}];
 If[Det[A] > 4000, Print[MatrixForm[A]] Print[Det[A]] Break[]]
]
Improve this answer
$\endgroup$

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