How to prove the $n\times n$ matrix $A=\big(\frac{1}{i+j+1}\big)_{i,j\in [n]}$ is positive semi-definite?

Question

We've been trying to show that the matrix $$A=\Big(\frac{1}{i+j+1}\Big)_{i,j\in [n]}$$ is positive semi-definite. We've tried induction on $n$ using the Schur complement, but there is no simple analytic way to find $A_{n-1}^{-1}$ for every $n$.

Any advice?

Answer 1

Here is a quick proof: $\sum_{j,k} c_j \overline {c_k} x^{j+k} =|\sum_j c_jx^{j}|^{2} \geq 0$ for all $x \in [0,1]$. Integrate this from $0$ to $1$ to get $\sum_{j,k} c_j \overline {c_k} \frac 1 {j+k+1} \geq 0$ for any finite set of complex numbers $c_1,c_2,...,c_n$.

$\int_0^{1} x^{j+k}dx=\frac 1 {j+k+1}$.

Answer 2

This is a Gram matrix with strong analogy to the Hilbert matrix. Just consider $\int_0^1 x^{j+i} dx$ for each component. Positive semidefinitenes follows.

For a different interpretation, consider uniform rv $U$in $(0,1)$ and random vector $\mathbf x$ whose kth component is $x_k = U^k$. Then your matrix is given by $\mathbb E\big[\mathbf x \mathbf x^T\big]$ which is of course positive semidefinite by a standard quadratic form argument

addendum:
the most slick proof of the positive semidefiniteness comes from the fact that trace and expectation commute, so for any $ v \in \mathbb R^n$

$ v^T \mathbb E\big[\mathbf x \mathbf x^T\big] v$
$=\text{trace}\Big(v^T \mathbb E\big[\mathbf x \mathbf x^T\big]v\Big)$
$=\text{trace}\Big( \mathbb E\big[\mathbf x \mathbf x^T\big]vv^T\Big)$
$=\text{trace}\Big( \mathbb E\big[\mathbf x \mathbf x^T v v^T\big]\Big)$
$=\mathbb E\Big[ \text{trace}\big(\mathbf x \mathbf x^T vv^T\big)\Big]$
$=\mathbb E\Big[ \text{trace}\big( v^T \mathbf x \mathbf x^T v\big)\Big]$
$=\mathbb E\Big[\big( v^T\mathbf x\big)^2\big)\Big]$
$\geq 0$
because $\big( v^T\mathbf x\big)^2\geq 0$ and so its expecation is non-negative as well.