Ask Your Question

Row reduction modulo prime powers

asked 2012-07-19 14:55:30 +0200

Robert Pollack gravatar image

updated 2012-07-19 15:07:23 +0200

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 flag offensive 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.

fidbc gravatar imagefidbc ( 2012-07-19 22:39:15 +0200 )edit

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

Robert Pollack gravatar imageRobert Pollack ( 2012-07-20 14:07:40 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2016-01-05 02:47:01 +0200

vdelecroix gravatar image

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
sage: v = 2*v0 + 3*v1 +7*v2
sage: v.lift() in F

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2012-07-19 14:55:30 +0200

Seen: 704 times

Last updated: Jan 05 '16