# A trace inequality for the inverse of a real positive semidefinite Toeplitz matrix.

This might be a simple problem for some. Let there be a real positive semidefinite Toeplitz matrix $\mathbf{R}_m$ of dimension $m+1$. Denoting its diagonal elements as $a_0$, we have Tr$(\mathbf{R}_m)=(m+1)a_0$. Moreover, as $\mathbf{R}_m$ is symmetric, it has the block form \begin{align} \mathbf{R}_m=\begin{bmatrix} \mathbf{R}_{m-1} & \mathbf{r}_m \\ \mathbf{r}^\mathsf{T}_m & a_0 \end{bmatrix}. \end{align} Clearly $\text{Tr}(\mathbf{R}_m)=\frac{m+1}{m}\text{Tr}(\mathbf{R}_{m-1})$. However, I want to prove if $\text{Tr}(\mathbf{R}^{-1}_m)\geq\frac{m+1}{m}\text{Tr}(\mathbf{R}^{-1}_{m-1})$. The inequality holds for several sample test cases. But does this extend to all possible $\mathbf{R}_m$?

My approach to the problem was to use the fact \begin{align} \text{Tr}(\mathbf{R}^{-1}_m)&=\text{Tr}(\mathbf{R}^{-1}_{m-1})+\frac{\text{Tr}(\mathbf{R}^{-1}_{m-1}\mathbf{r}_m\mathbf{r}_m^\mathsf{T}\mathbf{R}^{-1}_{m-1})+1}{\kappa} \\ &=\text{Tr}(\mathbf{R}^{-1}_{m-1})+\frac{\mathbf{r}_m^\mathsf{T}\mathbf{R}^{-1}_{m-1}\mathbf{R}^{-1}_{m-1}\mathbf{r}_m+1}{\kappa}, \end{align} where $\kappa$ is the Schur's complement of $\mathbf{R}_{m-1}$, i.e., $\kappa=a_0-\mathbf{r}_m^\mathsf{T}\mathbf{R}^{-1}_{m-1}\mathbf{r}_m$. The above expression stems from the Cholesky decomposition of the block form of $\mathbf{R}_m$ and subsequent inversion. The desired objective is then equivalent to proving if \begin{align} \frac{\mathbf{r}_m^\mathsf{T}\mathbf{R}^{-1}_{m-1}\mathbf{R}^{-1}_{m-1}\mathbf{r}_m+1}{\kappa}\geq\frac{\text{Tr}(\mathbf{R}^{-1}_{m-1})}{m}. \end{align}

An equality that might be useful is $\det(\mathbf{R}_m)=\det(\mathbf{R}_{m-1})\det(\kappa)\Rightarrow\kappa=\frac{\det(\mathbf{R}_m)}{\det(\mathbf{R}_{m-1})}$.

• Quite interesting, if one denotes $\lambda_i^{(m+1)}$ the $i$-th largest eigenvalue of $\mathbf R_m$, then it appears that $\lambda_i^{(m+1)} \geq \lambda_i^{(m)} \geq \lambda_{i+1}^{(m+1)}$. I wonder if this fact can be used to solve the original problem – uranix Dec 8 '16 at 18:57
• Yes it is intriguing, works perfectly for a diagonal matrix with entries $a_0≥0$. For the general case, $\mathbf{R}_m$ is symmetric and thus so is $\mathbf{R}_{m−1}$. The eigenvalue relationship mentioned above is indeed true and stems from Cauchy's interlace theorem. This leads to the sandwiched result $\text{Tr}(\mathbf{R}^{-1}_{m−1})+\frac{1}{λ^{(m+1)}_1}≥\text{Tr}(\mathbf{R}^{-1}_{m})≥\text{Tr}(\mathbf{R}^{-1}_{m−1})+\frac{1}{λ^{(m+1)}_{m+1}}$. But that's how far I've gotten it to go. – Ahmed Dec 9 '16 at 7:54