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

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)?

• The answers below write $k$ as the permanent of a matrix of size $k$ or $\log k$. I wonder if it is possible with a matrix of size $n$, where $(n-1)! < k \leq n!$? – Zach Teitler Aug 29 '17 at 18:39
• @Zach, it is true for some k in that range. However, if k is not a multiple of a factorial, one "needs a few more rows". I suspect there is an absolute constant C such that for k less than Cn! that k is representable as the permanent of an order n 0-1 matrix. Gerhard "Finding K Is Another Matter" Paseman, 2017.08.29. – Gerhard Paseman Aug 29 '17 at 19:52
• You can always direct sum with an identity matrix to get additional rows. – Timothy Chow Aug 29 '17 at 21:36
• In fact it seems that even for determinant we can construct $k\times k~0-1$ matrix to represent any number $k-1$, but in this case it's lower bound of size. – rus9384 Aug 29 '17 at 22:46
• @rus9384, indeed one can surpass the kth Fibonacci number in representing positive integers by a determinant of a k by k 0-1 matrix. once k is bigger than 5. Orrick's talk mentioned below gives some detail. Gerhard "And I Can Give More" Paseman, 2017.08.30. – Gerhard Paseman Aug 30 '17 at 16:48

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.

• Nice construction! Shortly after posting my question, I discovered the following paper by Kim, Lee, and Seol that also answers the question: ijpam.eu/contents/2005-19-3/12/12.pdf – Timothy Chow Aug 29 '17 at 17:44
• The graph picture for anyone who doesn't want to work out the details: this is a Hamilton cycle of length $2k$ together with a star whose leaves are all the elements of one colour class and whose centre is in the other. Any choice of matching edge for the centre of the star is a chord that splits the cycle into two paths, each of which has a unique perfect matching, giving the $k$ options. – Ben Barber Aug 29 '17 at 17:49

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 }$$

• Of course, one can represent pq by a block matrix for p and a block for q on the diagonal. This construction using binary of k-1 works well for odd numbers and is rather compact in general. However, even for determinant, the spectrum problem is not well understood, so finding the optimal n given k will require even more cleverness. For example, it is not clear that n=7 might work for k=389. Does the cited paper mention how optimal the construction is? Gerhard "Hasn't Determined Complexity Of Permanent" Paseman, 2017.08.29. – Gerhard Paseman Aug 29 '17 at 18:52
• @GerhardPaseman why pq form? – T.... Aug 30 '17 at 21:40
• pq here means the factor p times the factor q. For numbers m with small factors, the block matrix form reduces the problem of representing m compactly one of representing enough of its small factors compactly. Gerhard "Because It's Easy, That's Why" Paseman, 2017.08.30. – Gerhard Paseman Aug 30 '17 at 22:49

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.