On the maximal sum of the entries of a matrix power

Abstract

Let $p_n$ be the maximal sum of the entries of $A^2$, where $A$ is a square matrix of size $n$, consisting of the numbers $1,2,\dots ,n^2$, each appearing exactly once. We prove that $m_n=\Theta (n^7)$. More precisely, we show that $n(240n^6+28n^5+364n^4+210n^2-28n+26-105((-1{)}^n+1))/840\le p_n\le n^3(n^2+1)(7n^2+5)/24$.

6 pages