2
$\begingroup$

I am asked:

Let $n$ be a positive integer, let $I = \{1, 2, 3, . . . , n\}$ and let $A$ be the $n \times n$ matrix whose entry in row $i$ and column $j$ for each $i, j \in I$ is equal to $\frac12\bigl(1+(-1)^{i+j}\bigr)$. Evaluate the permanent of $A$.

Actually evaluating a permanent for a $2\times2$ or $3\times3$ matrix is pretty easy. However I am completely lost how to evaluate a matrix $\frac12\bigl(1+(-1)^{i+j}\bigr)$.

Can someone provide some guidance on how to start this problem?

3 Answers 3

3

You should forget about the formula for the matrix terms. This matrix has half of its terms $=1$, the other half is $=0$. To be precise, the $(i,j)$-th term is $=1$ iff $i$ and $j$ have the same parity. Therefore, the permanent of $A$ will be a sum of ones, one for every permutation that conserves parity: $\mathrm{perm}(A)=\#\mathrm{~permutations~that~preserve~parity}$ Obviously, any permutation that preserves parity induces a permutation of the subset of even integers between $1$ and $n$, and induces another permutation of the subset of odd integers between $1$ and $n$. Conversely, two such permutations induce a permutation of $\lbrace 1,\dots,n\rbrace$, so there are $m!\times m!$ such permutations if $n$ is even equal to $2m$, and $m!\times(m+1)!$ if $n$ is odd equal to $2m+1$.

1

So the description just says that the matrix entry at $(i,j)$ is $0$ if $i+j$ is odd, and $1$ if $i+j$ is even.

To evaluate the permanent of an $n\times $n$ matrix$, do an explicit calculation for $n=2$ and $n=3$.

For the permanent of a $4\times 4$, go down the first column. The permanent of the $4\times 4$ is calculated like the determinant, but without the minus signs. Proceed just like for the determinant. Go down the first column. We want $1$ times the permanent of the $3\times 3$ obtained as in determinant calculations, plus $0$ times the permanent of the second $3\times 3$ (nice!), and so on. You can read off the relevant permanents for the $3\times 3$'s from your earlier calculation.

Now for the $5\times 5$, proceed in the same way, using your $4\times 4$ result. Continue. You will get a nice pattern that can be formally proved by induction.

1

A matrix over $\{0,1\}$ could be seen as an adjacency matrix of bipartite graph. Moreover, the permanent of a matrix over $\{0,1\}$ is calculating the number of the perfect matching of the corresponding bipartite graph.

And the bipartite graph of matrix $\left\{\frac{1-(-1)^{i+j}}{2}\right\}_{n\times n}$ consists of two complete bipartite graphs. Hence, the permanent of matrix $\left\{\frac{1-(-1)^{i+j}}{2}\right\}_{n\times n}$ is equal to the $\lceil n/2\rceil!+\lfloor{n/2}\rfloor!$.