11.8.17 Row reduction to echelon form in ℤ/pℤ
The rref command finds the reduced
row echelon form of a matrix with elements in ℤ/pℤ (see 15.7.3).
-
rref takes
A, a matrix in ℤ/pℤ.
- rref(A) returns the echelon form of A.
Example
rref([[0,2,9]%15,[1,10,1]%15,[2,3,4]%15]) |
|
| ⎡
⎢
⎢
⎣ | 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
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 returns a matrix [A1,B1] where A1 has
ones on its principal diagonal and zeros outside. The
solutions in ℤ/pℤ of:
are the same as the solutions of (1).
Example
Solve in ℤ/13ℤ:
rref([[1,2,9]%13,[3,10,0]%13]) |
or:
rref([[1,2,9],[3,10,0]])%13 |
|
| ⎡
⎢
⎣ | 1%13 | 0%13 | 3%13 |
0%13 | 1%13 | 3%13
|
| ⎤
⎥
⎦ |
|
| | | | | | | | | | |
|
hence x=3%13 and y=3%13.