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 representationwith 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 that0=𝑐⋅𝑣+∑𝑛𝑖=1𝑎𝑖⋅𝑒𝑖.Then every vector has its representation:𝑣=∑𝑛𝑖=1−𝑎𝑖𝑐⋅𝑒𝑖If 𝑣 has two different representations, then 0=𝑣−𝑣 has two different representations, which is a contradiction.Therefore, every vector has a unique representation.∎Notice the use of division in the proofs (b) ⟹ (a) and (c) ⟹ (a). This shows why we needthe 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 vectorspace 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 anotherlinear 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 𝐵.