On solutions of a certain $n\times n$ linear system whose coefficients are all $\pm1$

115 Views Asked by At

Let $n>2$ and $A \in M_n(\mathbb{R})$ be a $\{-1,1\}$-matrix (whose elements are $-1$ or $1$). Let $b\in\mathbb R^n$ contains the row-wise counts of minus ones in $A$ (i.e. $b_i$ is the number of minus ones in the $i$-th row of $A$).

Suppose $Av = b$. Prove or disprove that if $Ax=0$ has only the trivial solution, then $v$ has at least two identical elements. For example, $$ A = \pmatrix{1 & 1 & 1 \\ -1 & 1 & 1\\ -1 & -1 & 1}, \ b=\pmatrix{0\\ 1\\ 2}, \ v=\pmatrix{-\frac12\\ -\frac12\\ 1}. $$ I couldn't find a counterexample, so for the moment I'm assuming it is indeed true. Perhaps the more pertinent issue I'm having is not knowing where to start, given the peculiar structure of the matrix and of $b$. I considered proving the contrapositive (if $v_1 = \ ...\ = v_n$, then there exists some nonzero/nontrivial solution to $Ax = 0$), but I didn't get far with that. I appreciate all help, even if it's just a nudge in the right direction (or if anyone finds a counterexample).

Thank you kindly!

Edit: In addition, I have not found a counterexample for the case where each $a_{ij}$ is either $-\delta$ or $\delta$ for $\delta \in \mathbb{R}$, so if the initial statement is indeed true, then something that would point to this fact would be optimal (or at the very least interesting). Thanks again!

1

There are 1 best solutions below

2
On BEST ANSWER

Edit. The hypothesis is false. The smallest counterexample I found was $5\times5$. We have $\det(A)=-16$ and $Av=b$ for $$ A=\pmatrix{-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}, \ b=\pmatrix{4\\ 2\\ 3\\ 2\\ 1}, \ v=\frac12\pmatrix{-11\\ 9\\ 4\\ -6\\ 14}. $$