# Prove $A_{ij} = \frac{1}{\sqrt{i+j}}$ is positive definite

I'm currently working through an exercise in an undergraduate functional analysis textbook and encountered the following problem:

Prove that the $$n\times n$$ matrix $$A$$ with entries defined as $$A_{ij} = \frac{1}{\sqrt{i+j}}$$ is positive definite.

In our lectures, we've just been introduced to the concept of inner products, and this problem was presented soon after. I suspect that the solution may not require advanced theorems.

I have checked the result with numeric methods. And it turns out that at least for $$n\le13$$ it's true. For $$n=14$$ somehow the determinant becomes $$−2.26×10^{−111}$$. Is it really negative or a numeric error?

• Check this result out. Nov 25, 2023 at 13:53
• Find an inner product space and vectors $v_i$ such that $\langle v_i,v_j\rangle =(i+j)^{-1/2}.$ Nov 25, 2023 at 13:58
• Mathematica tells me that with $n=14$ the determinant is $\approx 5.30256\cdot10^{-116}$. The answer was the same with both 200 as well as 400 digit precision, so I assume that the calculation was accurate enough in spite of inevitable loss of precision due to subtractions. Nov 25, 2023 at 16:57
• Linking 1, 2. Not because they would be relevant, but to make it easier to locate more somewhat related questions. Just in case :-) Nov 25, 2023 at 17:14
• A proof based on expressing the fraction as an infinite sum rather than an integral can be found in exercise 1.6.3 (pp.24-25) in the book Positive Definite Matrices by Bhatia. Nov 25, 2023 at 17:25

General Observation. If we can decompose a given $$n \times n$$ matrix $$\mathbf{A}$$ into the form

$$\mathbf{A} = \sum_{k=1}^{K} \mathbf{b}_k \mathbf{b}_k^{*}$$

where $$\mathbf{b}_1, \ldots, \mathbf{b}_K \in \mathbb{C}^n$$, then we know that $$\mathbf{A}$$ is psd because $$\mathbf{v}^* \mathbf{A} \mathbf{v} = \sum_{k=1}^{K} \| \mathbf{b}_k \mathbf{v}\|^2 \geq 0$$. In general, if we can find a $$\mathbb{C}^{n}$$-valued measurable function $$\mathbf{b}(x)$$ on a measure space $$(\mathcal{X}, \Sigma, \mu)$$ so that

$$\mathbf{A} = \int_{\mathcal{X}} \mathbf{b}(x) \mathbf{b}(x)^{*} \, \mu(\mathrm{d}x),$$

then $$\mathbf{A}$$ is psd with $$\mathbf{v}^* \mathbf{A} \mathbf{v} = \int_{\mathcal{X}} \|\mathbf{b}(x) \mathbf{v}\|^2 \, \mu(\mathrm{d}x) \geq 0$$.

OP's Case. Consider the vector-valued function

$$\mathbf{b}(t) = (e^{-t}, e^{-2t}, \ldots, e^{-nt})^{\top} = \sum_{k=1}^{n} e^{-kt} \mathbf{e}_k,$$

where $$\mathbf{e}_1, \ldots, \mathbf{e}_n$$ are the standard basis vectors of $$\mathbb{C}^n$$. If $$\mathbf{A}$$ denotes OP's matrix, then

\begin{align*} \int_{0}^{\infty} \mathbf{b}(t) \mathbf{b}(t)^{*} \, \frac{\mathrm{d}t}{\sqrt{t}} &= \sum_{j, k=1}^{n} \mathbf{e}_j \mathbf{e}_k^{*} \int_{0}^{\infty} e^{-(j+k)t} \, \frac{\mathrm{d}t}{\sqrt{t}} \\ &= \sum_{j, k=1}^{n} \mathbf{e}_j \mathbf{e}_k^{*} \sqrt{\frac{\pi}{j+k}} \\ &= \sqrt{\pi} \mathbf{A}, \end{align*}

