## 70 Reputation

5 years, 244 days

## To eliminate some entries of a list tha...

Maple 15

Let L=[a1,a2,...,an] be a list of positive real numbers.

My Question:

How to write a procedure to find a minimal interval such as [b,c]

provided that this interval covers entries of L which are close together.

Example:

let L:=[8.1 , 2.03 , 3.5 , 0.05 , 4.1]. Then the output of the procedure is the interval [2.03 , 4.1].

In fact we want to eliminate some entries of L that are not close to other entries of L.

## Computation of all determinants of sub m...

Maple 15

Let A be an nrxnr binary matrix. Suppose that the nxn binary matrix is obtained from the matrix A using the following code:

```n := upperbound(A)[1]/r;
B := Matrix(n, n, 0);
for i to n do
for j to n do
B[i, j] := SubMatrix(A, [(i-1)*r+1 .. i*r], [(j-1)*r+1 .. j*r])
end do;
end do;```

In other words, the matrix B is a decomposition of matrix A by rxr binary matrices. In the rest, we want to compute all determinants of the submatrices of B in module 2 as follows:

```u := 1;
for k to n do
P := choose(n, k);
for i to nops(P) do
for j to nops(P) do
W := [];
for ii in P[i] do
for jj in P[j] do
W := [op(W), B[ii, jj]]
end do
end do;
x := `mod`(Det(convert(blockmatrix(k, k, W), Matrix)), 2);
if x = 0 then
u := 0;
i := nops(P)+1;
j := nops(P)+1;
k := n+1
end if
end do
end do;
unassign('i, j, ii, jj, W, x, P')
end do
```

In the last step, we check that if the value of all sub determinants of B in module 2, are non zero, then we announce that the block matrix B is an MDS matrix

`if u = 1 then print(MDS) else print(NoMDS) end if`

Based on the above description I wrote the following procedure:

```restart

with(LinearAlgebra);
with(linalg, blockmatrix);
with(combinat)

MDS:=proc(A::Matrix,r::integer)
local n,B,i,j,u,ii,jj,k,P,W,x;
n:=upperbound(A)[1]/r;
B:=Matrix(n,n,0);
for i to n do
for j to n do
B[i,j]:=LinearAlgebra:-SubMatrix(A,[(i - 1)*r+1..i*r],[(j - 1)*r+1..j*r])
end do
end do;
unassign('i,j');
u:=1;
for k to n do
P:=combinat:-choose(n,k);
for i to nops(P) do
for j to nops(P) do
W:=[];
for ii in P[i] do
for jj in P[j] do
W:=[op(W),B[ii,jj]]
end do
end do;
x:=mod(Det(convert(linalg:-blockmatrix(k,k,W),Matrix)),2);
if x=0 then
u:=0;
i:=nops(P)+1;
j:=nops(P)+1;
k:=n+1
end if
end do
end do;
unassign('i,j,ii,jj,W,x,P')
end do;
if u=1 then print(MDS) else print(NoMDS) end if
end proc```

My problem is that if A is a 64x64 binary matrix and also r=8, then the procedure MDS(A,8) takes 453 seconds to run in my computer (Maple 15 on windows 7 32bit with 4G RAM).

Is it possible to optimize the procedure such that MDS(A,8) takes less than 1 minutes.

Thanks for any help

## Improved the Speed of a Procedure in Mod...

Maple 15

Let A=[V1, V2 ,..., Vn ] be a list of binary vectors such that the length of Vi for i=1...n is the positive integer number m. For instance, in the following example we have n=6 and m=5.

`A := [[1, 1, 1, 0, 0], [0, 1, 0, 1, 1], [1, 0, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 0, 1, 0], [0, 1, 1, 1, 1]]`

Suppose that ej with j=1...m are vectors of size m such that all entries of ej 's are zero except the jth entry where is equal to 1. Now set S=[e1,e2,...,em]. For example by m=5 we get

`S:=[[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]`

First, we choose i,j in [1...m] such that i<>j and then we update S as follows S=[e1,e2,...,em,ei+ej mod 2]. For example, it follows from i=1 and j=2 that

`S:=[[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [1, 1, 0, 0, 0]]`

Now consider the kth entry of A which is called Ak. Then we check that what is the minimum number of entries of S so that the summation of these entries mod 2 is equal to Ak. For example, for  S=[e1,e2,...,em,e1+e2 mod 2] we get [2, 3, 4, 3, 2, 4] which means the minimum number of entries of the S that are required to be added in order to obtain A1 is 2 and so on. Therefore, for the given example we get

```E:=[[1, 2, [2, 3, 4, 3, 2, 4], 18, 7.615773106],
[1, 3, [2, 3, 3, 3, 3, 4], 18, 7.483314774],
[1, 4, [3, 3, 3, 3, 2, 4], 18, 7.483314774],
[1, 5, [3, 3, 3, 3, 3, 4], 19, 7.810249676],
[2, 3, [2, 3, 4, 2, 3, 3], 17, 7.141428429],
[2, 4, [3, 2, 4, 2, 2, 3], 16, 6.782329983],
[2, 5, [3, 2, 4, 3, 3, 3], 18, 7.483314774],
[3, 4, [3, 3, 3, 2, 3, 3], 17, 7.],
[3, 5, [3, 3, 3, 3, 3, 3], 18, 7.348469229],
[4, 5, [3, 2, 3, 3, 3, 3], 17, 7.]];```

