# Tag Info

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

This is an instance of Holte's Amazing matrix. Consider addition of binary digits. Start with a carry of $c \in \{0,1,\ldots,2(m-1)\}$. Choose $2m-1$ bits uniformly at random, and add their sum to $c$....
• 10.6k

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

The Lindstrom-Gessel-Viennot lemma says that the number of families of nonintersecting lattice paths can be counted by a determinant. Let $a_i = (2m-i,i)$. Let $b_j = (2m-2j,-2m+2j)$. Then the number ...
• 27.7k
Accepted

### Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Consider the polytope in $\mathbb{R}^3$ with $8$ vertices at coordinates $(\pm 1, \pm 2, 1), (\pm 2, \pm 1, -1)$. Geometrically this looks like a cube where the top face is stretched in the direction ...
• 1,982

### Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Your question is essentially about extension complexity. In general, the extension complexity of a polytope $P$ is the minimum number of facets over all polytopes $Q$ which project to $P$. You are ...
• 30.2k

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Here is a very low-brow answer to the original question. Consider the lower-triangular matrix \begin{equation*} V = [V_{ij}] = \left[\binom{i-1}{j-1}\right]\quad \text{for}\quad i \ge j. \end{...
• 28.2k

### Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Another, combinatorially minimal, counterexample of such a polytope $P$ (with only five facets) is the convex hull of the six vertices $(\pm2, 0, 0)$, $(\pm1, \pm1, 1)$. Its projection to the $xy$-...
• 7,240

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Let $A_n(x,\lambda)$ be the $n\times n$ matrix $$\left[\binom{x}{2j-i+\lambda}\right]_{i,j=1}^n.$$ Let's "generalize to trivialize". Sometimes, generalizations offer more elbow room to maneuver, such ...

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

The matrix $A_n(x,\lambda)$ is obtained from the dual Jacobi matrix for the partition $\mu=(n+\lambda,n-1+\lambda,...,1+\lambda)$ by setting $x$ variables equal to 1 and the remaining variables equal ...
• 47.9k
Accepted

### Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?

This is a tough question, and I don’t think there’s a definitive answer yet. For some mathematical details, see the following survey articles: https://arxiv.org/abs/1611.01685 https://arxiv.org/abs/...
• 16.4k
Accepted

Accepted

### a linear programming problem

The statement in the gray box is an immediate consequence of Helly's theorem: for each $i$, the set $\{ v\in\mathbb{R}^n\colon\ f_i(v)\geq 0\}$ is convex, and because of $r>n+1$, the condition ...
• 5,911
Accepted

### Sampling uniformly from the vertices of a polytope

Here is one efficient approach, performing a random walk with a rapid mixing time, that has been implemented for a particular class of polytopes, but which might well be adaptable to a more general ...
• 168k