Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is $\sum_{i=1}^n x_i^2 + \sum_{1\leq i < j \leq n} x_{i}x_j$ positive definite?


The matrix of this quadratic form can be derived to be the following

$$M := \begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} \\ \frac{1}{2} & 1 & \frac{1}{2} & \cdots & \frac{1}{2} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \cdots & 1 \\ \end{pmatrix}$$

It suffices to show that $\operatorname{det}M > 0$, then the claim follows.

Any hints how to show the positivity of this determinant?

share|improve this question
I don't understund why $\det M > 0 $ suffices. For example the matrix : $$A=\left(\begin{array}{ccc}1&0&0\\0&-1&0\\0&0&-1\end{array} \right)$$ has a $ > 0 $ determinant but this matrix is note poistive ! –  Mohamed Jun 17 '12 at 18:18
@Mohamed, I am not at all sure that the person asking knows this, but it follows by induction using en.wikipedia.org/wiki/Sylvester%27s_criterion –  Will Jagy Jun 17 '12 at 18:39
It only suffices if we prove it for all $m=1..n$ –  leonbloy Jun 17 '12 at 18:42
@ leonbloy : this in general but for the case thank you very much @ Will Jgay who explained the real reason: it is the nature of this matrix that allows a proof of this fact by induction. –  Mohamed Jun 17 '12 at 20:16
add comment

6 Answers

A direct approach would note that your form is $${1\over2}\left[\left(\sum_{i=1}^n x_i\right)^2+\sum_{i=1}^n x_i^2\right].$$

share|improve this answer
add comment

The eigenvalues of an $n$ by $n$ matrix consisting entirely of 1's are $n$ and $0.$ An eigenvector for $n$ can be all entries 1. $0$ has multiplicity $n-1,$ for $1 \leq i \leq n-1$ take an eigenvector to have mostly 0's, but $-1$ at position $i$ and 1 at position $n.$ Adding the identity matrix makes the eigenvalues $n+1$ and $1.$ Dividing by 2 makes the eigenvalues $\frac{n+1}{2}$ and $\frac{1}{2}.$

It took me a few minutes to check, but the doubled version of this, with all 2's on the main diagonal and all 1's elsewhere, is isometric to the root lattice $A_n$ which comes from a Lie algebra. See A3, A4, A5, A6, A7 and so on.

share|improve this answer
A much more elegant solution than than finding triangular forms, if not quite that obvious. –  tomasz Jun 17 '12 at 16:51
@tomasz, the matrix of all 1's comes up fairly often on this site. It seems to me a simple thing, worth learning for any beginner. –  Will Jagy Jun 17 '12 at 17:12
add comment

We can more generally show that the $n\times n$ determinant of $$\left|\begin{array}{cccc}a & b & \cdots & b \\ c & a & \ddots & \vdots\\ \vdots & \ddots & \ddots & b \\ c & \cdots & c & a\end{array}\right|$$ is $\left\{\begin{array}{ll}\frac{1}{c-b}(c(a-b)^n-b(a-c)^n) & \text{ if }b\neq c \\ (a-b+nb)(a-b)^{n-1}& \text{ if } b=c\end{array}\right.$
So in your case, the determinant is $\frac{n+1}{2^n}>0$.

Proof :
Let $$H(x)=\left|\begin{array}{cccc}a-x & b-x & \cdots & b-x \\ c-x & a-x & \ddots & \vdots\\ \vdots & \ddots & \ddots & b-x \\ c-x & \cdots & c-x & a-x\end{array}\right|$$

Do $L_2\leftarrow L_2-L_1,\ldots,L_n\leftarrow L_n-L_1$ : $$H(x)=\left|\begin{array}{ccc}a-x & b-x & \cdots & \cdots & \cdots & b-x \\ \\ c-a & a-b & 0&\cdots&\cdots& 0\\\vdots & c-b & \ddots&\ddots&&\vdots\\\vdots&\vdots & \ddots&\ddots&\ddots&\vdots\\\vdots&\vdots&&\ddots&\ddots&0\\c-a&c-b&\cdots&\cdots&c-b&a-b\end{array}\right|$$

and $C_2\leftarrow C_2-C_1,\ldots,C_n\leftarrow C_n-C_1$ : $$H(x)=\left|\begin{array}{cccccc}a-x&b-a&\cdots&\cdots&\cdots&b-a\\c-a&2a-b-c&a-c&\cdots&\cdots&a-c\\\vdots&a-b&\ddots&\ddots&&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\\vdots&\vdots&&\ddots&\ddots&a-c\\c-a&a-b&\cdots&\cdots&a-b&2a-b-c\end{array}\right|$$

So it exists $\alpha$ and $\beta$ such as $H(x)=\alpha x+\beta$.
If $b\neq c$ we can evaluate $H(b)$ and $H(c)$ with the first writing of $H(x)$ : $$\left\{\begin{array}{c}\alpha b+\beta=(a-b)^n \\ \alpha c+\beta=(a-c)^n\end{array}\right.$$ So you get $\alpha$ and $\beta$, and your determinant is $H(0)=\frac{1}{c-b}(c(a-b)^n-b(a-c)^n)$.
If $b=c$ : your determinant is $\lim_{c\rightarrow b}\frac{1}{c-b}(c(a-b)^n-b(a-c)^n)=-f'(b)$ where $f(x)=(c+b-x)(a-x)^n$.

We can easily improve this proof to the case where the elements on the diagonal are not equal

share|improve this answer
add comment

One possible proof is to use the fact that for triangular $n\times n$ matrix $A$ it holds

$$\det(A) = \prod_{i=1}^n a_{i,i}$$

An example

$$\begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 1 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 1 \\ \end{pmatrix} \sim \begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{3}{4} & \frac{1}{4} \\ 0 & \frac{1}{4} & \frac{3}{4} \\ \end{pmatrix} \sim \begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{3}{4} & \frac{1}{4} \\ 0 & 0 & \frac{2}{3} \\ \end{pmatrix} $$ Determinant of the last form is clearly positive. Try to generalize this result.

share|improve this answer
add comment

We can write : $M= \frac 12 (I + J)$ were $I$ the unit matrix and $J$ the matrix who all entries equal $1$.

$J$ is diagonalizable as symetric real matrix with propre value $0$ , $n-1$ times because the rank of $J$ is $1$ and $n$ one time because $JX=nX$ where $X$ is the vector who has all coordinate equal $1$. $$J=P^{-1} \text{diag}(0,..,0,n)P= P^{-1} \Delta P$$ Then $$M=\frac 12 (P^{-1} I P + P^{-1} \Delta P = \frac 12 P^{-1} \text{diag}(1,...,1,n+1)P $$

share|improve this answer
add comment

This can be solved by probability theory: Let your matrix be $\Sigma$ with diagonal elements all 1 and the off-diagonal elements all equal to $\rho$. This is the variance-covariance matrix of a random vector $X$ where all components have variance 1 and all pairs of distinct elements have correlation $\rho$, where $|\rho| \le 1$ is necessary for this having any hope of being a variance-covariance matrix (which implies the determinant is nonnegative) Are there any other restrictions? Yes, we can calculate the variance of the sum of the elements of $X$, which clearly must be positive:

$$\mbox{var}\left(\sum_{i=1}^n X_i\right) = 1^T\Sigma 1 = \sum_i \sum_j \Sigma_{ij} =n + n(n-1) \rho >0$$

(where 1 stands for the vector with all ones)

First cancel one factor $n$, then solve the inequality, you get $\rho > -\frac{1}{n-1}$, and your value 1/2 clearly satisfies this!

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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