# An innocent linear algebra problem and an application of the probabilistic method

The following question was posed to me by a friend:

Suppose that $A \subset M_{n \times n}(\mathbb{R})$ is a symmetric matrix with non-negative trace, and $B \subset M_{n \times n}(\mathbb{R})$ is a symmetric matrix with negative trace. Prove that there exists a vector $\textbf{w} \in \mathbb{R}^n$ such that $\textbf{w}^T A \textbf{w} \geq 0$ and $\textbf{w}^T B \textbf{w} < 0.$

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 $A$ is diagonalized, as the matrix $P$ used to diagonalize $A$ when applied to $B$ gives $PBP^{-1}$, which remains a symmetric matrix with negative trace as trace is preserved under similarity. Now consider the random vector $\textbf{x} = (x_1, \cdots, x_n)$ where the $x_i$ are independent Bernoulli random variables with mean zero and variance 1. It is immediate that for any such vector $\textbf{x}$, we have

$\textbf{x} A \textbf{x}^T \geq 0.$

Now, we compute the expectation of $\textbf{x} B \textbf{x}^T$. By the linearity of expectation and the fact that the $x_i$‘s are independent, we have

$\displaystyle E(\textbf{x} B \textbf{x}^T) = \sum_{j=1}^n b_{jj} \text{Var}(x_j) = \text{Tr}(B) < 0.$

Hence there exists one particular vector $\textbf{x}'$ for which $\textbf{x}' B (\textbf{x}')^T < 0$, and we are done.

As remarked earlier, this argument is equivalent to considering the set of vectors $\textbf{x} = (\pm 1, \cdots, \pm1)$ and adding all of them and concluding that at least one of them must give the desired result.