Computing determinants, ranks and inverses

The determinant can be computed for any modulus, prime or composite. The rank and the inverse are defined through Gaussian elimination over a field and require a prime modulus. All four functions work on a copy of the input.

Determinant#

nmod_mat_det chooses the method from the dimension r:

The primality of n is decided by n_is_prime on every call. The cost for large r is that of an LU decomposition, O(r^\omega) with the exponent \omega of matrix multiplication, for a prime modulus, and O(r^3) operations and O(r^2) extended gcd computations for a composite one.

nmod_mat_det_howell reduces A to upper triangular form with row operations that never divide. To clear an entry b below a pivot a it subtracts a multiple of the pivot row if a divides b modulo n, and otherwise first replaces the pivot row by s times itself minus t times the other row, where sa - tb = \gcd(a, b) and s is chosen invertible modulo n. That operation multiplies the determinant by the unit s, which is divided out at the end. Row swaps change the sign. Despite its name, the function does not compute the Howell form.

Rank#

nmod_mat_rank returns the number of pivots found by nmod_mat_lu (without rank check) on a copy of A, which may have any shape. For a composite modulus the rank is not well defined; the function then raises a FLINT_IMPINV exception or returns a meaningless value.

Inverse#

nmod_mat_inv(B, A) solves AB = I with nmod_mat_solve, so its cost is that of an LU decomposition and two triangular solves with r right-hand sides, O(r^\omega). A 1 \times 1 matrix is inverted directly. It returns 0 if A is singular. B may be the same matrix as A.

For a composite modulus, a matrix can be invertible (its determinant is a unit) while elimination meets a pivot that is a zero divisor, for example \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} modulo 4. The function then raises a FLINT_IMPINV exception. A 1 \times 1 matrix with a nonzero, non-invertible entry also raises an exception.

Example#

The determinant of a 12 \times 12 matrix modulo a prime and modulo 10^6, which agree with the exact integer determinant 696989974644262065485477877973 reduced modulo these numbers, and an inverse and a rank modulo 11:

#include <flint/flint.h>
#include <flint/nmod_mat.h>

int main(void)
{
    nmod_mat_t A, B, I;
    slong i, j, n = 12;

    /* the same integer matrix modulo a prime and a composite number */
    ulong moduli[2] = { 1000003, 1000000 };

    for (i = 0; i < 2; i++)
    {
        nmod_mat_init(A, n, n, moduli[i]);
        /* entry j (in row-major order) is (j^2 + 3j + 1) mod 1000,
           plus 1 on the diagonal */
        for (j = 0; j < n * n; j++)
            nmod_mat_entry(A, j / n, j % n) =
                (j * j + 3 * j + 1) % 1000 + (j % (n + 1) == 0);

        flint_printf("n = %wu: det = %wu, det_howell = %wu\n", moduli[i],
                     nmod_mat_det(A), nmod_mat_det_howell(A));
        nmod_mat_clear(A);
    }

    /* inverse and rank modulo a prime */
    nmod_mat_init(A, 3, 3, 11);
    nmod_mat_init(B, 3, 3, 11);
    nmod_mat_init(I, 3, 3, 11);
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            nmod_mat_entry(A, i, j) = (i <= j) ? i + j + 1 : 0;

    flint_printf("invertible: %d\n", nmod_mat_inv(B, A));
    nmod_mat_print_pretty(B);
    nmod_mat_mul(I, A, B);
    flint_printf("A * A^-1 is one: %d\n", nmod_mat_is_one(I));

    nmod_mat_entry(A, 2, 2) = 0;
    flint_printf("rank %wd, det %wu, invertible: %d\n",
                 nmod_mat_rank(A), nmod_mat_det(A), nmod_mat_inv(B, A));

    nmod_mat_clear(A);
    nmod_mat_clear(B);
    nmod_mat_clear(I);
    return 0;
}

n = 1000003: det = 920755, det_howell = 920755
n = 1000000: det = 877973, det_howell = 877973
invertible: 1
<3 x 3 integer matrix mod 11>
[ 1  3  8]
[ 0  4 10]
[ 0  0  9]
A * A^-1 is one: 1
rank 2, det 0, invertible: 0