IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

THE POWER OF
COMMUTATIVITY

Laurent HYAFIL

Rapport de Recherche N° 249

Août 1977
THE POWER OF COMMUTATIVITY

Laurent HYAFIL

IRIA / LABORIA

Résumé :

Dans cet article nous montrons que le calcul d'un déterminant nécessite un nombre exponentiel de multiplication si l'on n'autorise pas la commutativité. Ceci montre que l'utilisation de la commutativité peut réduire un calcul de complexité exponentielle à un calcul de complexité polynomial.

Abstract :

In this paper we show that the computation of the determinant requires an exponential number of multiplications if the commutativity of indeterminates is not allowed. The determinant can be computed in polynomial time with the commutation of indeterminates. Hence the use of commutativity can reduce a computation of exponential complexity to a computation of polynomial complexity.

<figure><img src="image_2.png" /></figure>
# 1. INTRODUCTION

The power given by the use of the commutation of indeterminates to speed up the computations has only been studied for bilinear forms. In this case, Winograd [7] shows that when we assume noncommutativity, the nonscalar *-complexity doubles at most. Hopcroft and Kerr [3] prove that the use of commutativity of matrix elements effectively reduces the number of multiplications required.

In this paper we study the power given by the commutativity for the computation of polynomials. More specifically we show that the computation of the determinant without commutativity requires an exponential number of non-scalar multiplications. The determinant can be computed in polynomial time with the commutation of indeterminates, even without division (as a consequence of Strassen's result [6] on the way of avoiding divisions). This yields that the use of commutation can reduce a computation from exponential time to polynomial time.

After giving definitions in section 2 we give in section 3 a characterization of the complexity of a set of homogeneous polynomials. This characterization was first stated in [4] (in the commutative case) for

reducing the complexity of a multilinear form to the complexity of a set of linear forms. In section 4 we prove a lower bound on the computation of the determinant by reducing this problem to a problem of a rank of a tensor as it has been done for bilinear forms (Gastinel ([2]), Fiduccia ([1]), Strassen ([5])).

# 2. DEFINITIONS

- K will denote a commutative field.

- $K\{x_1, x_2, \dots, x_n\}$ the ring extension of K by the noncommuting indeterminates $x_1, x_2, \dots, x_n$.

- A program $\beta$ in $K\{x_1, x_2, \dots, x_n\}$ mod. $K\{x_1, x_2, \dots, x_n\}$ is a sequence $F = \{f_0, f_1, \dots, f_\ell\}$ of functions of $K\{x_1, x_2, \dots, x_n\}$ such that $f_i \in K\{x_1, x_2, \dots, x_n\}$ or $f_i = f_j \circ f_k$ with $j, k < i$ and $\circ \in \{+, -, x\}$.

- A program $\beta$ computes a function $f$ of $K\{x_1, x_2, \dots, x_n\}$ if $f \in F$.

- A non scalar multiplication is such that $f_i = f_j \circ f_k$ with $f_j, f_k \notin K$.

- $L(\ast/P_1, P_2, \dots, P_m)$ will denote the *-complexity of $P_1, P_2, \dots, P_m$ i.e. the minimum number of non scalar
lar multiplications necessary to compute $P_1,P_2...$ 
$P_m$ with a program $\beta$.

- A program $\beta$ will be called homogeneous of degree $d$ if:

a) For any additive operation of $\beta$, $P_i = Q_i + R_i$ 
then $Q_i$ and $R_i$ are homogeneous and have a same 
degree $\le d$.

b) For any multiplication $P_i = Q_i \times R_i$, $Q_i$ and $R_i$ are homogeneous and the degree of $P_i$ is $\le d$.

- $L(Hxd/P_1,P_2,\dots,P_m)$ will denote the minimum num- 
ber of non scalar multiplications necessary to 
compute $P_1,P_2,\dots,P_m$ with an homogeneous program 
of degree $d$.

