# Row reduction modulo prime powers

Has any kind of row reduction been implemented modulo prime powers? Right now I'm simply trying to write a particular element of (Z/9Z)^d as a linear combination of a handful of other elements in this space. (I happen to know for other reasons that the original element is in the span of these handful of elements.)

I tried to do this by working with matrices over pAdicField(3,2), but this didn't work. (I guess some division by 3 messes things up.)

Is there anyway to do this without writing my own row reduction code??

edit retag close merge delete

Have you tried working with matrices over GF(9,'a')? I believe you can get the row space of such matrices ( A.row_space() ) and also the reduced row echelon form ( A.rref() ) of a matrix A.

But I want to be working in Z/9Z -- not over a finite field! I really want characteristic 9 not 3.

Sort by » oldest newest most voted

Yes and no.

Row reduction in (Z/9Z)^d corresponds to Hermite normal form of integer lattices. More precisely, (Z/9Z)^d corresponds to the quotient of Z^d by (9Z)^d and submodules are just the quotient by lattices in between. In practice let me consider the three following vectors

sage: V = FreeModule(Zmod(9), 4)
sage: v0 = V((1,2,3,4)); v1 = V((1,0,2,0)); v2 = V((3,3,0,3))


Then what you can do is to lift everything to Z^d

sage: m = matrix(ZZ, 7, 4)
sage: m.set_row(0, v0)
sage: m.set_row(1, v1)
sage: m.set_row(2, v2)
sage: m.set_row(3, (9,0,0,0))
sage: m.set_row(4, (0,9,0,0))
sage: m.set_row(5, (0,0,9,0))
sage: m.set_row(6, (0,0,0,9))
sage: print m[1 2 3 4]
[1 0 2 0]
[3 3 0 3]
[9 0 0 0]
[0 9 0 0]
[0 0 9 0]
[0 0 0 9]


Now a vector in (Z/9Z)^4 belongs to the (Z/9Z)-span of v0,v1,v2 if and only if any of its lift belong to the row space of m. And you can do it as follows

sage: F = m.row_space()
sage: v = V((2,0,2,0))
sage: v.lift() in F
False
sage: v = 2*v0 + 3*v1 +7*v2
sage: v.lift() in F
True


I aimed to made this available within Sage with ticket #6452 but currently it lacks reviewer...

more