# Set of permanents over binary square matrices

I am interested in the collection of possible values for permanents over square binary matrices. Consider $n \times n$ 0-1 matrices. The possible permanents for $n=1$ are $\{0,1\}$. For $n=2$ the possible permanents are $\{0,1,2\}$, and for $n=3$ the permanents are $\{0,1,2,3,4,6\}$. Note that $5$ is missing for $n=3$.

Let $p(n)$ denote the set of permanents for $n \times n$ binary matrices, and let $$p(\mathbb{N}) = \bigcup_{n \in \mathbb{N}} p(n)$$ We can show at least that $n! \in p(\mathbb{N})$ for all $n$ and that $p(\mathbb{N})$ is closed under products.

Is this set $p(\mathbb{N})$ well understood? A pointer would be welcome. If $\mathbb{N} \subset p(\mathbb{N})$, a construction proof would be appreciated. It is not clear how to extend the trivial rectangular matrix with permanent $k$ to a square matrix.

The following related integer sequence counts distinct permanents: http://oeis.org/A087983

That set consists of all natural numbers. Consider the $n\times n$-matrix $A=(a_{ij})$ where all numbers on the diagonal, first row and first column are equal to 1, all the other entries are 0. Then the permanent of that matrix is $n$. Indeed, each non-zero summand in the definition of permanent should start with some $a_{1,i}$. Then the $i$-th factor of that product, $i > 1$, cannot be $a_{i,i}$. It must then be $a_{i,1}$. Hence all the other factors in that product are from the diagonal. Therefore exactly one non-zero summand in the permanent contains $a_{1,i}$, for every $i=1,...,n$. So the permanent contains exactly $n$ non-zero summands, and is equal to $n$.

• I guess describing the set of permanents for matrices of a specific size could be more involved? May 13, 2012 at 2:46
• Will Orrick has enhanced his his maxdet.indiana.edu site to contain information on the determinant spectrum problem as well as maximum determinant for order n 0-1 matrices. Perhaps he can be encouraged to add permanent spectrum info as well. Gerhard "Ask Me About Binary Matrices" Paseman, 2012.05.12 May 13, 2012 at 2:47
• @Mariano: certainly. For example it would be interesting, I think, to understand the function $n(k)$ - the minimal size of a matrix with permanent $k$. I only showed that $n(k)\le k$ but it may be much smaller than $k$.
– user6976
May 13, 2012 at 3:01
• or the function $l(n)$ which is the smallest number which is NOT a permanent of a $n\times n$-matrix.
– user6976
May 13, 2012 at 3:10
• Sequence $l(n)$ is A089477 in the Encyclopedia.
– user6976
May 13, 2012 at 4:15