I have a question: If $A$ and $B$ are $n\times n$ positive semidefinite matrices, why does it follow that $(A+B)^{2}$ is positive semidefinite?
I know that to prove that $(A+B)^{2}$ is positive semidefinite, I need to prove that the eigenvalues of $(A+B)^{2}$ are nonnegative, but I don't know how to about this.
Best Answer
The answer is: It depends!
There are two common definitions of positive semidefiniteness.
Definition 1: $\newcommand{\m}{\mathbf}\newcommand{\A}{\m A}\newcommand{\B}{\m B}\newcommand{\x}{\m x} \A \in M_n(\mathbb R)$ is positive semidefinite if and only if for all $\x \in \mathbb R^n$ we have $\x^T \A \x \geq 0$.
Definition 2: Same as Definition 1, with the additional requirement that $\A$ be symmetric.
Let's start with the second definition, which may be the more commonly assumed. In this case, the stated result is true and follows easily from the definitions. In particular, $$ \x^T(\A + \B)\x = \x^T \A \x + \x^T \B \x \geq 0 \>, $$ since both terms in the middle are nonnegative. Furthermore if $\A$ and $\B$ are both symmetric, then so is $\A + \B$. Hence, $$ \x^T (\A + \B)^2 \x = \x^T (\A+\B)^T (\A+\B) \x = \|(\A+\B) \x\|_2^2 \geq 0 \>. $$
Now, let's look at the first definition. If we drop the assumption that $\A$ and $\B$ are symmetric, then the stated result in the question is false.
It is, of course, still true that $\A+\B$ is positive semidefinite (the same proof above applies), but $(\A+\B)^2$ may not be.
Counterexample: It suffices to consider only a single matrix $\A$, with $\B = 0$. Take $$\A = \left(\begin{array}{rr} 1 & -2 \\ 0 & 1\end{array}\right) \>.$$ Then, if $\x = (x_i)$, $$ \x^T \A \x = x_1^2 - 2 x_1 x_2 + x_2^2 = (x_1 - x_2)^2 \geq 0 \>. $$ So, $\A$ is positive semidefinite. However, $$ \A^2 = \left(\begin{array}{rr} 1 & -4 \\ 0 & 1\end{array}\right) \>, $$ which is clearly not positive semidefinite; to see this, just take $\x$ to be a vector of ones.