The following question was posed to me by a friend:
Suppose that is a symmetric matrix with non-negative trace, and is a symmetric matrix with negative trace. Prove that there exists a vector such that and
After fruitlessly trying to give an explicit construction and trying to work out an inductive argument, the hint provided by my friend proved to be ingenious: one should consider a probabilistic argument.
In the end, one can argue that the probabilistic method is not really needed as the argument used below is equivalent to a counting argument. Nevertheless, we give the following proof.
First, we may suppose that is diagonalized, as the matrix used to diagonalize when applied to gives , which remains a symmetric matrix with negative trace as trace is preserved under similarity. Now consider the random vector where the are independent Bernoulli random variables with mean zero and variance 1. It is immediate that for any such vector , we have
Now, we compute the expectation of . By the linearity of expectation and the fact that the ‘s are independent, we have
Hence there exists one particular vector for which , and we are done.
As remarked earlier, this argument is equivalent to considering the set of vectors and adding all of them and concluding that at least one of them must give the desired result.