23
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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!$? $\endgroup$ – Zach Teitler Aug 29 '17 at 18:39
  • $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Aug 29 '17 at 19:52
  • $\begingroup$ You can always direct sum with an identity matrix to get additional rows. $\endgroup$ – Timothy Chow Aug 29 '17 at 21:36
  • $\begingroup$ 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. $\endgroup$ – rus9384 Aug 29 '17 at 22:46
  • 1
    $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Aug 30 '17 at 16:48
24
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Timothy Chow Aug 29 '17 at 17:44
  • 10
    $\begingroup$ 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. $\endgroup$ – Ben Barber Aug 29 '17 at 17:49
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Aug 29 '17 at 18:52
  • $\begingroup$ @GerhardPaseman why pq form? $\endgroup$ – T.... Aug 30 '17 at 21:40
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Aug 30 '17 at 22:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.