Definition and Theorems (Chapter 4)

christangdt留下评论

Definition. Let F be a field. A linear algebra over the field F is a vector space \Large{\frak a} over F with an additional operation called multiplication of vectors which associates with each pair of vectors \alpha, \beta in \Large{\frak a} a vector \alpha\beta in \Large{\frak a} called the product of \alpha and \beta in such a way that
( a ) multiplication is associative,

\displaystyle{\alpha(\beta\gamma)=(\alpha\beta)\gamma}

( b ) multiplication is distributive with respect to addition,

\displaystyle{\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma\quad\text{and}\quad(\alpha+\beta)\gamma=\alpha\gamma+\beta\gamma}

( c ) for each scalar c in F,

\displaystyle{c(\alpha\beta)=(c\alpha)\beta=\alpha(c\beta).}

If there is an element 1 in \Large{\frak a} such that 1\alpha=\alpha1=\alpha for each \alpha in \Large{\frak a}, we call \Large{\frak a} a linear algebra with identity over F, and call 1 the identity of \Large{\frak a}. The algebra \Large{\frak a} is called commutative if \alpha\beta=\beta\alpha for all \alpha and \beta in \Large{\frak a}.

Definition. Let F[x] be the subspace of F^{\infty} spanned by the vectors 1,x,x^2,\dots. An element of F[x] is called a polynomial over F.

Theorem 1. Let f and g be non-zero polynomials over F. Then
( i ) fg is a non-zero polynomial;
( ii ) \deg (fg)=\deg f+\deg g;
( iii ) fg is a monic polynomial if both f and g are monic polynomials;
( iv ) fg is a scalar polynomial if both f and g are scalar polynomials;
( v ) if f+g\neq 0, \deg (f+g) \leq \max(\deg f,\deg g).
Corollary 1. The set of all polynomials over a given field F equipped with the opertations

\displaystyle{af+bg=(af_0+bg_0,af_1+bg_1,af_2+bg_2,\dots)}

and

\displaystyle{(fg)_n=\sum_{i=0}^nf_jg_{n-i},\qquad n=0,1,2,\dots}

is a commutative linear algebra with identity over F.
Corollary 2. Suppose f,g and h are polynomials over the field F such that f\neq 0 and fg=fh. Then g=h.

Definition. Let \Large{\frak a} be a linear algebra with identity over the field F. We shall denote the identity of \Large{\frak a} by 1 and make the convention that \alpha^0=1 for each \alpha in \Large{\frak a}. Then to each polynomial f=\sum_{i=1}^nf_ix^i over F and \alpha in \Large{\frak a} we associate an element f(\alpha) in \Large{\frak a} by the rule

\displaystyle{f(\alpha)=\sum_{i=1}^nf_i{\alpha}^i}

Theorem 2. Let F be a field and \Large{\frak a} be a linear algebra with identity over F. Supopse f and g are polynomials over F, that \alpha is an element of \Large{\frak a}, and that c belongs to F. Then
( i ) (cf+g)(\alpha)=cf(\alpha)+g(\alpha);
( ii ) (fg)(\alpha)=f(\alpha)g(\alpha).

Lagrange’s interpolation formula: If V=\{f\in F[x]:\deg f\leq n\}+\{0\} and t_0,t_1,\dots,t_n are n+1 distinct elements in F, then for each f\in V, we have

\displaystyle{f=\sum_{i=0}^nf(t_i)P_i,\quad P_i=\prod_{j\neq i}\left(\frac{x-t_j}{t_i-t_j}\right)}

Definition. Let F be a field and let \Large{\mathfrak a} and \Large{\mathfrak a}^{\sim} be linear algebras over F. The algebras \Large{\mathfrak a} and \Large{\mathfrak a}^{\sim} are said to be isomorphic if there is a one-to-one mapping \alpha\to\alpha^{\sim} of \Large{\mathfrak a} onto \Large{\mathfrak a}^{\sim} such that

(c\alpha+d\beta)^{\sim}=c\alpha^{\sim}+d\beta^{\sim} \\ (\alpha\beta)^{\sim}={\alpha}^{\sim}{\beta}^{\sim}

for all \alpha,\beta in \Large{\mathfrak a} and all scalars c,d in F. The mapping \alpha\to\alpha^{\sim} is called an isomorphism of \Large{\mathfrak a} onto \Large{\mathfrak a}^{\sim}. An isomorphism of \Large{\mathfrak a} onto \Large{\mathfrak a}^{\sim} is thus a vector space isomorphism of \Large{\mathfrak a} onto \Large{\mathfrak a}^{\sim} which has the additional property of ‘preserving’ products.

