6
$\begingroup$

Let $n\ge 1$ and $A$ be any $n\times n$ real invertible matrix. Can we always find a 0-1 vector $b\in\{0,1\}^n$ such that each entry of $Ab$ is nonzero? For example, if $A$ is the identity matrix, then we can (only) take $b$ to be the all-one vector.

Edit: The answer given by Pat Devlin is beautiful. From his construction, we know that there exists a parallelepipedon whose each vertex lies on some coordinate plane. Indeed, for $n=3$ from the matrix $$A=\left(\begin{matrix}1&0&0\\ 0&1&-1\\ 1&-1&-1 \end{matrix}\right)$$ we can obtain the desired parallelepipedon using the columns of $A$. His solution suggests that the invertibility assumption on $A$ seems inappropriate.

Can we put a rectangular solid (particularly, a cube) in $R^3$ such that each vertex lies on some some coordinate plane. In higher dimension, if the column vectors of $A$ are orthogonal with each other (i.e.,$A^T A$ is a nonsingular diagonal matrix), can we always obtain a desired 0-1 vector $b$ such that each entry of $Ab$ is nonzero?

What is a appropriate assumption on $A$ for a positive solution? Does orthogonal matrices suffice?

$\endgroup$
6
  • 1
    $\begingroup$ @JohnMachacek Perhaps you are misunderstanding the question, because the answer is definitely yes for $n=2$: either one of the columns has all nonzero entries (in which case the corresponding basis vector is the desired $b$) or both have a single zero entry, in which case (to be invertible) each row has a single nonzero entry, hence the all-one vector suffices for $b$. $\endgroup$
    – Sean Clark
    Jun 19 '20 at 13:40
  • $\begingroup$ @SeanClark yes my mistake. I guess all this time off has left my especially slow in the mornings :) $\endgroup$ Jun 19 '20 at 14:18
  • 1
    $\begingroup$ Who and why vote to close ? $\endgroup$ Jun 19 '20 at 14:56
  • 1
    $\begingroup$ @ZachTeitler More specifically, $n$ hyperplanes (passing through the origin) in general position. $\endgroup$
    – user44191
    Jun 19 '20 at 17:11
  • 1
    $\begingroup$ Yes. See answer. :-) $\endgroup$
    – Pat Devlin
    Jun 19 '20 at 22:35
10
$\begingroup$

The answer for $n \leq 2$ is yes, and for $n \geq 3$, it's no. (The $n=1$ case is left to the reader)

The case $n=2$: If $v_i$ are the rows of the matrix, then each equation $v_1 \cdot x = 0$ and $v_2 \cdot x = 0$ describes a co-dimension $1$ space. And the four corners of the square $\{0,1\}^2$ cannot be covered by two lines passing through the origin.

The case $n \geq 3$: For $n \geq 3$, we can cover all the vertices of the cube with three independent hyperplanes through the origin. Namely... $$x_1 = 0$$ $$x_2 -x_3 = 0$$ $$x_1 - x_2 - x_3=0$$ It's easy to see these three conditions describe a co-dimension three space [i.e., the conditions are independent]. To see they cover the vertices of the cube, note that failure of the first and second equations would imply $x_1 =1$ and $x_2 \neq x_3$. Since each variable is $0,1$, this would force $x_2 + x_3 = 1$, so the third equation will be satisfied.

The $n\geq 3$ case phrased as a matrix: Make the first row $[1, 0, 0, 0, 0, \ldots]$. Then the second row $[0, 1, -1, 0, 0, \ldots]$. Then make the third row $[1, -1, -1, 0, 0, 0, \ldots]$. These three rows are independent (yay!), so just fill up the rest of the matrix with more linearly independent rows until you have a basis (i.e., an invertible matrix). Then see above argument why $A \vec{x}$ will have at least one of the first three coordinates equal to $0$.

Literature: Also, there are some really cool results about covering the cube with hyperplanes. See for instance this article about covering all but one of the vertices and also this article about covering the vertices in a way where each equation is needed, and every variable actually shows up.

Edit 1: I changed the equations to handle the $n=3$ as well.

Edit 2 (this part added to address orthogonal case): As per comment, perhaps you’d like the matrix to be orthogonal as well. That’s also fine (at least for $n \geq 4$. I haven’t thought about $n=3$ in this case).

Take the first three rows to be $[1, -1, 0, 0, 0, 0, \ldots]$ and $[0,0,1,-1,0,0,\ldots]$ and $[1,1,-1,-1,0,0,\ldots]$ (and renormalize these so that they each have length 1). Then extend this to an orthonormal basis and fill the rest of the matrix with those rows. This works in the same ways as the above example. (This was actually the first construction I gave, but then I swapped it out for the above, which only needed $n=3$.) ((I notice that I don’t enjoy thinking about the orthogonal $n=3$ case. It might be that you can’t make any orthogonal matrix to do it. On the other hand, it could be that I’m bad at visualizing rotations of the cube that put all its corners onto three orthogonal planes...))

Edit 3: You seem to want this to be true for really special matrices. I don’t think that’s really going to happen. The cube fits inside a pretty darn small space (union of three planes), so this seems to give us a lot of wiggle room for all sorts of stuff. :-/

$\endgroup$
3
  • $\begingroup$ Thank you for your cool construction. What happens if $A$ is an orthogonal matrix? $\endgroup$
    – W. Wang
    Jun 20 '20 at 2:17
  • $\begingroup$ That’s ok too. I’ll add a note $\endgroup$
    – Pat Devlin
    Jun 20 '20 at 12:52
  • $\begingroup$ @W.Wang let me know if there’s anything else you’d like to be answered with this. $\endgroup$
    – Pat Devlin
    Jun 21 '20 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.