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