Theorem 3. If F is a field containing an infinite number of distinct elements, the mapping f\to f^{\sim} is an isomorphism of the algebra of polynomials over F onto the algebra of polynomial functions over F.

Lemma. Suppose f and d are non-zero polynomials over a field F such that \deg d\leq \deg f. Then there exists a polynomial g in F[x] such that either f-dg=0 or \deg (f-dg)<\deg f.

Theorem 4. If f,d are polynomials over a field F and d\neq 0 then there exists polynomials q,r\in F[x] such that
( i ) f=dq+r.
( ii ) either r=0 or \deg r<\deg d.
The polynomials q,r satisfying (i) and (ii) are unique.

Definition. Let d be a non-zero polynomial over the field F. If f is in F[x], the preceding theorem shows there is at most one polynomial q in F[x] such that f=dq. If such a q exists we say that d divides f, that f is divisible by d, that f is a multiple of d, and call q the quotient of f and d. We also write q=f/d.
Corollary 1. Let f be a polynomial over the field F, and let c be an element of F. Then f is divisible by x-c if and only if f(c)=0.

Definition. Let F be a field. An element c in F is said to be a root or a zero of a given polynomial f over F if f(c)=0.
Corollary 2. A polynomial f of degree n over a field F has at most n roots in F.

Theorem 5. (Taylor’s Formula) Let F be a field of characteristic zero, c an element of F, and n a positive integer. If f is a polynomial over F and \deg f\leq n, then

\displaystyle{f=\sum_{k=0}^n\dfrac{(D^kf)}{k!}(c)(x-c)^k.}

Theorem 6. Let F be a field of characteristic zero and f a polynomial over F with \deg f\leq n. Then the scalars c is a root of f of multiplicity r if and only if

\displaystyle{(D^kf)(c)=0,\quad 0\leq k\leq r-1\qquad(D^rf)(c)\neq 0}

Definition. Let F be a field. An ideal in F[x] is a subspace M of F[x] such that fg belongs to M whenever f is in F[x] and g is in M. The principle ideal generated by d is M=dF[x].

Theorem 7. If F is a field, and M is any non-zero ideal in F[x], there is a unique monic polynomial d in F[x] such that M is the principle ideal generated by d.
Corollary. If p_1,\dots,p_n are polynomials over a field F, not all of which are 0, there is a unique monic polynomial d in F[x] such that
( a ) d is in the ideal generated by p_1,\dots,p_n;
( b ) d divides each of the polynomials p_i;
Any polynomial satisfying ( a ) and ( b ) necessarily satisfies
( c ) d is divisible by every polynomial which divides each of the polynomials p_1,\dots,p_n.

Definition. If p_1,\dots,p_n are polynomials over a field F, not all of which are 0, the monic generator d of the ideal p_1F[x]+\cdots+p_nF[x] is called the greatest common divisor (g.c.d.) of p_1,\dots,p_n. We say that the polynomials p_1,\dots,p_n are relatively prime if their greatest common divisor is 1, or equivalently if the ideal they generate is all of F[x].

Definition. Let F be a field. A polynomial f in F[x] is said to be reducible over F if there exist polynomials g,h in F[x] of degree \geq 1 such that f=gh, and if not, f is said to be irreducible over F. A non-scalar irreducible polynomial over F is called a prime polynomial over F, and we sometimes say it is a prime in F[x].

Theorem 8. Let p,f and g be polynomials over the field F. Suppose that p is a prime polynomial and that p divides the product fg. Then either p divides f or p divides g.
Corollary. If p is a prime and divides a product f_1,\dots,f_n, then p divides one of the polynomials f_1,\dots,f_n.

Theorem 9. If F is a field, a non-scalar monic polynomial in F[x] can be factored as a product of monic primes in F[x] in one and, except for order, only one way.

Theorem 10. Let f be a non-scalar monic polynomial over the field F and let

\displaystyle{f=p_1^{n_{1}}\cdots p_k^{n_{k}}}

be the prime factorization of f. For each j,1\leq j\leq k, let

\displaystyle{f_j=f/p_j^{n_j}=\prod_{i\neq j}p_i^{n_i}.}

Then f_1,\dots,f_k are relatively prime.

Theorem 11. Let f be a polynomial over the field F with derivative f'. Then f is a product of distinct irreducible polynomials over F if and only if f and f' are relatively prime.

Definition. The field F is called algebraically closed if every prime polynomial over F has degree 1.

