How to find Kernel of a Matrix in $\mathbb{Z}/n$
When I tried to find it directly using
A.kernel()
it said
Cannot compute a matrix kernel over Ring of integers modulo 11053185041
2 Answers
The integer n = 11053185041 that you are working with is not prime.
Therefore, Z/n is not a field, and (Z/n)^d is not a vector space.
Matrices of size d by d over Z/n act on (Z/n)^d, but the kernel method is not implemented in Sage for such matrices.
The reason is that the kernel might not have a simple structure (a subspace of a vector space) in this case.
In Sage, check if n is prime:
sage: n = 11053185041
sage: n.is_prime()
False
Define a matrix A like yours.
sage: Zn = Zmod(n)
sage: M = MatrixSpace(Zn, 3)
sage: A = M.random_element()
sage: A
[5536663376 7738465479 1500190241]
[3332719788 6363640206 7818018221]
[4113950387 3041564037 4475036832]
Observe that the kernel method raises a NotImplementedError.
sage: A.kernel()
Traceback (most recent call last)
...
NotImplementedError: Cannot compute a matrix kernel over Ring of integers modulo 11053185041
The functionality is available, because "the kernel of a matrix over Z/n" is 'the kernel of a morphism between finitely generated abelian groups" or (equivalently) "the kernel of a morphism between finitely generated Z-modules". To interpret the language you'll have to read some algebra texts that go beyond first year material, but the computations in the end all boil down to computing Hermite Normal Forms and possibly Smith Normal forms.
As an example, if you want to compute the (row) kernel of [[2,0],[0,3]] over Z/6Z you can proceed in the following way.
sage: Z2=ZZ^2
sage: M=Z2/(6*Z2)
sage: A=matrix([[2,0],[0,3]])
sage: phi=M.hom([M(a) for a in A])
sage: phi
Morphism from module over Integer Ring with invariants (6, 6) to module with invariants (6, 6) that sends the generators to [(0, 2), (3, 0)]
sage: phi.kernel()
Finitely generated module V/W over Integer Ring with invariants (6)
sage: [M(b) for b in phi.kernel()]
[(0, 0), (3, 4), (0, 2), (3, 0), (0, 4), (3, 2)]
sage: [M(b) for b in phi.kernel().gens()]
[(3, 4)]
This codes shows that the kernel itself looks like Z/6Z, what its 6 elements are, and that they are the Z/6Z multiples of the vector (3,4).
Your Answer
Stats
Asked: 2016-06-23 08:16:00 +0100
Seen: 2,247 times
Last updated: Jun 28 '16
@vishb: Please provide a minimal working example to save time to anyone trying to answer your question.