napkin solutions > Ch. 9

Back to Chapter Selection

Table of Contents

  1. 9.4.5
  2. Problem 9C
  3. Problem 9G

9.4.5 #

Theorem 9.4.5 (Maximality and minimality of bases)Let 𝑉 be a vector space over some field 𝑘 and take 𝑒1,…,𝑒𝑛∈𝑉. The following are equivalent:(a)The 𝑒𝑖 form a basis.(b)The 𝑒𝑖 are spanning, but no proper subset is spanning.(c)The 𝑒𝑖 are linearly independent, but adding any other element of 𝑉 makes them not linearly independent.Solution by kiwiyou(a) ⟹ (b)By definition of a basis, for all 𝑣∈𝑉, 𝑣=∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖 for unique 𝑎𝑖∈𝑘. It is clear that {𝑒𝑖} is spanning.Suppose that 𝑆={𝑒𝑖}𝑚𝑖=1 is spanning for some 𝑚<𝑛.Since 𝑆 is spanning, there exists 𝑏𝑖 such that 𝑒𝑛=∑𝑚𝑖=1𝑏𝑖⋅𝑒𝑖.𝑒𝑛 has two different representations, which is a contradiction.Therefore, {𝑒𝑖} is spanning, but no proper subset is spanning.∎(a) ⟹ (c)It is clear that {𝑒𝑖} is linearly independent. Also, every nonzero vector 𝑣∈𝑉 has a unique representation with at least one nonzero coefficient.Let 𝑣=∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖 be the representation of 𝑣 in {𝑒𝑖}.Since 0=(−1)𝑣𝑖+∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖, {𝑒𝑖}∪{𝑣} is not linearly independent.∎(b) ⟹ (a)Suppose that there exists a vector 𝑣0∈𝑉 with two different representations. In other words, there exists 𝑎𝑖,𝑏𝑖 such that 𝑣0=∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖=∑𝑛𝑖=1𝑏𝑖⋅𝑒𝑖 for some 𝑎𝑖,𝑏𝑖∈𝑘 and, without loss of generality, 𝑎𝑛≠𝑏𝑛.For all 𝑣∈𝑉, let 𝑣=∑𝑛𝑖=1𝑐𝑖⋅𝑒𝑖 be the representation of 𝑣 in 𝑆. Then we have:𝑣=𝑣+0=∑𝑛𝑖=1𝑐𝑖⋅𝑒𝑖+𝑐𝑛𝑎𝑛−𝑏𝑛∑𝑛𝑖=1(𝑎𝑖−𝑏𝑖)⋅𝑒𝑖=∑𝑛𝑖=1(𝑐𝑖+𝑐𝑛𝑎𝑛−𝑏𝑛(𝑎𝑖−𝑏𝑖))⋅𝑒𝑖Since the coefficient of 𝑒𝑛 is always 0, {𝑒𝑖}𝑛−1𝑖=1 is spanning. This is a contradiction.Therefore all vectors have unique representations in 𝑆.∎Bonus: (c) ⟹ (a)For all 𝑣∈𝑉∖{𝑒𝑖}, {𝑒𝑖}∪{𝑣} is not linear independent, which means there exists 𝑐≠0 and 𝑎𝑖 such that 0=𝑐⋅𝑣+∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖.Then every vector has its representation:𝑣=∑𝑛𝑖=1−𝑎𝑖𝑐⋅𝑒𝑖If 𝑣 has two different representations, then 0=𝑣−𝑣 has two different representations, which is a contra­diction.Therefore, every vector has a unique representation.∎Notice the use of division in the proofs (b) ⟹ (a) and (c) ⟹ (a). This shows why we need the field instead of a commutative ring.

Problem 9C #

