设是数域P上n维线性空间V的一个线性变换,证明:
1)在P[x]中有一次数≤n2的多项式f(x),使
2)如果,那么这里d(x)是f(x)与g(x)的最大公因式;
3)可逆的充分必要条件是,有一常数项不为零的多项式f(x)使
令V是实数域R上一个三维向量空间,σ是V的一个线性变换。它关于V的某一个基的矩阵是
(i)求出σ的最小多项式p(x),并把p(x)在R[x]内分解为两个最高次项系数是1的不可约多项式p1(x)与p2(x)的乘积;
(ii)令Wi={ξ∈V|pi(σ)ξ=0},i=1,2。证明,Wi是σ的不变子空间,并且V=W1⊕W2;
(iii)在每一子空间Wi中选取一个基,凑成V的一个基,使得σ关于这个基的矩阵里只出现三个非零元素。
a)任意字符比对的成功与失败概率分别为1/s和(s-1)/s,其中s=|∑|为字符表的规模;
b)在P与T的每一对齐位置,需连续执行恰好k次字符比对操作的概率为(s-1)/sk;
c)在P与T的每一对齐位置,需连续执行字符比对操作的期望次数不超过s/(s-1)≤2=o(1)。