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.Tue, 28 Jun 2016 09:27:45 -0500How to find Kernel of a Matrix in $\mathbb{Z}/n$https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/ When I tried to find it directly using
A.kernel()
it said
Cannot compute a matrix kernel over Ring of integers modulo 11053185041
Thu, 23 Jun 2016 01:16:00 -0500https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/Comment by slelievre for <p>When I tried to find it directly using </p>
<pre><code>A.kernel()
</code></pre>
<p>it said</p>
<pre><code> Cannot compute a matrix kernel over Ring of integers modulo 11053185041
</code></pre>
https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?comment=33894#post-id-33894@vishb: Please provide a minimal working example to save time to anyone trying to answer your question.Thu, 23 Jun 2016 06:10:38 -0500https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?comment=33894#post-id-33894Answer by slelievre for <p>When I tried to find it directly using </p>
<pre><code>A.kernel()
</code></pre>
<p>it said</p>
<pre><code> Cannot compute a matrix kernel over Ring of integers modulo 11053185041
</code></pre>
https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?answer=33895#post-id-33895The 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
Thu, 23 Jun 2016 06:17:56 -0500https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?answer=33895#post-id-33895Answer by nbruin for <p>When I tried to find it directly using </p>
<pre><code>A.kernel()
</code></pre>
<p>it said</p>
<pre><code> Cannot compute a matrix kernel over Ring of integers modulo 11053185041
</code></pre>
https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?answer=33950#post-id-33950The 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).
Tue, 28 Jun 2016 09:27:45 -0500https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/?answer=33950#post-id-33950