Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
1  
I guess describing the set of permanents for matrices of a specific size could be more involved? –  Mariano Suárez-Alvarez May 13 '12 at 2:46
2  
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 –  Gerhard Paseman May 13 '12 at 2:47
1  
@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$. –  Mark Sapir May 13 '12 at 3:01
1  
or the function $l(n)$ which is the smallest number which is NOT a permanent of a $n\times n$-matrix. –  Mark Sapir May 13 '12 at 3:10
1  
Sequence $l(n)$ is A089477 in the Encyclopedia. –  Mark Sapir May 13 '12 at 4:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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