Wikipedia:Reference desk/Archives/Mathematics/2018 September 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 22

Vertices of intersection of affine subspace and a cube

Let $A\in \{0,1\}^{n\times n},b\in \{0,1\}^{n}$

Statement: Every vertex $v$ of the polyhedron defined by $\{x\in [0,1]^{n}|Ax=b\}$ satisfies $v\in \{0,{\frac {1}{n}},{\frac {2}{n}},\dots ,{\frac {n-1}{n}},1\}^{n}$.

Is that statement correct? 2.52.79.251 (talk) 07:52, 22 September 2018 (UTC)

• No. Counterexample: $n=2,A={\begin{pmatrix}1&0\\0&0\end{pmatrix}},b={\begin{pmatrix}1\\0\end{pmatrix}},v={\begin{pmatrix}1\\\pi /4\end{pmatrix}}$.

More generally, I feel there should be a topology argument to say that is not true except if the set ("polyhedron") is empty or singleton. The rough idea is that $f:x\in [0,1]^{n}\rightarrow Ax$ is continuous so the reverse image of $\{b\}$ should be a connected set, hence contain points at nonrational coordinates as soon as it contains at least two points. The reverse image of a connected set by a continuous function is not always a connected set, though. Something should be feasible by matrix analysis, "inverting" A (obviously the problematic case is when A is not invertible, but you can still kind-of diagonalize etc. and probably show that the inverse function is continuous). Tigraan^{Click here to contact me} 12:41, 22 September 2018 (UTC)

@Tigraan: a vertex of a polyhedron is not the same thing as a point in the polyhedron. --JBL (talk) 15:24, 22 September 2018 (UTC)

A simple example with n=3 is

x₁+x₂=1

x₁+x₃=1

x₂+x₃=1

where the polyhedron in question consists of the of the single point (1/2, 1/2, 1/2), but 1/2 is not in {0, 1/3, 2/3, 1}. Btw, there was a question similar to this last month and what I mentioned there still goes: you can assume b is an all 1's vector. Also, statements like this that predict what a polytope might look like based on a few low-dimensional examples are almost always wrong, and in fact wrong in most cases. In fact I'd wager that if you took nearly any non-trivial combinatorial problem, converted it to the form given, or even if you took A to be a random 5x10 matrix, you'd get a counterexample. (The example I gave last month is not a counterexample but it's highly unusual due to its symmetry.) You need to do computer calculations to get a feel for what really happens in higher dimensions, but for some reason college courses and textbooks seem to prefer pictures you can draw and computations you can do by hand, giving a highly misleading impression of the subject. --RDBury (talk) 16:33, 22 September 2018 (UTC)

Great. It's a good counterexample!

Additionally, a similar statement but with: $v\in \{{\frac {a}{b}}\ |\ a,b\in \{0,\dots ,n\}\}^{n}$, would be true? 2.52.79.251 (talk) 18:11, 22 September 2018 (UTC)

First, I misread the question and thought you said mxn instead of nxn. It does't matter since you can just at rows of 0's to make A square and append a corresponding number of 0's to b. Actually it looks like a random 5 by 10 matrix won't work since the dimension of the polytopes is 5 which is still too small. But if you change the ='s to ≤'s by adding slack variables it does seem to work. I took a random 5 by 10 matrix, appended a 5 by 5 identity matrix for slack variables, deleted duplicate columns since they don't introduce new denominators, and got the 5 by 13 matrix A=

0 1 0 1 0 1 1 0 1 0 0 0 0
0 0 1 1 0 1 1 1 0 1 0 0 0
0 1 1 1 1 0 0 0 0 0 1 0 0
1 0 0 1 1 1 0 1 0 0 0 1 0
1 1 0 0 1 1 0 1 0 0 0 0 1

from which the polytope defined as above has vertices

(1/1)( 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0)
(1/1)( 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0)
(1/1)( 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0)
(1/1)( 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0)
(1/1)( 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0)
(1/1)( 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0)
(1/1)( 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0)
(1/1)( 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0)
(1/1)( 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1)
(1/1)( 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1)
(1/1)( 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1)
(1/1)( 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1)
(1/2)( 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0)
(1/2)( 0, 0, 1, 0, 1, 0, 0, 1, 2, 0, 0, 0, 0)
(1/2)( 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0)
(1/2)( 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0)
(1/2)( 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0)
(1/2)( 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0)
(1/2)( 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0)
(1/2)( 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 1)
(1/2)( 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0)
(1/3)( 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0)
(1/3)( 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0)
(1/3)( 2, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0)
(1/3)( 0, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 2, 0)
(1/4)( 0, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0)

In this case n=13 and there are 14 vertices where there denominator is not a divisor of 13. Even if you expand n by adding back in duplicate columns, and adding still more, you'd need to pad it out to 24 columns before all the denominators divide n. For the second version of the question, basically whether it possible for the denominators to be larger than n, I'm pretty sure the answer is still yes. One reason is in my experiments using LP to solve combinatorial problems with around 100 variables, I was using 32 bit integers, but they were being multiplied so there was an effective bound of 32,000 in the denominators to avoid overflow. Yet there was serious danger of that bound being exceeded if the number of variables was much over 100. Another reason is that when you compute the coordinates of the vertex points in terms of A, you essentially just use Cramer's rule on a subset of the columns of A, so an upper bound for the determinant is the maximum determinant of an mxm 0-1 matrix. Hadamard's maximal determinant problem addresses finding this maximum and, as can be seen from the tables on the page (or by looking it up on oeis) the bound increases rapidly as n increases. That doesn't imply that the bound is reached at an actual vertex, but it's not good if you were hoping for a reasonable bound for the denominators. --RDBury (talk) 21:20, 22 September 2018 (UTC)

Just to follow up, it's really not hard to find examples with n moderately large. I took a random 16x16 0-1 matrix, made some tweaks to ensure that the solution to Ax=1 is in the [0,1] 16-cube, and first try got denominators >16. Specifically, if A is

1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1
1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1
1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0
0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0
0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0
0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0
1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0
1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0
1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0
0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1
0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0
0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0
0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0
0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1

Then the polytope in question is the single point

(1/71)(7, 5, 23, 9, 4, 3, 5, 6, 2, 15, 17, 4, 7, 20, 6, 20).

--RDBury (talk) 09:25, 23 September 2018 (UTC)