TAOCP 4.6.4 Exercise 10

Let $X = (x_{ij})$ be an $n \times n$ matrix.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.4: Evaluation of Polynomials

Exercise 10. [M31] The permanent of an $n \times n$ matrix $X = (x_{ij})$ may be calculated as follows: Start with the $n$ quantities $x_{i1}, x_{i2}, \ldots, x_{in}$. For $1 \le k \le n$, assume that the $\binom{n}{k}$ quantities $A_{kS}$ have been computed, for all $k$-element subsets $S$ of ${1, 2, \ldots, n}$, where $A_{kS} = \sum x_{1j_1} \ldots x_{kj_k}$ summed over all $k!$ permutations $j_1 \ldots j_k$ of the elements of $S$; then form

$$A_{(k+1)\tilde{S}} = \sum_{j \in \tilde{S}} x_{(k+1)j} A_{kS}$$

We have $\text{per}(X) = A_{{1,2,\ldots,n}}$. How many additions and multiplications does this method require? How much temporary storage is needed?

Verified: yes
Solve time: 1m59s

Setup

Let $X = (x_{ij})$ be an $n \times n$ matrix. The permanent of $X$ is defined by

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

where the sum ranges over all $n!$ permutations $\sigma$ of ${1,2,\ldots,n}$.

The method described in the exercise computes intermediate quantities $A_{kS}$ for $1 \le k \le n$, where $S \subseteq {1,2,\ldots,n}$ with $|S| = k$, and

$$ A_{kS} = \sum_{\substack{(j_1, \ldots, j_k) \text{ distinct} \ {j_1, \ldots, j_k} = S}} x_{1j_1} \cdots x_{kj_k}. $$

These quantities satisfy the recurrence

$$ A_{(k+1)\tilde{S}} = \sum_{j \in \tilde{S}} x_{(k+1)j} A_{k,\tilde{S}\setminus{j}}, $$

for all $(k+1)$-element subsets $\tilde{S} \subseteq {1,\ldots,n}$, with the initial values $A_{1{j}} = x_{1j}$. Then

$$ \mathrm{per}(X) = A_{n{1,2,\ldots,n}}. $$

We are asked to determine the number of additions and multiplications required and the amount of temporary storage needed.

Solution

Counting multiplications

For $k = 1$, the initial quantities are

$$ A_{1{j}} = x_{1j}, \quad 1 \le j \le n, $$

which require no multiplications.

For $2 \le k \le n$, each $(k+1)$-element subset $\tilde{S}$ requires computing

$$ A_{(k+1)\tilde{S}} = \sum_{j \in \tilde{S}} x_{(k+1)j} A_{k,\tilde{S}\setminus{j}}. $$

Each term $x_{(k+1)j} A_{k,\tilde{S}\setminus{j}}$ is a single multiplication. Since there are $k+1$ elements in $\tilde{S}$, there are exactly $k+1$ multiplications per subset.

There are $\binom{n}{k+1}$ such subsets, so the total number of multiplications for level $k+1$ is

$$ \binom{n}{k+1} (k+1). $$

Summing over $k = 1, \ldots, n-1$, the total number of multiplications is

$$ \sum_{k=1}^{n-1} \binom{n}{k+1} (k+1) = \sum_{r=2}^{n} \binom{n}{r} r. $$

By the binomial identity

$$ \sum_{r=0}^n r \binom{n}{r} = n 2^{n-1}, \quad \text{and } r=0,1 \text{ terms contribute }0+1 = 1, $$

so

$$ \sum_{r=2}^{n} r \binom{n}{r} = n 2^{n-1} - n = n(2^{n-1}-1). $$

Hence, the total number of multiplications is

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

Counting additions

Each $A_{(k+1)\tilde{S}}$ is obtained by summing $k+1$ terms $x_{(k+1)j} A_{k,\tilde{S}\setminus{j}}$, which requires $k$ additions per subset. There are $\binom{n}{k+1}$ subsets of size $k+1$, so the total number of additions is

$$ \sum_{k=1}^{n-1} \binom{n}{k+1} k = \sum_{r=2}^{n} \binom{n}{r} (r-1) = \sum_{r=2}^{n} r \binom{n}{r} - \sum_{r=2}^{n} \binom{n}{r}. $$

We have

$$ \sum_{r=2}^{n} r \binom{n}{r} = n(2^{n-1}-1), \quad \sum_{r=2}^{n} \binom{n}{r} = 2^n - n - 1. $$

Therefore, the total number of additions is

$$ n(2^{n-1}-1) - (2^n - n - 1) = n 2^{n-1} - n - 2^n + n + 1 = (n-2) 2^{n-1} + 1. $$

Hence, the total number of additions is

$$ \boxed{(n-2)2^{n-1} + 1}. $$

Temporary storage

At any stage $k$, one must store the values of $A_{kS}$ for all $k$-element subsets $S$. There are $\binom{n}{k}$ such subsets, and the largest number occurs for $k = \lfloor n/2 \rfloor$, by symmetry of the binomial coefficients.

Thus, the temporary storage requirement is

$$ \boxed{\binom{n}{\lfloor n/2 \rfloor}}. $$

This allows overwriting lower-level values as soon as they are no longer needed, so no more storage is required.

Verification

For small $n$, e.g., $n=3$, the method computes

  • Level 1: $A_{1{1}} = x_{11}, A_{1{2}} = x_{12}, A_{1{3}} = x_{13}$, zero multiplications.
  • Level 2: subsets of size 2, each requires 2 multiplications and 1 addition. There are 3 subsets: total 6 multiplications, 3 additions.
  • Level 3: subset ${1,2,3}$ requires 3 multiplications and 2 additions.

Total: $6+3=9$ multiplications, $3+2=5$ additions. Check against formulas:

  • Multiplications: $n(2^{n-1}-1) = 3(4-1)=9$, correct.
  • Additions: $(n-2)2^{n-1}+1 = 1*4+1=5$, correct.

Temporary storage: $\binom{3}{1}=3$ or $\binom{3}{2}=3$, matches largest level.

This confirms the derivation.

Notes

This approach is equivalent to the Ryser formula for the permanent expressed via subset sums, adapted for recursive computation. Alternative methods, such as inclusion-exclusion formulas over $0$-$1$ indicator vectors, yield the same order of operations $O(n 2^n)$ but may differ in constants.

For large $n$, the method is exponential in $n$, and practical evaluation is feasible only for $n \le 20$ on typical computers.

∎