15
$\begingroup$

Suppose that I construct an $n \times n$ matrix $A$ such that each entry of $A$ is a random integer in the range $[1, \, n]$. I'd like to calculate the expected value of $\det(A)$.

My conjecture is that the answer is zero, though I could very well be incorrect. Running some numerical experiments with different values for $n$ and a large number of trials, it seems that $\mathbb{E}[\det(A)]$ is normally in the range $[0.25, \, 0.7]$, so I'm starting to lose faith in my intuition that it is zero.

Could anyone lend some advice on how to approach this problem and what strategies I may want to consider applying?

$\endgroup$
  • $\begingroup$ This seems like it would be a very complicated question. For example, in the $2 \times 2$ case, you would have to compute the expected value of $\left|\begin{pmatrix}a & b \\ c & d\end{pmatrix}\right|$, or $\mathbb{E}\left[ad - bc\right]$. You would need to examine products of uniform random variables and how they are distributed as well... I'll see if I can offer any insight later. Also, given the fact that they're discrete uniform random variables makes the question harder, in my opinion. But fascinating question nevertheless. $\endgroup$ – Clarinetist Jun 30 '14 at 0:52
  • 1
    $\begingroup$ Is there a typo in the statement "$\det(A)$ is normally in the range $[0.25,0.7]$"? As $A$ is an integer matrix its determinant must be an integer. $\endgroup$ – David Jun 30 '14 at 0:53
  • $\begingroup$ Oops, I meant $\mathbb{E}[\det(A)]$. Fixed. $\endgroup$ – Daniel Smith Jun 30 '14 at 0:56
  • 2
    $\begingroup$ This MO post is related and may be of use. In particular it points out that a more interesting question might be $\sqrt{\mathbb{E}((\det A)^2)}$. $\endgroup$ – Peter Woolfitt Jun 30 '14 at 1:56
  • 2
    $\begingroup$ @Clarinetist The $2\times2$ case gets a lot simpler with $\mathbb{E}[ad-bc] = \mathbb{E}[ad]-\mathbb{E}[bc]$. :) $\endgroup$ – JiK Jun 30 '14 at 10:41
23
$\begingroup$

Rebecca's answer is nice, but here's another solution that might be simpler for some people: Let $f$ be a function that swaps the first two rows. Notice that $f(A)$ and $A$ have the same distribution, and thus $$\mathbb{E}[\det A] = \mathbb{E}[\det f(A)] = \mathbb{E}[-\det A] = - \mathbb{E}[\det A].$$

$\endgroup$
  • 1
    $\begingroup$ Of course it's nice, which is why she got a "Nice Answer" badge for it ;) $\endgroup$ – M. Vinay Jul 2 '14 at 8:33
21
$\begingroup$

For $n \geq 2$, we partition the matrices into "orbits" formed by swapping the first two rows:

  • Orbits of size $1$ have two identical rows, so $\det=0$.

  • Orbits of size $2$ have matrices of determinants of equal magnitude but opposite sign.

Hence $\sum_A \det(A)=0$ and so $\mathbb{E}(\det(A))=\tfrac{1}{n^{n^2}}\sum_A \det(A)=0$.

$\endgroup$
3
$\begingroup$

The elements of your matrix appear to be independently and identically distributed random variables, all following a discrete Uniform distribution $a_{ij} \sim U(1,n)$. Then, at the theoretical level, all is nice and clear:
Any $n \times n$ determinant, $n>2$, is decomposed down to a sum (with varying signs of course) of $2 \times 2$ determinants, with multiplying terms in front of them.

One such term, typical in its structure, would be (neglecting the sign)

$$a_{11}\cdot a_{22}\cdot...a_{n-2,n-2} \cdot \left (a_{n-1,n-1} a_{nn} - a_{n-1,n}a_{n,n-1}\right)$$

and, due to independence

$$E\left[a_{11}\cdot a_{22}\cdot...a_{n-2,n-2} \cdot \left (a_{n-1,n-1} a_{nn} - a_{n-1,n}a_{n,n-1}\right)\right]$$

$$=E\left[a_{11}\cdot a_{22}\cdot...a_{n-2,n-2} \right]\cdot \left (E(a_{n-1,n-1}) E(a_{nn}) - E(a_{n-1,n})E(a_{n,n-1})\right)$$

But the variables are also identically distributed, so their expected value is the same. So