### 3. ON THE COMPLEXITY OF A FAMILY OF HOMOGENEOUS POLYNOMIALS

**Theorem 1** : Let $P_1,P_2,\dots,P_m$ a family of homogeneous polynomials of $K\{x_1,x_2,\dots,x_n\}$ of degrees $\le d$ :

$$ \underline{L(*/P_1P_2\dots P_m)} \ge \frac{2}{[d(d-1)]} L(Hxd/P_1P_2\dots P_m). $$

*Proof* : Let $\beta$ be a program computing $P_1P_2\dots P_m$ in $K\{x_1,x_2,\dots,x_n\}$ mod $Ku\{x_1,x_2,\dots,x_n\}$. $\beta$ is a sequence $F = \{f_0,f_1,\dots,f_\ell\}$ of functions of $K\{x_1,\dots,x_n\}$ where $f_i = f_j \circ f_k$ ($\alpha = +,-,x$).

For $1 \le \alpha \le n$ let $x_\alpha = \lambda x'_\alpha$. $\beta$ can be considered as a program on $K\{x_1,x_2,\dots,x_n\}(\lambda)$ computing polynomials $P'_1P'_2\dots P'_m$ in $\lambda$ which are in fact monomials of degrees $\le d$.

Define $f_u^\alpha \in K\{x'_1,x'_2,\dots,x'_n\}$ for $1 \le u \le \ell$ and $1 \le \alpha \le d$ by:

$$ f_u = \sum_{\alpha=0}^{\deg(f_u)} f_u^{\alpha} x'^{\alpha}. $$

$f_u^\alpha$ are homogeneous polynomials in $K\{x'_1,x'_2,\dots,x'_n\}$.

From $\beta$ we build an homogeneous program $\beta'$ in repla-
cing each instruction $f_i = f_j \circ f_k$ by a sequence of ins-
tructions in the following way :

a) $o = +,-$

$f_i^\alpha = f_j \circ f_k^\alpha$ is replaced in $\beta'$ by the $d+1$ instruc-
tions : $f_i = f_j \circ f_k$ for $0 \le \alpha \le d$.

b) $o = x$

$f_i = f_j \circ f_k$ is replaced in $\beta'$ by the instruc-
tions generated by the following program :

for $0 \le \alpha \le d$

$$ \underline{\underline{\underline{\underline{\text{set}}}}} \quad \left[ \begin{array}{l} g_i^{\alpha, -1} = 0 \\ \text{for } 0 \le \beta \le \alpha \\ \underline{\underline{\underline{\text{set}}}}} \quad \left[ \begin{array}{l} h_i^{\alpha, \beta} = f_j^{\beta} \times f_k^{\alpha-\beta} \\ g_i^{\alpha, \beta} = g_i^{\alpha, \beta-1} + h_i^{\alpha, \beta} \\ f_i^{\alpha} = g_i^{\alpha, \alpha} \end{array} \right. \end{array} \right. $$

It can easily be verified that for $\lambda = 1$, $\beta'$ is an
homogeneous program which computes $P_1P_2\dots P_m$ from
$x_1,x_2,\dots,x_n$. The number of non scalar multiplications
of $\beta'$ is at most $\frac{d(d-1)}{2}$ times the number of non scalar
multiplications of $\beta$. $\square$

Let $P_1,P_2,\dots,P_m$ be a family of homogeneous polyno-
mials of degrees $\le d$.

Define $\delta_d(P_1,P_2,\dots,P_n) \in N$ in the following way :
$\delta_d(P_1,P_2,\dots,P_m)$ is the least integer $\alpha$ such that
there exists a family of homogeneous polynomials of
$K\{x_1,x_2,\dots,x_n\}$ $U_1,U_2,\dots,U_\alpha$ with :

$$ -\frac{d}{3} \le \deg U_j \le \frac{2d}{3} \quad \text{for } 1 \le j \le \alpha. \qquad (1) $$

$$ - \text{For } 1 \le i \le m \text{ if } \frac{d}{3} \le \deg (P_i) \le d \text{ then there exist} \\ v_1^i, v_2^i, \dots, v_\alpha^i \text{ homogeneous polynomials of } (2) $$

$K\{x_1,x_2,\dots,x_n\}$ such that :

$$ P_i = \sum_{j=1}^{\alpha} U_j v_j^i. $$

**Theorem 2** : Let $P_1,P_2,\dots,P_m \in K\{x_1,\dots,x_n\}$ be a fami-
ly of homogeneous polynomials of degrees $\le d$, then :

$$ \underline{\underline{\delta_d(P_1,P_2,\dots,P_m)} \le L(Hxd/P_1,P_2,\dots,P_m) + n}} $$

