matrixzq¶
Functions to carry out operations on matrices over Zq (Z/qZ) where q is a positive integer greater than 1.
All matrix elements are expected to be nonnegative integers in the range [0, q-1]. All computations are carried out modulo q.
A Matrix of n rows and m columns is stored as an n x m list of lists.
A Vector type is stored as an n x 1 column matrix and can be used in any Matrix function.
There are some specific Vector functions which, for convenience, make their underlying
n x 1 matrix look like a simple vector of length n, for example print_vector()
.
The modulus q is stored as a global variable __Q
. It must be set using the
set_modulus()
function before calling functions that set or carry out
arithmetic operations (add, multiply, etc.) on the matrix elements.
If the modulus q is not a prime then the result of any operation that involves division (invert, solve) is undefined.
- matrixzq.add(M, N)¶
Adds matrices M and N.
- Parameters:
M – first matrix to be added to
N – second matrix to be added, must be the same size as M
- Returns:
Sum of M and N.
- Raises:
ValueError – If matrices are not the same size
- matrixzq.augment_matrix(A, B)¶
Create an augmented matrix [A | B].
- Parameters:
A – First matrix
B – Second matrix, must have the same number of rows as A
- Returns:
The augmented matrix
[A | B]
.- Raises:
ValueError – if number of rows are not equal.
Example
>>> set_modulus(11) >>> M = new_matrix([[2,3,7],[4,5,10],[9,0,7]]) >>> N = new_matrix([[7,8,9,10],[1,2,3,4],[2,3,4,5]]) >>> MN = augment_matrix(M, N) >>> print("[M|N]="); print_matrix(MN) [M|N]= [2, 3, 7, 7, 8, 9, 10] [4, 5, 10, 1, 2, 3, 4] [9, 0, 7, 2, 3, 4, 5]
- matrixzq.copy(M)¶
Creates and returns a copy of a matrix.
- Parameters:
M – Input matrix to be copied
- Returns:
Copy of matrix.
- matrixzq.determinant(A, total=0)¶
Compute determinant of matrix.
- Parameters:
A – Input matrix
total (int) – Optional previous total to be added to output.
- Returns:
(int) Determinant of matrix modulo q (plus any existing total).
- matrixzq.dotproduct(a, b)¶
Compute dot product of two vectors.
- Parameters:
a – first vector
b – second vector of same length as first
- Returns:
(int) A scalar equal to a dot b modulo q.
- matrixzq.equality(A, B)¶
Returns True if matrices are equal.
- Parameters:
A – First matrix
B – Second matrix
- Returns:
True if matrices are equal, otherwise False.
- matrixzq.get_element(M, row, col)¶
Get element at (row,col) in matrix M.
- Parameters:
M – Input matrix
row (int) – Index of row (zero-based)
col (int) – Index of column (zero-based)
- Returns:
(int) Value of element at (row,col).
- Raises:
IndexError – If (row,col) is out of range.
- matrixzq.get_modulus()¶
Return the global modulus value
q
value set by a previous call toset_modulus()
.
- matrixzq.identity_matrix(n)¶
Create and return an identity matrix.
- Parameters:
n (int) – the square size of the matrix
- Returns:
A square identity matrix.
- matrixzq.invert(A)¶
Invert a matrix.
- Parameters:
A – Input matrix, must be square and non-singular
- Returns:
Inverted matrix.
Note
The modulus
q
must be a prime.
- matrixzq.matrix_size(M)¶
Return size (rows, cols) of matrix M.
- matrixzq.multiply(A, B)¶
Compute the product of the matrices A and B.
- Parameters:
A – First matrix of size n x m
B – Second matrix, must have m rows
- Returns:
Matrix product A * B.
- Raises:
ValueError – if number of columns in A is not equal to number of rows in B
- matrixzq.new_matrix(M)¶
Create a new matrix given a list of lists.
- Parameters:
M – list of lists.
- Returns:
New matrix.
Example
>>> set_modulus(11) >>> NM = new_matrix([[0,1,2,3],[4,5,6,8],[7,8,9,10]]) >>> print_matrix(NM) [0, 1, 2, 3] [4, 5, 6, 8] [7, 8, 9, 10] >>> print("matrix_size =", matrix_size(NM)) matrix_size = (3, 4)
- matrixzq.new_vector(v)¶
Create a new vector.
A Vector is stored as an
n x 1
column matrix and can be used as a Matrix in all matrix computations.- Parameters:
v (
list
) – A single list[v1,v2,...,vn]
- Returns:
The vector as an
n x 1
matrix.
Example
>>> v = new_vector([1,2,3,4,5]) >>> print("Vector v:"); print_vector(v) Vector v: [1, 2, 3, 4, 5] >>> print("Vector as Matrix:"); print_matrix(v) Vector as Matrix: [1] [2] [3] [4] [5]
- matrixzq.print_matrix(M)¶
Print a matrix.
- Parameters:
M – Matrix to be printed.
- matrixzq.print_matrix_latex(M, delim='b')¶
Print matrix in LaTeX markup.
Copy and paste the output into your LaTeX document which uses the amsmath package:
\usepackage{amsmath} % ... \[ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \]
- Parameters:
M – Matrix to be printed.
delim – delimiter in [‘’, ‘p’, ‘b’, ‘B’, ‘v’, ‘V’]; default ‘b’ for “bmatrix”
Examples
>>> M = new_matrix([[1,2,3],[4,5,6]]) >>> print_matrix_latex(M) \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} >>> print_matrix_latex(M, delim='') \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}
- matrixzq.print_vector(v)¶
Print a vector.
- Parameters:
v – Vector to be printed.
- matrixzq.random_element()¶
Return a random element in the range
[0, q-1]
.
- matrixzq.round2int(x)¶
Compute x rounded to the nearest integer with ties being rounded up.
- Parameters:
x (float) – Real value to be rounded
- Returns:
(int) Rounded integer value (not modulo q)
Examples
>>> round2int(42.4999) 42 >>> round2int(42.5) 43
- matrixzq.roundfrac2int(a: int, b: int) int ¶
Compute rational number
a/b
rounded to the nearest integer with ties being rounded up.Avoids using floating point arithmetic.
- Parameters:
a (int) – Numerator of fraction
b (int) – Denominator of fraction
- Returns:
(int) Rounded integer value (not modulo q)
Examples
>>> roundfrac2int(424999, 10000) 42 >>> roundfrac2int(425, 10) 43
- matrixzq.row_addition(M, x, y, k)¶
Elementary row operation: Add a multiple k of row y to row x.
R_x --> R_x + k * R_y
- Parameters:
M – Input matrix
x (int) – Index of row to be added to (zero-based)
y (int) – Index of row to be added
k (int) – factor
- Returns:
New matrix.
- matrixzq.row_scale(M, i, k)¶
Elementary row operation: Scale row i by a multiple of itself.
Ri --> k * Ri
- Parameters:
M – Input matrix
i (int) – index of row to be scaled (zero-based)
k (int) – scalar value
- Returns:
Matrix with row scaled.
- matrixzq.row_swap(M, x, y)¶
Elementary row operation: Interchange (swap) rows x and y in matrix M.
R_x <--> R_y
- Parameters:
M – Input matrix
x (int) – Index of first row to be swapped (zero-based)
y (int) – Index of second row
- Returns:
Matrix with rows swapped.
- matrixzq.rref(M)¶
Compute the reduced row echelon form (RREF) of a matrix.
- Parameters:
M – Input matrix
- Returns:
Matrix in RREF (Row canonical form).
- matrixzq.scalar_mult(M, k)¶
Multiply matrix M by scalar.
- Parameters:
M – Input matrix
k (int) – scalar value, may be negative, e.g. -1
- Returns:
Matrix multiplied by scalar
k[M]
(modulo q).
Examples
>>> set_modulus(7) >> M = new_matrix([[1,2,3],[4,5,6]]) >>> print("M:"); print_matrix(M) M: [1, 2, 3] [4, 5, 6] >>> k = 3 >>> kM = scalar_mult(M, k) >>> print(f"kM (k={k}):"); print_matrix(kM) kM (k=3): [3, 6, 2] [5, 1, 4] >>> minusM = scalar_mult(M, -1) >>> print("-M:"); print_matrix(minusM) -M: [6, 5, 4] [3, 2, 1]
- matrixzq.set_element(M, row, col, value)¶
Set element (row,col) in matrix M.
- Parameters:
M – Input matrix
row (int) – Index of row (zero-based)
col (int) – Index of column (zero-based)
value (int) – Value to replace existing item
- Returns:
New matrix with element at (row,col) changed.
- Raises:
IndexError – If (row,col) is out of range.
- matrixzq.set_modulus(q)¶
Set the global modulus value
q
.- Parameters:
q (int) – modulus value, an integer greater than one
- Returns:
Modulus value as set.
- Return type:
int
- matrixzq.set_vector_elem(v, pos, value)¶
Set element in a vector.
- Parameters:
v – vector to be changed
pos (int) – position of element (starts at zero)
value (int) – Value to replace existing item
- Returns:
New vector with element changed.
- Raises:
IndexError – If pos is out of range.
- matrixzq.slice_matrix(M, startcol, numcols=0)¶
Slice matrix vertically (opposite of
augment_matrix()
).- Parameters:
M – Input matrix to be split of size n x m
startcol (int) – Start column to slice (zero-based); if negative count backwards from end
numcols (int) – Number of columns to copy (default to end of row)
- Returns:
Matrix slice of size
n x numcols
.
Examples
>>> print("[M|N]="); print_matrix(MN) [M|N]= [2, 3, 7, 7, 8, 9, 10] [4, 5, 10, 1, 2, 3, 4] [9, 0, 7, 2, 3, 4, 5] >>> MS = slice_matrix(MN, 3) >>> print("matrix_slice(3)="); print_matrix(MS) matrix_slice(3)= [7, 8, 9, 10] [1, 2, 3, 4] [2, 3, 4, 5] >>> MS = slice_matrix(MN, -1) >>> print("matrix_slice(-1)="); print_matrix(MS) matrix_slice(-1)= [10] [4] [5] >>> MS = slice_matrix(MN, -6, 3) >>> print("matrix_slice(-6, 3)="); print_matrix(MS) matrix_slice(-6, 3)= [3, 7, 7] [5, 10, 1] [0, 7, 2]
- matrixzq.solve(A, b)¶
Solve the matrix equation
Ax = b
.- Parameters:
A – Input matrix, n x n square, non-singular
b – Vector of length n
- Returns:
Vector solution for
x
of length n.
Note
The modulus
q
must be a prime.
- matrixzq.sprint_matrix(M)¶
Format a matrix as a string.
Like
print_matrix()
but returns a string instead of printing.- Parameters:
M – Input Matrix.
- Returns:
Matrix formatted as a string.
- matrixzq.sprint_vector(v)¶
Format a vector as a string.
Like
print_vector()
but returns a string instead of printing.- Parameters:
v – Input vector.
- Returns:
Vector formatted as a string.
Example
>>> r = new_vector([0, 1, 0, 1, 1, 0, 0]) >>> print("r =", sprint_vector(r)) r = [0, 1, 0, 1, 1, 0, 0]
- matrixzq.trace(A)¶
Compute the trace of a matrix.
- Parameters:
A – Input matrix; must be square
- Returns:
Scalar value of trace (=sum of diagonals modulo q)
- matrixzq.transpose(M)¶
Returns the transpose of a matrix.
- Parameters:
M – Matrix to be transposed
- Returns:
Transpose of given matrix.
- matrixzq.vector_concat(u, v)¶
Concatenate vectors u and v.
- Parameters:
u – First vector
(u1,...,uM)
v – Second vector
(v1,...,vN)
- Returns:
Concatenation of vectors u and v
(u1,...,uM,v1,...vN)
- matrixzq.zeros_matrix(rows, cols)¶
Creates a matrix filled with zeros.
- Parameters:
rows (int) – Number of rows required in the matrix
cols (int) – Number of columns required in the matrix
- Returns:
New all-zero matrix of size
rows x cols
.
- matrixzq.zeros_vector(n)¶
Create an all-zeros vector.
- Parameters:
n (int) – Required length of vector.
- Returns:
Vector as an all-zeros
n x 1
matrix.