Matrix with entries $A_{ij} = u^{|i-j|} - u^{i+j}$ is positive semidefinite when $u \in (0, 1)$?

Question

Consider the square $n \times n$ matrix $A_n$ with entries $u^{|i-j|} - u^{i+j}$ where $u \in (0, 1)$.

Is it true that $A$ is positive semidefinite?

In the case $n = 1$, we have $A_1 = 1-u^2 \geq 0$.

For the case $n = 2$, we have $A_2 = (1 - u^2)\begin{pmatrix} 1 & u \\ u & 1+u^2 \end{pmatrix}$.

We can look at a quadratic form to see it is again positive semidefinite: $$\frac{(x, y)^T A_2 (x, y)}{1-u^2} = x^2 + (1 +u^2)y^2 + 2xyu \geq x^2 + u^2 y^2 + 2xyu = (x + uy)^2 \geq 0. $$

I can't tell how to generalize this to $n \geq 3$. Perhaps there is a better way establish the claim? For instance, it suffices (by induction) to prove that $A_n$ has positive determinant, but this also seems a little tricky.

Answer 1

$A_n$ is positive-definite because it has a Cholesky decomposition (see proposition here) :

$$A_n=C_nC_n^T$$

(product of a lower triangular matrix by its transpose)

Precisely :

$$A_n=\underbrace{\color{red}{a} \pmatrix{1&&&&&\\u&1&&&&\\u^2&u&1&&&\\ \cdots&\cdots&&&& \\ \cdots&\cdots&&&& \\ u^{n-1}&u^{n-2}&u^{n-3}&\cdots& 1} \color{red}{a}}_{C_n}\underbrace{\pmatrix{1&u&u^2&u^3&\cdots &u^{n-1}\\&1&u&u^2&\cdots &u^{n-2}\\&&1&u&\cdots& u^{n-3}\\ &&&&\cdots&\cdots \\ &&&&\cdots&\cdots \\&&&&& 1}}_{C_n^T}$$

where $a:=\sqrt{1-u^2}.$

Proof :

We can assume, without loss of generality, that $i \le j$.

Entry $(A_n)_{i,j}$ is the product of the $i$th row "$u^{i-1} \ u^{i-2} \ \cdots \ u^2 \ 1$" of the first matrix by the $j$th column "$u^{j-1} \ u^{j-2} \ \cdots \ u^2 \ 1$" of the second matrix :

$$\color{red}{a^2}(u^{i+j-2}+u^{i+j-4}+\cdots+u^{j-i})$$

$$=\color{red}{a^2}u^{j-i}(u^{2i-2}+u^{2i-4}+\cdots+1)\tag{1}$$

The sum within parentheses being a geometric series with ratio $u^{2}$, (1) can be transformed into :

$$\color{red}{a^2}u^{j-i}\frac{1-u^{2i}}{1-u^{2}}$$

$$=u^{j-i}(1-u^{2i})=u^{j-i}-u^{i+j}$$

as desired.

Remarks about matrix $A_n$ :

1. This matrix can be interpreted (up to a constant factor) as the covariance matrix of a Orstein-Uhlenberg process. As such, it is positive (semi) definite.

2. The inverse of $A_n$ is a Toeplitz tridiagonal matrix. We could use this property in order to obtain its eigenvalues and show they are all positive.

Answer 2

Computations of the first several cases suggest that $$ (x_1,\dots,x_n)^T A_n (x_1,\dots,x_n) = (1-u^2) \sum_{k=1}^n \biggl( \sum_{\ell=k}^n u^{\ell-k} x_\ell \biggr)^2, $$ which would imply that $A_n$ is positive definite. For example, \begin{multline*} \frac{(x_1,x_2,x_3,x_4)^T A_4(x_1,x_2,x_3,x_4)}{1-u^2} \\ = (x_1+ux_2+u^2x_3+u^3x_4)^2 + (x_2+ux_3+u^2x_2)^2 + (x_3+ux_4)^2 + x_4^2. \end{multline*}

Answer 3

The determinant of $A_n$ can easily be computed by subtracting each row, multiplied by $u$, from the next row: $$ \det(A_n) = \begin{vmatrix} 1-u^2 & * & * & * & \cdots & * \\ 0 & 1-u^2 & * & * & \cdots & * \\ 0 & 0 & 1-u^2 & * & \cdots & * \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1-u^2 & *\\ 0 & 0 & \cdots & 0 & 0 & 1-u^2 \end{vmatrix} = (1-u^2)^n $$ This shows that all principal minors of $A_n$ have a positive determinant, so that $A_n$ is positive definite by Sylvester's criterion if $|u| < 1$.

Answer 4

Consider the matrix

$$A = \left(\frac{x_{\max(i,j)}}{x_{\min(i,j)}}- x_i \cdot x_j\right)_{1\le i,j \le n}$$

( $x_i = q^{i}$ we get our problem). Inspired by the solution of Jean Marie, we get the (square-root-free) Cholesky decomposition of the matrix $A$

$$A = L \cdot D\cdot U$$

where $L$ is the lower triangular with entries $\frac{x_i}{x_j}$, for $i \ge j$, $U = U^{t}$, and $D$ is the diagonal matrix with entries $1- \frac{x_i^2}{x_{i-1}^2}$, $i=1,\ldots, n$. ( $x_0 \colon = 1$). Conclude

If $x_i$ are real and $1> x_1^2 > \ldots >x_n^2$, then the matrix $A$ is positive definite.

$\bf{Added:}$ ( sketch of another approach using Laplace transforms)

It is worth investigating function $f(s)$ such that the matrix $$\left(f(\|v_i-v_j\|^2)- f(\|v_i+v_j\|^2) \right)_{1\le i,j\le n}$$

is positive semi-definite (for any $v_1$, $\ldots$, $v_n$ in an euclidean space). Examples: $s\mapsto e^{-t s}$, ( $t\ge 0$ parameter; see this answer for a similar calculation)

Since the function $f\colon s \mapsto \rho^{\sqrt{s}}$ is the Laplace transform of the positive function ( WA link) $$-\frac{\log \rho\, e^{-\frac{log^2 \rho}{4 t}}}{2 \sqrt{\pi}\, t^{\frac{3}{2}}}$$

( i. e. $f(s)$ is a positive linear combination of functions $s\mapsto e^{-t s}$) we conclude that $f$ also satisfies the condition, and so the matrix

$$(\rho^{\|v_i - v_j\|} - \rho^{\|v_i+v_j\|})_{1\le i,j\le n}$$

is positive semidefinite.