Linear Algebra (2ed) Hoffman & Kunze 4.5

christangdt留下评论

这一节的内容相对常规，主要谈多项式的因式分解，首先定义了一个多项式是否reducible，以及prime的定义。Theorem 8及其推论是很好理解的结论：如果p整除fg，则必整除其中一个，整除多个多项式乘积同理。Theorem 9是分解的唯一性，注意对monic polynomial才有此结论。由于分解唯一但分解出的prime可能有重复项，故将重复项加幂后，得到一个多项式的primary decomposition。Theorem 10是一个很简单的结论，主要是为了证明后面的定理，Theorem 11说明f是不同irreducible多项式的乘积（即primary decomposition的各多项式系数都为1），等价于f和f'是relatively prime的。最后给出了algebraically closed的定义，这里在线性代数中用到的比较重要结论是Fundamental Theorem of Algebra，即复数域是algebraically closed，而实数域虽然不是algebraically closed，但其primary decomposition的各多项式系数不会超过2。

Exercises

1.Let p be a monic polynomial over the field F, and let f and g be relatively prime polynomials over F. Prove that the g.c.d. of pf and pg is p.

Solution: We can find h_1,h_2\in F[x] such that fh_1+gh_2=1, thus pfh_1+pgh_2=p(fh_1+gh_2)=p, and obviously p divide both pf and pg, thus p=(pf,pg).

2.Assuming the Fundamental Theorem of Algebra, prove the following. If f and g are polynomials over the field of complex numbers, then g.c.d.(f,g)=1 if and only if f and g have no common root.

Solution: First if (f,g)=1, then \exists p,q\in C[x] such that fp+gq=1. Assume f and g have at least one common root, namely c, then 0=f(c)p(c)+g(c)q(c)=(fp+gq)(c)=1(c)=1, a contradiction.
Next suppose f and g have no common root, then by the Fundamental Theorem of Algebra, we have f=c(x-c_1)^{n_1}\cdots (x-c_k)^{n_k} and g=d(x-d_1)^{m_1}\cdots (x-d_l)^{m_l}, where c_i\neq d_j,1\leq i\leq k,\leq j\leq l, obviously (f,g)=1.

3.Let D be the differentiation operator on the space of polynomials over the field of complex numbers. Let f be a monic polynomial over the field of complex numbers. Prove that

\displaystyle{f=(x-c_1)\cdots (x-c_k)}

where c_1,\dots,c_k are distinct complex numbers if and only if f and Df are relatively prime. In other words, f has no repoeated root if and only if f and Df have no common root. (Assume the Fundamental Theorem of Algebra.)

Solution: Assuming the Fundamental Theorem of Algebra, we can have

\displaystyle{f=c(x-c_1)^{n_1}\cdots (x-c_k)^{n_k},\quad c_1,\dots,c_k\in C}

From Theorem 11 we know f and Df are relatively prime if and only if (x-c_j)^{n_j} are irreducible for all j, this happens if and only if n_j=1 for all j, and the conclusion follows.

4.Prove the following generalization of Taylor’s formula. Let f,g and h be polynomials over a subfield of the complex numbers, with \deg f\leq n. Then

\displaystyle{f(g)=\sum_{k=0}^n\frac{1}{k!}f^{(k)}(h)(g-h)^k.}

(Here f(g) denotes ‘f of g‘.)

Solution: By the binomial theorem g^m=[h+(g-h)]^m=\sum_{k=0}^m\binom{m}{k}h^{m-k}(g-h)^k, and if f=\sum_{m=0}^na_mx^m, then f^{(k)}(h)=\sum_ma_m(x^m)^{(k)}(h), thus

\displaystyle{\sum_{k=0}^n\frac{1}{k!}f^{(k)}(h)(g-h)^k=\sum_k\sum_ma_m\frac{(x^m)^{(k)}(h)}{k!}(g-h)^k=\sum_ma_mg^m=f(g)}

Note: For Exercises 5-8, we shall need the following definition. If f,g,p are polynomials over the field F with p\neq 0, we say that f is congruent to g modulo p if (f-g) is divisible by p. If f is congruent to g modulo p, we write f\equiv g \mod p.

5.Prove, for any non-zero polynomial p, that congruence modulo p is an equivalence relation.
( a ) It is reflexive: f\equiv f \mod p.
( b ) It is symmetric: if f\equiv g \mod p, then g\equiv f \mod p.
( c ) It is transitive: if f\equiv g \mod p and g\equiv h \mod p, then f\equiv h \mod p.

