Intereting Posts

Solution to 2nd order PDE
coin toss question
What is a natural number?
Non-free modules, with a free direct sum
Prove that $\log_a(b)=-\log_b(a)$
Minpoly and Charpoly of block diagonal matrix
Number of elements in cartesian power with a majority constraint
A commutative ring in which every prime ideal is 2-generated
The annihilator of an intersection is the sum of annihilators
Homology – why is a cycle a boundary?
“Conic sections” that are really just two straight lines
Plot $|z – i| + |z + i| = 16$ on the complex plane
Educational Math Software
Prove or disprove convergence for the series: $\sum_{n=2}^{\infty}\left((1+\frac{1}{n})^n-e\right)^{\sqrt{\log(n)}}$
Determine in How many ways $N!$ can be expressed as sum of consecutive numbers

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

- How does the determinant change with respect to a base change?
- How do I calculate the circulant determinant $C(1, a, a^2, a^3,\dots , a^{n-1})$?
- A determinant coming out from the computation of a volume form
- Determinant of a Certain Block Structured Positive Definite Matrix
- Coordinate-free proof of determinant of transpose
- Determinant identity: $\det M \det N = \det M_{ii} \det M_{jj} - \det M_{ij}\det M_{ji}$

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

- Why the SVD is named so…
- Matrices that are not diagonal or triangular, whose eigenvalues are the diagonal elements
- How many entries in $3\times 3$ matrix with integer entries and determinant equal to $1$ can be even?
- Tensor products of infinite-dimensional spaces and other objects
- Can you check my proof on the characterization of the trace function?
- Singular value decomposition of column & row vectors
- What is Binary Operation — is division a binary operation?
- Is the converse of Cayley-Hamilton Theorem true?
- How to randomly construct a square full-ranked matrix with low determinant?
- Norm inequality for sum and difference of positive-definite matrices

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

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.

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

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.

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

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!

The best answer is Byron’s, but it’s possible to show by induction that the characteristic polynomial of $M$ is $\big(\lambda – \frac{n+1}2\!\big)\big(\lambda – \frac 1 2\!\big)^{n-1}$, which means that the $M$ is (orthogonally) conjugate to a diagonal matrix with these (positive) eigenvalues along the diagonal.

- If the order divides a prime P then the order is P (or 1)
- Pigeon hole principle with sum of 5 integers
- Problem solving Logical Equivalence Question
- How to prove $(f \circ\ g) ^{-1} = g^{-1} \circ\ f^{-1}$? (inverse of composition)
- Why learning modern algebraic geometry is so complicated?
- Why is $\sum_{n=0}^{\infty }\left ( \frac{1}{2} \right )^{n}= 2$?
- Group of order $p^2$ is abelian.
- When does intersection of measure 0 implies interior-disjointness?
- Given $\lim\limits_{x\to 0} \frac {x(1+a\cos x)-b\sin x}{x^3}=1$, what is the value of $a+b$?
- Does $\gcd(a,bc)$ divides $\gcd(a, b)\gcd(a, c)$?
- Prove Quotient Group Isomorphism
- Function which is continuous everywhere in its domain, but differentiable only at one point
- How to find $\lim_{n \to \infty} \int_0^1 \cdots \int_0^1 \sqrt{x_1+\sqrt{x_2+\sqrt{\dots+\sqrt{x_n}}}}dx_1 dx_2\dots dx_n$
- Derivative of an even function is odd and vice versa
- Integral equal $0$ for all $x$ implies $f=0$ a.e.