Magma

40 Reputation

4 Badges

0 years, 195 days

MaplePrimes Activity


These are questions asked by Magma

Consider the finite field G:=GF(p,k) for some prime p and a positive integer k. Let H be an nxm matrix over G.

My question: How to obtain the minimum number of linearly dependent columns of the H over G. 

Thanks in advance  

Consider A is an nxn binary matrix where n>1000. Assume that there is an integer k<100 such that the entries of the kth power of A, denoted A^k, are all positive integer numbers.  

My problem is that the computation of A^k takes too times and I want to ask: Is there some techniques in Maple for obtaining the matrix A^k. 

One technique that I am used is based on the boolean semiring with 1+1=1. In fact, I evaluate A^k until I reach the full-1 matrix. But the mentioned technique dose not effect the time of computation. 

For example consider the 1024*1024 binary matrix which is given as an attachment. It takes 2278 seconds to find out the entries of the 20th power of this matrix are all positive integer numbers.

I am used the following version of Maple 15. 
Thanks for any suggestions.

 Matrix.txt

Edition(1): The following command maybe useful. From the next command you can upload the given matrix in your worksheet and test it for my claim.

input := FileTools:-Text:-ReadFile("C:/Users/Desktop/Matrix.txt")

I want to write a procedure P such that the input of P is a positive integer number n and the output of P is a random permutation of the numbers {1,2,..,n}. 

I know that there is a command in Maple 2017 such that the command produces the mentioned request (random permutation in the combinatoric package), but I should work with Maple 15 and there is no the random permutation command in Maple 15. 

One of the solutions that I am used is based on the random number and check that if the produced numbers are pairwise distinct or not. The problem of this method  is that for n>128, it takes too time to generate a random permutation of the length n.

Thanks for any suggestions. 

Let A=(a_{i,j}) be an nxn non-singular matrix over GF(2). Assume that we have a positive integer number s and an irreducible polynomial f of degree n over GF(2). 

My question: How to get nxn binary matrices such as A provided that the characteristic polynomial  of these matrices over GF(2) is f and also sum(a_{i,j}) is equal to s with 1<=i<=n and 1<=j<=n.

For example, consider n=8 and s=10 and f= x^8+x^7+x^5+x+1. Then I applied the following Maple code to generate the mentioned matrices. 

restart
with(LinearAlgebra):

randomize(); 
 roll := rand(1 .. 64);
 roll1 := rand(1 .. 8); 
 roll2 := rand(9 .. 16);
 roll3 := rand(17 .. 24);
 roll4 := rand(25 .. 32);
 roll5 := rand(33 .. 40);
 roll6 := rand(41 .. 48);
 roll7 := rand(49 .. 56); 
 roll8 := rand(57 .. 64);

u := 1; while u > 0 do 
L := [roll(), roll1(), roll2(), roll3(), roll4(), roll5(), roll6(), roll7(), roll8(), roll()];
if nops({L[]}) = 10 then
A := Matrix(8, 8, 0); s := 0;
for i to 8 do
for j to 8 do 
s := (i-1)*8+j; 
if evalb(`in`(s, L)) then A[i, j] := 1 end if
end do; end do;
if Determinant(A) <> 0 then
if evalb(`in`(sort(`mod`(Factor(CharacteristicPolynomial(A, x)), 2))[x^8+x^7+x^5+x+1]))
then print(A, sort(`mod`(Factor(CharacteristicPolynomial(A, x)), 2))); 
u := 0 end if; end if; 
unassign('A, s, i, j') 
end if; end do; 
unassign('u, i')

with my computer, it takes less than one minute to generate an 8x8 desired non-singular binary matrix as follows

  \left[
 \begin {array}{cccccccc}
 0&0&1&0&0&0&0&0\\
 0&1&1&0&0&0&0&0\\
 0&0&0&1&0&0&0&0\\
 0&1&0&0&0&0&1&0\\
 1&0&0&0&0&0&0&0\\
 0&0&0&0&1&0&0&0\\
 0&0&0&0&0&0&0&1\\
 0&0&0&0&0&1&0&0
 \end {array} 
 \right]

I wish I could find a systematic method to find these kind of matrices. 

Thanks for any suggestions 

Suppose that A is an nxn matrix over the finite field Z:=GF(2,q) for some q. I wan to get the smitform of A over Z. First I used the package  

with(LinearAlgebra[Generic]) 

and after that I applied the command 

S := SmithForm[Z](A)

but the mentioned command made some errors. In fact, I do not how to define commands igcdex, iquo, irem, sign and abs for SmithForm over finite fields.

Thanks for any suggestions 

1 2 Page 1 of 2