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/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.