From Boyd & Vandenberghe's Convex Optimization:
Suppose $G=\{Q_1,\cdots Q_k\}\subset R^{n\times n}$ is a group. We say that the function $f$ is $G$ invariant or symmetric with respect to $G$ if $f(Q_ix)=f(x)$ holds for all $x$ and $i\in \{1,\cdots k\}$. We define $\bar{x}=(\frac{1}{k})\sum_{i=1}^kQ_ix$, which is the average of $x$ over its $G$-orbit. We define the fixed subspace of $G$ as
$F=\{x, \text{such that } Q_ix=x, i\in\{1,\cdots k\}\}$.
Part d: As an example, suppose $f$ is convex and symmetric for every permutation $P$. Show that if $f$ has a minimizer then it has a minimizer of the form $\alpha [1, 1,\cdots 1]$.
Its solution is as follows:
Suppose $x^*$ is a minimizer of $f$. Let $\bar{x}=\frac{1}{n!}\sum_{P}Px^*$ where the sum is over all permutations. Since $\bar{x}$ is invariant under any permutation we conclude that $\bar{x}=\alpha [1,\cdots,1]$ for some $\alpha$ on real line. (I really do not understand this last sentence how to show that it its true. Any help in this regard will be much appreciated. Thanks in advance.)
Best Answer
You put all the permutations in a matrix, with each permutation as a row. You take sums column-wise. Do all the sums equal? Yes, because each column contains the same number of each element of $x^*$. Convince yourself that the number permutations with $x^*_1$ in slot 1 is the the same as that with $x^*_1$ in slot 2, and so on ...