Section 4.6.4: Evaluation of Polynomials

Exercise 9. [M25] (H. J. Ryser.) Show that if $X = (x_{ij})$ is an $n \times n$ matrix, then

$$\text{per}(X) = (-1)^n \sum_{\epsilon_1, \ldots, \epsilon_n} (-1)^{\epsilon_1 + \cdots + \epsilon_n} \prod_{1 \le i \le n} \sum_{1 \le j \le n} \epsilon_j x_{ij}$$

summed over all $2^n$ choices of $\epsilon_1, \ldots, \epsilon_n$ equal to 0 or 1 independently. Count the number of addition and multiplication operations required to evaluate $\text{per}(X)$ by this formula.

Verified: no
Solve time: 13m55s

---

Exercise 4.6.4.9 [M25] (H. J. Ryser)

Let

$$ R(X)=(-1)^n\sum_{\epsilon\in{0,1}^n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \prod_{i=1}^n\sum_{j=1}^n \epsilon_jx_{ij}. $$

We shall show that $R(X)=\operatorname{per}(X)$.

Proof of Ryser's formula

For fixed $\epsilon=(\epsilon_1,\ldots,\epsilon_n)$,

$$ \prod_{i=1}^n\sum_{j=1}^n\epsilon_jx_{ij}

\sum_{f:[n]\to[n]} \left(\prod_{i=1}^n x_{i,f(i)}\right) \prod_{i=1}^n \epsilon_{f(i)}. $$

If $I=\operatorname{Im}(f)$, then because $\epsilon_j^m=\epsilon_j$ for

$\epsilon_j\in{0,1}$ and $m\ge1$,

$$ \prod_{i=1}^n \epsilon_{f(i)}

\prod_{j\in I}\epsilon_j . $$

Hence

$$ R(X)

(-1)^n \sum_{f:[n]\to[n]} \left(\prod_{i=1}^n x_{i,f(i)}\right) \sum_{\epsilon\in{0,1}^n} (-1)^{|\epsilon|} \prod_{j\in I}\epsilon_j , $$

where $|\epsilon|=\epsilon_1+\cdots+\epsilon_n$.

It remains to evaluate

$$ C(I)

(-1)^n \sum_{\epsilon\in{0,1}^n} (-1)^{|\epsilon|} \prod_{j\in I}\epsilon_j . $$

Since $\prod_{j\in I}\epsilon_j$ forces $\epsilon_j=1$ for every

$j\in I$,

$$ C(I)

(-1)^n \sum_{\substack{\epsilon_k\in{0,1}\ k\notin I}} (-1)^{|I|+\sum_{k\notin I}\epsilon_k}. $$

Therefore

$$ C(I)

(-1)^{n+|I|} \prod_{k\notin I} \left(\sum_{\epsilon_k=0}^1(-1)^{\epsilon_k}\right). $$

But

$$ \sum_{\epsilon_k=0}^1(-1)^{\epsilon_k} =1-1=0. $$

Hence $C(I)=0$ unless $I=[n]$. When $I=[n]$,

$$ C([n])=(-1)^n(-1)^n=1. $$

Thus the coefficient of

$$ \prod_{i=1}^n x_{i,f(i)} $$

is $1$ if $\operatorname{Im}(f)=[n]$, and $0$ otherwise.

Since $f:[n]\to[n]$ has image $[n]$ exactly when $f$ is a permutation,

$$ R(X)

\sum_{\sigma\in S_n} \prod_{i=1}^n x_{i,\sigma(i)}

\operatorname{per}(X). $$

This proves the identity.

Operation count

Write the formula in subset form. If

$$ S={j:\epsilon_j=1}, $$

then

$$ \operatorname{per}(X)

(-1)^n \sum_{S\subseteq[n]} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S}x_{ij}. $$

There are $2^n$ subsets $S$.

For a fixed subset $S$:

1. For each row $i$, compute

$$ r_i(S)=\sum_{j\in S}x_{ij}. $$

If $|S|=k$, this requires $k-1$ additions. For all rows, the cost is

$$ n(k-1) $$

additions. 2. Compute

$$ \prod_{i=1}^n r_i(S), $$

requiring $n-1$ multiplications.

Summing over all subsets,

$$ \sum_{S\subseteq[n]}(|S|-1)

\sum_{S}|S|-2^n

n2^{,n-1}-2^n. $$

Therefore the total number of additions used in forming all row sums is

$$ n\bigl(n2^{,n-1}-2^n\bigr). $$

Finally, the $2^n$ subset contributions must be accumulated, requiring

$$ 2^n-1 $$

additional additions.

Hence

$$ A

n\bigl(n2^{,n-1}-2^n\bigr)+(2^n-1)

2^{,n-1}(n^2-2n)+2^n-1

2^{,n-1}(n-2)^2-1 $$

additions.

For multiplications, each subset requires $n-1$ multiplications to form the product of the $n$ row sums, so

$$ M=(n-1)2^n. $$

Therefore evaluation of Ryser's formula, interpreted as sums over selected columns, requires

$$ \boxed{(n-1)2^n\ \text{multiplications}} $$

and

$$ \boxed{,2^{,n-1}(n-2)^2-1\ \text{additions}.} $$

These counts correspond to direct evaluation of the subset formula, treating the coefficients $\epsilon_j\in{0,1}$ as selectors rather than counting multiplications by $0$ or $1$.