Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is the product of non-negative definite matrices also non-negative definite? If not, let A and B be non-negative definite matrices, is '$tr(A^T B) >=0$' ?

share|improve this question
1  
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  
-1 for lack of background context (curiosity? overheard? read as a claim in a book?) –  Yemon Choi Mar 23 '10 at 15:32
1  
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
show 1 more comment

1 Answer

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.

share|improve this answer
1  
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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.