2
$\begingroup$

André Nicolas, in his very neat answer to is the following matrix invertible? uses the fact that the matrix

$$ \begin{bmatrix} 1235 &2344 &1234 &1990\\ 2124 & 4123& 1990& 3026 \\ 1230 &1234 &9095 &1230\\ 1262 &2312& 2324 &3907 \end{bmatrix}$$

Modulo 2 is the identity, to show that its determinant is different from zero, something that also requires $$\det(A\mod x)\mod x=\det(A)\mod x$$ Where the modulo in $(A\mod x)$ is applied to the matrix elementwise. This happens because the determinant is a polynomial in the matrix entries and $$(a+bc^d)\mod x=(a\mod x + (b\mod x)(c\mod x)^d)\mod x$$

My question is then whether the successive application of such modular reductions could be a useful method to know if $\det(A)=0$. Perhaps this is so only in some particular situations, it would also be helpful if you show some of them.

$\endgroup$

2 Answers 2

4
$\begingroup$

It is indeed a useful technique of wide applicability, and not just for determinants: to test whether some difficult-to-compute polynomial identity (over the integers) is true, compute it in the integers mod $p$ where $p$ is some prime. If it's false mod $p$, it's false for the integers as well. If it's true mod $p$, it has some chance of being true. To reduce the number of "false positives", you might use a larger prime $p$: a "random" integer has probability $1/p$ of being $0$ mod $p$. To reduce even more, do this for several different primes. You can also handle rational expressions, if $p$ is chosen so that none of the denominators is $0$; you can handle expressions involving variables by assigning each variable a random number mod $p$.

See e.g. Gonnet, Gaston. "Determining Equivalence of Expressions in Random Polynomial Time." Proceedings of the 16th ACM Symposium on the Theory of Computing. Washington DC. April 1984. pp. 334-341.

$\endgroup$
3
$\begingroup$

Yes, if $M$ is an $n \times n$ matrix with entries in $\mathbf{Z}$, then, its determinant is bounded by $n!(\max_{i,j} m_{ij})^n$. Thus, for example, if $\det M \equiv 0 \bmod p$ for all primes $p$ with $p^2 \leqslant n!(\max_{i,j} m_{ij})^n$, then, $\det M$ must be identically $0$.

Edit. As Giuseppe points out, if one starts with Hadamard's inequality for the determinant, then, one gets a better bound. Hadamard's theorem is: $$|\det([v_1, \dots, v_n])| \leqslant \prod_{i=1}^n \|v_i\|$$ where $\|\cdot\|$ is the $2$-norm on $\mathbf{R}^n$.

$\endgroup$
2

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.