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

Let $A=(a_{ij}) \in \mathbb{R}^{n \times n}$ be a matrix with $a_{ij} = a_{ji} \geq 0$ and $B=(b_{ij})$ with $b_{ij} = \sqrt{a_{ij}}$.

Is $B$ positive-definite whenever $A$ is?

In other words:

$\sum_{1 \leq i,j \leq n} c_i c_j a_{ij} > 0 \iff \sum_{1 \leq i,j \leq n} c_i c_j \sqrt{a_{ij}} > 0$ for every choice of $c_i \in \mathbb{R}$?

A counterexample or any hint to a proof would be appreciated, thanks!

share|improve this question
    
It would be very strange. It is known that $A$ is positive-definite whenever $B$ is (more generally, the componentwise product of two positive-definite matrices is positive definite, because it is a submatrix of the Kronecker product), so we would get an if-and-only-if assertion, which would (by real algebraic geometry or something like that) mean some identities between dets, which almost certainly don't hold. –  darij grinberg Jan 20 '11 at 16:12
1  
And as a corollary to darij's observation: Not only are there counterexamples, but almost every matrix A with the required properties gives a counterexample. –  Johannes Hahn Jan 20 '11 at 17:12
    
Uhm, I don't think so. –  darij grinberg Jan 20 '11 at 18:09
2  
Hmm, I didn't realise (before doing the calculation) that this is true for $n=2$ –  Yemon Choi Jan 20 '11 at 21:50
    
@darij: The set where your "some identity" does not hold is a null set, open and dense subset of $\lbrace sym.matrices\rbrace = \mathbb{R}^{n(n+1)/2}$. If you intersect it with the space of all matrices with the required properties it is still a null set which is open and dense in this subspace (positive definite + positive entries is an open set in $\mathbb{R}^{n(n+1)/2}$ so there are no problems with dimensions etc.). –  Johannes Hahn Jan 21 '11 at 11:30
show 1 more comment

3 Answers

up vote 7 down vote accepted

Counterexample:

$B=\left(\begin{array}{ccc} 1 & 0 & 1 \\\\ 0 & 1 & 1 \\\\ 1 & 1 & \sqrt3 \end{array}\right)$.

This is for $n=3$, and easily extends to all $n\geq 3$.

For $n=2$ it holds, though.

share|improve this answer
    
ah, you beat me to typing it up. (btw, I think the pmatrix environment works here, so you don't have to type up the full array.) –  Willie Wong Jan 20 '11 at 16:29
    
you probably should also specify that the one you wrote down is $B$, the "square root" matrix for clarity's sake. –  Willie Wong Jan 20 '11 at 16:31
    
Thank you very much for your quick answer! This is just the counterexample I need. –  Christian Stahlhut Jan 21 '11 at 14:12
add comment

As a slightly longish comment, however, I would like to point out that there is a rich class of matrices, for which component-wise square root remains positive definite. The simplest example is the "unit" of this class of matrices, namely the matrix of all ones.

In general, there are several wonderful matrices, for which not only componentwise squareroot, but any root, continues remaining positive definite (in other words, the matrix $a_{ij}^\epsilon$ is positive definite too).

Simple, but instructive examples include:

  1. $a_{ij} = \frac{1}{\lambda_i + \lambda_j}$, where the $\lambda$s are nonnegative.
  2. $a_{ij} = \min(i,j)$
  3. $a_{ij} = \mbox{gcd}(i,j)$

These matrices are called infinitely divisible matrices. Please see the linked PDF for a very nice introduction to such matrices. Additional references can also be found in my related answer to an old question

share|improve this answer
    
Thanks for these hints! –  Christian Stahlhut Jan 21 '11 at 14:19
add comment

In the tradition (local to this question) of pointing out special cases or related results as answers, there is the amazing theorem of I. J. Schoenberg, of which I state the simplest form: Let $a_1, \dotsc, a_{n(n-1)/2}$ be the edge lengths of a simplex in $\mathbb{R}^n.$ Then, so are $a_1^\alpha, \dotsc, a_{n(n-1)/2}^\alpha,$ for any $0\leq \alpha \leq 1.$ This theorem is really about positive-semidefinite functions in the sense of Bochner (but has a direct spectral interpretation if you use the Cayley-Menger matrix).

share|improve this answer
    
Hmm.. interesting. I don't know what to make of it yet, but thank you for your comment! –  Christian Stahlhut Jan 21 '11 at 14:23
add comment

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.