Is every positive integer the permanent of some 0-1 matrix?

Question

In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:

Is it true that for every positive integer $k$ there exists a balanced bipartite graph with exactly $k$ perfect matchings?

Equivalently, as stated in the title, is every positive integer the permanent of some 0-1 matrix?

The answer is surely yes, but it is not clear to me how to prove it. Entry A089479 of the OEIS reports the number $T(n,k)$ of times the permanent of a real $n\times n$ zero-one matrix takes the value $k$ but does not address the question of whether, for every $k$, there exists $n$ such that $T(n,k)\ne 0$. Assuming the answer is yes, the followup question is, what else can we say about the values of $n$ for which $T(n,k)\ne 0$ (e.g., upper and lower bounds)?

Answer 1

The answer to the question is yes. Given $k$, the 0-1 matrix given by

$1$ $1$ $\dotsc$ $1$ $0$ $0$ $\dotsc$ $0$ $0$ $0$ $0$

$0$ $1$ $1$ $0$ $\dotsc$ $0$ $0$ $\dotsc$ $0$ $0$ $0$

$0$ $0$ $1$ $1$ $0$ $\dotsc$ $0$ $\dotsc$ $0$ $0$ $0$

$\dotsc$

$1$ $0$ $0$ $0$ $0$ $\dotsc$ $\dotsc$ $0$ $0$ $0$ $1$

where the first row has precisely $k$ entries equal to $1$, evidently has permanent equal to $k$.

For $k=1$ the matrix is ($1$). For $k=2$ the matrix is

$1$ $1$

$1$ $1$

For $k=3$ the matrix is

$1$ $1$ $1$

$0$ $1$ $1$

$1$ $0$ $1$.

For $k=4$ the matrix is

$1$ $1$ $1$ $1$

$0$ $1$ $1$ $0$

$0$ $0$ $1$ $1$

$1$ $0$ $0$ $1$

which evidently has permanent equal to $4$.

Please note that also, for each given $k$ and $1\leq \ell \leq k$, this construction can be tweaked to give an explicit $k\times k$ sized $0$-$1$-matrix having permanent precisely $\ell$, just by making the first row have precisely $\ell$ entries equal to $1$.

Please also note that my construction does not have any bearing on the interesting and apparently difficult question which was cited in the present OP: my construction is too wasteful: it utilizes a $k\times k$ matrix, which is far too large when it comes to meet the demands of the OP in said question.

Answer 2

For the record, here is the construction of Kim, Lee, and Seol that I alluded to in my comment to Peter Heinig's answer.

Write $k-1$ in binary, and let $n$ be 1 plus the number of binary digits of $k-1$.

Start with an $n\times n$ matrix with all $1$'s on or above the main diagonal and all $0$'s below the diagonal. Then replace the first $n-1$ entries of the bottom row of the matrix with the binary representation of $k-1$ (one bit per entry).

For example, if $k=389$, then $k-1$ in binary is $110000100$. Then $n=1+9=10$ and the matrix is $$\matrix{ 1&1&1&1&1&1&1&1&1&1\cr 0&1&1&1&1&1&1&1&1&1\cr 0&0&1&1&1&1&1&1&1&1\cr 0&0&0&1&1&1&1&1&1&1\cr 0&0&0&0&1&1&1&1&1&1\cr 0&0&0&0&0&1&1&1&1&1\cr 0&0&0&0&0&0&1&1&1&1\cr 0&0&0&0&0&0&0&1&1&1\cr 0&0&0&0&0&0&0&0&1&1\cr 1&1&0&0&0&0&1&0&0&1\cr }$$

EDIT. Igor Pak has pointed out to me that the above result dates back to at least the 1965 paper by Brualdi and Newman, Some theorems on the permanent, J. Research NBS 69B, 159–163.

Answer 3

If an order n (0,1) matrix has r rows with all ones, its permanent is a multiple of r! by an easy argument. It follows that the largest odd number which is a permanent of an order n matrix is q = der(n) + der(n-1), which is a sum of numbers of derangements, and is a little larger than $n!/e$. I suspect that the smallest positive number not expressible as a permanent of this size matrix is an odd integer which is not much smaller, perhaps about half, of q. If so, then we can shave a little bit off of n=log(k) in the construction in Timothy Chow's post. For some motivation for this problem, look at Will Orrick's talk mentioned (for determinants) at https://mathoverflow.net/a/271273 .

Gerhard "Also A Potential Polymath Project" Paseman, 2017.08.29.