Let $$\mathbf{E} = \left[ \begin{array}{ccc} 1 & a_1 & b_1 \\ 1 & a_2 & b_2 \\ \vdots & \vdots & \vdots \\ 1 & a_n & b_n \end{array} \right] $$ where $0 < a_i,b_i < 1$, $b_i < a_i$ for $i=1,...n$, and $a_{i+1} < a_{i}$ for $i=1,...,n-1$.

Is there a proof that, for $n>2$, $\mathbf{A} := \mathbf{E}'\mathbf{E}$ is positive (semi-) definite (I've done endless simulations and the suggestion is that it is, plus, in the context of the application it makes sense that it is)? Reference to book or paper would be ideal.

Here is what I have so far:

Since $$ \mathbf{A} = \left[ \begin{array}{ccc} N & \sum a_i & \sum b_i \\ \sum a_i & \sum a_i^2 & \sum a_i b_i \\ \sum b_i & \sum a_i b_i & \sum b_i^2 \end{array} \right] $$ where $ \sum x_i := \sum_{i=1}^n x_i$, clearly $\mathbf{A}$ is symmetric. Further, as regards the principal minors, we have, first, $N>0$ and second (by Chebyshev sum inequality), $N \sum a_i^2 - \left(\sum a_i \right)^2 \geq 0$, so it remains to show $|\mathbf{A}| \geq 0$ (note that since the $b_i$ are not ordered Chebyshev is not available for the $b_i$).

Probably unsurprisingly, whether I use Schur complement, Descartes change-of-sign rule on the characteristic equation, or the determinant itself, the proof seems to lead to the same requirement, being to show that $$ N\sum a_i^2 \sum b_i^2 + 2 \sum a_i \sum b_i \sum a_i b_i - \left[ N\left( \sum a_i b_i \right)^2 + \left( \sum a_i \right)^2\sum b_i^2 + \sum a_i^2 \left( \sum b_i \right) ^2 \right] \geq 0. $$


It fails if the columns of $E$ are linearly dependent. This would include all $a_i = b_i,$ for example. This would also include all $b_i = (1/2) a_i.$ In general, the existence of a triple of real constants $\gamma, \alpha, \beta$ such that $\gamma + \alpha a_i + \beta b_i = 0$ for all $i$ would mean your $E^T E$ has rank two or one, is positive semidefinite but not definite. Indeed, take column vector $$ v = \left( \begin{array}{c} \gamma \\ \alpha \\ \beta \end{array} \right) $$

Then $$ v^T E^T E v = 0. $$

  • $\begingroup$ Thanks for pointing that out. The relation $b_i < a_i$ should have been strict inequality. $\endgroup$ – pt908 Nov 23 '15 at 20:40
  • $\begingroup$ @pt908, doesn't change the outcome. Edited in answer $\endgroup$ – Will Jagy Nov 23 '15 at 20:43
  • $\begingroup$ And, now that you bring this to attention, proof that $\mathbf{E}'\mathbf{E}$ is PSD would be just as useful, if it's the case that it is not PD $\endgroup$ – pt908 Nov 23 '15 at 20:43
  • $\begingroup$ @pt908 Of course $E'E$ is always positive semi-definite since $x'E'Ex=\|Ex\|^2\geqslant0$ for every $x$. $\endgroup$ – Did Nov 24 '15 at 8:18
  • $\begingroup$ Thanks! I did think that but when I tried to confirm it by hand I made a mistake (note to self: don't do maths when tired!). $\endgroup$ – pt908 Nov 24 '15 at 10:04

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.