Math 2.0

Linear and multilinear algebra; matrix theory Proof

Proof of the decomposition into generalised eigenspaces

Builds on Generalised eigenspaceDirect sum of subspacesPolynomial of an endomorphismCayley–Hamilton theorem for linear mapsK[x] is a Euclidean domainEuclidean domains are principal ideal domainsPrincipal ideal domainPID implies UFDUnique factorisation domainIrreducible polynomialIdeal generated by a subsetKernel of a linear mapInvariant subspaceRestriction of an endomorphism to an invariant subspaceMatrix of a linear mapBlock diagonal matrixDeterminant of a block triangular matrixCharacteristic polynomial of a linear mapEigenvalues are the roots of the characteristic polynomialBasis

Proof

We split VV with polynomials in TT that add up to the identity, as in the primary decomposition. Then we compute the dimensions from the characteristic polynomial.

  1. Write p=pTp = p_T, qi=(t−λi)miq_i = (t - \lambda_i)^{m_i} and fi=∏j≠iqjf_i = \prod_{j \ne i} q_j, so p=qifip = q_i f_i for each ii. Let Wi=ker⁡qi(T)W_i = \ker q_i(T), a kernel in VV.
  2. The ring F[t]F[t] is a Euclidean domain, hence a principal ideal domain, hence a unique factorisation domain. Each t−ct - c is an irreducible polynomial, since it has degree 11. Distinct monic polynomials t−ct - c are not associates.
  3. By step 2 and the uniqueness of factorisations, each monic divisor of ∏j(t−λj)mj\prod_j (t - \lambda_j)^{m_j} has the form ∏j(t−λj)ej\prod_j (t - \lambda_j)^{e_j} with 0≤ej≤mj0 \le e_j \le m_j. The same holds for monic divisors of (t−c)N(t - c)^N, with a single factor.
  4. The ideal generated by f1,…,fkf_1, \dots, f_k is principal and nonzero, so it is generated by a monic dd. Then dd divides each fif_i and pp.
  5. By step 3, d=∏j(t−λj)ejd = \prod_j (t - \lambda_j)^{e_j}. Since dd divides fif_i, and t−λit - \lambda_i does not occur in the factorisation of fif_i, uniqueness gives ei=0e_i = 0. This holds for each ii, so d=1d = 1.
  6. Hence there are a1,…,ak∈F[t]a_1, \dots, a_k \in F[t] with ∑iaifi=1\sum_i a_i f_i = 1. Let πi=ai(T)fi(T)\pi_i = a_i(T) f_i(T). Evaluation at TT respects sums and products, so ∑iπi=id⁡V\sum_i \pi_i = \id_V, by the definition of the value at TT.
  7. Polynomials in TT commute with each other. So each WiW_i is mapped into itself by every polynomial in TT. In particular, WiW_i is TT-invariant.
  8. Let v∈Vv \in V. Then qi(T)πi(v)=ai(T)p(T)(v)=0q_i(T) \pi_i(v) = a_i(T) p(T)(v) = 0 by the Cayley–Hamilton theorem. So πi(v)∈Wi\pi_i(v) \in W_i, and v=∑iπi(v)v = \sum_i \pi_i(v) lies in W1+⋯+WkW_1 + \cdots + W_k.
  9. Let w∈Wjw \in W_j and i≠ji \ne j. Then qjq_j divides fif_i, so πi(w)=0\pi_i(w) = 0. With step 6, w=πj(w)w = \pi_j(w).
  10. Let wj∈Wjw_j \in W_j with ∑jwj=0\sum_j w_j = 0. Applying πl\pi_l and using step 9 gives wl=πl(0)=0w_l = \pi_l(0) = 0 for each ll. With step 8, V=W1⊕⋯⊕WkV = W_1 \oplus \cdots \oplus W_k as a direct sum.
  11. We show Wi=VλiW_i = V_{\lambda_i}, the generalised eigenspace. If mi≥1m_i \ge 1, the definition gives Wi⊆VλiW_i \subseteq V_{\lambda_i} with exponent mim_i. If mi=0m_i = 0, then Wi=ker⁡id⁡V=0W_i = \ker \id_V = 0.
  12. Conversely, let v∈Vλiv \in V_{\lambda_i}, with (T−λiid⁡V)N(v)=0(T - \lambda_i \id_V)^N (v) = 0. Let j≠ij \ne i and u=πj(v)u = \pi_j(v). By step 7, (T−λiid⁡V)N(u)=πj((T−λiid⁡V)N(v))=0(T - \lambda_i \id_V)^N (u) = \pi_j\big((T - \lambda_i \id_V)^N (v)\big) = 0. Also qj(T)(u)=0q_j(T)(u) = 0 by step 8.
  13. The ideal generated by (t−λi)N(t - \lambda_i)^N and qjq_j has a monic generator d′d'. By step 3, d′d' divides qjq_j, so d′=(t−λj)ed' = (t - \lambda_j)^e. It also divides (t−λi)N(t - \lambda_i)^N, so uniqueness gives e=0e = 0 and d′=1d' = 1.
  14. So 1=b(t−λi)N+cqj1 = b (t - \lambda_i)^N + c q_j for some b,c∈F[t]b, c \in F[t]. Applying this to uu gives u=0u = 0 by step 12.
  15. Hence πj(v)=0\pi_j(v) = 0 for j≠ij \ne i, and v=πi(v)∈Wiv = \pi_i(v) \in W_i by step 8. So Wi=VλiW_i = V_{\lambda_i}, and V=Vλ1⊕⋯⊕VλkV = V_{\lambda_1} \oplus \cdots \oplus V_{\lambda_k}.
  16. Let di=dim⁡Wid_i = \dim W_i, and choose a basis of each WiW_i. Their concatenation BB spans VV by step 8. It is linearly independent, because a relation splits into vectors wi∈Wiw_i \in W_i with sum 00, so each wi=0w_i = 0 by step 10.
  17. Let Ti=T∣WiT_i = T|_{W_i} be the restriction, and let AiA_i be its matrix in the chosen basis of WiW_i. By step 7, the matrix of TT in BB is the block diagonal matrix diag⁡(A1,…,Ak)\operatorname{diag}(A_1, \dots, A_k). Blocks with di=0d_i = 0 are omitted, and we set pAi=1p_{A_i} = 1 for them.
  18. The matrix tI−diag⁡(A1,…,Ak)t I - \operatorname{diag}(A_1, \dots, A_k) is block diagonal with blocks tI−Ait I - A_i. Using the determinant of a block triangular matrix k−1k - 1 times, pT=∏ipAip_T = \prod_i p_{A_i}, by the definition of pTp_T.
  19. Let w∈Wiw \in W_i be nonzero with T(w)=μwT(w) = \mu w. Then 0=qi(T)(w)=(μ−λi)miw0 = q_i(T)(w) = (\mu - \lambda_i)^{m_i} w, so μ=λi\mu = \lambda_i. Thus λi\lambda_i is the only possible eigenvalue of TiT_i.
  20. The polynomial pAip_{A_i} is monic of degree did_i and divides pTp_T by step 18. By step 3, pAi=∏j(t−λj)eijp_{A_i} = \prod_j (t - \lambda_j)^{e_{ij}}.
  21. If eij>0e_{ij} > 0 for some j≠ij \ne i, then λj\lambda_j is a root of pAip_{A_i}. By the roots of the characteristic polynomial, it is an eigenvalue of TiT_i. This contradicts step 19, since λj≠λi\lambda_j \ne \lambda_i.
  22. So pAi=(t−λi)dip_{A_i} = (t - \lambda_i)^{d_i}, by comparing degrees. Then step 18 gives ∏i(t−λi)di=pT=∏i(t−λi)mi\prod_i (t - \lambda_i)^{d_i} = p_T = \prod_i (t - \lambda_i)^{m_i}.
  23. The t−λit - \lambda_i are pairwise non-associate irreducible elements by step 2. Uniqueness of factorisation in the unique factorisation domain F[t]F[t] gives di=mid_i = m_i for each ii.
  24. So dim⁡Vλi=mi\dim V_{\lambda_i} = m_i, which completes the proof.

