4
$\begingroup$

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?

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

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} $$

$\endgroup$
  • $\begingroup$ $$ \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? $\endgroup$ – lballes May 15 '17 at 15:34
  • $\begingroup$ @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$ $\endgroup$ – Reinhard Meier May 15 '17 at 15:48
  • $\begingroup$ 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$. $\endgroup$ – Reinhard Meier May 15 '17 at 16:04

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.