*Proof* : The proof is by induction on $L(Hd/P_1,P_2,\dots,P_m)$
minimal length of an homogeneous program of degree $d$
which computes $P_1,P_2,\dots,P_m$.

a) We first show that if $L(Hd/P_1,P_2,\dots,P_m) = 0$ 
then $\delta_d(P_1,P_2,\dots,P_m) \le n$. If $L(Hd/P_1,P_2,\dots,P_m)=0$ 
then $\forall i, P_i \in K \cup x_1 \cup x_2 \cup \dots \cup x_n$ and we can 
choose $U_i = x_i$ for $1 \le i \le n$.

b) Assume $L(Hd/P_1,P_2,\dots,P_m) \le \lambda \Rightarrow \delta_d(P_1,P_2,\dots,P_m) \le n+L(Hxd/P_1,P_2,\dots,P_m)$ and we show that $L(Hd/P_1,P_2,\dots,P_m) = \lambda+1 \Rightarrow \delta_d(P_1,P_2,\dots,P_m) \le n+L(Hxd/P_1,P_2,\dots,P_m)$
Let $Q_1, Q_2, \dots, Q_m$ be a set of homogeneous polynomials
such that $L(Hd/Q_1, Q_2, \dots, Q_m) = \lambda+1$. The homogeneous
program $\beta$ which computes $Q_1, Q_2, \dots, Q_m$ in $\lambda+1$ instruc-
tions has a last instruction the result of which can be
assumed to be $Q_1$. So $Q_1 = f_i \circ f'_i$ and
$L(Hd/f_i, f'_i, Q_2, \dots, Q_m) \le \lambda$. According to the induction
hypothesis $\delta_d(f_i, f'_i, Q_2, \dots, Q_m) \le n+\ell$, with
$\ell = L(H \times_d f_i, f'_i, Q_2, \dots, Q_m)$, we can associate to $f_i$,
$f'_i, Q_2, \dots, Q_m$ a family of homogeneous polynomials $U_1$,
$U_2, \dots, U_{n+\ell}$ satisfying the previous conditions (1) and
(2). Then we have :

$$
- \text{ if deg } (f_i) \ge \frac{d}{3} : f_i = \sum_{j=1}^{n+\ell} U_j V_j,
$$

$$
- \text{ if deg } (f'_i) \ge \frac{d}{3} : f'_i = \sum_{j=1}^{n+\ell} U_j V_j,
$$

$$
- \text{ if } i \ge 2, \deg(Q_i) \ge \frac{d}{3} \text{ then } Q_i = \sum_{\substack{j=1 \\ j \ne i}} U_j V_j, \qquad n+\ell
$$

for a set of homogeneous polynomials $V_j, V'_j, V_j^i$.

We want to show that there exists a set of polynomials
$W_j$, $1 \le j \le t$, generating $Q_1, Q_2, \dots, Q_m$, which satisfies the
above conditions (1) and (2) where $t \le n+L(H \times_d Q_1, Q_2, \dots, Q_m)$.
Hence $t$ must satisfy $t \le n+\ell$ if $Q_1 = f_i \pm f_i'$ and
$t \le n+\ell+1$ if $Q_1 = f_i \times f_i'$.

If $\deg(Q_1) < \frac{d}{3}$ or $\deg(Q_1) > d$ we choose for generating $Q_1, Q_2, \dots, Q_m$ the set $W_h = U_h$ for $h = 1, n+\ell$.

$$
\text{Assume } \frac{d}{3} \le \deg(Q_1) \le d :
$$

Case 1 $Q_1 = f_i \pm f'_i$

We choose $W_h = U_h$ for $h=1, n+\ell$, since :

$$
Q_1 = f_i \pm f'_i = \sum_{j=1}^{n+\ell} U_j (V_j \pm V'_j).
$$

Case 2 $Q_i = f_i \times f_i'$

$$
a) \deg(f_i) \ge \frac{d}{3} (\text{resp. } \deg(f_i') \ge \frac{d}{3}).
$$

$$
f_i = \sum_{j=1}^{n+\ell} U_j V_j \text{ and } Q_i = f_i f_i' = \sum_{j=1}^{n+\ell} U_j (V_j f_i')
$$

so we can choose : $W_h = U_h$ for $h = 1, n+\ell$.

$$
b) \deg(f_i) < \frac{d}{3} \text{ and } \deg(f_i') < \frac{d}{3}.
$$

$$
\frac{d}{3} \leq \deg(Q_i) < \frac{2d}{3} \text{ and we can choose}
$$

$$
W_h = U_h, \text{ for } h=1, n+\ell \text{ and } W_{\ell+n+1} = Q_1. \Box
$$

4. THE COMPLEXITY OF THE NON-COMMUTATIVE COMPUTATION OF
A DETERMINANT

From Theorem 2 we can relate the complexity of the
noncommutative computation of a determinant D to the
quantity $\delta_d(D)$. In this section we give lower bounds on
$\delta_d(D)$ which will induce lower bounds on $L(\ast/D)$. We first
give some definitions.

- $\mathbf{x}_i$ denotes the vector of noncommutating indeterminates $x_i^j$ for $1 \le j \le n$.

- A multilinear form in the $n$ vectors $\mathbf{x}_i$ for $a \le i \le b$ is a polynomial :

$$
\sum_{1 \le j_a \le n} \lambda^{j_a} j_a \prod_{a=1}^{j_a+1} x_a^{j_a+1} \cdots x_b^{j_b} .
$$
$$
\begin{array}{r@{\,}l}
1 \le & j_a+1 \le n \\
& \vdots \\
& 1 \le j_b \le n
\end{array}
$$

with $\lambda_{j_a} \cdots j_b \in K$.

- $D_n$ is the determinant in the $n^2$ noncommuting indeterminates :

$$
x_i^j \quad 1 \le i \le n, \ 1 \le j \le n.
$$

- We define $r(D_{2q})$ by :

$$
r(D_{2q}) = \min \{ \alpha | D_{2q} = \sum_{k=1}^{\alpha} U_K V_K \},
$$

where $U_K$ is a multilinear form of the $q$ vectors
$X_i$ for $1 \le i \le q$ and $V_K$ a multilinear form in the $q$
vectors $X_i$ for $q < i \le 2q$. All polynomials are with
noncommutative indeterminates.

**Lemma 1 :** $r(D_2[\frac{n}{3}]) \le \delta_n(D_n)$.

**Proof** : We have :

$$
D_n = \sum_{i=1}^{\delta_n(D_n)} U_i V_i \quad (1)
$$

where $U_i$ and $V_i$ are homogeneous polynomials which satisfy :

$$
\frac{n}{3} \le \deg(U_i) \le \frac{2n}{3} \text{ for } 1 \le i \le \delta(D_n).
$$
Since the above decomposition is minimal, $U_i$ and $V_i$ are multilinear forms, $U_i$ is multilinear in the $s_i$ vectors $X_k$ with $1 \le k \le s_i$ and $V_i$ in the $n-s_i$ vectors $X_k$ with $s_i \le k \le n$, where $\frac{n}{3} \le s_i \le \frac{2n}{3}$.

If in equation (1) we replace $x_i^j$ by:

$$0 \text{ for } \left[\frac{n}{3}\right] \le i, j \le n - \left[\frac{n}{3}\right], i \ne j,$$

and by:

$$1 \text{ for } \left[\frac{n}{3}\right] \le i, j \le n - \left[\frac{n}{3}\right], i = j,$$

then, the left part of the equation (1) is (within a change of sign) exactly a determinant $2\left[\frac{n}{3}\right] \times 2\left[\frac{n}{3}\right]$ and the right part becomes a decomposition of the type $r(D_2\left[\frac{n}{3}\right])$. $\square$

**Theorem 3** : Let $L(\*/D_n)$ be the minimum number of non-scalar multiplications necessary to compute the determinant of order $n$ in $n^2$ noncommutative indeterminates, then :

$$\left[ \left( \left[ \frac{2}{3} \right] \right)^2 - n^2 \right] \times \frac{2}{n(n-1)} \le L(\*/D_n).$$

*Proof* : From theorem 1 and 2 and Lemma 1 we only need to prove that :

$$\binom{2q}{q} \le r(D_{2q}) \text{ for all } q.$$

Let $E$ be the vector space of multilinear forms in the $q$ vectors of dimension $n$, $X_i$ for $1 \le i \le q$.

Let $F$ be the vector space of multilinear forms in the $q$ vectors of dimension $n$, $X_i$ for $q \le i \le 2q$.

The vector space $H$ of the multilinear forms in the $2q$ vectors $X_i$ for $1 \le i \le 2q$ is the tensorial product of $E$ and $F$ : $H = E \otimes_F F$. The decomposition given by the definition of $r(D_q)$ :

$$r(D_{2q}) = \min\{\alpha | D_{2q} = \sum_{i=1}^{\alpha} U_i V_i, U_i \in E, V_i \in F\}$$

defines $r(D_{2q})$ as the rank of a tensor of order 2.

This rank is achieved by a decomposition in which the $U_i$ (resp. $V_i$) are independent in $E$ (resp. $F$). This

is the case for the Lagrange decomposition of a determinant of order $2q$ as a sum of product of minors of order $q$. The minors of order $q$ are all independent since they have no common subterms. Such a decomposition has a length $\binom{2q}{q}$. $\square$

## 5. REFERENCES

[1] Fiduccia, C.M., "On obtaining upper bounds on the complexity of matrix multiplication", in *Complexity of Computer Computations*, Plenum Press, pp 31-40, 1972.

[2] Gastinel, N. "Sur le calcul des produits de matrices", *Numerische Mathematik*, Vol. 17, pp. 222-229, 1971

[3] Hopcroft, J., Kerr, L., "On minimizing the number of multiplications necessary for matrix multiplication", *SIAM Journal on Appl. Math.*, vol 20, n°1, pp. 30-36, 1971.

[4] Hyafil, L., Van de Wiele, J.P., "Bornes inférieures pour la complexité des polynômes à coefficient 0-1", *Rapport Laboria* n° 192, 1976.

[5] Strassen, V., "Evaluation of rational functions", in *Complexity of Computer Computations*, Plenum Press, pp 1-10, 1972.

[6] Strassen, V., "Vermeidung von divisionen", *J. Reine Angew. Math.*, vol. 264, pp 184-202, 1973.

[7] Winograd, S. "On the number of multiplications necessary to compute certain functions", *Communications on Pure and Appl. Math.*, vol. 23, pp 165-179, 1970.

## 6. ACKNOWLEDGEMENTS

Many thanks to J.P. Van de Wiele for his helpful comments.