Return to Question

If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be?

If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be, compared to the number of $1$s in $M$?

For $n=7$, with $2n+1$ ones there is one equivalence class that gives a difference of $(n-2)^2$. The canonical matrix is:

0 0 0 0 0 1 1
0 0 0 0 1 0 1
0 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 0
1 1 1 0 0 0 0

with inverse

1 1 0 1 1 0 1
1 0 1 1 0 1 1
0 1 1 0 1 1 1
1 1 0 1 1 1 1
1 0 1 1 1 1 1
0 1 1 1 1 1 1
1 1 1 1 1 1 1

For $n=4$, with $2n+1$ ones there is one equivalence that gives a difference of $(n-2)^2$. The canonical matrix is:

 0 0 1 1
 0 1 0 1
 1 0 0 1
 1 1 1 0

with inverse

1 1 0 1
1 0 1 1
0 1 1 1
1 1 1 1

For $n=5$, with $2n+1$ ones there is one equivalence class that gives a difference of $(n-2)^2$. The canonical matrix is:

 0 0 0 1 1
 0 0 1 0 1
 0 1 0 0 1
 1 0 0 1 0
 1 1 1 0 0

with inverse

 0 1 1 0 1
 1 1 0 1 1
 1 0 1 1 1
 0 1 1 1 1
 1 1 1 1 1

For $n=6$, with $2n+1$ ones there is one equivalence class that gives a difference of $(n-2)^2$. The canonical matrix is:

 0 0 0 0 1 1
 0 0 0 1 0 1
 0 0 1 0 0 1
 0 1 0 0 1 0
 1 0 0 1 0 0
 1 1 1 0 0 0

with inverse

1 0 1 1 0 1
0 1 1 0 1 1
1 1 0 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
1 1 1 1 1 1