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

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

The rref command can find the reduced row echelon form of a matrix with elements in ℤ/pℤ. (See 6.56.3):

rref takes one argument:
A, a matrix in ℤ/pℤ.
rref(A) returns the echelon form of A.

Example.
Input:

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

Output:

⎡
⎢
⎢
⎣

1%15	0%15	0%15
0%15	1%15	0%15
0%15	0%15	1%15

⎤
⎥
⎥
⎦

This can be used to solve a linear system of equations with coefficients in ℤ/pℤ by rewriting it in matrix form

A· X = B

rref can then take as argument the augmented matrix of the system (the matrix obtained by augmenting matrix A to the right with the column vector B).
rref will returns a matrix [A₁,B₁] where A₁ has 1s on its principal diagonal and zeros outside. The solutions in ℤ/pℤ of:

A₁· X = B₁

are the same as the solutions of:

A*X=B

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.