3
$\begingroup$

Let $\{A_i, i\ge 3\}$ be the matrices whose columns represent numbers from $0$ to $2^i-1$ in binary form. For example,

$A_3 = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ % 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{bmatrix}$

$A_4 = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$

I am interested in vectors $x$ such that $Ax = \vec{0}$, with the additional constraint that half of the values in $x$ are $-1$ and the other half is $1$. For example,

$x_a=\begin{bmatrix}1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \end{bmatrix}^T$ and

$x_b=\begin{bmatrix}1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{bmatrix}^T$ are two possible solutions for $A_3x=\vec{0}$.

Observe that the set of solution is always non-empty. For example, $x_a$ could be generalized for any $i\ge 3$, with half of the $1$'s at the beginning, half of them in the end, and all $-1$'s in the middle.

I want to understand whether solutions are still guaranteed when additional rows are added $A_i$ as follows:

  • $2^{i-1}$ extra rows are added,
  • Each of them has only two 1's (0 elsewhere),
  • One of these 1's is in the first half of the columns, the other is in the other half,
  • Each column receives only one $1$ over these rows

Apart from these restrictions, the extra rows could be any.

For example,

$A_3'= \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\\hline 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \end{bmatrix}$

My question is the following:

  • Does $A_i'x=\vec{0},$ with $i \ge 3$, always have a solution?

Based on experiments, this seems plausible, although I can't find a clear argument as to why this should be true.

Improve this question
$\endgroup$
1
  • $\begingroup$ Your matrices $A_i$ come up as generator matrices for Hamming codes (except those don't have an all-zero column). $\endgroup$ Commented Nov 23, 2023 at 22:15

1 Answer 1

Reset to default
3
$\begingroup$

No. Here is an explicit counter-example for the $i = 3$ case:

$$ A_3^\prime = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{bmatrix} $$ The null space of this matrix is the span of the vector $(1,0,-1,0,0,-1,0,1)$, so there is no solution to $A_3^\prime x = \vec{0}$ having each entry equal to $\pm 1$, let alone with half of the entries equal to $+1$ and half equal to $-1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good catch. Interestingly, this configuration never shows up in my use cases (where all the A'3 and A'4 that I actually get do admit a solution). This means there must be additional conditions on the extra-rows, which I haven't identified yet (these constraints come themselves from a complicated process). If I may, I'd like to think a bit more before we settle this question, to get a chance to add these constraints here. In the meantime, do you see any (if possible, not too trivial) restriction that may guarantee a solution, for some algebraic reasons? $\endgroup$ Commented Nov 26, 2023 at 19:53

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.