1

Problem

When reading an advanced text in numerical computing, I encountered the following claim

If a symmetric matrix $\mathbf{A}\in \mathbb{R}^{n\times n}$ has entries $\mathbf{A}_{ij}=i(n-j+1)$ for $j \geq i$, then it is positive semidefinite.

I verified this numerically using Julia and it seems to be a valid claim. However, I could not see why this is true theoretically. Specially, I do not know how to convert this to the following three conditions for positive-semidefiniteness enter image description here Could anyone help me, thank you in advance.

Mr.Robot
  • 646

2 Answers2

2

Let $\mathbf{P} \in \mathbb{R}^{n\times n}$ be defined by

$$ \mathbf{P}_{ij} = (n+1-j) \mathbf{1}(i \leq j) = \begin{cases} n+1-j, & \text{if } i \leq j; \\ 0, & \text{otherwise}. \end{cases} $$

Also, let $\lambda_i = (n+1)\left( \frac{1}{n+1-i} - \frac{1}{n+2-i}\right) $. Then we claim that

$$ \mathbf{A} = \mathbf{P}^{\mathsf{T}} \operatorname{diag}(\lambda_1, \cdots, \lambda_n) \mathbf{P}. $$

(Since $\lambda_i > 0$, this is enough to establish the positive definiteness of $\mathbf{A}$.) Indeed, the $(i,j)$-entry of the RHS is given by

\begin{align*} \sum_{k=1}^{n} \lambda_k \mathbf{P}_{ki} \mathbf{P}_{kj} &= (n+1-i)(n+1-j) \sum_{k=1}^{n} \lambda_k \mathbf{1}(k \leq i, k \leq j) \\ &= (n+1)(n+1-i)(n+1-j) \sum_{k=1}^{\min\{i,j\}} \left( \frac{1}{n+1-k} - \frac{1}{n+2-k}\right) \\ &= (n+1)(n+1-i)(n+1-j) \left( \frac{1}{n+1-\min\{i,j\}} - \frac{1}{n+1} \right) \\ &= (n+1)(n+1-\max\{i,j\}) - (n+1-i)(n+1-j) \\ &= (n+1)(i+j-\max\{i,j\}) - ij \\ &= (n+1)\min\{i,j\} - ij \\ &= \mathbf{A}_{ij}. \end{align*}

Therefore the proof is complete.

Sangchul Lee
  • 167,468
2

Let $L$ be the lower triangular matrix of $1$s (with all entries above the main diagonal equal to $0$). Sangchul Lee has observed (in a previous version of their answer) that $A=(n+1)LL^T-uu^T$, where $u=(1,2,\ldots,n)^T$. Thus we may further rewrite $A$ as $L\left((n+1)I-ee^T\right)L^T$, where $e=(1,1,\ldots,1)^T$ is the all-one vector. Hence $A$ is positive definite, because it is congruent to the positive definite matrix $(n+1)I-ee^T$.

user1551
  • 139,064