Ask Your Question
1

How to find Kernel of a Matrix in $\mathbb{Z}/n$

asked 2016-06-23 01:16:00 -0500

vishb gravatar image

updated 2016-06-23 06:21:12 -0500

When I tried to find it directly using

A.kernel()

it said

 Cannot compute a matrix kernel over Ring of integers modulo 11053185041
edit retag flag offensive close merge delete

Comments

1

@vishb: Please provide a minimal working example to save time to anyone trying to answer your question.

slelievre gravatar imageslelievre ( 2016-06-23 06:10:38 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
1

answered 2016-06-23 06:17:56 -0500

updated 2016-06-23 06:20:46 -0500

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
edit flag offensive delete link more
2

answered 2016-06-28 09:27:45 -0500

nbruin gravatar image

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).

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

Stats

Asked: 2016-06-23 01:16:00 -0500

Seen: 312 times

Last updated: Jun 28 '16