Problem 1740

1. Expectation Calculation:
We start by considering the random variables $\varepsilon_i$ which are chosen independently and uniformly from $\{-1, 1\}$. We need to calculate the expected value of the trace of the square of the sum of these matrices:
$$\mathbb{E}\left[\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right)\right]$$

2. Expanding the Square:
Expand the square inside the trace:
$$(\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2 = \sum_{i=1}^m \varepsilon_i^2 A_i^2 + \sum_{1 \leq i \neq j \leq m} \varepsilon_i \varepsilon_j A_i A_j$$
Since $\varepsilon_i^2 = 1$ for all $i$, this simplifies to:
$$(\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2 = \sum_{i=1}^m A_i^2 + \sum_{1 \leq i \neq j \leq m} \varepsilon_i \varepsilon_j A_i A_j$$

3. Taking the Trace:
Now, take the trace of both sides:
$$\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right) = \text{tr}\left(\sum_{i=1}^m A_i^2\right) + \text{tr}\left(\sum_{1 \leq i \neq j \leq m} \varepsilon_i \varepsilon_j A_i A_j\right)$$

4. Linearity of Trace and Expectation:
Using the linearity of the trace and expectation, we get:
$$\mathbb{E}\left[\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right)\right] = \text{tr}\left(\sum_{i=1}^m A_i^2\right) + \mathbb{E}\left[\text{tr}\left(\sum_{1 \leq i \neq j \leq m} \varepsilon_i \varepsilon_j A_i A_j\right)\right]$$

5. Expectation of Cross Terms:
Since $\varepsilon_i$ and $\varepsilon_j$ are independent and have mean zero, the expectation of the cross terms $\varepsilon_i \varepsilon_j$ for $i \neq j$ is zero:
$$\mathbb{E}[\varepsilon_i \varepsilon_j] = \mathbb{E}[\varepsilon_i] \mathbb{E}[\varepsilon_j] = 0$$
Therefore,
$$\mathbb{E}\left[\text{tr}\left(\sum_{1 \leq i \neq j \leq m} \varepsilon_i \varepsilon_j A_i A_j\right)\right] = 0$$

6. Final Simplification:
This simplifies our expectation to:
$$\mathbb{E}\left[\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right)\right] = \text{tr}\left(\sum_{i=1}^m A_i^2\right)$$
Since $\text{tr}\left(\sum_{i=1}^m A_i^2\right) = \text{tr}(A_1^2) + \text{tr}(A_2^2) + \dots + \text{tr}(A_m^2)$, we have:
$$\mathbb{E}\left[\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right)\right] = \text{tr}(A_1^2) + \text{tr}(A_2^2) + \dots + \text{tr}(A_m^2)$$

7. **Existence of $\varepsilon_i$:**
Since the expected value of a random variable is a weighted average of its possible values, there must exist some specific choice of $\varepsilon_1, \varepsilon_2, \dots, \varepsilon_m \in \{-1, 1\}$ such that:
$$\text{tr}\left((\varepsilon_1 A_1 + \varepsilon_2 A_2 + \dots + \varepsilon_m A_m)^2\right) \geq \text{tr}(A_1^2) + \text{tr}(A_2^2) + \dots + \text{tr}(A_m^2)$$

$\blacksquare$