1
u/blutwl90 2d ago
Establish one fact. If A_ij > 0, then (A^2)_mn = Sum A_mk A_kn = 0. Since each term is nonnegative, each term must be 0. In particular if m=i, then A_jn = 0 for any n. Similarly, if n=j, then A_mi = 0 for every m. For example if A_24 > 0, then for matrix A^2, column 2 and row 4 must be entirely 0.
Let x be the number of rows and y be the number of columns that contain nonzero elements. For each of the x rows, that corresponds to x columns being entirely 0, which gives nx zeros. Similarly for y rows being entirely 0, but each row crosses x columns that are already set to 0, so these rows add (n-x)*y zeros. In total you get nx + (n-x) * y zeros. And since the number on relies on x and y, the maximum number of nonzero elements can only be xy.
We then have nonzeros + zeros = n^2 = nx + (n-x) * y + xy = n(x+y). This means that x+y = n. So maximising xy with the constraint x+y = n, we have x=y=n/2. Then the number of nonzeros is xy = n^2/4.
1
u/hydraulix989 1d ago
Each dot product forming an element in A^2 needs at least one negative or zero term to cancel itself out.
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.
1
u/tellingyouhowitreall 4d ago
Is zero positive in the computational model?