For instance, the interpretation of [3, 5, [3, 3, 3, 3, 3, 3], 18, 7.348469229] is that if S be [e1,e2,e3,e4,e5,e3+e5 mod 2] then we get [3, 3, 3, 3, 3, 3] where 18 is the summation of [3, 3, 3, 3, 3, 3] and also the number 7.348469229 is obtained from the following command:

`MatrixNorm(convert([3, 3, 3, 3, 3, 3], Matrix), Frobenius);`

Now we choose Ek for k in [1..nops(E)] such that Ek[4] be minimum over all Ek[4]'s. For example we choose [2, 4, [3, 2, 4, 2, 2, 3], 16, 6.782329983] since 16 is minimum between Ek[4]'s.

There are two points: First one is that if we have Ei and Ej such that Ei[4]=Ej[4] then we choose Ei if  Ei[5]>Ej[5] . The second point is that if Ei[4]=Ej[4] and also Ei[5]=Ej[5] then we choose one of them such as the first one. Finally we update the set S from the first two entries of Ek that we have obtained. For instance, the updated S in our example is:

`S=[e[1],e[2],e[3],e[4],e[5],S[E[6][1]]+S[E[6][2]] mod 2]=[e[1],e[2],e[3],e[4],e[5],e[2]+e[4] mod 2]`

Now we repeat this procedure for the updated S until that in one of the entries of E such as Ek we get Ek[3]=[1,1,..,1].

I have written a procedure in Maple for the mentioned question. But my procedure takes long time to compute when I run it over a list such as A with parameters n=m=64.

I want to kindly request you please modify the following code or suggest another fast procedure for this question.

```
restart;

with(LinearAlgebra):
with(ListTools):
with(combinat):

BP := proc (A::list)
local n, m, r, S, U, tt, P, E, t, Q, Z, R, k, T, j, PP, i, QQ;
n := nops(A);
m := nops(A[1]);
r := [seq(0, i = 1 .. m)];
r[1] := 1;
S := [seq(Rotate(r, m-i+1), i = 1 .. m)];
unassign('r');
U := [];
tt := 1;
while 0 < tt do
P := choose(nops(S), 2);
E := [];
for t to nops(P) do
Q := P[t];
Z := [];
R := [S[], `mod`(S[Q[1]]+S[Q[2]], 2)];
for k to n do
T := A[k];
for j to nops(R) do
PP := choose(nops(R), j);
for i to nops(PP) do
QQ := PP[i]; r := `mod`(add(R[QQ[i]], i = 1 .. nops(QQ)), 2);
if Occurrences(0, r-T) = m then
Z := [op(Z), j];
i := nops(PP)+1;
j := nops(R)+1
end if;
end do;
unassign('i, QQ, r, PP'):
end do;
end do;
E := [op(E), [Q[], Z, add(Z[i], i = 1 .. nops(Z)), evalf(MatrixNorm(convert(Z, Matrix), Frobenius))]];
unassign('k, Z, Q, R'):
end do;
r := FindMinimalElement([seq(E[i][4], i = 1 .. nops(E))]);
R := [];
for i to nops(E) do
if E[i][4] = r then R := [op(R), E[i]] end if
end do;
T := [FindMaximalElement([seq(R[i][5], i = 1 .. nops(R))], position)];
S := [S[], `mod`(S[R[T[2]][1]]+S[R[T[2]][2]], 2)];
U := [op(U), [R[T[2]][1], R[T[2]][2]]];
if Occurrences(1, R[T[2]][3]) = n then tt := 0 end if;
unassign('r, i, R, T, E')
end do;
return U;
end proc:

A := [[1, 1, 1, 0, 0], [0, 1, 0, 1, 1], [1, 0, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 0, 1, 0], [0, 1, 1, 1, 1]];

BP(A);
[[2, 4], [3, 6], [5, 7], [1, 2], [1, 6], [3, 8], [3, 9], [8, 9]]
```

## Optimization over Binary Polynomials...

Maple 15

Assume that x[i] with 1≤i≤n are binary numbers. Let I_[k] be a subset with k elements of the set {1,2,⋯,n}.

Now Consider the following binary linear functions

It is clear that to obtain f[j]'s we need to compute ∑k[j] XOR bitwise operator. But it is possible to get f[j]'s with less than ∑k[j] XOR.

Example: Let n=8 and m=7 and suppose that

It follows from (1) that we need to do 20 XOR bitwise operator to get f[j]'s with 1≤j≤7. But set

which results in  f[j]'s are computed with just 9 XOR.

It is useful to mention that the relation (1) can be represented by a 8x8 binary matrix in the form of M*X=F.

Question: Is it possible to implement a procedure in Maple such that by applying the procedure we get  f[j]'s with the minimum number of XOR bitwise operator.

One solution for this question is the "parr algorithm" that is given in the following paper

https://ieeexplore.ieee.org/document/613165

This edition is because of @Carl Love commnet.

The paar algorithm is provided in C++ in the following link

https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices/blob/master/paar.cpp

and is defined by

My problem is that I couldn't implement the paar algorithm in Maple.

Thanks for any help

## To Obtain the Column Rank of a Matrix Ov...

Maple 15

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.