proving that $$\mathbf{A}$$ is psd. Also, for any $$\mathbf{v} \in \mathbb{C}^n$$,

\begin{align*} \mathbf{v}^* \mathbf{A} \mathbf{v} &= \frac{1}{\sqrt{\pi}} \int_{0}^{\infty} \| \mathbf{b}(t) \mathbf{v}\|^2 \, \frac{\mathrm{d}t}{\sqrt{t}}. \end{align*}

To show that $$\mathbf{A}$$ is actually pd, suppose $$\mathbf{v}^* \mathbf{A} \mathbf{v} = 0$$. Then $$\mathbf{b}(t) \mathbf{v} = 0$$ for Lebesgue almost every $$t > 0$$, and in particular, there are $$n$$ distinct points $$t_1, \ldots, t_n$$ in $$(0, \infty)$$ so that $$\mathbf{b}(t_k) \mathbf{v} = 0$$ for each $$k = 1, \ldots, n$$. By invoking Vandermonde determinant, we know that $$\mathbf{b}(t_1), \ldots, \mathbf{b}(t_n)$$ are linearly independent, we conclude $$\mathbf{v} = 0$$ and therefore $$\mathbf{A}$$ is pd.

• +1 but Isn't there a typo on which side the conjugate transpose should be? Nov 25, 2023 at 16:37
• @operatorerror, Aww yes, you are right! Thank you, it is fixed now :) Nov 25, 2023 at 16:40
• No problem, very nice answer Nov 25, 2023 at 16:41
• (+) Beautiful answer! Nov 25, 2023 at 16:49
• @SangchulLee Should the $\mathbf{b}(t)$ in your second definition of $\mathbf{A}$ be $\mathbf{b}(x)$ ?
– NNN
Nov 27, 2023 at 3:56

We can show the more general fact that the matrix $$A$$ with entries $$A_{ij}=(i+j)^{-a}$$ where $$a > 0$$ is positive definite. To do that we need to prove that for all $$\mathbf{x}=(x_1,\dots,x_n)^T \in \mathbb{R}^n\setminus \{\mathbf{0}\}$$ we have $$\mathbf{x}^T A \mathbf{x}>0$$. This is equivalent to proving that $$\sum_{j,k} x_j x_k (j+k)^{-a} > 0$$ By using the integral representation $$x^{-a} = \frac{1}{\Gamma(a)}\int_0^\infty e^{-sx}s^{a-1}ds$$ valid for $$x>0$$ we get $$\sum_{j,k} x_j x_k (j+k)^{-a} = \frac{1}{\Gamma(a)}\int_0^\infty \sum_{j,k}x_j x_k e^{-s(j+k)}s^{a-1}ds = \frac{1}{\Gamma(a)}\int_0^\infty \left|\sum_{j=1}^n x_j e^{-sj}\right|^2s^{a-1}ds \geq 0$$

If the final integral is $$0$$ then $$\sum_{i=1}^n x_j e^{-sj} = 0$$ for almost every $$s > 0$$ and by linear independence of the family of functions $$\{e^{-jx}\}_{j\in [n]}$$ it follows that $$\mathbf{x} = \mathbf{0}$$, contradiction. Therefore, $$A$$ is positive definite.

Addendum: To derive the integral representation start with the definition of $$\Gamma(a)=\int_0^\infty e^{-s}s^{a-1}\,ds$$ and perform the substitution $$s=xu$$ to get $$\Gamma(a) = \int_0^\infty e^{-ux}(ux)^{a-1}x\,du = x^a \int_0^\infty e^{-sx}s^{a-1}\,ds$$

• Is that absolute value necessary? It can be just a square of a sum (which is the same as the square of absolute value) Nov 27, 2023 at 6:02
• @SidharthGhoshal It's not necessary in the real case, you're right. Nov 27, 2023 at 6:08