$\min(\det(\mathbf{A}))$ for special matrix $\mathbf{A}$

Question

(The construction of matrix $\mathbf{A}$ is not difficult to be understood. You can first jump to A Toy Example to take a glance. Any idea or suggestion would be appealing for me.)

---

The Original Problem:

Given $N,D\in\mathbb{Z}^+~(D\ge N)$ and $\alpha\in\mathbb{R}^+$, the vector $\mathbf{p}$ and the matrix $\mathbf{A}_\mathbf{p}$ are defined as follows:

• $\mathbf{p}=[p_1,p_2,\cdots,p_N]$, where $p_i$s are selected from $\{1,2,\cdots,D\}$ and satisfying the condition of $(p_1<p_2<\cdots<p_N)$.

• Given $\mathbf{p}$, there is $\mathbf{A}_\mathbf{p}=[a_{ij}]_{N\times N}$, where $a_{ij}=e^{-\alpha |p_i-p_j|}$.

I am trying to find out the property of $\det(\mathbf{A}_\mathbf{p})$. Based some of my findings, I am confused by the following two subproblems:

$(\text{Q}1)$ Can we conveniently calculate the value of $\det(\mathbf{A}_\mathbf{p})=f(\mathbf{p})$ for a given $\mathbf{p}$? In other words, is there a way to explicitly unfold $\det(\mathbf{A}_\mathbf{p})$?

$(\text{Q}2)$ Is $\mathbf{A}_\mathbf{p}$ positive semi-definite?

$(\text{Q}3)$ Does $\det(\mathbf{A}_\mathbf{p})$ hit its minimal value only when $(p_{i+1}-p_i=1)$? By the way, in this case, $\mathbf{A}_\mathbf{p}$ will become a special symmetric Toeplitz matrix.

---

A Toy Example:

Given $N=3$, $D=10$ and $\alpha =1$. I construct $\mathbf{p}_1=[3,4,5]$ and $\mathbf{p}_2=[2,5,7]$. Then we have:

$$ \det \left( \mathbf{A}_{\mathbf{p}_1} \right) =\left| \begin{matrix} 1& e^{-1}& e^{-2}\\ e^{-1}& 1& e^{-1}\\ e^{-2}& e^{-1}& 1\\ \end{matrix} \right|\approx 0.748, $$

and

$$ \det \left( \mathbf{A}_{\mathbf{p}_2} \right) =\left| \begin{matrix} 1& e^{-3}& e^{-5}\\ e^{-3}& 1& e^{-2}\\ e^{-5}& e^{-2}& 1\\ \end{matrix} \right|\approx 0.979 > \det \left( \mathbf{A}_{\mathbf{p}_1} \right) . $$

---

Some of My Efforts:

I may have the following observations:

$(\text{O}1)$ The diagonal elements of $\mathbf{A}_\mathbf{p}$ are all ones since $|p_i-p_i|=0$.

$(\text{O}2)$ All elements of $\mathbf{A}_\mathbf{p}$ are in $[0,1]$.

$(\text{O}3)$ $\mathbf{A}_\mathbf{p}$ is symmetric since $|p_i-p_j|=|p_j-p_i|$.

$(\text{O}4)$ Actually, the order of $\mathbf{p}_i$s do not affect the value of $\det(\mathbf{A}_\mathbf{p})$.

I guess that $\mathbf{A}_\mathbf{p}$ has the following two properties:

$(\text{P}1)$ The answer of $(\text{Q}2)$ is "Yes", i.e., $\mathbf{A}_\mathbf{p}$ is positive semi-definite.

$(\text{P}2)$ The answer of $(\text{Q}3)$ is "Yes", i.e., $\left[\det(\mathbf{A}_\mathbf{p})=\min\left\{{\det(\mathbf{A}_{\mathbf{p}_k})}\right\}\right] \Leftrightarrow \left[ \forall i, ~p_{i+1}-p_{i}=1 \right]$.

The above conjectures of $(\text{P}1)$ and $(\text{P}2)$ is empirically presented. I write the following Python code to validate them and find that all randomly generated $\mathbf{A}_\mathbf{p}$ satisfy $(\text{P}1)$ and $(\text{P}2)$:

import numpy as np
import random
from scipy import spatial

alpha = 1
N = 10
X = np.arange(N).reshape(N, 1)
X = np.exp(-alpha * spatial.distance.cdist(X, X))
X_det = np.linalg.det(X)
for D in range(N, 1000):
    for i in range(100):
        p = np.array(random.sample(range(1, D + 1), N)).reshape(N, 1)
        A = np.exp(-alpha * spatial.distance.cdist(p, p))
        A_det = np.linalg.det(A)
        if A_det <= 0:
            print(A_det, p.reshape(N,))  # det(A) <= 0
            exit(0)
        if A_det < X_det and abs(A_det - X_det) > 1e-8:
            print(p, p.reshape(N,))  # det(A) < det(X) with numerical tolerance
            exit(0)
