Bounds for the difference in the number of ones in $M$ and $M^{-1}$

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, compared to the number of $1$s in $M$?

Clearly the identity matrix is an example where the number of ones doesn’t change at all.

This is a question just for mathematical interest. I am trying to understand the properties of matrices over $\mathbb{F}_2$.

Examples

For $n=6$ there are 251610 inequivalent binary matrices (up to row and column permutations). Taking only the full rank matrices from this set, these are the max differences in the number of ones between a matrix and its inverse. The first number is the number of ones in the matrix and the second is the max absolute difference for matrices with that number of ones.

6 0
7 0
8 1
9 3
10 6
11 10
12 9
13 16
14 10
15 16
16 10
17 12
18 9
19 9
20 9
21 10
22 9
23 10
24 11
25 12
26 13
27 14
28 15
29 16
30 15
31 16

An equivalent set of results for $n=7$ is:

7 0
8 0
9 1
10 3 
11 6
12 10
13 15
14 16
15 25
16 18
17 25
18 18
19 24
20 17
21 19
22 16
23 17
24 15
25 16
26 13
27 14
28 15
29 15
30 16
31 16 
32 17
33 18
34 19
35 20
36 21
37 22
38 21
39 24
40 25
41 24
42 25
43 24

The first six max absolute differences are the same as the $n=6$ case.

Are there provable bounds for this relationship for general $n$?

(Previously asked at math.se unsuccessfully.)

Added examples by request

For n=3

3 0
4 0
5 1
6 1 
7 0

For n=4

4 0
5 0
6 1
7 3
8 1
9 4 
10 3 
11 2
12 3 
13 4

For n=5

5 0
6 0
7 1
8 3
9 6 
10 4
11 9 
12 4 
13 8
14 5
15 6
16 5
17 6
18 7
19 8
20 9
21 8

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

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

Answer 1

The difference is indeed always at most $(n-2)^2$, and combined with an example from the answer by Bill Bradley (the check that the product of his matrices is identity is rather straightforward), this answers to the initial question, if we do not specify the number of 1's in $M$.

Assume that $M$ is a matrix with $k$ 1's, $M^{-1}=E+N$, where $E$ is all-1 matrix, and $N$ has $\ell$ 1's. We should prove that $k+\ell\geqslant 4n-4$. Let $I_0$, $I_1\subset \{1, 2,\dots,n\} $ be the sets of (indices of) rows with even, respectively odd, number of 1's in $M$. Then $[MN]_{i, j}=\delta_{ij}+{\bf 1}(i\in I_1)$. Note that $I_1$ is non-empty as otherwise $M$ would be singular (with all-1 vector in the kernel). Denote $r=|I_1|$.

Assume that we have exactly one 1 in the, say, $s$-th row of $M$, say, $[M]_{s, x}=\delta_{t, x}$ for some $t$ and all $x=1, 2,\dots,n$. Then $[MN]_{s,i}=[N]_{t,i}$ for all $i=1, 2,\dots,n$. Thus, as $s\in I_1$, the $t$-th row of $N$ contains $n-1$ 1's, and for different $s$ we have different $t$'s. If $j\geqslant 1$ is the number of rows of $M$ with exactly one 1, we get that the total number of 1s in $M$ and $N$ is not less then $j\cdot1+j\cdot (n-1)+(n-j)\cdot 2+(n-j-1)\cdot 1=3n-1+j\cdot (n-3)\geqslant 3n-1+n-3=4n-4$ as needed (we used that $M$ is non-singular, thus every row of $M$ contains at least one 1, and $E+N$ is non-singular, thus at most one row of $E+N$ may be all-1, equivalently, at most one row of $N$ may be all-0.)

So, further we may assume that every row of $M$ contains at least two 1's, and also every column of $M$ contains at least two 1's (as the question is invariant under replacement of $M$ to the transpose of $M$).

Assume that we have exactly one 1 in the, say, $s$-th column of $N$: $[N]_{x, s}=\delta_{x, t}$ for some $t=t_s$ and all $x=1, 2,\dots,n$. Then $[MN]_{i,s}=[M]_{i,t}$ for all $i=1, 2,\dots,n$. It means that the $t_s$-th column of $M$ is the same as the $s$-th column of $MN$.

Note that since $M$ is invertible, for the basic vector, say, $e_j$ we get $Ne_j=0 \Leftrightarrow (MN)e_j=0$. This is impossible if $|I_1|>1$, and happens for exactly one index $j$ if $|I_1|=1$. Now consider several cases.

1. $|I_1|\geqslant 4$. Then the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least $4$ 1's. Other columns of $M$ contain at least two 1's, and so do other columns of $N$, totally at least $4n$ 1's in $M$ and $N$.

2. $|I_1|=3$. The difference with the previous case is that there can be three values of $s$ for which the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least three 1's (not at least four). We still get at least $4n-3$ 1's in $M$ and $N$.

3. $|I_1|=2$. The difference with the first case is that there can be two values of $s$ for which the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least two 1's. We still get at least $4n-4$ 1's in $M$ and $N$.

4. $|I_1|=1$. Let $I_1=\{n\}$, we may suppose this without loss of generality. Then $Ne_n=0$. If there are $\theta$ columns of $N$ with exactly one 1, they correspond to $\theta$ columns of $M$ which are the same as $\theta$ distinct columns of $N$. In particular, the $n$-th row of $M$ contains at least $\theta$ 1's, so totally we get at least $\theta+(n-1)2+\theta\cdot 1+(n-1-\theta)\cdot 2=4n-4$ 1's in $M$ and $N$. (We counted 1's in $M$ by rows and in $N$ by columns).

Answer 2

This is a little numerical experiment, not an answer, but it provides a hypothesis for the shape of a solution. We (computationally) confirmed that matrices with this form have a discrepancy of $(n-2)^2$ for $n=3,...,1000$.

The form looks like the following (where here we show $n=14$): $$ \left( \begin{array}{cccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right) $$ There are two anti-diagonals of ones. The first is one row above the main diagonal and the second is $2\lfloor n/4 \rfloor+1$ below; there are also ones along the rightmost column and bottom row that attach the two diagonals. The inverse in this case is: $$ \left( \begin{array}{cccccccccccccc} 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right) $$

For anyone interested in replicating the experiment (or who would like a more concrete definition of the matrix), here's the Python code I used:

def proposed_matrix(N=7):
    k = 2*(N//4)+1
    
    A = np.zeros((N,N))
    for i in range(N-1):
        A[i,N-2-i] = 1
    A[N-1,:k] = 1
    A[:k,N-1] = 1
    for i in range(N - k +1):
        A[k+i-1, N-i-1] = 1
    A = A.astype(int)
    
    return(A)