# Product of Positive Matrices

Is the product of non-negative definite matrices also non-negative definite? If not, let A and B be non-negative definite matrices, is '$\operatorname{tr}(A^T B) \ge0$' ?

-
Hmm. Your notation suggests that your definition of "positive-definite" doesn't include "symmetric", right? – darij grinberg Mar 23 '10 at 9:29
And in this case, not even the trace thing is true, because the (1, 0; 2, 1) * (1, 0; -2, 1)^T = (1, -2; 2, -3) has trace -2. (Sorry for the matrix notation. (a, b; c, d) means the 2x2 matrix with a and b in the first row and c and d in the lower row). – darij grinberg Mar 23 '10 at 9:48
In the symmetric case, the product still doesn't need to be nonnegative definite: for instance, (1, 1; 1, 1) * (2, 0; 0, 1)^T = (2, 1; 2, 1) is not nonnegative-definite. – darij grinberg Mar 23 '10 at 9:51
-1 for lack of background context (curiosity? overheard? read as a claim in a book?) – Yemon Choi Mar 23 '10 at 15:32
There's absolutely no reason for asking about $A^TB$ rather than $AB$, unless your definition of "non-negative definite" is not preservied under $A \mapsto A^T$. The usual definition is $x^TAx \geq 0$ for all vectors $x$. – Theo Johnson-Freyd Mar 23 '10 at 16:23

Lemma 1. Let $k$ be a field, and $A\in k^{n\times n}$ be a symmetric matrix.

(a) Then, there exist an invertible matrix $U\in k^{n\times n}$ and a diagonal matrix $D\in k^{n\times n}$ such that $A=U^TDU$.

(b) Let the field $k$ be ordered. The matrix $A$ is nonnegative-definite if and only if all entries of the matrix $D$ are nonnegative.

I'm writing a proof of this, mainly because too many sources do it wrong (for instance, by assuming $k$ to be ordered in (a), where it is useless, or using the spectral theorem, which is much stronger and requires $k=\mathbb R$). But it isn't necessary for your question: you only seem to need the $k=\mathbb R$ case, where any proof would do.

EDIT: I'm not writing a proof of this. Too tired from the rest. See Proposition 15.1 in J. S. Milne's "Algebraic Groups, Lie Groups, and their Arithmetic Subgroups" Chapter I for a proof of Lemma 1 (a), and derive Lemma 1 (b) from it.

Corollary 2. Let $k$ be an ordered field. Let $A\in k^{n\times n}$ and $B\in k^{n\times n}$ be two symmetric nonnegative-definite matrices. Then, $\mathrm{Tr}\left(AB\right)\geq 0$.

Proof of Corollary 2. Consider the Kronecker product $A\otimes B\in k^{n^2\times n^2}$ of the two matrices $A$ and $B$. This Kronecker product $A\otimes B$ is defined as the matrix $\left(A_{i,j}B_{i',j'}\right)_{\left(1,1\right)\leq \left(i,i'\right)\leq \left(n,n\right),\ \left(1,1\right)\leq \left(j,j'\right)\leq \left(n,n\right)}$. Here, $A_{i,j}$ is the $\left(i,j\right)$-th entry of the matrix $A$, and $B_{i',j'}$ is the $\left(i',j'\right)$-th entry of the matrix $B$. Besides, the coordinates in the vector space $k^{n^2}$ are indexed by pairs $\left(i,i'\right)\in\left\lbrace 1,2,...,n\right\rbrace^2$, and these pairs are ordered lexicographically.

Lemma 1 (a) yields the existence of an invertible matrix $U\in k^{n\times n}$ and a diagonal matrix $D\in k^{n\times n}$ such that $A=U^TDU$, and Lemma 1 (b) shows that all entries of the matrix $D$ are nonnegative. Similarly, Lemma 1 (a) (applied to the matrix $B$ instead of $A$) yields the existence of an invertible matrix $V\in k^{n\times n}$ and a diagonal matrix $E\in k^{n\times n}$ such that $B=V^TEV$, and Lemma 1 (b) shows that all entries of the matrix $E$ are nonnegative. Thus, $A\otimes B=\left(U^TDU\right)\otimes\left(V^TEV\right)=\left(U\otimes V\right)^T\left(D\otimes E\right)\left(U\otimes V\right)$, so that the matrix $A\otimes B$ is nonnegative-definite (because the matrix $D\otimes E$ is a diagonal matrix all of whose entries are nonnegative, and therefore it is nonnegative-definite).

Now, let $v\in k^{n^2}$ be the vector given by $v_{\left(i,i'\right)}=\left[i=i'\right]$ for any pair $\left(i,i'\right)\in\left\lbrace 1,2,...,n\right\rbrace^2$. Here, for any assertion $\mathcal A$, we denote by $\left[\mathcal A\right]$ the truth value of $\mathcal A$, defined by $\left[\mathcal A\right]=1$ if $\mathcal A$ is true and $\left[\mathcal A\right]=0$ otherwise.

Now, an easy computation yields $v^T\left(A\otimes B\right)v=\mathrm{Tr}\left(AB^T\right)$. Since $B^T=B$, this becomes $v^T\left(A\otimes B\right)v=\mathrm{Tr}\left(AB\right)$. But $v^T\left(A\otimes B\right)v\geq 0$, since $A\otimes B$ is a nonnegative-definite matrix. Thus, $\mathrm{Tr}\left(AB\right)\geq 0$, proving Corollary 2.

-
I think that the second result can also be proved from $\mathrm{Tr(AB)}=\mathrm{Tr}(BA)$, without using the Kronecker product. In detail, $\mathrm{Tr}(UDU^TVEV^T)$ equals $\mathrm{Tr}(DU^TVEV^TU)$ equals $\mathrm{Tr}(\sqrt{D}U^TV\sqrt{E}\sqrt{E}V^TU\sqrt{D})$. The matrix inside is a Gram matrix, and hence symmetric non-negative definite, and so has a non-negative trace. – user2734 Mar 23 '10 at 11:47
Of course if you use the spectral theorem, you get the trace result (properly rewritten as $\mathrm{Tr}(AB)\ge 0$) for complex Hermitian matrices too. This appears in Horn and Johnson's book "Matrix Analysis" as "Fejer's Theorem". – Mark Meckes Mar 23 '10 at 11:47
@unknown: Thanks. I knew that there was such a proof, but forgot how to do it. – darij grinberg Mar 23 '10 at 11:49
The Kronecker product proof appears to work more generally, though, since it doesn't require the existence of square roots. – Mark Meckes Mar 23 '10 at 12:35
Square roots aren't particularly evil. It's easy to show that if $u$ is a nonnegative element of an ordered field $k$, then $k\left[X\right]/\sqrt(X^2-u\right)$ can be ordered as well. Much harder is the spectral theorem, as it requires adjoining the root of an $n$-th degree equation. – darij grinberg Mar 23 '10 at 12:45