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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s