Solution:
( a ) f-f=0=0p, thus f-f is divisible by p.
( b ) If f\equiv g \mod p, then there is q\in F[x] such that f-g=pq,thus for the polynomial -q\in F[x] we have p(-q)=-(pq)=-(f-g)=g-f, which means g\equiv f \mod p.
( c ) Since we can find q,q'\in F[x] such that f-g=pq,g-h=pq', then f-h=(f-g)+(g-h)=pq+pq'=p(q+q') and q+q'\in F[x], so f\equiv h \mod p.

6.Suppose f\equiv g \mod p and f_1\equiv g_1 \mod p.
( a ) Prove that f+f_1\equiv g+g_1 \mod p.
( b ) Prove that ff_1\equiv gg_1 \mod p.

Solution: Since we can find q,q_1\in F[x] such that f-g=pq,f_1-g_1=pq_1, then
( a ) (f+f_1)-(g+g_1)=(f-g)+(f_1-g_1)=pq+pq_1=p(q+q_1)
( b ) Use the “middle-man” trick we have

\displaystyle{\begin{aligned}(ff_1)-(gg_1)&=(ff_1)-(fg_1)+(fg_1)-(gg_1)\\&=f(f_1-g_1)+g_1(f-g)\\&=fpq_1+g_1pq=p(fq_1+qg_1)\end{aligned}}

7.Use Exercise 6 to prove the following. If f,g,h,p are polynomials over the field F and p\neq 0, and if f\equiv g \mod p, then h(f)\equiv h(g) \mod p.

Solution: In cases when h is scalar polynomial or f=g we have h(f)=h(g) and the conclusion obviously holds. Now suppose \deg h=n\geq 1 and f\neq g. We write h=\sum_{i=0}^nh_ix^i, then h(f)=\sum_{i=0}^nh_if^i and h(g)=\sum_{i=0}^nh_ig^i. From Exercise 6(b) we know that f^i \equiv g^i \mod p for all 1\leq i\leq n, and since h_i\equiv h_i \mod p, use 6(b) again we get h_if^i \equiv h_ig^i \mod p for all 1\leq i\leq n. Now use Exercise 6(a) we get \sum_{i=0}^nh_if^i \equiv \sum_{i=0}^nh_ig^i \mod p, or h(f)\equiv h(g) \mod p.

8.If p is an irreducible polynomial and fg\equiv 0 \mod p, prove that either f\equiv 0 \mod p or g\equiv 0 \mod p. Give an example which shows that this is false if p is not irreducible.

Solution: fg\equiv 0 \mod p means fg is divisible by p, from Theorem 8 we know either p divides f or p divides g, this is the conclusion.
If p is not irreducible, we may let p=(x-1)^2 and f=g=(x-1), then we have fg\equiv 0 \mod p but neither f\equiv 0 \mod p nor g\equiv 0 \mod p.

Linear Algebra (2ed) Hoffman & Kunze 4.4

christangdt留下评论

这一节先说了一些多项式整除的结论（Theorem 4）和多项式空间中的Taylor公式（Theorem 5），Theorem 6揭示了多项式的根的multiplicity和求导算子D之间的关系。
下一部分引入的是ideal，Theorem 7证明了任何一个ideal都由唯一一个monic polynomial生成，通过这一定理的推论可以得到最大公约数（greatest common divisor）的概念，用ideal的generator引入g.c.d.是一个很有意思的做法，看起来不好理解，但实际计算时也会方便，由于所考虑的ideal是形如p_1F[x]+\cdots+p_nF[x]的组合，g.c.d.是这个ideal的monic generator，那么只要找到在此ideal中的任何一个多项式，g.c.d.一定比此多项式低阶。

Exercises

1.Let Q be the field of rational numbers. Determing which of the following subsets of Q[x] are ideals. When the set is an ideal, find its monic generator.
( a ) all f of even degree;
( b ) all f of degree \geq 5;
( c ) all f such that f(0)=0;
( d ) all f such that f(2)=f(4)=0;
( e ) all f in the range of the linear operator T defined by

\displaystyle{T\left(\sum_{i=0}^nc_ix^i\right)=\sum_{i=0}^n\frac{c_i}{i+1}x^{i+1}}

Solution:
( a ) No. As g=x^2 is in this set, but xg=x^3 is not.
( b ) No. As f=x^5+x^2 and g=x^5 are in this set, but f-g=x^2 is not.
( c ) Yes, its monic generator is d=x.
( d ) Yes, its monic generator is d=(x-2)(x-4).
( e ) Yes, its monic generator is d=x.

