I'm playing around with involutory ($M^2 = I$) matrices over finite fields with characteristic 2 ($\mathbb{F}_{2^m}$). I came across the nullity theorem, which seems very useful to check if submatrices are (non)singular. It basically states (as far as I understand it), that the nullity of a submatrix in $M$ is equal to the complementary submatrix of the inverse ($M^{-1}$).
Out of caution I routinely check my assumptions and try to find counterexamples. I checked the 4x4 matrices for $m=6$ and found one which seems to contradict the theorem:
(sagemath code)
G=GF(2**6, repr='int')
a=G(58.bits())
b=G(59.bits())
c=G(62.bits())
d=G(63.bits())
M=matrix(4,4,[b,a,d,c,d,c,a,d,d,d,c,a,d,d,d,b])
print(M)
# [59 58 63 62]
# [63 62 58 63]
# [63 63 62 58]
# [63 63 63 59]
print(M*M)
# [1 0 0 0]
# [0 1 0 0]
# [0 0 1 0]
# [0 0 0 1]
import itertools
for d in [2,3]:
for p1 in itertools.combinations(range(4), d):
for p2 in itertools.combinations(range(4), d):
S=M.matrix_from_rows_and_columns(p1, p2)
if S.determinant() == 0:
print('det', p1, p2)
if S.nullity() != 0:
print('nul', p1, p2)
# det (2, 3) (0, 1)
# nul (2, 3) (0, 1)
print(M.matrix_from_rows_and_columns((2,3), (0,1)))
# [63 63]
# [63 63]
As you can see, the matrix $M$ is clearly involutory, so $M = M^{-1}$, but it also has one obviously singular submatrix.
In addition, it ONLY contains this one singular and nullity non-zero submatrix!
According to the nullity theorem, I would expect a second singular submatrix, as there should be a complementary submatrix in the inverse of $M$.
I checked various sources, incl. the original papers, but found no obvious reason, the theorem should not work over special fields.
So my questions are:
- Is there a problem/error in the nullity theorem?
- If not, what is the reason it does not work over $\mathbb{F}_{2^m}$?
- Is there something (e.g. additional constraints) to make it work over $\mathbb{F}_{2^m}$?
Everything seems ok with your computations. The theorem doesn't forbid a submatrix to be it's own complementary submatrix. In fact, exactly the case you described is covered in the wiki article as $\operatorname{nullity} C = \operatorname{nullity} G$.