fmpq_mat.h – matrices over the rational numbers¶
Description.
Memory management¶
-
void
fmpq_mat_init
(fmpq_mat_t mat, slong rows, slong cols)¶ Initialises a matrix with the given number of rows and columns for use.
-
void
fmpq_mat_init_set
(fmpq_mat_t mat1, const fmpq_mat_t mat2)¶ Initialises
mat1
and sets it equal tomat2
.
-
void
fmpq_mat_clear
(fmpq_mat_t mat)¶ Frees all memory associated with the matrix. The matrix must be reinitialised if it is to be used again.
-
void
fmpq_mat_swap
(fmpq_mat_t mat1, fmpq_mat_t mat2)¶ Swaps two matrices. The dimensions of
mat1
andmat2
are allowed to be different.
Entry access¶
-
fmpq *
fmpq_mat_entry
(const fmpq_mat_t mat, slong i, slong j)¶ Gives a reference to the entry at row
i
and columnj
. The reference can be passed as an input or output variable to anyfmpq
function for direct manipulation of the matrix element. No bounds checking is performed.
-
fmpz *
fmpq_mat_entry_num
(const fmpq_mat_t mat, slong i, slong j)¶ Gives a reference to the numerator of the entry at row
i
and columnj
. The reference can be passed as an input or output variable to anyfmpz
function for direct manipulation of the matrix element. No bounds checking is performed.
-
fmpz *
fmpq_mat_entry_den
(const fmpq_mat_t mat, slong i, slong j)¶ Gives a reference to the denominator of the entry at row
i
and columnj
. The reference can be passed as an input or output variable to anyfmpz
function for direct manipulation of the matrix element. No bounds checking is performed.
-
slong
fmpq_mat_nrows
(const fmpq_mat_t mat)¶ Return the number of rows of the matrix
mat
.
-
slong
fmpq_mat_ncols
(const fmpq_mat_t mat)¶ Return the number of columns of the matrix
mat
.
Basic assignment¶
-
void
fmpq_mat_set
(fmpq_mat_t dest, const fmpq_mat_t src)¶ Sets the entries in
dest
to the same values as insrc
, assuming the two matrices have the same dimensions.
-
void
fmpq_mat_zero
(fmpq_mat_t mat)¶ Sets
mat
to the zero matrix.
-
void
fmpq_mat_one
(fmpq_mat_t mat)¶ Let \(m\) be the minimum of the number of rows and columns in the matrix
mat
. This function sets the first \(m \times m\) block to the identity matrix, and the remaining block to zero.
-
void
fmpq_mat_transpose
(fmpq_mat_t rop, const fmpq_mat_t op)¶ Sets the matrix
rop
to the transpose of the matrixop
, assuming that their dimensions are compatible.
Addition, scalar multiplication¶
-
void
fmpq_mat_add
(fmpq_mat_t mat, const fmpq_mat_t mat1, const fmpq_mat_t mat2)¶ Sets
mat
to the sum ofmat1
andmat2
, assuming that all three matrices have the same dimensions.
-
void
fmpq_mat_sub
(fmpq_mat_t mat, const fmpq_mat_t mat1, const fmpq_mat_t mat2)¶ Sets
mat
to the difference ofmat1
andmat2
, assuming that all three matrices have the same dimensions.
-
void
fmpq_mat_neg
(fmpq_mat_t rop, const fmpq_mat_t op)¶ Sets
rop
to the negative ofop
, assuming that the two matrices have the same dimensions.
-
void
fmpq_mat_scalar_mul_fmpq
(fmpq_mat_t rop, const fmpq_mat_t op, const fmpq_t x)¶ Sets
rop
toop
multiplied by the rational \(x\), assuming that the two matrices have the same dimensions.Note that the rational
x
may not be aliased with any part of the entries ofrop
.
-
void
fmpq_mat_scalar_mul_fmpz
(fmpq_mat_t rop, const fmpq_mat_t op, const fmpz_t x)¶ Sets
rop
toop
multiplied by the integer \(x\), assuming that the two matrices have the same dimensions.Note that the integer \(x\) may not be aliased with any part of the entries of
rop
.
-
void
fmpq_mat_scalar_div_fmpz
(fmpq_mat_t rop, const fmpq_mat_t op, const fmpz_t x)¶ Sets
rop
toop
divided by the integer \(x\), assuming that the two matrices have the same dimensions and that \(x\) is non-zero.Note that the integer \(x\) may not be aliased with any part of the entries of
rop
.
Input and output¶
-
void
fmpq_mat_print
(const fmpq_mat_t mat)¶ Prints the matrix
mat
to standard output.
Random matrix generation¶
-
void
fmpq_mat_randbits
(fmpq_mat_t mat, flint_rand_t state, mp_bitcnt_t bits)¶ This is equivalent to applying
fmpq_randbits
to all entries in the matrix.
-
void
fmpq_mat_randtest
(fmpq_mat_t mat, flint_rand_t state, mp_bitcnt_t bits)¶ This is equivalent to applying
fmpq_randtest
to all entries in the matrix.
Window¶
-
void
fmpq_mat_window_init
(fmpq_mat_t window, const fmpq_mat_t mat, slong r1, slong c1, slong r2, slong c2)¶ Initializes the matrix
window
to be anr2 - r1
byc2 - c1
submatrix ofmat
whose(0,0)
entry is the(r1, c1)
entry ofmat
. The memory for the elements ofwindow
is shared withmat
.
-
void
fmpq_mat_window_clear
(fmpq_mat_t window)¶ Clears the matrix
window
and releases any memory that it uses. Note that the memory to the underlying matrix thatwindow
points to is not freed.
Concatenate¶
-
void fmpq_mat_concat_vertical(fmpq_mat_t res, const fmpq_mat_t mat1, const fmpq_mat_t mat2) Sets code{res} to vertical concatenation of (code{mat1}, code{mat2}) in that order. Matrix dimensions : code{mat1} : $m times n$, code{mat2} : $k times n$, code{res} : $(m + k) times n$.
-
void fmpq_mat_concat_horizontal(fmpq_mat_t res, const fmpq_mat_t mat1, const fmpq_mat_t mat2) Sets code{res} to horizontal concatenation of (code{mat1}, code{mat2}) in that order. Matrix dimensions : code{mat1} : $m times n$, code{mat2} : $m times k$, code{res} : $m times (n + k)$.
Special matrices¶
-
void
fmpq_mat_hilbert_matrix
(fmpq_mat_t mat)¶ Sets
mat
to a Hilbert matrix of the given size. That is, the entry at row \(i\) and column \(j\) is set to \(1/(i+j+1)\).
Basic comparison and properties¶
-
int
fmpq_mat_equal
(const fmpq_mat_t mat1, const fmpq_mat_t mat2)¶ Returns nonzero if
mat1
andmat2
have the same shape and all their entries agree, and returns zero otherwise. Assumes the entries in bothmat1
andmat2
are in canonical form.
-
int
fmpq_mat_is_integral
(const fmpq_mat_t mat)¶ Returns nonzero if all entries in
mat
are integer-valued, and returns zero otherwise. Assumes that the entries inmat
are in canonical form.
-
int
fmpq_mat_is_zero
(const fmpq_mat_t mat)¶ Returns nonzero if all entries in
mat
are zero, and returns zero otherwise.
-
int
fmpq_mat_is_one
(const fmpq_mat_t mat)¶ Returns nonzero if
mat
ones along the diagonal and zeros elsewhere, and returns zero otherwise.
-
int
fmpq_mat_is_empty
(const fmpq_mat_t mat)¶ Returns a non-zero value if the number of rows or the number of columns in
mat
is zero, and otherwise returns zero.
-
int
fmpq_mat_is_square
(const fmpq_mat_t mat)¶ Returns a non-zero value if the number of rows is equal to the number of columns in
mat
, and otherwise returns zero.
Integer matrix conversion¶
-
int
fmpq_mat_get_fmpz_mat
(fmpz_mat_t dest, const fmpq_mat_t mat)¶ Sets
dest
tomat
and returns nonzero if all entries inmat
are integer-valued. If not all entries inmat
are integer-valued, setsdest
to an undefined matrix and returns zero. Assumes that the entries inmat
are in canonical form.
-
void
fmpq_mat_get_fmpz_mat_entrywise
(fmpz_mat_t num, fmpz_mat_t den, const fmpq_mat_t mat)¶ Sets the integer matrices
num
andden
respectively to the numerators and denominators of the entries inmat
.
-
void
fmpq_mat_get_fmpz_mat_matwise
(fmpz_mat_t num, fmpz_t den, const fmpq_mat_t mat)¶ Converts all entries in
mat
to a common denominator, storing the rescaled numerators innum
and the denominator inden
. The denominator will be minimal if the entries inmat
are in canonical form.
-
void
fmpq_mat_get_fmpz_mat_rowwise
(fmpz_mat_t num, fmpz * den, const fmpq_mat_t mat)¶ Clears denominators in
mat
row by row. The rescaled numerators are written tonum
, and the denominator of rowi
is written to positioni
inden
which can be a preinitialisedfmpz
vector. Alternatively,NULL
can be passed as theden
variable, in which case the denominators will not be stored.
-
void
fmpq_mat_get_fmpz_mat_rowwise_2
(fmpz_mat_t num, fmpz_mat_t num2, fmpz * den, const fmpq_mat_t mat, const fmpq_mat_t mat2)¶ Clears denominators row by row of both
mat
andmat2
, writing the respective numerators tonum
andnum2
. This is equivalent to concatenatingmat
andmat2
horizontally, callingfmpq_mat_get_fmpz_mat_rowwise
, and extracting the two submatrices in the result.
-
void
fmpq_mat_get_fmpz_mat_colwise
(fmpz_mat_t num, fmpz * den, const fmpq_mat_t mat)¶ Clears denominators in
mat
column by column. The rescaled numerators are written tonum
, and the denominator of columni
is written to positioni
inden
which can be a preinitialisedfmpz
vector. Alternatively,NULL
can be passed as theden
variable, in which case the denominators will not be stored.
-
void
fmpq_mat_set_fmpz_mat
(fmpq_mat_t dest, const fmpz_mat_t src)¶ Sets
dest
tosrc
.
-
void
fmpq_mat_set_fmpz_mat_div_fmpz
(fmpq_mat_t mat, const fmpz_mat_t num, const fmpz_t den)¶ Sets
mat
to the integer matrixnum
divided by the common denominatorden
.
Modular reduction and rational reconstruction¶
-
void
fmpq_mat_get_fmpz_mat_mod_fmpz
(fmpz_mat_t dest, const fmpq_mat_t mat, const fmpz_t mod)¶ Sets each entry in
dest
to the corresponding entry inmat
, reduced modulomod
.
-
int
fmpq_mat_set_fmpz_mat_mod_fmpz
(fmpq_mat_t X, const fmpz_mat_t Xmod, const fmpz_t mod)¶ Set
X
to the entrywise rational reconstruction integer matrixXmod
modulomod
, and returns nonzero if the reconstruction is successful. If rational reconstruction fails for any element, returns zero and sets the entries inX
to undefined values.
Matrix multiplication¶
-
void
fmpq_mat_mul_direct
(fmpq_mat_t C, const fmpq_mat_t A, const fmpq_mat_t B)¶ Sets
C
to the matrix productAB
, computed naively using rational arithmetic. This is typically very slow and should only be used in circumstances where clearing denominators would consume too much memory.
-
void
fmpq_mat_mul_cleared
(fmpq_mat_t C, const fmpq_mat_t A, const fmpq_mat_t B)¶ Sets
C
to the matrix productAB
, computed by clearing denominators and multiplying over the integers.
-
void
fmpq_mat_mul
(fmpq_mat_t C, const fmpq_mat_t A, const fmpq_mat_t B)¶ Sets
C
to the matrix productAB
. This simply callsfmpq_mat_mul_cleared
.
-
void
fmpq_mat_mul_fmpz_mat
(fmpq_mat_t C, const fmpq_mat_t A, const fmpz_mat_t B)¶ Sets
C
to the matrix productAB
, withB
an integer matrix. This function works efficiently by clearing denominators ofA
.
-
void
fmpq_mat_mul_r_fmpz_mat
(fmpq_mat_t C, const fmpz_mat_t A, const fmpq_mat_t B)¶ Sets
C
to the matrix productAB
, withA
an integer matrix. This function works efficiently by clearing denominators ofB
.
Kronecker product¶
-
void
fmpq_mat_kronecker_product
(fmpq_mat_t C, const fmpq_mat_t A, const fmpq_mat_t B)¶ Sets
C
to the Kronecker product ofA
andB
.
Trace¶
-
void
fmpq_mat_trace
(fmpq_t trace, const fmpq_mat_t mat)¶ Computes the trace of the matrix, i.e. the sum of the entries on the main diagonal. The matrix is required to be square.
Determinant¶
-
void
fmpq_mat_det
(fmpq_t det, const fmpq_mat_t mat)¶ Sets
det
to the determinant ofmat
. In the general case, the determinant is computed by clearing denominators and computing a determinant over the integers. Matrices of size 0, 1 or 2 are handled directly.
Nonsingular solving¶
-
int
fmpq_mat_solve_fraction_free
(fmpq_mat_t X, const fmpq_mat_t A, const fmpq_mat_t B)¶ Solves
AX = B
for nonsingularA
by clearing denominators and solving the rescaled system over the integers using a fraction-free algorithm. This is usually the fastest algorithm for small systems. Returns nonzero ifX
is nonsingular or if the right hand side is empty, and zero otherwise.
-
int
fmpq_mat_solve_dixon
(fmpq_mat_t X, const fmpq_mat_t A, const fmpq_mat_t B)¶ Solves
AX = B
for nonsingularA
by clearing denominators and solving the rescaled system over the integers using Dixon’s algorithm. The rational solution matrix is generated using rational reconstruction. This is usually the fastest algorithm for large systems. Returns nonzero ifX
is nonsingular or if the right hand side is empty, and zero otherwise.
-
int
fmpq_mat_solve_fmpz_mat
(fmpq_mat_t X, const fmpz_mat_t A, const fmpz_mat_t B)¶ Solves
AX = B
for integer matricesA
andB
withA
nonsingular by choosing betweenfmpz_mat_solve
andfmpz_mat_solve_dixon
and restoring the solutionX
from the output of these functions. Returns nonzero ifX
is nonsingular or if the right hand side is empty, and zero otherwise.
Inverse¶
-
int
fmpq_mat_inv
(fmpq_mat_t B, const fmpq_mat_t A)¶ Sets
B
to the inverse matrix ofA
and returns nonzero. Returns zero ifA
is singular.A
must be a square matrix.
Echelon form¶
-
int
fmpq_mat_pivot
(slong * perm, fmpq_mat_t mat, slong r, slong c)¶ Helper function for row reduction. Returns 1 if the entry of
mat
at row \(r\) and column \(c\) is nonzero. Otherwise searches for a nonzero entry in the same column among rows \(r+1, r+2, \ldots\). If a nonzero entry is found at row \(s\), swaps rows \(r\) and \(s\) and the corresponding entries inperm
(unlessNULL
) and returns -1. If no nonzero pivot entry is found, leaves the inputs unchanged and returns 0.
-
slong
fmpq_mat_rref_classical
(fmpq_mat_t B, const fmpq_mat_t A)¶ Sets
B
to the reduced row echelon form ofA
and returns the rank. Performs Gauss-Jordan elimination directly over the rational numbers. This algorithm is usually inefficient and is mainly intended to be used for testing purposes.
-
slong
fmpq_mat_rref_fraction_free
(fmpq_mat_t B, const fmpq_mat_t A)¶ Sets
B
to the reduced row echelon form ofA
and returns the rank. Clears denominators and performs fraction-free Gauss-Jordan elimination usingfmpz_mat
functions.
-
slong
fmpq_mat_rref
(fmpq_mat_t B, const fmpq_mat_t A)¶ Sets
B
to the reduced row echelon form ofA
and returns the rank. This function automatically chooses between the classical and fraction-free algorithms depending on the size of the matrix.
Gram-Schmidt Orthogonalisation¶
-
void
fmpq_mat_gso
(fmpq_mat_t B, const fmpq_mat_t A)¶ Takes a subset of \(\mathbb{Q}^m\) \(S = \{a_1, a_2, \ldots ,a_n\}\) (as the columns of a \(m \times n\) matrix
A
) and generates an orthogonal set \(S' = \{b_1, b_2, \ldots ,b_n\}\) (as the columns of the \(m \times n\) matrixB
) that spans the same subspace of \(\mathbb{Q}^m\) as \(S\).
Transforms¶
-
void
fmpq_mat_similarity
(fmpq_mat_t A, slong r, fmpq_t d)¶ 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.
Characteristic polynomial¶
-
void
_fmpq_mat_charpoly
(fmpz * coeffs, fmpz_t den, const fmpq_mat_t mat)¶ Set
(coeffs, den)
to the characteristic polynomial of the given \(n\times n\) matrix.
-
void
fmpq_mat_charpoly
(fmpq_poly_t pol, const fmpq_mat_t mat)¶ Set
pol
to the characteristic polynomial of the given \(n\times n\) matrix. Ifmat
is not square, an exception is raised.
Minimal polynomial¶
-
slong
_fmpq_mat_minpoly
(fmpz * coeffs, fmpz_t den, const fmpq_mat_t mat)¶ Set
(coeffs, den)
to the minimal polynomial of the given \(n\times n\) matrix and return the length of the polynomial.
-
void fmpq_mat_minpoly(fmpq_poly_t pol, const fmpq_mat_t mat);
Set
pol
to the minimal polynomial of the given \(n\times n\) matrix. Ifmat
is not square, an exception is raised.