Positive definite quadratic form $\sum_{i=1}^n x_i^2 + \sum_{1\leq i < j \leq n} x_{i}x_j$

Question

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

---

Approach:

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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].$$

Answer 6

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!