Skip to main content
31 votes

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$....
Mark Wildon's user avatar
  • 10.9k
26 votes

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 ...
Douglas Zare's user avatar
  • 27.8k
25 votes
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 ...
Nate's user avatar
  • 2,092
25 votes

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 ...
Tony Huynh's user avatar
  • 31.7k
21 votes

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{...
Suvrit's user avatar
  • 28.5k
16 votes

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$-...
Wlodek Kuperberg's user avatar
15 votes

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 ...
T. Amdeberhan's user avatar
14 votes

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 ...
Richard Stanley's user avatar
13 votes
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/...
Henry Cohn's user avatar
  • 16.7k
12 votes
Accepted

The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

It is quite likely. At least, the proof for the case $d\mid n$ is easy. First of all, the restriction $i\ne j$ does not matter: adding $n$ ones changes nothing in the problem. Now notice that $|\...
fedja's user avatar
  • 60.6k
11 votes

How did they come up with the MRRW bound?

For linear programming type bounds it is sometimes only possible to give effective bounds (that is bounds that work and are manageable) and what is surprising is that the primitive method often gives ...
Josiah Park's user avatar
  • 3,177
11 votes

Formula for volume of a convex polytope

Here is one paper, whose introduction will lead you to others: Lasserre, Jean B., and Eduardo S. Zeron. "A new algorithm for the volume of a convex polytope." arXiv math/0106168 (2001). If you ...
Joseph O'Rourke's user avatar
11 votes

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

In my understanding, the connection to modular forms came via a result of Cohn and Elkies in their paper "New upper bounds on sphere packings I," Ann. of Math. 157 (2003) 689-714, also on the arxiv. ...
Harry Richman's user avatar
10 votes
Accepted

Applications of linear programming duality in combinatorics

How about Boosting1 and the Hardcore Lemma, as described in this paper? Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy ...
Joseph O'Rourke's user avatar
8 votes

Applications of linear programming duality in combinatorics

So, this is not an example of using linear programming duality within a proof of a theorem but, rather, an example of using linear programming duality to search for a proof. The discharging method ...
Jon Noel's user avatar
  • 761
8 votes
Accepted

Definition of packing property

That Def 1 and Def 2 are equivalent is a well-known Conjecture, still open as far as I know. Curiously, you can translate the whole conjecture to the language of commutative algebra, see for example ...
Hailong Dao's user avatar
  • 30.3k
7 votes

The cone of positive semidefinite matrices is self-dual? (reference needed)

I know you are looking for a reference and you probably know how to prove it (and that the post is old). However, I want to include a short form of the proof for those coming to the post for this ...
M. Winter's user avatar
  • 12.8k
7 votes
Accepted

Linear programming is continuous

The answer is no. Consider the probem $$x+y\to\max,$$ $$x\geq 0,\; y\geq 0,$$ $$x+y\leq 1.$$ It has infinitely many solutions. One of them is $(0,1)$. Now change the last inequality to $$x+(1+\...
Alexandre Eremenko's user avatar
7 votes

The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

In addition to fedja's clever argument for the case $d|n$, let me prove this for $d=2$ (and $n$ of arbitrary parity). We have $|\cos x|\geqslant 1-\frac2\pi x$ for $x\in [0,\pi/2]$ by concavity of ...
Fedor Petrov's user avatar
7 votes

Is Binary Integer Linear Programming solvable in polynomial time?

Often called Binary Integer Programming (BIP). Wikipedia: Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and ...
Joseph O'Rourke's user avatar
7 votes

Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers

Here is a proof of Conjecture 2. First, we have \begin{split} \sum_{k=1}^n M(n,k) &= \sum_{k=1}^n \sum_{m=k}^n \sum_{d|\gcd(m,k)} d\cdot\mu(d) \\ &= \sum_{m=1}^n \sum_{k=1}^m \sum_{d|\gcd(m,k)...
Max Alekseyev's user avatar
7 votes
Accepted

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an ...
RobPratt's user avatar
  • 5,179
6 votes

Applications of linear programming duality in combinatorics

In Examples of combinatorial duality Garth Isaak demonstrates how Farkas' Lemma (which is LP duality) can be used to prove Landau's characterization of the possible score sequences in round robin ...
Thomas Kalinowski's user avatar
6 votes
Accepted

If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

The application of proximal gradient to this exact problem is considered in (equations (2) and (35) in) the Uncertainty in Artificial Intelligence (UAI) 2019 paper Fast Proximal Gradient Descent for A ...
Mark L. Stone's user avatar
5 votes
Accepted

Better tactics for removing redundant constraints than Linear Programming?

I don't know why you find this surprising. Saying that a particular linear inequality $a x \le b$ is non-redundant is exactly the statement that the linear programming problem, maximize $a x$ subject ...
Robert Israel's user avatar
5 votes

Applications of linear programming duality in combinatorics

Here is a fairly recent example. Davies, Jenssen, Perkins and Roberts use linear programming duality to obtain a tight upper bound on the number of independent sets and matchings in a $d$-regular ...
Jon Noel's user avatar
  • 761
5 votes

Linear programming is continuous

You can get this kind of continuity if the optimal solution is nondegenerate in the following sense. Let the coefficient matrix be $m \times n$, and suppose there is a subset $B$ of $[1,\ldots,n]$ ...
Robert Israel's user avatar
5 votes

The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

In fact, the minimizers of the sum $\sum \langle v_i, v_j \rangle^2$ are precisely tight frames, i.e. sets such that for some $C>0$and for each $x\in \mathbb R^d$, one has $\| x \|^2 = C \sum \...
Dmitriy Bilyk's user avatar
5 votes

Under what conditions does an Integer Programming problem run in polynomial time?

The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed ...
kbala's user avatar
  • 151
5 votes
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 ...
Peter Heinig's user avatar
  • 6,031

Only top scored, non community-wiki answers of a minimum length are eligible