Can you please help me to understand how a (non-negative diagonal) matrix say $Q \geq 0\in M_t$ can be transformed into a scaled identity form via a sum of possible permutation matrices say $\Pi$, i.e., $\widetilde{Q} = \frac{1}{t!}\sum_{\Pi} \Pi Q \Pi^* = \alpha I$, subject to constraint that $\textrm{tr}[\widetilde{Q}] = \textrm{tr}[Q]$? Also, $\alpha \in F$ is some scalar.
Reference: This method of diagonalization is mentioned in this famous paper http://web.mit.edu/18.325/www/telatar_capacity.pdf (on page 10).
I am familiar with a diagonalization of a matrix via a similarity transformation (e.g., cf. Meyer's linear algebra book). However, the above method of diagonalization is so new to me.
Can you please enlighten me?
Many thanks for your help.
You are not reading the paper correctly.
First, although this is unimportant, $Q$ is $t\times t$, not $n\times n$. The $t$ in the definition of $\widetilde{Q}$ is exactly the number of rows/columns of $Q$.
Second, $Q$ is not just any positive semidefinite matrix, but a nonnegative diagonal matrix. The author initially does consider a general positive semidefinite matrix $Q$, but via a unitary similarity transform, he soon reduces the problem to one in which the new $Q$ is a nonnegative diagonal matrix.
For each permutation matrix $\Pi$, the product $\Pi Q\Pi^\top$ permute the diagonal entries of $Q$ while leaving all off-diagonal entries zero. Since all diagonal elements of $Q$ play the same roles in the sum $\sum_\Pi\Pi Q\Pi^\top$, the sum must be a scalar multiple of the identity matrix.
Put it another way, if $\Pi$ runs through all permutation matrices and $\Pi_0$ is some permutation matrix, then $\Pi_1=\Pi_0\Pi$ runs through all permutation matrices too. Hence $$ \Pi_0\widetilde{Q}\Pi_0^\top=\frac1{t!}\sum_\Pi\Pi_0\Pi Q\Pi^\top\Pi_0^\top=\frac1{t!}\sum_{\Pi_1}\Pi_1 Q\Pi_1^\top=\widetilde{Q}. $$ Since the permutation matrix $\Pi_0$ is arbitrary, the diagonal entries of $\widetilde{Q}$ must be identical to each other and hence $\widetilde{Q}=\alpha I_t$ for some scalar $\alpha$ (by taking matrix traces on both sides, we see that $\alpha=\frac1t\operatorname{tr}(Q)$, but again, this is unimportant here). So, the original $Q$ (before reduction by unitary similarity transform) must be equal to $\alpha I_t$ too.