Let the field be complex, $U$ be an $n\times n$ unitary matrix, $M$ be any $n\times n$ matrix, and $|M|$ denote the matrix formed by taking the absolute value of every entry of $M$.
Edited Question: What is the general upper bound on $|trace(UM)|$?
As asked previously, the following statement is false –
There exists a permutation matrix $\Pi$, such that $|trace(UM)|\leq trace(\Pi|M|)$
Counter-example: $U=[[1/2,(1+i\sqrt2)/2],[(1-i\sqrt2)/2,-1/2]]$, $M=[[1.1,0],[1,0]]$
Best Answer
Let $M=\sum_{i=1}^na_iv_iw_i^t$ be a singular value decomposition of $M$, i.e., $a_i\geq 0$, $\{v_1,\ldots,v_n\}$ and $\{w_1,\ldots,w_n\}$ are orthonormal bases of $\mathbb{C}^n$.
If $U$ is a unitary matrix then $\{Uv_1,\ldots,Uv_n\}$ still is an orthornormal basis of $\mathbb{C}^n$.
Thus, $|tr(UM)|=|tr(\sum_{i=1}^na_iUv_iw_i^t)|\leq\sum_{i=1}^na_i|tr(Uv_iw_i^t)|\leq \sum_{i=1}^na_i|Uv_i||w_i|\leq \sum_{i=1}^na_i$.
Let $U=\sum_{i=1}^n\overline{w_i}\ \overline{v_i}^t$. Notice that $U$ is unitary.
Now, $|tr(UM)|=|tr(\sum_{i=1}^na_iUv_iw_i^t)|=|tr(\sum_{i=1}^na_i\overline{w_i}w_i^t)|=\sum_{i=1}^na_i$.
Thus, a sharp upper bound for $|tr(UM)|$ is the sum of the singular values of $M$.