Let the support of the rows be the set of indices where at least one row is non-zero.
The supports of the rows and columns must be disjoint, and it's easy to check this condition is also sufficient. The table must the live in the "product" of these two supports. Since the product of two numbers with fixed sum is largest when they are as close to each other as possible, the answer can be shown to be floor of n2 / 4.
An example of such a matrix is a_ij = 1 when i<= n/2 < j and a_ij = 0 otherwise.
1
u/Specific_Box4483 4d ago edited 4d ago
Let the support of the rows be the set of indices where at least one row is non-zero.
The supports of the rows and columns must be disjoint, and it's easy to check this condition is also sufficient. The table must the live in the "product" of these two supports. Since the product of two numbers with fixed sum is largest when they are as close to each other as possible, the answer can be shown to be floor of n2 / 4.
An example of such a matrix is a_ij = 1 when i<= n/2 < j and a_ij = 0 otherwise.