# Bound on $x^TAx$ for spd matrix $A$ in terms of diagonal

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric positive definite matrix and $x\in\mathbb{R}^n$ some vector. I want to find a bound of the form $$x^T Ax \leq c \sum_{i=1}^n a_{ii} x_i^2$$ with a constant $c>0$.

If $\lambda_\text{min}$ and $\lambda_\text{max}$ denote the smallest and largest eigenvalue of $A$ (both are positive due to spd assumption), then one bound that holds is $$x^T Ax \leq \frac{\lambda_\text{max}}{\lambda_\text{min}} \sum_{i=1}^n a_{ii} x_i^2.$$ Proof: $x^TAx \leq \lambda_\text{max} \Vert x\Vert^2 = \frac{\lambda_\text{max}}{\lambda_\text{min}} \sum_{i=1}^n \lambda_\text{min} x_i^2 \leq \frac{\lambda_\text{max}}{\lambda_\text{min}} \sum_{i=1}^n a_{ii} x_i^2$, where we used that $a_{ii} \geq \lambda_\text{min}$ for all $i$.

However, I think there should be a tighter bound. For example, the inequality holds with $c=1$ if $A$ is diagonal. Any ideas?

• I think you can have $c = n$ in general – Omnomnomnom May 15 '17 at 14:39

You can substitute $y_i = \sqrt{a_{ii}}\;x_i$. Then you are looking for the smallest $c$ with $$y^T \begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix} A \begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix} y \leq c \| y \|_2^2 \;\;\forall y\in\mathbb{R}^n$$ which is the largest eigenvalue of $$\begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix} A \begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix}$$
• $$\begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix} A \begin{pmatrix} \frac{1}{\sqrt{a_{11}}} & & & 0 \\ & \frac{1}{\sqrt{a_{22}}} & & \\ & & \ddots & \\ 0 & & & \frac{1}{\sqrt{a_{nn}}} \end{pmatrix}$$ has only ones on the diagonal, right? And it is positive definite? Does that mean that all eigenvalues of this matrix are one? – lballes May 15 '17 at 15:34
• @lballes Yes, it has only ones on the diagonal. Its elements are $a_{ij}/\sqrt{a_{ii}a_{jj}}$. Yes, it is positive definite, because $y\neq 0 \Rightarrow Dy \neq 0 \Rightarrow y^T(DAD)y = (Dy)^TA(Dy) > 0$ with $D=diag(1/\sqrt{a_{11}},\ldots,1/\sqrt{a_{nn}}).$ No, the eigenvalues are not necessarily all $1$. Example $\begin{pmatrix} 1 & 0.5 \\ 0.5 & 1\end{pmatrix}$ which has eigenvalues $1.5$ and $0.5$ – Reinhard Meier May 15 '17 at 15:48
• We can also show that the best $c$, which is independent of $A$, is indeed $n$, as Omnomnomnom stated. The largest eigenvalue of $DAD$ can get arbitrarily close to $n$, if $A$ is a matrix with $1$ on the diagonal and $1-\epsilon$ everywhere else ($\epsilon$ must be a small number > 0). This matrix has the eigenvalue $n-(n-1)\epsilon$ with multiplicity $1$ and the eigenvalue $\epsilon$ with multiplicity $n-1$. – Reinhard Meier May 15 '17 at 16:04