3
$\begingroup$

I have a very large random matrix which its elements are either $0$ or $1$ randomly. The size of the matrix is $5000$, however when I want to calculate the determinant of the matrix, it is either $Inf$ or $-Inf$. Why it is the case (as I know thw determinant is a real number and for a finite size matrix with finite elements, it cannot be $Inf$) and how can I remedy any possible mistake?

$\endgroup$
  • $\begingroup$ However, the determinant can easily overflow the double precision range.. $\endgroup$ – Carl Christian Mar 12 '16 at 2:29
  • $\begingroup$ @CarlChristian So why do I have overflow for every scenario. As I said the matrix is generated randomly, and for each generation, the determinant is $Inf$ or $-Inf$ $\endgroup$ – Carl_Gauß Mar 12 '16 at 2:31
  • $\begingroup$ Try dividing the matrix by $5000$ before taking the determinant; that should give you results that won't overflow. $\endgroup$ – Omnomnomnom Mar 12 '16 at 2:48
  • $\begingroup$ See this answer on SciComp.SE for why numerically calculating the determinant of a large matrix is not a good idea. Inf in Matlab means larger than realmax ($\approx10^{308}$). $\endgroup$ – horchler Mar 12 '16 at 3:18
4
$\begingroup$

I did a search for "determinant of random matrix" and found this article:

https://people.math.osu.edu/nguyen.1261/cikk/loglaw.pdf

It shows that the log of the determinant of a n by n random matrix is usually about $n\log(n)/2 $.

Therefore, for large $n$, any computation of the determinant will almost certainly overflow.

$\endgroup$
  • $\begingroup$ $5000\ln(5000)$ is not a large number. The reason why it overflows is because of roundoffs in the LU decomposition of A, which matlab uses to compute the determinant. $\endgroup$ – bartgol Mar 12 '16 at 4:27
  • 3
    $\begingroup$ This is the log of the determinant. The determinant is about $5000^{2500}$. $\endgroup$ – marty cohen Mar 12 '16 at 4:37
  • $\begingroup$ My bad, I missed the first "log" in your answer. $\endgroup$ – bartgol Mar 12 '16 at 4:48
  • $\begingroup$ For clarity it might help to put the formula for the determinant itself in the post ($\sqrt{n^n}$), or italicize the "log", or some such thing. I think this is an easy reading mistake to make. $\endgroup$ – David Z Mar 12 '16 at 10:13
3
$\begingroup$

If the determinant is needed, then a numerically reliable strategy is to compute the $QR$ decomposition of $A$ with column pivoting, i.e. $AP = QR$, where $P$ is a permutation matrix, $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. In MATLAB the relevant subroutine is 'qr'. Then the determinant of $A$ equals the product of the diagonal entries of $R$ (up to a sign change which is determined by the determinant of $P$). The question of computing the determinant then reduces to handling the product of $n$ terms. This product can easily overflow or underflow, but it is likely that you will be able to determine the logarithm of the absolute value of this product, using the relation $\log(ab) = \log(a) + \log(b)$.

There are exceptions, but normally the condition number of a matrix is more important than the determinant.

$\endgroup$

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.