ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 04 Jan 2016 19:47:01 -0600Row reduction modulo prime powershttps://ask.sagemath.org/question/9163/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??Thu, 19 Jul 2012 07:55:30 -0500https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/Comment by fidbc for <p>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.)</p>
<p>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.)</p>
<p>Is there anyway to do this without writing my own row reduction code??</p>
https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?comment=19380#post-id-19380Have 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.Thu, 19 Jul 2012 15:39:15 -0500https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?comment=19380#post-id-19380Comment by Robert Pollack for <p>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.)</p>
<p>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.)</p>
<p>Is there anyway to do this without writing my own row reduction code??</p>
https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?comment=19377#post-id-19377But I want to be working in Z/9Z -- not over a finite field! I really want characteristic 9 not 3. Fri, 20 Jul 2012 07:07:40 -0500https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?comment=19377#post-id-19377Answer by vdelecroix for <p>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.)</p>
<p>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.)</p>
<p>Is there anyway to do this without writing my own row reduction code??</p>
https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?answer=32069#post-id-32069Yes and no.
Row reduction in (Z/9Z)^d corresponds to [Hermite normal form](https://en.wikipedia.org/wiki/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](http://trac.sagemath.org/ticket/6452) but currently it lacks reviewer...Mon, 04 Jan 2016 19:47:01 -0600https://ask.sagemath.org/question/9163/row-reduction-modulo-prime-powers/?answer=32069#post-id-32069