Integer matrix rank certification
Arne Storjohann · 2009
Let M = [A B/C D] be a 2n x 2n integer matrix with the principal block A square and nonsingular. An algorithm is presented to determine if the Schur complement D--CA--1 B is equal to the zero matrix in O~(nω log ||M||) bit operations. Here, ω is the exponent of matrix multiplication and ||M|| denotes the largest entry in absolute value. The algorithm is randomized of the Las Vegas type, and either returns the correct answer ("yes" or "no"), or returns fail with probability less than 1/2. This gives a Las Vegas algorithm for computing the rank r of an n x m integer matrix A in an expected number of O~(nmrω--2 log ||A||) bit operations.