$$E(a_{n-1,n-1}) E(a_{nn}) - E(a_{n-1,n})E(a_{n,n-1}) =0$$

in all cases, and so all such terms are zero, and the expected value of the determinant will be zero.

Obviously, if the elements of the matrix are not independent r.v.'s, we cannot break the expected values and the zero result does not hold in general. So perhaps, the way you draw your random numbers makes the elements of the matrix non-independent? Perhaps for each row or column you draw "without replacement"?

But assume that we do draw correctly independent numbers/random variables, and we want to "see with our own eyes" that the "average value" does converge to zero. How do we go about it? For given $n$, the "sample analogue" of the expected value of the determinant is

$$\overline {\det(A)}= \frac 1m\sum_{i=1}^m\det(A_m)$$ where $m$ is the number of matrices generated in the same fashion...

...and the nice clean picture provided by the Expected Value operator and the i.i.d. assumption just vanished, because the sample mean of the determinants is not the average of a sum of independent r.v.'s: the components of each determinant is of course independent from the components of all other determinants, indeed. Each component of each determinant, is comprised of i.i.d r.v.'s indeed (it is a product of i.i.d discrete uniforms). But between certain components of each determinant, there will be dependence since they will have some r.v.'s in common. For example the determinant of the matrix

$$B=\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}$$ is

$$|B|=aei+bfg+cdh-ceg-bdi-afh$$

and you can see the various stochastic dependencies. This makes the fate of simulations for $\overline {\det(A)}$ a rather more complicated issue to determine, get a sense of the rate of convergence, etc. In other words, your conjecture is correct -but seeing it materialize through computer simulation may be another matter.

$\endgroup$
2
$\begingroup$

Let $A_n$ be an $n \times n$ matrix.

The case of a $1 \times 1$ matrix is a little different than the general case. Since the determinant is just the single entry itself, it follows that since the entry must be one, the determinant is also one.

For $n \geq 2$, you can show that the answer is zero using induction. Consider the case $n=2$ and the corresponding matrix $A_2$. It's determinant is

$$ \det(A_2) = \left| \left( \begin{array}{cc} a & b \\ c & d \end{array} \right) \right| = ad - bc. $$

In other words,

$$ \mathbb{E}[\det(A_2)] = \mathbb{E}[ad-bc] = \mathbb{E}[ad] - \mathbb{E}[bc] = \mathbb{E}[a]\mathbb{E}[d] - \mathbb{E}[b]\mathbb{E}[c] $$

where the second equality comes from the linearity of the expected value and the second comes from the fact that $a$, $b$, $c$, and $d$ are independent random variables. It's not hard to see that $\mathbb{E}[X] = (2+1)/2 = 3/2$ for $X \in \{ a, \, b, \, c, \, d \}$. Thus,

$$ \mathbb{E}[\det(A_2)] = \left(\frac{3}{2}\right)^2 - \left(\frac{3}{2}\right)^2 = 0. $$

Next assume that $\det(A_n) = 0$, where $A_n$ is an $n \times n$ matrix.

For the inductive step, note that $\det(A_{n+1})$ can be written as

$$ \det(A_{n+1}) = \lambda_1\det\left(A_{n}^{(1)}\right) - \lambda_2\det\left(A_{n}^{(2)}\right) + \lambda_3\det\left(A_{n}^{(3)}\right) - \cdots \pm \lambda_{n+1}\det\left(A_{n}^{(n+1)}\right) $$

by using the usual method to expand the determinant across the top row (or any row/column, really) of the $(n+11) \times (n+1)$ matrix (note that I used the superscripts simply to index the $n \times n$ matrices). Since $\det\left(A_n^k\right) = 0$ for $k = 1, \, 2, \dots, \, n+1$, the determinant is zero for $n \geq 2$, by induction.

Putting these results together, we have

$$ \mathbb{E}[\det(A_n)] = \begin{cases} 1, & n = 1 \\ 0, & n \geq 2. \end{cases} $$

Note that you can easily extend this result to show that if the entries come from any bounded set, the determinant must be zero for $n \geq 2$.

$\endgroup$
  • $\begingroup$ [+1] for the idea. But operator $\mathbb{E}$ is missing at different places in the second part of you answer : for example "Next assume that $\det(A_n)=0$" should be "Next assume that $\mathbb{E}[\det(A_n)]=0$". $\endgroup$ – Jean Marie Nov 9 '17 at 7:54

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.