# RowReduce modulo 3

When I wanted to compute a row echelon form of a matrix over the finite field ${\Bbb F}_9$ with 9 elements (which is the three element field ${\Bbb F}_3$ adjoined a square root of $-1$ which I denote by "I"), I think that I encountered a contradiction:

RowReduce[{{I, -1, I, 1}, {1, 1, I, 0}, {1 + 2 I, -2 I, 2 + 2 I, 2}},  Modulus -> 3]


{{1, 0, 1 + I, 0}, {0, 1, 2, 0}, {0, 0, 1, 1}}

while

RowReduce[{{I, -1, I}, {1, 1, I}, {1 + 2 I, -2 I, 2 + 2 I}},  Modulus -> 3]


{{1, 0, 1 + I}, {0, 1, 2}, {0, 0, 0}}

It thus seems that the inhomogeneous system (three equations in three variables $x_1$, $x_2$ and $x_3$) of linear equations given by the 3x4 matrix has only solutions where $x_3 = 1$. At the same time the underlying homogeneous system of linear equations would have solutions with arbitrary third component. This is contradictory.

Any explanations?

• The second result is wrong. Looks like a bug, unless working with a Modulus is only guaranteed to work over the (real) integers and not over the Gaussian integers. – Michael E2 Feb 27 '18 at 12:42
• RowReduce mod primes only works over Z, not augmented by I. – Daniel Lichtblau Feb 27 '18 at 17:11

It appears that it is the first result that is misleading. Offhand I do not recall how the combination of complex values and a nonzero modulus are handled in the linear algebra internals. But it is not done in a way that respects the notion that I is some prime field extension element that square to 1.

This can however be recast as a Groebner basis computation (you probably knew that). Here is one way to go about it. We start with the homogeneous example. The idea is to convert the matrix rows to linear polynomials by maing each column effectively into a variable, then replace I by a new variable,and add a defining equation to make it act as a root of -1.

mat = {{I, -1, I}, {1, 1, I}, {1 + 2 I, -2 I, 2 + 2 I}};
polys = mat.{x, y, z};
polys2 = polys /. Complex[a_, b_] :> a + alpha*b

(* Out[275]= {alpha x - y + alpha z,
x + y + alpha z, (1 + 2 alpha) x - 2 alpha y + (2 + 2 alpha) z} *)


Now compute a Groebner basis over Z_3. gb = GroebnerBasis[Join[polys2, {alpha^2 + 1}], {x, y, z, alpha}, Modulus -> 3]

(* Out[276]= {1 + alpha^2, y + 2 z, x + z + alpha z} *)


We recover in effect the second row reduction result.

If we now try to treat the inhomogeneous case we have a couple of possible directions. First is the obvious one.

mat = {{I, -1, I}, {1, 1, I}, {1 + 2 I, -2 I, 2 + 2 I}};
polys = mat.{x, y, z} + {1, 0, 2};
polys2 = polys /. Complex[a_, b_] :> a + alpha*b

(* Out[279]= {1 + alpha x - y + alpha z, x + y + alpha z,
2 + (1 + 2 alpha) x - 2 alpha y + (2 + 2 alpha) z} *)

GroebnerBasis[Join[polys2, {alpha^2 + 1}], {x, y, z, alpha},
Modulus -> 3]

(* Out[280]= {1} *)


So the system is inconsistent. I remark that this happens whether I add or subtract the constant terms.

An alternative is to homogenize and see if we get something consistent.

mat = {{I, -1, I}, {1, 1, I}, {1 + 2 I, -2 I, 2 + 2 I}};
polys = mat.{x, y, z} + w*{1, 0, 2};
polys2 = polys /. Complex[a_, b_] :> a + alpha*b
GroebnerBasis[Join[polys2, {alpha^2 + 1}], {x, y, z, w, alpha},
Modulus -> 3]

(* Out[291]= {w + alpha x - y + alpha z, x + y + alpha z,
2 w + (1 + 2 alpha) x - 2 alpha y + (2 + 2 alpha) z}

Out[292]= {1 + alpha^2, w, y + 2 z, x + z + alpha z} *)


So the only solution is at GF[3^3] projective infinity, and this is consistent with what we found in the prior computation.

• Many thanks! Another possibility is to use the finite fields package: << FiniteFields` ii = GF[3, {1, 0, 1}][{0, 1}] RowReduce[{{ii, -1, ii, 1}, {1, 1, ii, 0}, {1 + 2 ii, -2 ii, 2 + 2 ii, 2}}] – Markus Schweighofer Feb 28 '18 at 14:37