Configurations of signs in a matrix under certain conditions

Question

I have a combinatorial question which is out of my research area.

Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible to allocate $0,\pm1$ satisfying the following two conditions?

1. Each row and each column contain precisely $k+1$ nonzero (i.e., $1$ or $-1$) elements. (In particular, the number of nonzero elements in the matrix $A$ is $2^k(k+1)$.)
2. For every pair of two rows $(a_{i_1,1},\dots,a_{i_1,2^k})$ and $(a_{i_2,1},\dots,a_{i_2,2^k})$, there exists a $j_0\in\lbrace1,\dots,2^k\rbrace$ such that $a_{i_1,j_0}a_{i_2,j_0}=-1$. (That is, $a_{i_1,j_0}$ and $a_{i_2,j_0}$ are nonzero and have opposite signs.)

I observed the affirmative answer only for $k=1,2,3$, but not in a systematical way. I could not find an algorithm to systematically allocate nonzero elements and their signs. So, I wonder if it is possible for a larger $k$.

Answer 1

Thank you user21478 and Yemon for your answer/comments. Actually, I observed quite easily that the "nonzero-sharing condition" is not compatible with the condition (1) for a large $k$.

Proof. For simplicity, suppose that, without loss of generality, the first $k+1$ entries in the first row are nonzero. Then for each of the remaining $2^k-1$ rows, there exists at least one nonzero element in the first $k+1$ entries by the nonzero-sharing condition. Thus, the first $k+1$ columns contain at least $(k+1)+(2^k-1)=k+2^k$ nonzero elements. Hence, at least one column among these contains at least $\left\lceil\frac{2^k+k}{k+1}\right\rceil$ nonzero elements, and $\frac{2^k+k}{k+1}>k+1$ for $k\ge5$. So, if $k\ge5$, then the condition (1) and nonzero-sharing condition cannot be satisfied simultaneously, let alone the sign condition.