Swap and Matrix Multiplication

Let $S_0$ be the value before the operation. Suppose $A_{x,k}=a$ and $B_{k,x}=b$ are swapped, and let $d=b-a$. Then $A_{x,k}$ increases by $d$, while $B_{k,x}$ decreases by $d$.

Among the entries included in $S$, the total change strictly to the right of the diagonal in row $x$ is

$$d\sum_{j=x+1}^{N}B_{k,j},$$

and the total change strictly above the diagonal in column $x$ is

$$-d\sum_{i=1}^{x-1}A_{i,k}.$$

The diagonal entry does not change because the affected product $A_{x,k}B_{k,x}=ab$ becomes $ba=ab$. Hence,

$$\Delta_{x,k}=(B_{k,x}-A_{x,k})\left(\sum_{j=x+1}^{N}B_{k,j}-\sum_{i=1}^{x-1}A_{i,k}\right).$$

Define column prefix sums of $A$ and row suffix sums of $B$ by

$$P_{i,k}=\sum_{r=1}^{i}A_{r,k},\qquad Q_{k,i}=\sum_{c=i}^{N}B_{k,c}.$$

With $P_{0,k}=0$ and $Q_{k,N+1}=0$, each change is computed in as

$$\Delta_{x,k}=(B_{k,x}-A_{x,k})(Q_{k,x+1}-P_{x-1,k}).$$

The initial sum can also be computed without constructing the entire product by changing the order of summation:

$$S_0=\sum_{i=1}^{N}\sum_{k=1}^{N}A_{i,k}Q_{k,i}.$$

Since performing no operation is allowed, the answer is

$$S_0+\max\left(0,\max_{1\leq x,k\leq N}\Delta_{x,k}\right).$$

Both the time and space complexities are $O(N^2)$.

Solution written by GPT6