Bounding matrix quadratic form using eigenvalues

Dependencies:

  1. Matrix
  2. Eigenvalues and Eigenvectors
  3. All eigenvalues of a hermitian matrix are real
  4. Orthogonally diagonalizable iff hermitian
  5. Matrix multiplication is associative
  6. Transpose of product

Let $A$ be a $n$ by $n$ real symmetric matrix. Let $\lambda_{\textrm{min}}$ and $\lambda_{\textrm{max}}$ be the minimum and maximum eigenvalues of $A$ and $v_{\textrm{min}}$ and $v_{\textrm{max}}$ be the corresponding eigenvectors. Then \[ \forall u \in \mathbb{R}^n, \lambda_{\textrm{min}}u^Tu \le u^TAu \le \lambda_{\textrm{max}}u^Tu \] Also, \[ v_{\textrm{min}}^TAv_{\textrm{min}} = \lambda_{\textrm{min}}v_{\textrm{min}}^Tv_{\textrm{min}} \bigwedge v_{\textrm{max}}^TAv_{\textrm{max}} = \lambda_{\textrm{max}}v_{\textrm{max}}^Tv_{\textrm{max}} \] so the above bound is tight.

Proof

\[ v_{\textrm{min}}^TAv_{\textrm{min}} = v_{\textrm{min}}^T(\lambda_{\textrm{min}}v_{\textrm{min}}) = \lambda_{\textrm{min}}v_{\textrm{min}}^Tv_{\textrm{min}} \] \[ v_{\textrm{max}}^TAv_{\textrm{max}} = v_{\textrm{max}}^T(\lambda_{\textrm{max}}v_{\textrm{max}}) = \lambda_{\textrm{max}}v_{\textrm{max}}^Tv_{\textrm{max}} \]

Since $A$ is real and symmetric, it is orthogonally diagonalizable. Specifically, let $[v_1, v_2, \ldots, v_n]$ be $n$ orthonormal eigenvectors of $A$ and let $[\lambda_1, \lambda_2, \ldots, \lambda_n]$ be the corresponding eigenvalues. Let $P$ be the matrix whose $i^{\textrm{th}}$ column is $v_i$ and let $D$ be a diagonal matrix whose $i^{\textrm{th}}$ diagonal entry is $\lambda_i$. Then $P$ and $D$ are real and $A = PDP^T$ and $P^TP = I$.

Let $v = P^Tu$. Then \[ v^Tv = (P^Tu)^T(P^Tu) = u^T(PP^T)u = u^Tu \] \[ u^TAu = u^T(PDP^T)u = (P^Tu)^TD(P^Tu) = v^TDv = \sum_{i=1}^n \lambda_i v_i^2 \]

Without loss of generality, assume that $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$. \begin{align} & \forall i, \lambda_n \le \lambda_i \le \lambda_1 \\ &\Rightarrow \sum_{i=1}^n \lambda_n v_i^2 \le \sum_{i=1}^n \lambda_i v_i^2 \le \sum_{i=1}^n \lambda_1 v_i^2 \\ &\Rightarrow \lambda_n v^Tv \le \sum_{i=1}^n \lambda_i v_i^2 \le \lambda_1 v^Tv \\ &\Rightarrow \lambda_n u^Tu \le u^TAu \le \lambda_1 u^Tu \end{align}

Dependency for:

  1. Positive definite iff eigenvalues are positive

Info:

Transitive dependencies:

  1. /linear-algebra/eigenvectors/cayley-hamilton-theorem
  2. /misc/fundamental-theorem-of-algebra
  3. /complex-numbers/complex-numbers
  4. /linear-algebra/matrices/gauss-jordan-algo
  5. /linear-algebra/vector-spaces/condition-for-subspace
  6. /complex-numbers/conjugate-product-abs
  7. /complex-numbers/conjugation-is-homomorphic
  8. /sets-and-relations/equivalence-relation
  9. /sets-and-relations/composition-of-bijections-is-a-bijection
  10. Group
  11. Ring
  12. Polynomial
  13. Vector
  14. Dot-product of vectors
  15. Field
  16. Vector Space
  17. Inner product space
  18. Orthogonality and orthonormality
  19. Inner product is anti-linear in second argument
  20. Linear independence
  21. A set of mutually orthogonal vectors is linearly independent
  22. Incrementing a linearly independent set
  23. Span
  24. Gram-Schmidt Process
  25. Linear transformation
  26. Composition of linear transformations
  27. Vector space isomorphism is an equivalence relation
  28. Symmetric operator
  29. 0x = 0 = x0
  30. Integral Domain
  31. Comparing coefficients of a polynomial with disjoint variables
  32. A field is an integral domain
  33. Semiring
  34. Matrix
  35. Stacking
  36. System of linear equations
  37. Transpose of stacked matrix
  38. Product of stacked matrices
  39. Matrix multiplication is associative
  40. Trace of a matrix
  41. Conjugation of matrices is homomorphic
  42. Transpose of product
  43. Reduced Row Echelon Form (RREF)
  44. Submatrix
  45. Determinant
  46. Swapping last 2 rows of a matrix negates its determinant
  47. Determinant of upper triangular matrix
  48. Conjugate Transpose and Hermitian
  49. Elementary row operation
  50. Determinant after elementary row operation
  51. Every elementary row operation has a unique inverse
  52. Row equivalence of matrices
  53. Matrices over a field form a vector space
  54. Row space
  55. Row equivalent matrices have the same row space
  56. RREF is unique
  57. Matrices form an inner-product space
  58. Identity matrix
  59. Full-rank square matrix in RREF is the identity matrix
  60. Inverse of a matrix
  61. Inverse of product
  62. Elementary row operation is matrix pre-multiplication
  63. Row equivalence matrix
  64. Equations with row equivalent matrices have the same solution set
  65. Basis of a vector space
  66. Linearly independent set is not bigger than a span
  67. Homogeneous linear equations with more variables than equations
  68. Rank of a homogenous system of linear equations
  69. Rank of a matrix
  70. Basis of F^n
  71. Matrix of linear transformation
  72. A set of dim(V) linearly independent vectors is a basis
  73. Linearly independent set can be expanded into a basis
  74. Coordinatization over a basis
  75. Basis changer
  76. Basis change is an isomorphic linear transformation
  77. Vector spaces are isomorphic iff their dimensions are same
  78. Canonical decomposition of a linear transformation
  79. Eigenvalues and Eigenvectors
  80. Diagonalization
  81. All eigenvalues of a hermitian matrix are real
  82. All eigenvalues of a symmetric operator are real
  83. Real matrix with real eigenvalues has real eigenvectors
  84. Symmetric operator iff hermitian
  85. A matrix is full-rank iff its determinant is non-0
  86. Characteristic polynomial of a matrix
  87. Degree and monicness of a characteristic polynomial
  88. Full-rank square matrix is invertible
  89. AB = I implies BA = I
  90. Determinant of product is product of determinants
  91. Every complex matrix has an eigenvalue
  92. Symmetric operator on V has a basis of orthonormal eigenvectors
  93. Orthogonal matrix
  94. Orthogonally diagonalizable iff hermitian