# A122527 and A121231 (number of binary matrices)

Rob Pratt Rob.Pratt at sas.com
Sun Aug 3 07:33:01 CEST 2008

```The answer to the question posed in A121231 is NOT A121294, despite the comment.  The conjecture in A121294 is false, as can be seen from n = 5.  The following matrix has 11 ones, and its square is binary:

0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 1 0 1 0
1 1 0 1 0

The problem of maximizing the number of ones can be solved using integer linear programming.

Let N = {1, ..., n}.

Maximize sum {i in N, j in N} x[i,j]
Subject to
x[i,k] + x[k,j] - 1 <= y[i,k,j] for i in N, j in N, k in N
sum {k in N} y[i,k,j] <= 1 for i in N, j in N
x[i,j] in {0,1} for i in N, j in N
y[i,k,j] in {0,1} for i in N, j in N, k in N

The interpretation is that x[i,j] is the (i,j) entry of the matrix M, and y[i,k,j] >= x[i,k] * x[k,j], so that sum {k in N} y[i,k,j] is an upper bound on the (i,j) entry in M^2.  (Note that since x[i,j] is in {0,1}, we can relax y[i,k,j] to continuous [0,1] since replacing any fractional y[i,k,j] with 0 preserves both feasibility and the objective value.)

Solving the LP relaxation yields an upper bound of n*(n+1)/2 for the maximum number of ones.  An optimal fractional solution is x[i,j] = (n+1)/(2n) for all (i,j), and y[i,k,j] = 1/n for all (i,j,k).

The values in A121294 do provide a lower bound for the maximum number of ones, but the optimal values seem to match A070214.  I have checked up through n = 7 and am running n = 8 now.  Does replacing the positive entries in a monotonic matrix yield a binary matrix whose square is binary?

Rob

-----Original Message-----
From: Richard Mathar [mailto:mathar at strw.leidenuniv.nl]
Sent: Saturday, August 02, 2008 4:47 PM
To: seqfan at ext.jussieu.fr
Subject: A122527 and A121231 (number of binary matrices)

A comparison of A122527 and A121231 shows that they

http://research.att.com/~njas/sequences/?q=id:A122527|id:A121231

Is this some coincidence enforced by the odd-prime dimension