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/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. Positive definite
41. Sum of positive definite matrices is positive definite
42. Reduced Row Echelon Form (RREF)
43. Conjugate Transpose and Hermitian
44. Transpose of product
45. Conjugation of matrices is homomorphic
46. Submatrix
47. Determinant
48. Determinant of upper triangular matrix
49. Swapping last 2 rows of a matrix negates its determinant
50. Trace of a matrix
51. Matrices over a field form a vector space
52. Row space
53. Matrices form an inner-product space
54. Elementary row operation
55. Determinant after elementary row operation
56. Every elementary row operation has a unique inverse
57. Row equivalence of matrices
58. Row equivalent matrices have the same row space
59. RREF is unique
60. Identity matrix
61. Inverse of a matrix
62. Inverse of product
63. Elementary row operation is matrix pre-multiplication
64. Row equivalence matrix
65. Equations with row equivalent matrices have the same solution set
66. Basis of a vector space
67. Linearly independent set is not bigger than a span
68. Homogeneous linear equations with more variables than equations
69. Rank of a homogenous system of linear equations
70. Rank of a matrix
71. A set of dim(V) linearly independent vectors is a basis
72. Basis of F^n
73. Matrix of linear transformation
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. All eigenvalues of a hermitian matrix are real
81. All eigenvalues of a symmetric operator are real
82. Real matrix with real eigenvalues has real eigenvectors
83. Diagonalization
84. Symmetric operator iff hermitian
85. Linearly independent set can be expanded into a basis
86. Full-rank square matrix in RREF is the identity matrix
87. A matrix is full-rank iff its determinant is non-0
88. Characteristic polynomial of a matrix
89. Degree and monicness of a characteristic polynomial
90. Full-rank square matrix is invertible
91. AB = I implies BA = I
92. Determinant of product is product of determinants
93. Every complex matrix has an eigenvalue
94. Symmetric operator on V has a basis of orthonormal eigenvectors
95. Orthogonal matrix
96. Orthogonally diagonalizable iff hermitian
97. Bounding matrix quadratic form using eigenvalues
98. Positive definite iff eigenvalues are positive
99. Eigenpair of affine transformation