2023 CMO Problems/Problem 2

Find the largest real number $C$ such that for any positive integer $n$ and any real numbers $x_1, x_2, \ldots, x_n$ , the following inequality holds: $\sum_{i=1}^n \sum_{j=1}^n(n-|j-i|) x_i x_j \geq C \sum_{i=1}^n x_i^2$

Solution 1

Define the $n \times n$ matrix $A_n$ as follows: $A_n=\left(\begin{array}{cccccc} n & n-1 & n-2 & \cdots & 2 & 1 \\ 1 & n & n-1 & \cdots & 3 & 2 \\ 2 & 1 & n & \cdots & 4 & 3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ n-2 & n-3 & n-4 & \cdots & n & n-1 \\ n-1 & n-2 & n-3 & \cdots & 1 & n \end{array}\right)$

The problem simplifies to finding the smallest real number $C$ such that for all $n \in \mathbb{N}^*$ and any vector $x \in \mathbb{R}^n$ , the following inequality holds: $x^T A_n x \geq C x^T x$

In other words, find the real number $C$ such that: $C \leq \inf _{n \in \mathbb{N}^*} \inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}$ Given that $A_n$ is not easily invertible directly, but is invertible (as it is a sparse matrix): $A_n^{-1}=\left(\begin{array}{cccccc} \frac{n+2}{2 n+2} & \frac{1}{2} & 0 & \cdots & 0 & \frac{1}{2 n+2} \\ -\frac{1}{2} & 1 & \frac{1}{2} & \cdots & 0 & 0 \\ 0 & -\frac{1}{2} & 1 & \frac{1}{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & -\frac{1}{2} & 1 & \frac{1}{2} \\ \frac{1}{2 n+2} & 0 & \cdots & 0 & -\frac{1}{2} & \frac{n+2}{2 n+2} \end{array}\right)$

Since the inverse has non-zero entries: $\inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}=\left(\sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}$

For the eigenvalues $\mu$ of $A_n$ : $\frac{1}{2}+\frac{1}{2 n+2} \leq \mu-1 \leq \frac{1}{2}+\frac{1}{2 n+2}$

Thus: $0 \leq \mu \leq 2$ Given that $A_n^{-1}$ is invertible, $\mu \neq 0$ , therefore: $\begin{gathered} 0<\mu \leq 2 \\ \sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x} \leq 2 \end{gathered}$

For a specific $y \in \mathbb{R}^n, y=[1,-1,1,-1, \ldots]^T \in \mathbb{R}^n$ , we have: $\begin{gathered} y^T y=n \\ y^T A_n^{-1} y= \begin{cases}2(n-2)+\frac{2(n+2)}{n+1} & \text { if } n \text { is even } \\ 2(n-1) & \text { if } n \text { is odd }\end{cases} \\ \sup _n \sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x} \geq \sup _n \frac{y^T A_n y}{y^T y} \geq 2 \end{gathered}$

In conclusion: $\inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}=\inf _n\left(\sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}=\left(\sup _{\substack{n \\ n \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}=\frac{1}{2}$

Therefore, the maximum value of the real number $C$ is $\frac{1}{2}$ .

~dalian xes|szm

2023 CMO(CHINA) (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All CMO(CHINA) Problems and Solutions

Page

Toolbox

Search

2023 CMO Problems/Problem 2

Solution 1

See also