# Question:Computation of all determinants of sub matrices of a block-matrix in modulo 2

## Question:Computation of all determinants of sub matrices of a block-matrix in modulo 2

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)/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)/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 ﻿