TAOCP 4.6.4 Exercise 12
Let S=\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_jx_{ij},
Section 4.6.4: Evaluation of Polynomials
Exercise 12. [M50] What is the minimum number of multiplications required to form the product of two $n \times n$ matrices? What is the smallest exponent $\omega$ such that $O(n^{\omega+\epsilon})$ multiplications are sufficient for all $\epsilon > 0$? (Find good upper and lower bounds for small $n$ as well as large $n$.)
Verified: no
Solve time: 6m16s
Setup
Let
$$ S=\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_jx_{ij}, $$
where each $\epsilon_j\in{0,1}$.
We must prove that
$$ \operatorname{per}(X)=(-1)^n S, $$
and then count the arithmetic operations required to evaluate the permanent by this formula.
The permanent is
$$ \operatorname{per}(X) =\sum_{\sigma\in S_n} \prod_{i=1}^n x_{i,\sigma(i)}. $$
Solution
Expand the product in $S$:
$$ \prod_{i=1}^n \sum_{j=1}^n \epsilon_jx_{ij} = \sum_{j_1,\ldots,j_n} \epsilon_{j_1}\cdots\epsilon_{j_n} x_{1j_1}\cdots x_{nj_n}, $$
where the sum ranges over all $n$-tuples $(j_1,\ldots,j_n)$ with $1\le j_i\le n$.
Substituting into $S$ and interchanging the order of summation gives
$$ S = \sum_{j_1,\ldots,j_n} x_{1j_1}\cdots x_{nj_n} \sum_{\epsilon_1,\ldots,\epsilon_n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \epsilon_{j_1}\cdots\epsilon_{j_n}. $$
For a fixed $n$-tuple $(j_1,\ldots,j_n)$, let
$$ T(j_1,\ldots,j_n) = \sum_{\epsilon_1,\ldots,\epsilon_n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \epsilon_{j_1}\cdots\epsilon_{j_n}. $$
Let $A={j_1,\ldots,j_n}$ be the set of distinct indices occurring among the $j_i$, and let $|A|=r$.
Since $\epsilon_j^k=\epsilon_j$ for $k\ge1$,
$$ \epsilon_{j_1}\cdots\epsilon_{j_n} = \prod_{j\in A}\epsilon_j. $$
Hence
$$ T(j_1,\ldots,j_n) = \sum_{\epsilon_1,\ldots,\epsilon_n} \prod_{j\in A}(-\epsilon_j) \prod_{j\notin A}(-1)^{\epsilon_j}. $$
The variables separate, so
$$ T(j_1,\ldots,j_n) = \prod_{j\in A} \left(\sum_{\epsilon_j=0}^1(-1)^{\epsilon_j}\epsilon_j\right) \prod_{j\notin A} \left(\sum_{\epsilon_j=0}^1(-1)^{\epsilon_j}\right). $$
The two elementary sums are
$$ \sum_{\epsilon=0}^1(-1)^\epsilon\epsilon =0-1=-1, $$
and
$$ \sum_{\epsilon=0}^1(-1)^\epsilon =1-1=0. $$
Therefore
$$ T(j_1,\ldots,j_n) = (-1)^r,0^{,n-r}. $$
If $r<n$, then $T(j_1,\ldots,j_n)=0$.
If $r=n$, every index $1,\ldots,n$ occurs exactly once among $j_1,\ldots,j_n$. Thus $(j_1,\ldots,j_n)$ is a permutation $(\sigma(1),\ldots,\sigma(n))$, and
$$ T(j_1,\ldots,j_n)=(-1)^n. $$
Consequently,
$$ S = (-1)^n \sum_{\sigma\in S_n} \prod_{i=1}^n x_{i,\sigma(i)} = (-1)^n\operatorname{per}(X). $$
Hence
$$ \boxed{\operatorname{per}(X) = (-1)^n \sum_{\epsilon_1,\ldots,\epsilon_n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \prod_{i=1}^n \sum_{j=1}^n \epsilon_jx_{ij}}. $$
To evaluate the permanent directly from this formula, consider one fixed choice of $(\epsilon_1,\ldots,\epsilon_n)$.
For each row $i$, the quantity
$$ s_i=\sum_{j=1}^n\epsilon_jx_{ij} $$
requires $n-1$ additions. Since there are $n$ rows, this contributes
$$ n(n-1) $$
additions.
The product
$$ s_1s_2\cdots s_n $$
requires
$$ n-1 $$
multiplications.
Multiplication by the sign $(-1)^{\epsilon_1+\cdots+\epsilon_n}$ is merely a change of sign and is counted as an addition operation under the convention stated in the text. Accumulating the $2^n$ terms into the final sum requires one addition per term. Thus each of the $2^n$ summands contributes one addition to the accumulation.
Therefore, over all $2^n$ choices of $(\epsilon_1,\ldots,\epsilon_n)$,
$$ 2^n(n-1) $$
multiplications are required, and
$$ 2^n n(n-1)+2^n = 2^n\bigl(n^2-n+1\bigr) $$
additions are required.
Thus the operation counts are
$$ \boxed{2^n(n-1)\ \text{multiplications}} $$
and
$$ \boxed{2^n\bigl(n^2-n+1\bigr)\ \text{additions}}. $$
Verification
The coefficient of a monomial
$$ x_{1j_1}\cdots x_{nj_n} $$
in the expanded formula is
$$ T(j_1,\ldots,j_n). $$
This coefficient vanishes unless every column index $1,\ldots,n$ occurs exactly once. Hence every non-permutation term cancels.
For a permutation term, the coefficient equals $(-1)^n$. Multiplication by the outer factor $(-1)^n$ changes this coefficient to $1$. Therefore each permanent term appears exactly once, and no other terms remain.
The arithmetic count follows from evaluating $n$ row sums and one $n$-factor product for each of the $2^n$ choices of $(\epsilon_1,\ldots,\epsilon_n)$, then accumulating the resulting signed terms. ∎