Reducing the set L when using B = ATA
Use the fact that p2 | valence( charpoly(B) ) if p | si
Suppose that a prime p appears singly in valence(minpoly(B)).
M = minpoly(B) factors in R N = M, and suppose that p appears in R.
We want to show that R is not repeated in charpoly(B), that is to say we want to show that dim( ker( R(B) )) = deg(R) and not a power of it.
Theorem : If R.N are coprime, then ker(R(B)) = span(N(B))
- set d = deg(R)
- select d+1 random vectors ui and see if the vi=N(B)ui are dependent
If so :
- with high probability the dimension of ker( R(B) ) is d
- then R is not repeated in charpoly(B)
- then any prime occurring singly in valence(R) and valence(M) will occur also singly in valence(charpoly(B))
- then such a prime cannot divide si !
Then there are many chances that also p2 | valence( minpoly(B) )
Cex : 1 1 has Smith form 1 0 but ATA = AAT = 2 0
-1 1 0 2 0 2
with (x-2) and (x-2)2 as minimum and characteristic polynomials