# Why is my $D'D$ matrix not positive definite?

I am trying to write a quadratic program to minimize a sum of squares. My goal is to obtain a "smooth" vector $x$, so I'm trying to minimize $(x_1-x_2)^2 + (x_2-x_3)^2 + (x_3-x_4)^2 + (x_4 + x_5)^2$ (with some restrictions).

If I understood correctly, the quadratic program representation is then:

$\min x^\top A x$, where $A=D^\top D$.

The first order difference matrix is $D = \begin{pmatrix} -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix}$

Then, $A$ will be $A = D^\top D = \begin{pmatrix} 1 & -1 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix}$

This matrix $A$ is not positive definite (but semi-definite) according to my quadratic program solver, which throws an error. On Wikipedia, though, it says that all gram matrices of the form $D^\top D$ are positive definite.

I seem to have a mistake somewhere. My hunch is that my matrix $A$ does not represent what I want, which is to minimize $(x_1-x_2)^2 + (x_2-x_3)^2 + (x_3-x_4)^2 + (x_4 + x_5)^2$.

So, my question: Where is my mistake? My sum of squares is clearly positive for all $x$, but my matrix $A$ is not positive definite.

Wikipedia also gives an example that a matrix $\begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$ is positive definite. This one differs in my version only in the top left and lower right elements. Does that have anything to do with what I'm trying to solve?

• The dimensions of your matrices seem to be off. A doesn't look square to me. And $D^TD$ will only be positive definite if the vectors of D are linearly independent, which is not the case, since you seem to have $n+1$ vectors in $\mathbb{R}^n$. – mlk May 23 '17 at 8:17
• Should your $\mathbf{D}$ matrix not be the negative of what you have written? As in: $$\mathbf{D} = \begin{pmatrix}1 & -1 & \dots & 0 \\ 0 & 1 & -1 & \dots \\ \vdots & \ddots & &\vdots \end{pmatrix}$$ – Thomas Russell May 23 '17 at 8:17
• @mlk: $D$ is a 4x5 matrix, and $A=D^\top D$ is always square, as far as I know. If $A$ is not positive definite, then $x^\top A x$ does not equal my sum of squares I want to minimize, right? – Alexander Engelhardt May 23 '17 at 8:30
• @Thomas: Maybe, but $A$ is the same regardless if I use $D$ or $-D$. – Alexander Engelhardt May 23 '17 at 8:30

$D$ is $4\times 5$ matrix, rank of $D$ $\le 4$. $D^t$ is $5\times 4$ matrix, thus $A$ is a $5 \times 5$. Rank $A$ $\le$ Rank $D$ $= 4$. Thus $A$ is a $5 \times 5$ matrix of rank $\le 4$. Thus $\exists \ v \in \mathbb{R}^{5}$ such that $Av =0$. So $A$ is not positive definite and only semi-definite.
• Explained this way, I understand how $A$ is not positive definite. But if I write out $x^\top A x$, it becomes the sum of squares I wrote down above, which is clearly positive for all nonzero $x$. That means $A$ should be positive definite, doesn't it? – Alexander Engelhardt May 23 '17 at 8:57
• sum of squares can be zero, you see $Dx$ can be zero for a non-zero $x$. Therefore only positive semidefinite($<v,v> \ge 0$) but not positive definite (<v,v> > 0 ).. – Affineline May 23 '17 at 9:03
• Oh god, you're right. I completely missed that. If all $x_i$ are the same value, the sum of squares is zero. Thanks for the help! – Alexander Engelhardt May 23 '17 at 9:05