# Question:How to get an nxn binary matrix with some limitations on it

## Question:How to get an nxn binary matrix with some limitations on it

Maple 15

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

﻿