Row reduction to echelon form in ℤ/pℤ : rref

5.36.17 Row reduction to echelon form in ℤ/pℤ : rref

rref finds the row reduction to echelon form of a matrix with coefficients in ℤ/pℤ.

This may be used to solve a linear system of equations with coefficients in ℤ/pℤ by rewriting it in matrix form (see also 5.61.3) :

A*X=B

rref takes as argument the augmented matrix of the system (the matrix obtained by augmenting matrix A to the right with the column vector B).
rref returns a matrix [A1,B1] : A1 has 1 on its principal diagonal, and zeros outside, and the solutions in ℤ/pℤ, of :

A1*X=B1

are the same as the solutions of:

A*X=B

Example, solve in ℤ/13ℤ

⎧
⎨
⎩

x + 2 · y	=	9
3 · x +10 · y	=	0

Input :

rref([[1, 2, 9]%13,[3,10,0]%13])

or :

rref([[1, 2, 9],[3,10,0]])%13

Output :

[[1%13,0%13,3%13],[0%13,1%13,3%13]]

hence x=3%13 and y=3%13.