fmpz_mod_mat.h

Return a pointer to the entry in row i and column j, respectively to the first entry of row i (the entries of a row are contiguous). Indices are 0-based and not checked.

Copy val into the entry in row i and column j (without reduction: val must be canonical), respectively copy that entry to x.

Initialises mat as a rows by cols zero matrix.

Initialises mat as a copy of src, with the same dimensions.

Frees the memory used by mat.

Return the number of rows and of columns of mat.

Return 1 if mat has zero rows or zero columns, respectively as many rows as columns, and 0 otherwise.

Set mat to the zero matrix, respectively to the matrix with ones on the main diagonal and zeros elsewhere (the zero matrix if n = 1). mat need not be square.

Sets B to a copy of A, which must have the same dimensions.

Swap two matrices. fmpz_mod_mat_swap swaps the structures in constant time; fmpz_mod_mat_swap_entrywise swaps the entries one by one, which also works for windows, and requires equal dimensions.

Sets B to the transpose of A. Aliasing is allowed for square matrices.

Sets A to the integer matrix B with every entry reduced modulo n. B may have any entries and the same dimensions as A. Large matrices are reduced in parallel.

Sets A to the integer matrix with the entries of B (in [0, n)).

Sets A to the matrix with the entries of B, read as unsigned integers. No reduction is done, so the modulus of B should be at most n (normally they are equal).

Reduces every entry of mat modulo n, in place; the entries may be any integers.

Sets the entries of mat to uniformly random residues in [0, n).

Sets the entries to uniformly random nonzero residues in [1, n) (to zero if n = 1).

Sets mat to a random matrix for testing: fmpz_mat_randtest with the bit size of n (which favours special values and produces sparse matrices with probability 1/2), reduced modulo n.

Sets mat to a random sparse matrix of the given rank: rank random nonzero residues placed in distinct rows and columns, the other entries zero. For prime n the rank is exactly rank. Throws an exception if rank is negative or exceeds a dimension. fmpz_mod_mat_randops turns the result into a dense matrix of the same rank.

Set mat to a random lower, respectively upper, triangular matrix with uniformly random entries below (above) the diagonal and nonzero diagonal entries, which are 1 if unit is nonzero.

Applies up to count random elementary operations (additions and subtractions of distinct rows or columns, fmpz_mat_randops) to mat and reduces the result. The rank and the determinant are unchanged.

fmpz_mod_mat_window_init initialises window as the (r_2 - r_1) \times (c_2 - c_1) submatrix of mat with top left entry in row r_1 and column c_1, sharing its entries with mat. fmpz_mod_mat_window_clear releases the window without freeing the entries.

Set res to (\mathit{mat1} \; \mathit{mat2}), the m \times (k + l) matrix with mat1 (m \times k) on the left and mat2 (m \times l) on the right, respectively to the (m + k) \times l matrix with mat1 (m \times l) above mat2 (k \times l).

Print mat to file or to stdout in the format of fmpz_mat_fprint: the numbers of rows and columns, two spaces, and the entries in row-major order separated by spaces. Return a positive value on success and a nonpositive value if a write failed.

Print mat to file or to stdout in the format of fmpz_mat_fprint_pretty: rows in square brackets, one per line, inside an outer pair of brackets.

Returns 1 if the matrices have the same dimensions and entries, and 0 otherwise.

Return 1 if mat is the zero matrix, respectively has ones on the main diagonal and zeros elsewhere (always true for n = 1), and 0 otherwise.

Set C = A + B, C = A - B and B = -A, row by row with the fmpz_mod_vec functions.

Set B = cA for any integer c. The products are computed exactly and reduced.

Set C = AB, respectively B = A^2 for square A. The number of columns of A must equal the number of rows of B.

Sets C = AB with the classical algorithm: each entry is an exact dot product (_fmpz_vec_dot on a transposed copy of B) reduced once. Blocks of entries are distributed over the available threads when all dimensions are at least 10. fmpz_mod_mat_mul does not call this function.

Sets D = AB + \mathit{op} \cdot C for \mathit{op} \in \{-1, 0, 1\} (C is not read for \mathit{op} = 0), with the classical algorithm on the calling thread and the num_threads threads of the pool given by threads. All dimensions must be positive.

Sets D = C - AB, using fmpz_mod_mat_mul and a temporary matrix.

Sets B = A^e for a square matrix A, with A^0 the identity. A wrapper of gr_mat_pow_ui (binary exponentiation). Aliasing is allowed.

Set the column vector c, of length the number of rows of A, to Ab modulo n, where b is truncated or zero-extended to the number of columns of A. The ptr variant takes arrays of pointers to the entries. b may contain any integers; c must not overlap b. The products are computed exactly with fmpz_mat_mul_fmpz_vec and reduced.

Set the row vector c, of length the number of columns of B, to aB modulo n, where a is truncated or zero-extended to the number of rows of B. As above, a may contain any integers and c must not overlap a.

Sets trace to the sum of the diagonal entries of the square matrix mat, modulo n.

Swap rows (columns) r and s of mat and, if perm is not NULL, entries r and s of the permutation array perm.

Reverse the order of the rows (columns) of mat and, if perm is not NULL, of the entries of perm.

Computes a generalised LU decomposition PA = LU of A in place and returns the rank of A. P must have room for as many entries as A has rows; it receives the row permutation. A wrapper of gr_mat_lu.

Set X = L^{-1} B, respectively X = U^{-1} B, for a square lower (upper) triangular matrix whose diagonal entries are invertible; if unit is nonzero, the diagonal is taken to be 1 and not read. Only the lower (upper) triangle is read. X may alias B. Wrappers of gr_mat_nonsingular_solve_tril and gr_mat_nonsingular_solve_triu, which choose between substitution and a block recursive algorithm; they throw an exception if a diagonal entry is not invertible.

Solves AX = B for a square matrix A. Returns 1 if A is nonsingular; otherwise returns 0 and leaves X undefined. A wrapper of gr_mat_nonsingular_solve_lu.

Solves AX = B for a matrix A of any shape and rank. Returns 1 and sets X to one solution if a solution exists; otherwise returns 0 and leaves X undefined. A wrapper of gr_mat_solve_field.

Sets B = A^{-1} and returns 1 if the square matrix A is invertible; otherwise returns 0 and leaves B undefined. A and B must have the same dimensions. The inverse is computed by solving AB = I with fmpz_mod_mat_solve; a 1 \times 1 matrix is inverted with fmpz_mod_inv, which throws an exception for a nonzero non-unit.

Returns the rank of A, computed by LU decomposition (gr_mat_rank_lu).

Sets res to the reduced row echelon form of mat, which has the same dimensions, and returns the rank. A wrapper of gr_mat_rref_lu.

Computes a basis of the right nullspace \{x : Ax = 0\} of A and returns its dimension (the nullity) k. The basis vectors are written to the first k columns of X, and all other entries of X are set to zero. X is not resized: it must have as many rows as A has columns and at least k columns (allocate it square, with the number of columns of A, when k is not known).

Sets res to the determinant of the square matrix mat, and throws an exception if mat is not square. A wrapper of gr_mat_det; this works for every modulus, since a failed LU decomposition falls back to a division-free algorithm.

Reduces row m of A against the earlier rows, with the conventions of gr_mat_reduce_row: P[i] is the row with its pivot in column i, or -1; L[i] bounds the nonzero columns of row i. Sets *column to the pivot column of the reduced row (made monic and recorded in P), or to -1 if the row becomes zero. Returns GR_SUCCESS, or GR_DOMAIN if the new pivot is not invertible. The sums are accumulated exactly and each entry is reduced once, when it is reached.

Transforms mat into its strong echelon form [FieHof2014], which equals the Howell form up to the order of the rows. mat must have at least as many rows as columns.

Transforms mat into its Howell form [How1986; StoMul1998] and returns the number of nonzero rows. mat must have at least as many rows as columns. Two matrices generate the same submodule of (\mathbb{Z}/n\mathbb{Z})^c if and only if their Howell forms are equal.

Applies a similarity transform to the square matrix A in place: with P the identity matrix whose row r (0-indexed) has its zero entries replaced by d, sets A = P^{-1} A P. d must be canonical. A wrapper of gr_mat_apply_row_similarity; it uses no divisions and works for every modulus. Similarity transforms preserve the determinant and the characteristic and minimal polynomials.

Set p to the characteristic polynomial \det(xI - M) of the square matrix M; the underscore version writes its m + 1 coefficients for an m \times m matrix. fmpz_mod_mat_charpoly throws an exception if M is not square. These work for every modulus: the generic fmpz_mod ring uses Danilevsky's algorithm for m \ge 16 and falls back to the division-free Berkowitz algorithm when it fails, and uses Berkowitz for smaller m.

Sets p to the minimal polynomial of the square matrix M, using gr_mat_minpoly_field. Throws an exception if M is not square. The modulus must be prime; the ring is declared a field without checking.