Bound on eigenvalues of sum of matrices

Dependencies:

1. Eigenvalues and Eigenvectors
2. Eigenpair of affine transformation
3. Positive definite iff eigenvalues are positive
4. All eigenvalues of a hermitian matrix are real
5. Identity matrix
6. Sum of positive definite matrices is positive definite

Let $A$ and $B$ be real $n$ by $n$ symmetric matrices. Then $A$, $B$ and $A+B$ have real eigenvalues.

• Let $\lambda^-$ and $\lambda^+$ be the minimum and maximum eigenvalues of $A$.
• Let $\mu^-$ and $\mu^+$ be the minimum and maximum eigenvalues of $B$.
• Let $\gamma^-$ and $\gamma^+$ be the minimum and maximum eigenvalues of $A+B$.

Then \[ \lambda^- + \mu^- \le \gamma^- \le \gamma^+ \le \lambda^+ + \mu^+ \]

Proof

Let $\lambda(X)$ be the set of eigenvalues of matrix $X$.

\begin{align} & \lambda(A) \in [\lambda^-, \lambda^+] \wedge \lambda(B) \in [\mu^-, \mu^+] \\ &\Rightarrow \lambda(A-\lambda^-I) \subseteq [0, \lambda^+ - \lambda^-] \wedge \lambda(B-\mu^-I) \subseteq [0, \mu^+ - \mu^-] \tag{affine transformation} \\ &\Rightarrow (A-\lambda^-I) \textrm{ is PSD } \wedge (B-\mu^-I) \textrm{ is PSD} \\ &\Rightarrow (A-\lambda^-I) + (B - \mu^-I) \textrm{ is PSD} \\ &\Rightarrow (A + B) - (\lambda^- + \mu^-)I \textrm{ is PSD} \\ &\Rightarrow \lambda((A + B) - (\lambda^- + \mu^-)I) \subseteq [0, \infty) \\ &\Rightarrow \lambda(A + B) \subseteq [\lambda^- + \mu^-, \infty) \end{align}

\begin{align} & \lambda(A) \in [\lambda^-, \lambda^+] \wedge \lambda(B) \in [\mu^-, \mu^+] \\ &\Rightarrow \lambda(A-\lambda^+I) \subseteq [\lambda^- - \lambda^+, 0] \wedge \lambda(B-\mu^+I) \subseteq [\mu^- - \mu^+, 0] \tag{affine transformation} \\ &\Rightarrow (A-\lambda^+I) \textrm{ is NSD } \wedge (B-\mu^-I) \textrm{ is NSD} \\ &\Rightarrow (A-\lambda^+I) + (B - \mu^+I) \textrm{ is NSD} \\ &\Rightarrow (A + B) - (\lambda^+ + \mu^+)I \textrm{ is NSD} \\ &\Rightarrow \lambda((A + B) - (\lambda^+ + \mu^+)I) \subseteq (-\infty, 0] \\ &\Rightarrow \lambda(A + B) \subseteq (-\infty, \lambda^+ + \mu^+] \end{align}

Therefore, $\lambda(A+B) \subseteq [\lambda^- + \mu^-, \lambda^+ + \mu^+]$.

Dependency for: None

Info:

• Depth: 19
• Number of transitive dependencies: 99

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. Positive definite
54. Sum of positive definite matrices is positive definite
55. Matrices over a field form a vector space
56. Row space
57. Row equivalent matrices have the same row space
58. RREF is unique
59. Matrices form an inner-product space
60. Identity matrix
61. Full-rank square matrix in RREF is the identity matrix
62. Inverse of a matrix
63. Inverse of product
64. Elementary row operation is matrix pre-multiplication
65. Row equivalence matrix
66. Equations with row equivalent matrices have the same solution set
67. Basis of a vector space
68. Linearly independent set is not bigger than a span
69. Homogeneous linear equations with more variables than equations
70. Rank of a homogenous system of linear equations
71. Rank of a matrix
72. Basis of F^n
73. Matrix of linear transformation
74. A set of dim(V) linearly independent vectors is a basis
75. Linearly independent set can be expanded into a basis
76. Coordinatization over a basis
77. Basis changer
78. Basis change is an isomorphic linear transformation
79. Vector spaces are isomorphic iff their dimensions are same
80. Canonical decomposition of a linear transformation
81. Eigenvalues and Eigenvectors
82. Diagonalization
83. All eigenvalues of a hermitian matrix are real
84. All eigenvalues of a symmetric operator are real
85. Eigenpair of affine transformation
86. Real matrix with real eigenvalues has real eigenvectors
87. Symmetric operator iff hermitian
88. A matrix is full-rank iff its determinant is non-0
89. Characteristic polynomial of a matrix
90. Degree and monicness of a characteristic polynomial
91. Full-rank square matrix is invertible
92. AB = I implies BA = I
93. Determinant of product is product of determinants
94. Every complex matrix has an eigenvalue
95. Symmetric operator on V has a basis of orthonormal eigenvectors
96. Orthogonal matrix
97. Orthogonally diagonalizable iff hermitian
98. Bounding matrix quadratic form using eigenvalues
99. Positive definite iff eigenvalues are positive