[math-fun] Cool fact about certain matrices over GF(2)
Compute the inverse of the 3x3 companion matrix over an arbitrary field: (%i1) [M,M^^-1]; [ f ] [ - - 1 0 ] [ c ] [ 0 0 -c ] [ ] [ ] [ i ] (%o1) [[ 1 0 -f ], [ - - 0 1 ]] [ ] [ c ] [ 0 1 -i ] [ ] [ 1 ] [ - 0 0 ] [ c ] Charpoly can't be irreducible unless c=1, so choose i,f,c for x^3+i*x^2+f*x+c = x^3+x+1, which is irreducible (mod 2): (%i2) %,i=0,f=1,c=1; [ 0 0 -1 ] [ -1 1 0 ] [ ] [ ] (%o2) [[ 1 0 -1 ], [ 0 0 1 ]] [ ] [ ] [ 0 1 0 ] [ 1 0 0 ] Reduce mod 2: (%i3) rat(%); [ 0 0 1 ] [ 1 1 0 ] [ ] [ ] (%o3)/R/ [[ 1 0 1 ], [ 0 0 1 ]] [ ] [ ] [ 0 1 0 ] [ 1 0 0 ] (Note that M^^-1 = M^^6 and M^^7=I.] Choose i,f,c for x^3+x^2+1, also irreducible (in fact, the *only* other irreducible poly of deg 3): (%i4) [M,M^^-1],i=1,f=0,c=1; [ 0 0 -1 ] [ 0 1 0 ] [ ] [ ] (%o4) [[ 1 0 0 ], [ -1 0 1 ]] [ ] [ ] [ 0 1 -1 ] [ 1 0 0 ] Again, reduce mod 2: (%i5) rat(%); [ 0 0 1 ] [ 0 1 0 ] [ ] [ ] (%o5)/R/ [[ 1 0 0 ], [ 1 0 1 ]] [ ] [ ] [ 0 1 1 ] [ 1 0 0 ] Note that the inverse of the second matrix (%o5[2]) is the first matrix (%o3[1]) reflected about the central vertical axis and then cyclicly rotated vertically by one, and ditto for the inverse of the second matrix. (Due to the structure of the inverse of the companion matrix, this should be true for *every* nxn binary companion matrix.) I.e., %o3[2] is the reflection+cyclic of %o5[1], and %o3[1] is the reflection+cyclic of %o5[2]. How's that for a cool proof that these two extension fields are isomorphic! Thus, these two matrices/irreducible polynomials are in some sense "conjugates". Presumably, there are other types of conjugation that make *all* irreducible polynomials of the same degree over GF(p) in some sense "conjugate" ??
This phenomenon does indeed generalize to larger matrices over an arbitrary field: (%i1) [M,C,M^^-1,C.M.C]; [ 0 0 0 - 1 ] [ 0 1 0 0 ] [ - d 1 0 0 ] [ - d 1 0 0 ] [ ] [ ] [ ] [ ] [ 1 0 0 - d ] [ 0 0 1 0 ] [ - c 0 1 0 ] [ - c 0 1 0 ] (%o1) [[ ], [ ], [ ], [ ]] [ 0 1 0 - c ] [ 0 0 0 1 ] [ - b 0 0 1 ] [ - b 0 0 1 ] [ ] [ ] [ ] [ ] [ 0 0 1 - b ] [ 1 0 0 0 ] [ - 1 0 0 0 ] [ - 1 0 0 0 ] C is a circulant matrix. Note that C.M.C is NOT (C^^-1).M.C, because C.M.C *reverses* the coefficients in the characteristic polynomial of M -- i.e., if r is a root/eigenvalue, r->1/r. Checking, C.M.C is indeed the inverse of M, because M.(C.M.C)=I and (C.M.C).M=I. At 12:31 PM 8/6/2017, Henry Baker wrote:
Compute the inverse of the 3x3 companion matrix over an arbitrary field:
(%i1) [M,M^^-1]; [ f ] [ - - 1 0 ] [ c ] [ 0 0 -c ] [ ] [ ] [ i ] (%o1) [[ 1 0 -f ], [ - - 0 1 ]] [ ] [ c ] [ 0 1 -i ] [ ] [ 1 ] [ - 0 0 ] [ c ]
Charpoly can't be irreducible unless c=1, so choose i,f,c for x^3+i*x^2+f*x+c = x^3+x+1, which is irreducible (mod 2):
(%i2) %,i=0,f=1,c=1; [ 0 0 -1 ] [ -1 1 0 ] [ ] [ ] (%o2) [[ 1 0 -1 ], [ 0 0 1 ]] [ ] [ ] [ 0 1 0 ] [ 1 0 0 ]
Reduce mod 2:
(%i3) rat(%); [ 0 0 1 ] [ 1 1 0 ] [ ] [ ] (%o3)/R/ [[ 1 0 1 ], [ 0 0 1 ]] [ ] [ ] [ 0 1 0 ] [ 1 0 0 ]
(Note that M^^-1 = M^^6 and M^^7=I.]
Choose i,f,c for x^3+x^2+1, also irreducible (in fact, the *only* other irreducible poly of deg 3):
(%i4) [M,M^^-1],i=1,f=0,c=1; [ 0 0 -1 ] [ 0 1 0 ] [ ] [ ] (%o4) [[ 1 0 0 ], [ -1 0 1 ]] [ ] [ ] [ 0 1 -1 ] [ 1 0 0 ]
Again, reduce mod 2:
(%i5) rat(%); [ 0 0 1 ] [ 0 1 0 ] [ ] [ ] (%o5)/R/ [[ 1 0 0 ], [ 1 0 1 ]] [ ] [ ] [ 0 1 1 ] [ 1 0 0 ]
Note that the inverse of the second matrix (%o5[2]) is the first matrix (%o3[1]) reflected about the central vertical axis and then cyclicly rotated vertically by one, and ditto for the inverse of the second matrix. (Due to the structure of the inverse of the companion matrix, this should be true for *every* nxn binary companion matrix.)
I.e., %o3[2] is the reflection+cyclic of %o5[1], and %o3[1] is the reflection+cyclic of %o5[2].
How's that for a cool proof that these two extension fields are isomorphic!
Thus, these two matrices/irreducible polynomials are in some sense "conjugates".
Presumably, there are other types of conjugation that make *all* irreducible polynomials of the same degree over GF(p) in some sense "conjugate" ??
participants (1)
-
Henry Baker