In the course of discussing [another MO question](https://mathoverflow.net/questions/279690/graph-to-bipartite-conversion-preserving-number-of-perfect-matchings?noredirect=1#comment689778_279690) 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](http://oeis.org/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)?



Is every positive integer the permanent of some 0-1 matrix?
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](https://mathoverflow.net/questions/279690/graph-to-bipartite-conversion-preserving-number-of-perfect-matchings?noredirect=1#comment689778_279690)** 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](https://mathoverflow.net/questions/279690/graph-to-bipartite-conversion-preserving-number-of-perfect-matchings?noredirect=1#comment689778_279690).