2.Find the g.c.d. of each of the following pairs of polynomials
( a ) 2x^5-x^3-3x^2-6x+4,x^4+x^3-x^2-2x-2;
( b ) 3x^4+8x^2-3,x^3+2x^2+3x+6;
( c ) x^4-2x^3-2x^2-2x-3,x^3+6x^2+7x+1.

Solution:
( a ) If we let f=2x^5-x^3-3x^2-6x+4,g=x^4+x^3-x^2-2x-2, and denote M=fF[x]+gF[x], then

f-(2x-2)g=3x^3-x^2-6x\in M \\ x(3x^3-x^2-6x)-3g=-4x^3-3x^2+6x+6\in M

combined we get -13x^2-6x+18\in M, similarly we can see 31x^2+14x\in M, continue these steps we shall find f and g are relatively prime.
( b ) Since 3x^4+8x^2-3=(3x^2-1)(x^2+3) and x^3+2x^2+3x+6=(x+2)(x^2+3), we see x^2+3 divides both polynomials and further

\displaystyle{\frac{1}{11}(3x^4+8x^2-3)+\frac{6-3x}{11}(x^3+2x^2+3x+6)=x^2+3}

the desired g.c.d is x^2+3.
( c ) A similar procedure can show they are relatively prime.

3.Let A be an n\times n matrix over a field F. Show that the set of all polynomials f\in F[x] such that f(A)=0 is an ideal.

Solution: Let M=\{f\in F[x]:f(A)=0\}, then if f,g\in M, then for any c\in F we have

\displaystyle{(cf+g)(A)=cf(A)+g(A)=0\Rightarrow cf+g\in M}

also if g\in M, then g(A)=0, and for any f\in F[x], we have (fg)(A)=f(A)g(A)=f(A)0=0, so fg\in M.

4.Let F be a subfield of complex numbers, and let A=\begin{bmatrix}1&-2\\0&3\end{bmatrix}. Find the monic generator of the ideal of all polynomials f in F[x] such that f(A)=0.

Solution: Since A^2=\begin{bmatrix}1&-8\\0&9\end{bmatrix}, we see

\displaystyle{A^2-4A+3I=\begin{bmatrix}1&-8\\0&9\end{bmatrix}-4\begin{bmatrix}1&-2\\0&3\end{bmatrix}+3\begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}}

thus the polynomial f=x^2-4x+3 is in the ideal. As no polynomial g of degree 1 can make g(A)=0 and f is monic, f is the result.

5.Let F be a field. Show that the intersection of any number of ideals in F[x] is an ideal.

Solution: Let \{M_{\alpha}\} be any number of ideals in F[x], and M=\cap_{\alpha}M_{\alpha}.
First let f,g\in M,c\in F, then f,g\in M_{\alpha} for all \alpha, thus cf+g\in M_{\alpha} for all \alpha, and cf+g\in M, and M is a subspace of F[x].
Next let f\in F[x] and g\in M, then g\in M_{\alpha} for all \alpha, as M_{\alpha} is an ideal, we see fg\in M_{\alpha} for all \alpha, which means fg\in M. This shows M is an ideal.

6.Let F be a field. Show that the ideal generated by a finite number of polynomials f_1,\dots,f_n in F[x] is the intersection of all ideals containing f_1,\dots,f_n.

Solution: Let M be the intersection of all ideals containing f_1,\dots,f_n. From Exercise 5 we know M is an ideal which contains f_1,\dots,f_n, thus contains f_1F[x]+\cdots+f_nF[x]. On the other hand, f_1F[x]+\cdots+f_nF[x] is an ideal containing f_1,\dots,f_n, thus shall contain M.

7.Let K be a subfield of a field F, and suppose f,g are polynomials in K[x]. Let M_K be the ideal generated by f and g in K[x] and M_F be the ideal they generate in F[x]. Show that M_K and M_F have the same monic generator.

Solution: Let d_K,d_F be the monic generator of M_K and M_F, then there is p,q\in K[x] such that d_K=fp+gq, since K is a subfield of F, p,q\in F[x] as well, thus d_K\in M_F,so d_K=hd_F for some h\in F[x]. Since d_K divides f and g in F, by Corollary of Theorem 7 we know d_F is divisible by d_K, so d_F=h'd_K for some h'\in F[x]. Now we have

\displaystyle{(d_K=hd_F=hh'd_K)\Rightarrow(hh'=1)\Rightarrow(h=h'=1)\Rightarrow(d_K=d_F)}