[seqfan] Re: Number of n X n (0, 1)-matrices having permanent equal to 1

[Max Alekseyev]

Suppose that we have a (0,1)-matrix M with permanent equal to 1. Then
in M there is a unique set of n elements, each equal to 1, whose
product makes the permanent equal 1.
Permute the columns of M so that these n elements become arranged
along the main diagonal, denote the resulting matrix by M'.
It is clear that each M' correspond to n! different matrices M (here
the factor n! comes).

Let M'' be the same as M' except for zeros on the main diagonal. Then
the permanent of M'' is zero.
Viewing M'' as an adjacency matrix of a directed graph G, we notice
that G cannot have a cycle. Indeed, if there is a cycle x_1 -> x_2 ->
... -> x_k -> x_1, then the set of elements (x_1,x_2), (x_2,x_3), ...,
(x_k,x_1) together (y_1,y_1), ..., (y_{n-k},y_{n-k}), where {
y_1,...,y_{n-k} } is the complement of { x_1, ..., x_k } in the set {
1, 2, ..., n }, form a set of elements of the matrix M' whose product
is 1, making the permanent of M' greater than 1. This works in the
reverse direction as well, resulting in the statement:

The permanent of M' is 1 if and only if M'' represents the adjacency
matrix of some DAG.

Therefore, there exist A003024(n) distinct matrices M'.

Regards,
Max

On Tue, Oct 27, 2009 at 1:52 PM, Vladeta Jovovic <vladeta at eunet.rs> wrote:
>
>
>
> SeqFans,
>
> Can someone confirm (my) claim that
>
> A089482(n) =  n!*A003024(n).
>
>
> Best to all,
> Vladeta Jovovic
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>