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 to set_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.

Indices and tables