print('Done.')

I test many combinations of $\{\alpha, N, D\}$. I see that there is no any case satisfy the conditions of A_det <= 0 and A_det < X_det.

---

Why I Try to Study $\det(\mathbf{A}_\mathbf{p})$?

I study the entropy of multivariate Gaussian distributions with some special covariance matrices (i.e., the above defined $\mathbf{A}_\mathbf{p}$). The entropy value is related to $\det(\mathbf{A}_\mathbf{p})$ (you can see more details from my previous problems below).

I have made efforts and spent more than 14 days on it. Specifically, I read some textbooks, papers and blogs related to it. Here are some previous problems posted by me: Problem 1, Problem 2, Problem 3 and Problem 4. However, I am still stucked. Now I think that the key step is to resolve the problem I posted above.

I am sorry for occupying much public resource of this platform. But I really want to resolve the problems, especially $(\text{Q}2)$ and $(\text{Q}3)$. Could you please provide help or some tips?

Answer 1

Q1 The determinant is $\prod_{n=1}^{N-1} (1 - e^{-2\alpha(p_{n+1}-p_n)})$.

Q2 Yes, using the answer to Q1.

Q3 Yes, using the answer to Q1.

---

---

The formula for Q1 is proved by induction on $N$. The base case $N=1$ is just $\det(1)_{1\times1} = 1$. For $N>1$, let $c = e^{-\alpha(p_N^{\phantom.} - p_{N-1}^{\phantom.})}$, and let ${\bf A'_p}$ be the matrix obtained from ${\bf A_p}$ by subtracting $c$ times row $N-1$ from row $N$ and then subtracting $c$ times column $N-1$ from column $N$. Then $\det{\bf A'_p} = \det{\bf A_p}$. But the last row and column of ${\bf A'_p}$ are all zero except for the $(N,N)$ entry which is $1-c^2$. Therefore $\det{\bf A'_p}$ is $1-c^2$ times the determinant of the symmetric matrix obtained from ${\bf A_p}$ by deleting its $N$-th row and $N$-th column -- which is just ${\bf A_{p'}}$ where ${\bf p'} = [p_1, p_2, \ldots, p_{N-1}]$. This completes the induction step and the proof.

---

Q2 By the product formula, $\det A$ is positive, as is the determinant of every symmetric minor of $A$ (which is of the same form as $A$ for some subsequence of $p_1,\ldots,p_N$).

---

Q3 This too follows from the product formula: each factor $1 - e^{-2\alpha(p_{n+1}-p_n)}$ is at least $1 - e^{-2\alpha}$, with equality if and only if $p_{n+1} - p_n = 1$.

---

---

We can also deduce the positive answer to Q2 by constructing linearly independent probability distributions $\mu_i$ on the real numbers whose covariance matrix is proportional to ${\bf A_p}$: the distribution $\mu_i$ chooses integers $p \geq p_i$ with probability $(1-e^{-\alpha}) e^{-\alpha(p-p_i)}$. If the real numbers $p_i$ are not required to be integers then we can achieve the same goal using continuous $\mu_i$ with distribution functions $\alpha e^{-\alpha(p-p_i)}$ supported on $p \geq p_i$.

Answer 2

To answer Question Q2: Yes, as the special case $u_j = \alpha p_j$ of the following result. We use $j,k$ for the indices rather than $i,j$ because we need $i = \sqrt{-1}$.

Proposition. For pairwise distinct real numbers $u_j$ the symmetric matrix $a_{jk} = \exp \left(-\left| u_j - u_k \right|\right)$ $(1 \leq j,k \leq N)$ is positive definite.

Proof: This will follow from the fact that the function $e^{-|x|}$ has a positive Fourier transform, and thus can be written as a positive linear combination of the functions $e^{ixy}$; namely $$ e^{-|x|} = \frac1\pi \int_{-\infty}^\infty e^{ixy} \frac{dy}{y^2+1} $$ (a well-known application of contour integration or Fourier inversion). Indeed for any nonzero test vector $(c_j)_{j=1}^N$ we find $$ \sum_{j=1}^N\!\sum_{k=1}^N a_{jk} c_j c_k = \frac1\pi \int_{-\infty}^\infty \left|\sum_{j=1}^N c_j e^{iu_j y}\right|^2 \frac{dy}{y^2+1} \geq 0; $$ and the equality is strict unless $\sum_{j=1}^N c_j e^{iu_j y} = 0$ for all $y$, which is impossible for distinct $u_j$. QED