fmpz_mod_mat.h – matrices over integers mod n

Types, macros and constants

type fmpz_mod_mat_struct

type fmpz_mod_mat_t

Element access

fmpz *fmpz_mod_mat_entry(const fmpz_mod_mat_t mat, slong i, slong j)

Return a reference to the element at row i and column j of mat.

void fmpz_mod_mat_set_entry(fmpz_mod_mat_t mat, slong i, slong j, const fmpz_t val, const fmpz_mod_ctx_t ctx)

Set the entry at row i and column j of mat to val.

Memory management

void fmpz_mod_mat_init(fmpz_mod_mat_t mat, slong rows, slong cols, const fmpz_mod_ctx_t ctx)

Initialise mat as a matrix with the given number of rows and cols and modulus defined by ctx.

void fmpz_mod_mat_init_set(fmpz_mod_mat_t mat, const fmpz_mod_mat_t src, const fmpz_mod_ctx_t ctx)

Initialise mat and set it equal to the matrix src, including the number of rows and columns and the modulus.

void fmpz_mod_mat_clear(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Clear mat and release any memory it used.

Basic manipulation ——————————————————————————–

slong fmpz_mod_mat_nrows(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Return the number of rows of mat.

slong fmpz_mod_mat_ncols(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Return the number of columns of mat.

void _fmpz_mod_mat_set_mod(fmpz_mod_mat_t mat, const fmpz_t n, const fmpz_mod_ctx_t ctx)

Set the modulus of the matrix mat to n.

void fmpz_mod_mat_one(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Set mat to the identity matrix (ones down the diagonal).

void fmpz_mod_mat_zero(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Set mat to the zero matrix.

void fmpz_mod_mat_swap(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)

Efficiently swap the matrices mat1 and mat2.

void fmpz_mod_mat_swap_entrywise(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)

Swaps two matrices by swapping the individual entries rather than swapping the contents of the structs.

int fmpz_mod_mat_is_empty(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Return \(1\) if mat has either zero rows or columns.

int fmpz_mod_mat_is_square(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Return \(1\) if mat has the same number of rows and columns.

void _fmpz_mod_mat_reduce(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Reduce all the entries of mat by the modulus n. This function is only needed internally.

Random generation

void fmpz_mod_mat_randtest(fmpz_mod_mat_t mat, flint_rand_t state, const fmpz_mod_ctx_t ctx)

Generate a random matrix with the existing dimensions and entries in \([0, n)\) where n is the modulus.

Windows and concatenation

void fmpz_mod_mat_window_init(fmpz_mod_mat_t window, const fmpz_mod_mat_t mat, slong r1, slong c1, slong r2, slong c2, const fmpz_mod_ctx_t ctx)

Initializes the matrix window to be an r2 - r1 by c2 - c1 submatrix of mat whose (0, 0) entry is the (r1, c1) entry of mat. The memory for the elements of window is shared with mat.

void fmpz_mod_mat_window_clear(fmpz_mod_mat_t window, const fmpz_mod_ctx_t ctx)

Clears the matrix window and releases any memory that it uses. Note that the memory to the underlying matrix that window points to is not freed.

void fmpz_mod_mat_concat_horizontal(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat1, const fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)

Sets res to vertical concatenation of (mat1, mat2) in that order. Matrix dimensions : mat1 : \(m \times n\), mat2 : \(k \times n\), res : \((m + k) \times n\).

void fmpz_mod_mat_concat_vertical(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat1, const fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)

Sets res to horizontal concatenation of (mat1, mat2) in that order. Matrix dimensions : mat1 : \(m \times n\), mat2 : \(m \times k\), res : \(m \times (n + k)\).

Input and output

void fmpz_mod_mat_print_pretty(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Prints the given matrix to stdout. The format is an opening square bracket then on each line a row of the matrix, followed by a closing square bracket. Each row is written as an opening square bracket followed by a space separated list of coefficients followed by a closing square bracket.

Comparison

int fmpz_mod_mat_is_zero(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Return \(1\) if mat is the zero matrix.

Set and transpose

void fmpz_mod_mat_set(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)

Set B to equal A.

void fmpz_mod_mat_transpose(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)

Set B to the transpose of A.

Conversions

void fmpz_mod_mat_set_fmpz_mat(fmpz_mod_mat_t A, const fmpz_mat_t B, const fmpz_mod_ctx_t ctx)

Set A to the matrix B reducing modulo the modulus of A.

void fmpz_mod_mat_get_fmpz_mat(fmpz_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Set A to a lift of B.

Addition and subtraction

void fmpz_mod_mat_add(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Set C to \(A + B\).

void fmpz_mod_mat_sub(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Set C to \(A - B\).

void fmpz_mod_mat_neg(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)

Set B to \(-A\).

Scalar arithmetic

void fmpz_mod_mat_scalar_mul_si(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, slong c, const fmpz_mod_ctx_t ctx)

Set B to \(cA\) where c is a constant.

void fmpz_mod_mat_scalar_mul_ui(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, ulong c, const fmpz_mod_ctx_t ctx)

Set B to \(cA\) where c is a constant.

void fmpz_mod_mat_scalar_mul_fmpz(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, fmpz_t c, const fmpz_mod_ctx_t ctx)

Set B to \(cA\) where c is a constant.

Matrix multiplication

void fmpz_mod_mat_mul(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Set C to A\times B. The number of rows of B must match the number of columns of A.

void _fmpz_mod_mat_mul_classical_threaded_pool_op(fmpz_mod_mat_t D, const fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, int op, thread_pool_handle *threads, slong num_threads, const fmpz_mod_ctx_t ctx)

Set D to A\times B + op*C where op is +1, -1 or 0.

void _fmpz_mod_mat_mul_classical_threaded_op(fmpz_mod_mat_t D, const fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, int op, const fmpz_mod_ctx_t ctx)

Set D to A\times B + op*C where op is +1, -1 or 0.

void fmpz_mod_mat_mul_classical_threaded(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Set C to A\times B. The number of rows of B must match the number of columns of A.

void fmpz_mod_mat_sqr(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)

Set B to A^2. The matrix A must be square.

void fmpz_mod_mat_mul_fmpz_vec(fmpz *c, const fmpz_mod_mat_t A, const fmpz *b, slong blen, const fmpz_mod_ctx_t ctx)

void fmpz_mod_mat_mul_fmpz_vec_ptr(fmpz *const *c, const fmpz_mod_mat_t A, const fmpz *const *b, slong blen, const fmpz_mod_ctx_t ctx)

Compute a matrix-vector product of A and (b, blen) and store the result in c. The vector (b, blen) is either truncated or zero-extended to the number of columns of A. The number entries written to c is always equal to the number of rows of A.

void fmpz_mod_mat_fmpz_vec_mul(fmpz *c, const fmpz *a, slong alen, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

void fmpz_mod_mat_fmpz_vec_mul_ptr(fmpz *const *c, const fmpz *const *a, slong alen, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Compute a vector-matrix product of (a, alen) and B and and store the result in c. The vector (a, alen) is either truncated or zero-extended to the number of rows of B. The number entries written to c is always equal to the number of columns of B.

Trace

void fmpz_mod_mat_trace(fmpz_t trace, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Set trace to the trace of the matrix mat.

Gaussian elimination

void fmpz_mod_mat_det(fmpz_t res, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Set res to the determinant of the matrix mat.

slong fmpz_mod_mat_rref(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Sets res to the reduced row echelon form of mat and returns the rank.

The modulus is assumed to be prime.

Strong echelon form and Howell form

void fmpz_mod_mat_strong_echelon_form(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Transforms \(mat\) into the strong echelon form of \(mat\). The Howell form and the strong echelon form are equal up to permutation of the rows, see [FieHof2014] for a definition of the strong echelon form and the algorithm used here.

\(mat\) must have at least as many rows as columns.

slong fmpz_mod_mat_howell_form(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)

Transforms \(mat\) into the Howell form of \(mat\). For a definition of the Howell form see [StoMul1998]. The Howell form is computed by first putting \(mat\) into strong echelon form and then ordering the rows.

\(mat\) must have at least as many rows as columns.

Inverse

int fmpz_mod_mat_inv(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)

Sets \(B = A^{-1}\) and returns \(1\) if \(A\) is invertible. If \(A\) is singular, returns \(0\) and sets the elements of \(B\) to undefined values.

\(A\) and \(B\) must be square matrices with the same dimensions.

The modulus is assumed to be prime.

LU decomposition

slong fmpz_mod_mat_lu(slong *P, fmpz_mod_mat_t A, int rank_check, const fmpz_mod_ctx_t ctx)

Computes a generalised LU decomposition \(LU = PA\) of a given matrix \(A\), returning the rank of \(A\).

If \(A\) is a nonsingular square matrix, it will be overwritten with a unit diagonal lower triangular matrix \(L\) and an upper triangular matrix \(U\) (the diagonal of \(L\) will not be stored explicitly).

If \(A\) is an arbitrary matrix of rank \(r\), \(U\) will be in row echelon form having \(r\) nonzero rows, and \(L\) will be lower triangular but truncated to \(r\) columns, having implicit ones on the \(r\) first entries of the main diagonal. All other entries will be zero.

If a nonzero value for rank_check is passed, the function will abandon the output matrix in an undefined state and return 0 if \(A\) is detected to be rank-deficient.

The modulus is assumed to be prime.

Triangular solving

void fmpz_mod_mat_solve_tril(fmpz_mod_mat_t X, const fmpz_mod_mat_t L, const fmpz_mod_mat_t B, int unit, const fmpz_mod_ctx_t ctx)

Sets \(X = L^{-1} B\) where \(L\) is a full rank lower triangular square matrix. If unit = 1, \(L\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Automatically chooses between the classical and recursive algorithms.

The modulus is assumed to be prime.

void fmpz_mod_mat_solve_triu(fmpz_mod_mat_t X, const fmpz_mod_mat_t U, const fmpz_mod_mat_t B, int unit, const fmpz_mod_ctx_t ctx)

Sets \(X = U^{-1} B\) where \(U\) is a full rank upper triangular square matrix. If unit = 1, \(U\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Automatically chooses between the classical and recursive algorithms.

The modulus is assumed to be prime.

Solving

int fmpz_mod_mat_solve(fmpz_mod_mat_t X, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Solves the matrix-matrix equation \(AX = B\).

Returns \(1\) if \(A\) has full rank; otherwise returns \(0\) and sets the elements of \(X\) to undefined values.

The matrix \(A\) must be square.

The modulus is assumed to be prime.

int fmpz_mod_mat_can_solve(fmpz_mod_mat_t X, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)

Solves the matrix-matrix equation \(AX = B\) over \(Fp\).

Returns \(1\) if a solution exists; otherwise returns \(0\) and sets the elements of \(X\) to zero. If more than one solution exists, one of the valid solutions is given.

There are no restrictions on the shape of \(A\) and it may be singular.

The modulus is assumed to be prime.

Transforms

void fmpz_mod_mat_similarity(fmpz_mod_mat_t M, slong r, fmpz_t d, const fmpz_mod_ctx_t ctx)

Applies a similarity transform to the \(n\times n\) matrix \(M\) in-place.

If \(P\) is the \(n\times n\) identity matrix the zero entries of whose row \(r\) (\(0\)-indexed) have been replaced by \(d\), this transform is equivalent to \(M = P^{-1}MP\).

Similarity transforms preserve the determinant, characteristic polynomial and minimal polynomial.

The value \(d\) is required to be reduced modulo the modulus of the entries in the matrix.

The modulus is assumed to be prime.

Characteristic polynomial

void fmpz_mod_mat_charpoly(fmpz_mod_poly_t p, const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx)

Compute the characteristic polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.

Minimal polynomial

void fmpz_mod_mat_minpoly(fmpz_mod_poly_t p, const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx)

Compute the minimal polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.

The modulus is assumed to be prime.