4
$\begingroup$

I am looking for the best upper bounds on the bit complexity for testing the singularity of an integer $n\times n$ matrix, where each integer is represented with $k$ bits.

I know the fast method for computation of the determinant in Storjohann, The shifted number system for fast linear algebra on integer matrices, but it assumes that the determinant is nonzero.

What about lower bounds on the complexity?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is addressed in Storjohann's paper on computing Smith Normal Form.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Lemma 13 indeed asserts the existence of a deterministic algorithm that computes the determinant in $\tilde O(n^{\theta+1}k)$ bit operations, where $\theta$ is the exponent for matrix multiplication. (In fact a slightly more detailed result of this order is given.) The paper is from 1996, is this still the state of the art? Is checking for singularity as expensive as computing the determinant? $\endgroup$
    – Arnold Neumaier
    Commented Sep 9, 2015 at 17:38
  • $\begingroup$ There is a 2004 paper by Kaltofen and Villard (Computing the sign or the value of the determinant of an integer matrix, a complexity survey Erich Kaltofena, Gilles Villardb;) The paper was actually written in 2001, so not THAT much later than Storjohann's $\endgroup$
    – Igor Rivin
    Commented Sep 9, 2015 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .