ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 23 Mar 2021 20:46:11 +0100Sagemath: Closest_vector not working on mxn matrix when m!=n?https://ask.sagemath.org/question/56336/sagemath-closest_vector-not-working-on-mxn-matrix-when-mn/ I want to solve the following closest vector problem: Given an mxn matrix A where A \in Z_q^n and a vector u, find the closest vector to u in the q-ary lattice spanned by A, that is in the lattice that contains all points y=(Az mod q) for some z \in Z_q^n. Do to do this, I implemented the following sage code.
import random
from sage.modules.free_module_integer import IntegerLattice
Q = 7
B = [[1,2],[4,5],[3,6],[5,2]]
R = Integers(Q)
MS = MatrixSpace(R, 4, 2)
A= MS(B)
N = A.change_ring(ZZ)
N = N.augment(Q * identity_matrix(4)) # To enforce calculation modulo q
L = IntegerLattice(N)
u = [1,2,3,4]
print(L.closest_vector(u))
From my understanding, this should work even though m!=n, because the vectors in the lattice spanned by the Basis N are still 4-dimensional. However, I am getting the following error:
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 6 by 6 dense matrices over Rational Field' and 'Ambient free module of rank 4 over the principal ideal domain Integer Ring'
What am I doing wrong?
Tue, 23 Mar 2021 18:21:05 +0100https://ask.sagemath.org/question/56336/sagemath-closest_vector-not-working-on-mxn-matrix-when-mn/Answer by dan_fulea for <p>I want to solve the following closest vector problem: Given an mxn matrix A where A \in Z_q^n and a vector u, find the closest vector to u in the q-ary lattice spanned by A, that is in the lattice that contains all points y=(Az mod q) for some z \in Z_q^n. Do to do this, I implemented the following sage code.</p>
<pre><code>import random
from sage.modules.free_module_integer import IntegerLattice
Q = 7
B = [[1,2],[4,5],[3,6],[5,2]]
R = Integers(Q)
MS = MatrixSpace(R, 4, 2)
A= MS(B)
N = A.change_ring(ZZ)
N = N.augment(Q * identity_matrix(4)) # To enforce calculation modulo q
L = IntegerLattice(N)
u = [1,2,3,4]
print(L.closest_vector(u))
</code></pre>
<p>From my understanding, this should work even though m!=n, because the vectors in the lattice spanned by the Basis N are still 4-dimensional. However, I am getting the following error: </p>
<pre><code>TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 6 by 6 dense matrices over Rational Field' and 'Ambient free module of rank 4 over the principal ideal domain Integer Ring'
</code></pre>
<p>What am I doing wrong?</p>
https://ask.sagemath.org/question/56336/sagemath-closest_vector-not-working-on-mxn-matrix-when-mn/?answer=56340#post-id-56340In order to get the bug in some code, a good way to proceed is to reproduce the error using alternative, explicit, minimal code. This also applies for a question, written to go to the point without contorsions, and if the answer does not show after the own try to find it - which is the best way to improve the own path through structure and coding - , it will pop up in a second on this site (or elsewhere in a similar situation).
(There is no need to import the random package, there is no need to use a matrix space in between, then lift a matrix from characteristic seven, masked by `Q = 7`, then extend this matrix by seven times the identity matrix. You certainly had that matrix in your hand, so print it and use it as it is.)
I did the following to reproduce the error:
from sage.modules.free_module_integer import IntegerLattice
A = matrix(ZZ, [[1, 2], [4, 5], [3, 6], [5, 2]])
C = A.augment(7 * identity_matrix(4))
L = IntegerLattice(C)
print(L)
The print shows the following object, and shortly after the print i also wanted to see the basis, to confirm my suspicion:
Free module of degree 6 and rank 4 over Integer Ring
User basis matrix:
[1 2 7 0 0 0]
[5 2 0 0 0 7]
[4 5 0 7 0 0]
[3 6 0 0 7 0]
sage: L.basis()
[
(1, 2, 7, 0, 0, 0),
(5, 2, 0, 0, 0, 7),
(4, 5, 0, 7, 0, 0),
(3, 6, 0, 0, 7, 0)
]
So we do not have an object of vectors inside $\Bbb Z^4$, but rather inside $\Bbb Z^6$, and some vector with four components will be incompatible to this. Instead, let us try the transposed of the above $C$:
from sage.modules.free_module_integer import IntegerLattice
A = matrix(ZZ, [[1, 2], [4, 5], [3, 6], [5, 2]])
C = A.augment(7 * identity_matrix(4))
L = IntegerLattice(C.transpose())
u = [1, 2, 3, 4]
print(L.closest_vector(u))
This gives:
(1, 1, 3, 4)Tue, 23 Mar 2021 20:46:11 +0100https://ask.sagemath.org/question/56336/sagemath-closest_vector-not-working-on-mxn-matrix-when-mn/?answer=56340#post-id-56340