1
$\begingroup$

Problem. Let $\psi(t) = (1, t, t^2, \ldots, t^{p-1})^\top$ - a polynomial basis. Suppose there is a matrix $$ A = \int_{-1}^1 \psi(t) \psi^\top(t) dt, \ \text{i.e. } \ A_{ij} = [2 \, | \, i+j] \cdot \dfrac{2}{i+j+1} \enspace , $$ that is, e.g. $$ A = 2\cdot\begin{pmatrix} 1 & 0 & 1/3 & 0 & 1/5 \\ 0 & 1/3 & 0 & 1/5 & 0 \\ 1/3 & 0 & 1/5 & 0 & 1/7 \\ 0 & 1/5 & 0 & 1/7 & 0 \\ 1/5 & 0 & 1/7 & 0 & 1/9 \end{pmatrix} \enspace . $$ We consider the polynomial

$$ P(t) = \psi^\top(t) A^{-1} \psi(t) $$ on the segment $t \in [-1, 1]$ for different values of dimension $p$. The observation is that the maximum is always attained at $t = \pm 1$ and equals to $p^2$. I don't know how to prove that, any help is appreciated. So,

Want to prove: $$ \max_{t \in [-1,1]}P(t) = P(\pm 1) = p^2/2 . $$

Observation 1a. The matrix $A$ is strictly positive-definite (it is easy to prove that least eigenvalue is not zero), therefore $P(t) > 0$.

Observation 1b. Using all this $Tr[AB]=Tr[BA]$ pretty techniques it is not difficult to obtain properties like $\int_{-1}^1 P(t) dt = 1$. However, trying to represent maximum as a limit $\left(\int[P(t)]^q dt)\right)^{1/q}$ is complicated.

Observation 1c. We also could note that the inverse matrix has the same zeroes, because it is block inverse matrix.

Observation 2. Googling across known series of polynomials didn't seem to be successful. I also didn't find any pattern in what the roots are. However, worth noticing that all the roots lie inside the segment $[-1, 1]$ - again I don't know why.

Observation 3. The plots of $P(t)$ for different $p$ look like the following: Plot for $p=3$, Plot for $p=5$. It can be noted that the polynomials $P(t)$ factor in an interesting way. If we number them like $P_1(t), P_2(t), \ldots$ then: $$ P'_{p+1}(t) = t Q_p(t) \cdot Q_{p+1} (t), $$ where the sequence of degrees of $Q_p(t)$ is $2,2,4,4,6,6,\ldots$.

Up to a constant, the coefficients of $Q_p(t)$ seem to obey some pattern. For example, $$ Q'_8(t) = t \cdot P_7(t) P_8(t) = t \left( 13 t^{6} - 15 t^{4} + \frac{45 t^{2}}{11} - \frac{5}{33} \right) \left( 15 t^{6} - 21 t^{4} + \frac{105 t^{2}}{13} - \frac{105}{143} \right) \enspace , $$ and you can see below that the coefficients have a nice factorization, and the signs of coefficients alternate as for the polynomial $P(t)$.

The polynomials $Q_p(t)$ also attain their maximum at $t = \pm 1$.

Observe the interesting pattern: \begin{eqnarray*} Q_1(t) &=& 5t^2 - 1 \cdot 1\\ Q_2(t) &=& 7t^2 - 1 \cdot 3\\ Q_3(t) &=& 9t^4 - 2 \cdot 3 t^2 + \dfrac{1 \cdot 3}{7} \\ Q_4(t) &=& 11t^4 - 2 \cdot 5 t^2 + \dfrac{3 \cdot 5}{9} \\ Q_5(t) &=& 13 t^6 - 3 \cdot 5 t^4 + \dfrac{5 \cdot 9}{11}t^2 - \dfrac{1 \cdot 3 \cdot 5}{9 \cdot 11}\\ Q_6(t) &=& 15 t^6 - 3 \cdot 7 t^4 + \dfrac{3 \cdot 5 \cdot 7}{13} t^2 - \dfrac{3 \cdot 5 \cdot 7}{11 \cdot 13}\\ && \ldots \end{eqnarray*} Generally, I have observed this for $p = 1..10$, but didn't understand the pattern well enough to represent it with some particular formula. For the subsequent polynomials it becomes far less trivial, e.g. a random multiple of $2$ or $4$ appears in some coefficients, and so on. I don't believe this is the most promising path to a solution.

Motivation. I am working on the problem of statistical probability density estimation, and the matrix $A$ is kind of local curvature matrix or Fisher information matrix for the particular model. I tried to present the most simple case of the matrix $A$, few complications are also possible, but my goal now is to understand this simple case. The value $\max_{t \in [-1,1]} P(t)$ is crucial for finite-sample confidence intervals.

Acknowledgements. I highly appreciate the possibility of a modern scientist to use symbolic computations, in particular sympy.

$\endgroup$
1
  • $\begingroup$ UPD: I have corrected the mess with the notation, now the vectors are columns, but in Ilya Bogdanov's proof the vectors are still rows, but it doesn't change the essence of matter. $\endgroup$ May 18 '16 at 14:34
2
$\begingroup$

It seems that the matrix you present as an example is $A/2$, not $A$; I assume that $A$ is exactly what is defined (so, e.g., $A_{11}=2$, not $1$).

Well, $A$ is the Gram matrix of the basis $\psi$ with respect to the scalar product $(f,g)=\int_{-1}^1 f(x)g(x)\,dx$; so, if we pass to the orthonormal basis of (normed) Legendre polynomials $\tilde P_n(x)=\sqrt{\frac{2n+1}2}P_n(x)$, say $(\tilde P_0,\dots,\tilde P_{p-1})=\psi S$, then $A=S^{-T}S^{-1}$. Thus $A^{-1}=SS^T$, and hence the polynomial you need is $P(x)=(\psi S)(\psi S)^T=\sum_{n=0}^{p-1}\tilde P_i^2(x)$.

It seems to be well-known (?) thath the maximum of $|P_n(x)|$ on $[-1,1]$ is attained at the endpoints; thus the claim follows.

$\endgroup$
3
  • $\begingroup$ Thank you! The derivation is correct (I messed a bit with vector-columns and vector-rows, when gave the problem formulation, but finally everything collided). It is surprising that the fact holds independent on the choice of basis $\psi(t)$. As for legendre polynomials, there are proofs of the fact using some integral representation, e.g. pskgu.ru/ebooks/ts/ts_dop2_2_1.pdf page 677. $\endgroup$ Apr 19 '16 at 11:16
  • $\begingroup$ By the way, though the nature of factorization of derivatives of $P_k(t)$ is not essential for the problem, it is somehow interesting. Perhaps it could be also explained through numerous properties of legendre polynomials. $\endgroup$ Apr 19 '16 at 11:17
  • $\begingroup$ Then it is better to correct the mess your question... $\endgroup$ Apr 20 '16 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.