Are the banded versions of a positive definite matrix positive definite? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:41:13Z http://mathoverflow.net/feeds/question/29921 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29921/are-the-banded-versions-of-a-positive-definite-matrix-positive-definite Are the banded versions of a positive definite matrix positive definite? lemire 2010-06-29T14:22:09Z 2010-06-29T15:24:52Z <p>Consider $M$, a positive definite matrix. Let $M^{(1)}$ be the diagonal matrix which agrees with $M$ on the diagonal ($M_{ii}=M^{(1)}_{ii}$). We have that $M^{(1)}$ is positive definite because it is diagonalizable and it has non-negative eigenvalues.</p> <p>What about general bands? Let $M^{(b)}$ be the restriction of $M$ on a band: $M_{ij}^{(b)}=M_{ij}$ when $i$ and $j$ differ by less than $b$ in absolute value and $M^{(b)}_{ij}=0$ for otherwise. Is $M^{(b)}$ positive definite for all $b$?</p> http://mathoverflow.net/questions/29921/are-the-banded-versions-of-a-positive-definite-matrix-positive-definite/29925#29925 Answer by Noah Stein for Are the banded versions of a positive definite matrix positive definite? Noah Stein 2010-06-29T14:45:28Z 2010-06-29T14:45:28Z <p>No. The matrix</p> <p>$M = \begin{bmatrix}5 &amp; 4 &amp; 4 \\ 4 &amp; 5 &amp; 4 \\ 4 &amp; 4 &amp; 5\end{bmatrix} = \begin{bmatrix}2 &amp; 2 &amp; 2\end{bmatrix}\begin{bmatrix}2 \\ 2 \\ 2\end{bmatrix} + I$</p> <p>is positive definite, but </p> <p>$\begin{bmatrix}1 &amp; -\sqrt{2} &amp; 1\end{bmatrix}M^{(2)}\begin{bmatrix}1 \\ -\sqrt{2} \\ 1\end{bmatrix} = 20 - 16\sqrt{2}&lt;20 - 22.4 &lt; 0$,</p> <p>so $M^{(2)}$ is not.</p> http://mathoverflow.net/questions/29921/are-the-banded-versions-of-a-positive-definite-matrix-positive-definite/29927#29927 Answer by darij grinberg for Are the banded versions of a positive definite matrix positive definite? darij grinberg 2010-06-29T14:46:11Z 2010-06-29T15:24:52Z <p>Wouldn't that mean that the quadratic form $x^2+y^2+z^2+2xy+2yz$ must be nonnegative definite (as it is a band restriction of the quadratic form $x^2+y^2+z^2+2xy+2yz+2zx$, which is clearly nonnegative definite), which contradicts its value at $x=1$, $y=-1$, $z=1$ ?</p> <p>(Note that I replaced your "positive definite" by "nonnegative definite" - feel free to add $\epsilon\left(x^2+y^2+z^2\right)$ to the form for some $\epsilon>0$ to keep everything positive.)</p> <p>EDIT: There's a bit more to this:</p> <p>Let us denote by $A\ast B$ the <em>Hadamard product</em> of two $n\times n$ matrices $A$ and $B$ (defined by</p> <p>$A\ast B=\left(a_{i,j}b_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$,</p> <p>where</p> <p>$A=\left(a_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$</p> <p>and $B=\left(b_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$).</p> <p>Let $A$ be a symmetric matrix. Then, (the matrix $A\ast B$ is nonnegative definite for every nonnegative definite matrix $B$) if and only if the matrix $A$ is nonnegative definite. The $\Longrightarrow$ direction is more or less trivial (just take $B$ to be the matrix $\left(1\right)_{1\leq i\leq n,\ 1\leq j\leq n}$) and disproves your conjecture (by taking $A$ to be the matrix whose $\left(i,j\right)$-th entry is $1$ if $\left|i-j\right|\leq d$ and $0$ otherwise). The $\Longleftarrow$ direction is interesting and most easily proven by decomposing the matrix $A$ in the form $u_1u_1^T+u_2u_2^T+...+u_nu_n^T$, where $u_1$, $u_2$, ..., $u_n$ are appropriate vectors. Another proof reduces it to Corollary 2 in <a href="http://mathoverflow.net/questions/19100/product-of-positive-matrices" rel="nofollow">my answer to MathOverflow #19100</a> - do you see how?</p>