4
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ Check this result out. $\endgroup$ Nov 25, 2023 at 13:53
  • 4
    $\begingroup$ Find an inner product space and vectors $v_i$ such that $\langle v_i,v_j\rangle =(i+j)^{-1/2}.$ $\endgroup$ Nov 25, 2023 at 13:58
  • $\begingroup$ 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. $\endgroup$ Nov 25, 2023 at 16:57
  • 1
    $\begingroup$ Linking 1, 2. Not because they would be relevant, but to make it easier to locate more somewhat related questions. Just in case :-) $\endgroup$ Nov 25, 2023 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – user1551
    Nov 25, 2023 at 17:25

2 Answers 2

8
$\begingroup$

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.

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

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .