A122527 and A121231 (number of binary matrices)

[Rob Pratt]

I asked
> Does replacing the positive entries in a monotonic matrix yield a binary matrix whose square is binary?

I meant to ask
> Does replacing the positive entries with ones in a monotonic matrix yield a binary matrix whose square is binary?

But that doesn't even work for the examples given in A070214.  So if there is a correspondence, it must be more complicated.

-----Original Message-----
From: Rob Pratt [mailto:Rob.Pratt at sas.com]
Sent: Sunday, August 03, 2008 1:33 AM
To: Richard Mathar; seqfan at ext.jussieu.fr
Subject: RE: A122527 and A121231 (number of binary matrices)

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
start with the same numbers

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

Is this some coincidence enforced by the odd-prime dimension
of the row count? (See also A052264) Can these numbers
be smaller than those in A055084 for the 6xn matrices although
the latter are counted with restrictions?

Richard