# Are the banded versions of a positive definite matrix positive definite?

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.

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$?

-
I think you mean "less than $b$ in absolute value" to be consistent with your example of $M^{(1)}$. I have followed this convention in my answer below. –  Noah Stein Jun 29 '10 at 14:47
Yes. Thanks for pointing it out. –  lemire Jun 29 '10 at 14:58

No. The matrix

$M = \begin{bmatrix}5 & 4 & 4 \\\\ 4 & 5 & 4 \\\\ 4 & 4 & 5\end{bmatrix} = \begin{bmatrix}2 & 2 & 2\end{bmatrix}\begin{bmatrix}2 \\\\ 2 \\\\ 2\end{bmatrix} + I$

is positive definite, but

$\begin{bmatrix}1 & -\sqrt{2} & 1\end{bmatrix}M^{(2)}\begin{bmatrix}1 \\\\ -\sqrt{2} \\\\ 1\end{bmatrix} = 20 - 16\sqrt{2}<20 - 22.4 < 0$,

so $M^{(2)}$ is not.

-

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$ ?

(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.)

EDIT: There's a bit more to this:

Let us denote by $A\ast B$ the Hadamard product of two $n\times n$ matrices $A$ and $B$ (defined by

$A\ast B=\left(a_{i,j}b_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$,

where

$A=\left(a_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$

and $B=\left(b_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq n}$).

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 my answer to MathOverflow #19100 - do you see how?

-
This is exactly how I got my example, but then I added the epsilon explicitly (then scaled because integers look nicer). –  Noah Stein Jun 29 '10 at 14:49