Problem 9C. Let’s say a magic square is a 3×3 matrix of real numbers where the sum of all diagonals, columns, and rows is equal, such as [834159672]. Find the dimension of the set of margin squares, as a real vector space under addition.Solution by RanolPTheorem 9.7.7 (Rank-nullity theorem)Let 𝑉 and 𝑊 be finite-dimensional vector spaces. If 𝑇:𝑉→𝑊, thendim𝑉=dimker𝑇+dimim𝑇Let’s say the vector space as 𝑉, consider following linear map𝑇=[𝑎𝑖𝑗]↦𝑎00+𝑎01+𝑎02:𝑉→ℝSince we know it’s 𝑉 is finite-dimensional because 𝑉⊆ℝ9, we can apply rank-nullity theorem.dim𝑉=dimker𝑇++dimim𝑇=dimker𝑇+dimℝ=dimker𝑇+1Now we need to find dimension of ker𝑇, which is the dimension of magic square with sum 0. Consider another linear map 𝑄𝑄=[𝑎𝑖𝑗]↦𝑎00:𝑉→ℝdimker𝑇=dimker𝑄+dimim𝑄=dimker𝑄+dimℝ=dimker𝑄+1And then we have following matrix.[0𝑦−𝑦𝑥𝑧−𝑥−𝑧−𝑥−𝑦−𝑧𝑥+𝑦+𝑧]Since we know 0+𝑧+(𝑥+𝑦+𝑧)=0, 𝑥=−𝑦−2𝑧. Substitute 𝑥 and simplify.[0𝑦−𝑦−𝑦−2𝑧𝑧𝑦+𝑧𝑦+2𝑧−𝑦−𝑧−𝑧]Since we know (−𝑦)+𝑧+(𝑦+2𝑧)=0, 3𝑧=0, Substitute 𝑧 and simplify.[0𝑦−𝑦−𝑦0𝑦𝑦−𝑦0]Use rank-nulllity theorem again! Now consider following linear map𝑅:[𝑎𝑖𝑗]↦𝑎02:ker𝑄→ℝdimker𝑄=dimker𝑅+dimim𝑅=dimker𝑅+dimℝ=dimker𝑅+1.𝑦=0 for ker𝑅. So ker𝑅={[000000000]}, which is zero-dimensional.Thus, dim𝑉=dimker𝑅+dimim𝑅+dimim𝑄+dimim𝑇=0+1+1+1=3.

Problem 9G #

Problem 9G (TSTST 2014). Let 𝑃(𝑥) and 𝑄(𝑥) be arbitrary polynomials with real coefficients, and let 𝑑 be the degree of 𝑃(𝑥). Assume that 𝑃(𝑥) is not the zero polynomial.. Prove that there exist polynomials 𝐴(𝑥) and 𝐵(𝑥) such that.(i)Both 𝐴 and 𝐵 have degree at most 𝑑/2,(ii)At most one of 𝐴 and 𝐵 is the zero polynomial,(iii)𝑃 divdes 𝐴+𝑄⋅𝐵Solution by RanolPPowered by Gemini™Theorem 9.7.7 (Rank-nullity theorem)Let 𝑉 and 𝑊 be finite-dimensional vector spaces. If 𝑇:𝑉→𝑊, thendim𝑉=dimker𝑇+dimim𝑇At most 𝑘-degree polynomial vector space is isomorphic to ℝ𝑘+1.Consider 𝑉=ℝ⊕(⌊𝑑/2⌋)+1×ℝ⊕(⌊𝑑/2⌋+1), 𝑊=ℝ⊕𝑑, and a linear map𝑇=(𝐴,𝐵)↦(𝐴+𝑄⋅𝐵)mod𝑃:𝑉→𝑊By rank-nullity theoremdim𝑉=dimker𝑇+dimim𝑇2(⌊𝑑/2⌋+1)=dimker𝑇+dimim𝑇In other words, dimker𝑇=2(⌊𝑑/2⌋+1)−dimim𝑇.In this case, im𝑇⊆ℝ⊕𝑑 so dimim𝑇≤𝑑. For evaluating dimker𝑇, choose the maximal value 𝑑.Let’s case work to evaluate dimker𝑇,•𝑑 is even: dimker𝑇≥𝑑+2−𝑑=2•𝑑 is odd: dimker𝑇≥(𝑑−1)+2−𝑑=1Thus, dimker𝑇≥1.Since ker𝑇 is non-trivial, there exists non-zero (𝐴,𝐵)∈𝑉.In other words, there exist non-zero 𝐴 or non-zero 𝐵.