# Boyd & Vandenberghe, exercise 4.4(d)

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.)

• All the last sentence is saying is that since the vector $\bar{x}$ never changes if you permute (re-order) its elements, it must be a vector where every element is the same. Can you show this? (If not, consider what would happen if two of the elements happened to be different and you applied a certain permutation of the elements...) Also, make sure you understand why $\bar{x}$ is invariant under any permutation! Apr 13 '19 at 11:07
• @MinusOne-Twelfth thank you so much for the prompt response. Apr 13 '19 at 11:10
• @MinusOne-Twelfth yes they have explained it in the part (a) of the question. But I have a little confusion about that too. I think that it is assumed in the solution that for a fixed $Q_j$, $Q_jQ_i$ is different for all $i$'s. Is it true? Apr 13 '19 at 11:13
• @FrankMoses (d) is a special case. For a general group you don't have the result for (d). Apr 13 '19 at 11:22
• @FrankMoses Group theory time: suppose ab = ac, do we know b=c? Yes, multiply on the left by $a^{-1}$. So yes, if b!=c, then ab!=ac. Apr 13 '19 at 11:33

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 ...