Idea

The polynomials fif_i have no common factor, so a combination of them equals 11. Plugging in TT gives maps πi\pi_i that add up to the identity, and Cayley–Hamilton shows that πi\pi_i lands in ker⁡(T−λi)mi\ker (T - \lambda_i)^{m_i}. For the dimensions, TT is block diagonal with one block for each eigenvalue. Each block has characteristic polynomial a power of t−λit - \lambda_i, and unique factorisation matches the exponents.

Reading path

To understand this page from the ground up, read these 285 pages in order. The foundations come first. The path takes the proofs Proof of the Steinitz exchange lemma by induction, Proof of the associativity of matrix multiplication, Proof of cancellation in an integral domain, Proof that a subspace of full dimension is the whole space, Proof of the decomposition of a permutation into transpositions, Proof that the symmetric group is generated by transpositions, Proof of the Laplace expansion along a column by transposition, Proof of the commutativity of addition by induction, Proof that R/P is an integral domain iff P is prime, Proof that equivalence classes form a partition, Proof that every principal ideal domain is a unique factorisation domain, Proof of the distributivity of matrix multiplication, Proof that the matrix of a composition is the product of the matrices, Proof that the determinant is multiplicative by expanding the rows, Proof that permuting rows multiplies the determinant by the sign, Proof that disjoint cycles commute, Proof that R[x] is an integral domain iff R is, Proof that a matrix is invertible iff its determinant is a unit, Proof of the determinant of a block triangular matrix by the Leibniz formula, Proof that a function is bijective iff it has a two-sided inverse, Proof that a matrix with two equal rows has determinant zero, Proof that maximal ideals are prime, Proof of the Laplace expansion along a row by the Leibniz formula, Proof of the degree of a product over an integral domain, Proof that the coordinate map is a linear isomorphism, Proof of strong induction from ordinary induction, Proof that the determinant of a transpose equals the determinant, Proof of the laws of exponents in a group, Proof of the inverse in terms of the adjugate, Proof of the correspondence theorem for rings, Proof that R/M is a field iff M is maximal, Proof that an injective endomorphism of a finite-dimensional space is surjective, Proof that the only ideals of a field are zero and the whole field, Proof that an intersection of subgroups is a subgroup, Proof that the sign is a homomorphism, Proof of the determinant of the inverse, Proof that the determinant of the identity matrix is one, Proof that a linear map is injective iff its kernel is trivial, Proof that every linearly independent set extends to a basis, by Zorn's lemma, Proof of Zorn's lemma, Proof of the decomposition of a permutation into disjoint cycles, Proof of the product of a matrix and its adjugate by Laplace expansion, Proof of the well-ordering principle from strong induction, Proof that n independent or n spanning vectors in an n-dimensional space form a basis, Proof of the division algorithm, Proof of the sign of a cycle, Proof of the Leibniz formula from the defining properties of the determinant, Proof of the Cayley–Hamilton theorem for linear maps, Proof of the uniqueness of inverses, Proof that a subspace of a finite-dimensional space has smaller or equal dimension, Proof that in a PID a nonzero element is irreducible iff it generates a maximal ideal, Proof that the determinant is multilinear in the rows, Proof that the eigenvalues are the roots of the characteristic polynomial, Proof of the rank–nullity theorem by extending a basis of the kernel, Proof of the subgroup criterion, Proof of the Cayley–Hamilton theorem with the adjugate, Proof that Euclidean domains are principal ideal domains, Proof that K[x] is a Euclidean domain, Proof that similar matrices have the same characteristic polynomial.

  1. Basis concept
  2. Binary operation definition
  3. Composition of linear maps concept
  4. Coordinate space object
  5. Coordinate vector concept
  6. Cycle notation concept
  7. Definition by recursion concept
  8. Dimension concept
  9. Divisibility definition
  10. Element definition
  11. Group concept
  12. Identity matrix object
  13. Image of a linear map concept
  14. Kernel of a linear map concept
  15. Linear independence concept
  16. Linear isomorphism concept
  17. Linear map concept
  18. Linear subspace concept
  19. Mathematical induction concept
  20. Matrix definition
  21. Matrix multiplication concept
  22. Matrix of a linear map concept
  23. Multilinear map concept
  24. Natural numbers object
  25. Nullity concept
  26. Peano axioms concept
  27. Permutation concept
  28. Permutation definition
  29. Proof of Zorn's lemma proof
  30. Proposition concept
  31. Rank of a linear map concept
  32. Spanning set concept
  33. Transposition concept
  34. Vector space definition
  35. Identity element definition
  36. Set definition
  37. Group homomorphism definition
  38. Ring definition
  39. Subgroup definition
  40. Symmetric group definition
  41. Proof that the matrix of a composition is the product of the matrices proof
  42. Proof that a linear map is injective iff its kernel is trivial proof
  43. Block matrix definition
  44. Matrix addition definition
  45. Matrix multiplication definition
  46. Square matrix definition
  47. Transpose definition
  48. Successor function definition
  49. Conjunction definition
  50. Disjunction definition
  51. Implication definition
  52. Predicate definition
  53. Linear combination definition
  54. Linear map definition
  55. Linear subspace definition
  56. Inverse element definition
  57. Empty set object
  58. Family of sets definition
  59. Ordered pair definition
  60. Commutative ring definition
  61. Polynomial ring definition
  62. Ring homomorphism definition
  63. Unit of a ring definition
  64. Zero divisor definition
  65. Transposition definition
  66. Ideal definition
  67. Proof of the associativity of matrix multiplication proof
  68. Proof that an intersection of subgroups is a subgroup proof
  69. Proof of the distributivity of matrix multiplication proof
  70. Block diagonal matrix definition
  71. Intersection definition
  72. Union definition
  73. Set-builder notation concept
  74. Invertible matrix definition
  75. Addition of natural numbers definition
  76. Biconditional definition
  77. Existential quantifier definition
  78. Universal quantifier definition
  79. Linear independence definition
  80. Composition of linear maps definition
  81. Endomorphism definition
  82. Image of a linear map definition
  83. Kernel of a linear map definition
  84. Linear isomorphism definition
  85. Linear span definition
  86. Multilinear map definition
  87. The successor function is injective statement
  88. Zero is not a successor statement
  89. Sum of subspaces definition
  90. Cartesian product definition
  91. Divisibility in a commutative ring definition
  92. Degree of a polynomial definition
  93. Polynomial evaluation definition
  94. Proof of the uniqueness of inverses proof
  95. Field definition
  96. Integral domain definition
  97. Ideal generated by a subset definition
  98. Prime ideal definition
  99. Disjoint sets definition
  100. Maximal ideal definition
  101. Two-sided ideal definition
  102. Associativity of matrix multiplication statement
  103. Distributivity of matrix multiplication statement
  104. Subset definition
  105. Axiom of extensionality statement
  106. Union of a family of sets definition
  107. Proof of the commutativity of addition by induction proof
  108. A linear map is injective iff its kernel is trivial statement
  109. Similar matrices definition
  110. Order on the natural numbers definition
  111. Uniqueness quantifier definition
  112. Invariant subspace definition
  113. Eigenvalue definition
  114. Polynomial of an endomorphism definition
  115. Spanning set definition
  116. Alternating multilinear map definition
  117. Direct sum of subspaces definition
  118. Leading coefficient definition
  119. Associate elements definition
  120. Prime element definition
  121. Proof of cancellation in an integral domain proof
  122. Evaluation homomorphism definition
  123. Uniqueness of inverses statement
  124. Euclidean domain definition
  125. Irreducible element definition
  126. Binary relation definition
  127. Principal ideal definition
  128. Quotient ring definition
  129. Proof that the only ideals of a field are zero and the whole field proof
  130. Partition of a set definition
  131. Determinant definition
  132. Commutativity of addition statement
  133. Restriction of an endomorphism to an invariant subspace definition
  134. Proof of strong induction from ordinary induction proof
  135. Eigenvector definition
  136. Basis definition
  137. Proof of the Steinitz exchange lemma by induction proof
  138. Finite-dimensional vector space definition
  139. Monic polynomial definition
  140. Proof of the degree of a product over an integral domain proof
  141. Cancellation in an integral domain statement
  142. Unique factorisation domain definition
  143. Irreducible polynomial definition
  144. Proof of the subgroup criterion proof
  145. Principal ideal domain definition
  146. Proof of the laws of exponents in a group proof
  147. Proof that R/P is an integral domain iff P is prime proof
  148. Proof that R/M is a field iff M is maximal proof
  149. Antisymmetric relation definition
  150. Reflexive relation definition
  151. Symmetric relation definition
  152. Transitive relation definition
  153. The only ideals of a field are zero and the whole field statement
  154. Characteristic polynomial definition
  155. Proof that the determinant of the identity matrix is one proof
  156. Proof that a matrix with two equal rows has determinant zero proof
  157. Function definition
  158. Minor definition
  159. Proof that the determinant is multilinear in the rows proof
  160. Coordinate vector definition
  161. Dimension theorem for vector spaces statement
  162. Strong induction statement
  163. Dimension definition
  164. Generalised eigenvector definition
  165. Steinitz exchange lemma statement
  166. Degree of a product statement
  167. Division algorithm for polynomials statement
  168. Subgroup criterion statement
  169. Proof that in a PID a nonzero element is irreducible iff it generates a maximal ideal proof
  170. R/P is an integral domain iff P is prime statement
  171. Laws of exponents in a group statement
  172. Equivalence relation definition
  173. Preorder definition
  174. Determinant of the identity matrix statement
  175. Determinant of a matrix with two equal rows statement
  176. Image of a set definition
  177. Preimage of a set definition
  178. Determinant is multilinear in the rows statement
  179. Choice function definition
  180. Proof of the well-ordering principle from strong induction proof
  181. Codomain definition
  182. Function composition definition
  183. Identity function definition
  184. Injective function definition
  185. Cofactor definition
  186. Matrix of a linear map definition
  187. Proof that a subspace of a finite-dimensional space has smaller or equal dimension proof
  188. Proof that n independent or n spanning vectors in an n-dimensional space form a basis proof
  189. Generalised eigenspace definition
  190. Rank of a linear map definition
  191. Nullity definition
  192. Proof that R[x] is an integral domain iff R is proof
  193. Intersection of subgroups is a subgroup statement
  194. In a PID a nonzero element is irreducible iff it generates a maximal ideal statement
  195. Partial order definition
  196. Proof that disjoint cycles commute proof
  197. Equivalence class definition
  198. Matrix of a composition is the product of matrices statement
  199. Adjugate matrix definition
  200. Axiom of choice statement
  201. Left inverse definition
  202. Right inverse definition
  203. Surjective function definition
  204. Well-ordering principle statement
  205. Characteristic polynomial of a linear map definition
  206. Dimension of a subspace statement
  207. Linearly independent set of the right size is a basis statement
  208. Subgroup generated by a subset definition
  209. R[x] is an integral domain iff R is statement
  210. Maximal element definition
  211. Total order definition
  212. Upper bound definition
  213. Disjoint cycles commute statement
  214. Proof that Euclidean domains are principal ideal domains proof
  215. Proof that equivalence classes form a partition proof
  216. Proof of the division algorithm proof
  217. Bijective function definition
  218. Proof that a subspace of full dimension is the whole space proof
  219. Proof that K[x] is a Euclidean domain proof
  220. Chain definition
  221. Euclidean domains are principal ideal domains statement
  222. Division algorithm statement
  223. Equivalence classes form a partition statement
  224. Proof of the correspondence theorem for rings proof
  225. Proof that a function is bijective iff it has a two-sided inverse proof
  226. A subspace of full dimension is the whole space statement
  227. K[x] is a Euclidean domain statement
  228. Proof of the decomposition of a permutation into disjoint cycles proof
  229. Correspondence theorem for rings statement
  230. Bijective iff it has a two-sided inverse statement
  231. Zorn's lemma statement
  232. Decomposition of a permutation into disjoint cycles statement
  233. Proof that the coordinate map is a linear isomorphism proof
  234. R/M is a field iff M is maximal statement
  235. Proof that every linearly independent set extends to a basis, by Zorn's lemma proof
  236. Proof of the decomposition of a permutation into transpositions proof
  237. Proof that maximal ideals are prime proof
  238. Every linearly independent set extends to a basis statement
  239. Isomorphism with the coordinate space statement
  240. Decomposition of a permutation into transpositions statement
  241. Maximal ideals are prime statement
  242. Proof of the rank–nullity theorem by extending a basis of the kernel proof
  243. Sign of a permutation definition
  244. Proof that the symmetric group is generated by transpositions proof
  245. Proof that every principal ideal domain is a unique factorisation domain proof
  246. Rank–nullity theorem statement
  247. The symmetric group is generated by transpositions statement
  248. Proof that the sign is a homomorphism proof
  249. PID implies UFD statement
  250. Proof of the sign of a cycle proof
  251. Proof that an injective endomorphism of a finite-dimensional space is surjective proof
  252. Sign is a homomorphism statement
  253. Sign of a cycle statement
  254. An injective endomorphism of a finite-dimensional space is surjective statement
  255. Proof that permuting rows multiplies the determinant by the sign proof
  256. Permuting rows multiplies the determinant by the sign statement
  257. Proof of the Leibniz formula from the defining properties of the determinant proof
  258. Leibniz formula for determinants statement
  259. Proof of the determinant of a block triangular matrix by the Leibniz formula proof
  260. Proof of the Laplace expansion along a row by the Leibniz formula proof
  261. Proof that the determinant is multiplicative by expanding the rows proof
  262. Proof that the determinant of a transpose equals the determinant proof
  263. Determinant of a block triangular matrix statement
  264. Determinant is multiplicative statement
  265. Determinant of a transpose statement
  266. Laplace expansion along a row statement
  267. Proof of the determinant of the inverse proof
  268. Proof of the Laplace expansion along a column by transposition proof
  269. Proof that similar matrices have the same characteristic polynomial proof
  270. Determinant of the inverse statement
  271. Laplace expansion along a column statement
  272. Characteristic polynomial does not depend on the basis statement
  273. Proof of the product of a matrix and its adjugate by Laplace expansion proof
  274. Product of a matrix and its adjugate statement
  275. Proof of the inverse in terms of the adjugate proof
  276. Proof of the Cayley–Hamilton theorem with the adjugate proof
  277. Inverse in terms of the adjugate statement
  278. Cayley–Hamilton theorem statement
  279. Proof that a matrix is invertible iff its determinant is a unit proof
  280. Proof of the Cayley–Hamilton theorem for linear maps proof
  281. A matrix is invertible iff its determinant is a unit statement
  282. Cayley–Hamilton theorem for linear maps statement
  283. Proof that the eigenvalues are the roots of the characteristic polynomial proof
  284. Eigenvalues are the roots of the characteristic polynomial statement
  285. Proof of the decomposition into generalised eigenspaces proof

Where this leads

1 page builds on this one.

Further reading

  1. Web https://kconrad.math.uconn.edu/blurbs/linmultialg/minpolyandappns.pdf, Proof of Theorem 4.17
About this page