9
$\begingroup$

Background: Let $M$ be an $n\times n$ matrix with nonnegative entries. It is immediate that for any integer $k$, $M^k$ has nonnegative entries.

Suppose now that, on top of having nonnegative entries, $M$ is a positive semi-definite matrix (i.e., it is symmetric and has nonnegative eigenvalues). Now one may ask whether for any real $p\ge 1$, $M^p$ has nonnegative entries. Surprisingly, the answer is a no. The matrix $$ M= \begin{bmatrix} 0.96523 & 2.6398 & 0.012905 & 0.059013\\ 2.6398 & 10.053 & 3.0808 & 0.029887\\ 0.012905 & 3.0808 & 26.252 & 3.2929\\ 0.059013 & 0.029887 & 3.2929 & 0.52308 \end{bmatrix} $$ has positive eigenvalues, however $M^{1.5}$ has negative entries. This example is due to Koenraad Audenaert.

A nicer looking matrix of the same kind is $$ M= \begin{bmatrix} 2 &6 &0.1 &0.1\\ 6 &30 &6 &0.1\\ 0.1 &6 &30 &6\\ 0.1 &0.1 &6 &2 \end{bmatrix} $$

Question: Are there such (i.e., $M^p$ has negative values) positive PSD matrices whose eigenbasis is the discrete Fourier transform?

To be more explicit, let us fix the Fourier transform on $\mathbb F_2^n$ as $$H_{x,y} = (-1)^{\langle x,y\rangle}\quad x,y\in\mathbb F_2^n$$

Is there a nonnegative function $f:\mathbb F_2^n\to\mathbb R_+$ such that $Hf\geq 0$ however, $Hf^p$ has negative values for some $p\geq 1$? Here, $f^p$ denotes the coordinate-wise powering of $f$.

Recall that $H/2^{n/2}$ diagonalizes matrices of the form $M(x,y)=f(x+y)$, so the existence of such an $f$ is equivalent to existence of positive PSD matrices diagonalized in the Fourier basis whose $p$th power contains negative entries.

Thank you

$\endgroup$
2
$\begingroup$

There is an $f$ such that $f\ge 0$, $Hf\ge 0$ however $Hf^{p}$ contains negative values for some $p\ge 1$. Take $$ f = \begin{bmatrix} 727 & 200 & 163 & 234 & 429 & 448 & 437 & 6 \end{bmatrix}^T $$ The vector $Hf$ is positive, however $(Hf^{8/7})_{100}\approx -3.35$. Here the subscript $100\in \mathbb F_2^3$ is the 5th index in lexicographic order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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