Is there an efficient algorithm that allows to construct a binary word with particular properties related to its horizontal and vertical “subwords”?

Question

Let $w$ denote an $mn$-bit word (i.e. a binary word of length $mn$). Assuming that $b_{i,j}$ denote individual bits, we can represent $w$ in the “rectangular” form as follows:

$$\begin{array}{l} b_{1.1}b_{1.2} \ldots b_{1.(m-1)}b_{1.m}\\ b_{2.1}b_{2.2} \ldots b_{2.(m-1)}b_{2.m}\\ \ldots\\ b_{(n-1).1}b_{(n-1).2} \ldots b_{(n-1).(m-1)}b_{(n-1).m}\\ b_{n.1}b_{n.2} \ldots b_{n.(m-1)}b_{n.m}. \end{array}$$

Then $$H_{i,m}(w) = b_{i.1}b_{i.2} \ldots b_{i.(m-1)}b_{i.m}$$ are $m$-bit horizontal subwords of $w$ (for $1 \leq i \leq n$) and $$V_{n,i}(w) = b_{1.i}b_{2.i} \ldots b_{(n-1).i}b_{n.i}.$$ are $n$-bit vertical subwords of $w$ (for $1 \leq i \leq m$).

Given a pair of arbitrary (see note 1 below) integers $(m, n),$ I am interested in an efficient algorithm that allows to construct an example of an $mn$-bit word $W$ that satisfies all of the following five properties:

1. All $m$-bit horizontal subwords of $W$ are different from each other;
2. All $n$-bit vertical subwords of $W$ are different from each other;
3. Any $m$-bit horizontal subword of $W$ is different from any $n$-bit vertical subword of $W$, i.e. there does not exist an $m$-bit horizontal subword of $W$ that is equal to some $n$-bit vertical subword of $W$ (this property is automatically satisfied if $m \neq n$);
4. The number of non-zero bits in any $m$-bit horizontal subword of $W$ is equal to $m/2$;
5. The number of non-zero bits in any $n$-bit vertical subword of $W$ is equal to $n/2$.

Is it possible to solve this problem?

Note 1.
Obviously, both $m$ and $n$ must be even and such that $m \leq \binom{n}{n/2}, n \leq \binom{m}{m/2}.$ Maybe there are some other requirements for $(m, n).$ For example, if $m=8, n=8,$ does there exist a $64$-bit word $W_{64}$ satisfying the above conditions?

Answer 1

This construction works for $n=m$ both powers of 2. Take an enumeration of the truth tables of the linear functions $$\{[\langle a,x\rangle: x \in GF(2)^k],a \in GF(2)^k\}.$$ This will have the weight property except for the fact that the first row and column will be all zeroes, for example, for $k=3,$ we get

.

Call this matrix $A,$ and let $J$ be the all one matrix with the same dimensions. The blockmatrix $$ \left( \begin{array}{c|c} A+J & A \\ A & A+J \end{array} \right) $$ almost has the desired property with size $n=m=2^{k+1}.$ In this case we get

I have taken an $8\times 8$ seed matrix but one can take smaller ones or larger ones as needed.

The problem is the rows and columns match. To remove this, I have rotated the rows of the matrix to the right by one. Note that the original rows of matrix $A$ were the linear multivariate boolean functions, and shifting them by one yields nonlinear functions, so they are now distinct from the columns. The final outcome is below:

I used the magma calculator online available here. The code is below (without the cyclic rotation):

V:=VectorSpace(GF(2),3); L:=[v: v in V];

A:=Matrix([[InnerProduct(L[i+1],L[j]): j in [1..8]]: i in [0..7]]);A;

J:=Matrix([[1: i in [1..8]]: j in [1..8]]); C:=BlockMatrix(2,2,[A+J,A,A,A+J]); C;

function GetRowW(A,j,n) return Weight(VectorSpace(GF(2),n)![A[j,k]: k in [1..n]]); end function;

function GetColW(A,j,n) return Weight(VectorSpace(GF(2),n)![A[k,j]: k in [1..n]]); end function;

"row weights",{* GetRowW(C,j,16): j in [1..16] *};

"number of rows"; #{ [C[j,k]: k in [1..16]]: j in [1..16] };

"column weights",{* GetColW(C,j,16): j in [1..16] *};

"number of cols"; #{ [C[j,k]: j in [1..16]]: k in [1..16] };