<figure><img src="image_19.png" /><figcaption>■ Figure 13 Matrices $E_1, E_d$ and $E_k$.</figcaption></figure>

1. For every $k \in [3, d-2]$, $\mathcal{Y}_k = \mathcal{X}_{\sigma(k)}$.

2. Either $\mathcal{Y}_1, \mathcal{Y}_{1,2}$ and $\mathcal{Y}_d, \mathcal{Y}_{d-1,d}$ are $\mathcal{X}_1, \mathcal{X}_{1,2}$ and $\mathcal{X}_d, \mathcal{X}_{d-1,d}$ respectively, or $\mathcal{Y}_1, \mathcal{Y}_{1,2}$ and $\mathcal{Y}_d, \mathcal{Y}_{d-1,d}$ are $\mathcal{X}_d, \mathcal{X}_{d-1,d}$ and $\mathcal{X}_1, \mathcal{X}_{1,2}$ respectively.

**Proof.** Assume $\mathcal{V}_1$ and $\mathcal{V}_d$ are the spaces $A^{-1}\mathcal{U}_{1,2}$ and $A^{-1}\mathcal{U}_{d-1,d}$ respectively. In this case we will show $\mathcal{Y}_1, \mathcal{Y}_{1,2}$ and $\mathcal{Y}_d, \mathcal{Y}_{d-1,d}$ are $\mathcal{X}_1, \mathcal{X}_{1,2}$ and $\mathcal{X}_d, \mathcal{X}_{d-1,d}$ respectively$^{41}$. Hence, $u_1 = w_1 + w_1w_2, u_2 = w_1w_2, u_{d-1} = w_{d-2}w_{d-1}$ and $u_d = w_{d-1} + w_{d-2}w_{d-1}$. From the order of the columns in $V_1$ and $V_d$ we have $V_1 = A^{-1}E_1$ and $V_d = A^{-1}E_d$, where $E_1$ and $E_d$ are $n \times u_1$ and $n \times u_d$ matrices respectively and they look as shown in Figure 13.

The rows of $E_1$ and $E_d$ are labelled by $n$ variables in $\mathbf{x}_1$ to $\mathbf{x}_d$, whereas the columns of $E_1$ are labelled by variables in $\mathbf{x}_1$ and $\mathbf{x}_2$ and the columns of $E_d$ are labelled by variables in $\mathbf{x}_{d-1}$ and $\mathbf{x}_d$. Moreover, the nonzero entries in these matrices are restricted to the shaded region in Figure 13.

For $k \in [3, d-2]$, $\mathcal{V}_k = A^{-1}\mathcal{U}_{\sigma(k)}$ where $\sigma$ is a permutation on $[3, d-2]$. Hence, $u_k = w_{\sigma(k)-1}w_{\sigma(k)}$ and $V_k = A^{-1}E_k$ where $E_k$ is a $n \times u_k$ matrix and looks as shown in Figure 13. Again the rows of $E_k$ are labelled by the variables $\mathbf{x}_1$ to $\mathbf{x}_d$, whereas the columns of $E_k$ are labelled by variables in $\mathbf{x}_{\sigma(k)}$. The nonzero entries in $E_k$ are restricted to the shaded region in Figure 13 whose rows are labelled by variables in $\mathbf{x}_{\sigma(k)}$. Let $E$ be the concatenation of these matrices, $E = [E_1 | E_3 | E_4 | \dots | E_{d-2} | E_d]$. The rows of $E$ are labelled by $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_d$ as usual, but now the columns are labelled by $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_{\sigma(3)}, \dots, \mathbf{x}_{\sigma(d-2)}, \mathbf{x}_{d-1}, \mathbf{x}_d$ in order as shown in Figure 14. Then $V = A^{-1}E$ implying $V^{-1} = E^{-1}A$. Owing to the structure of $E, E^{-1}$ looks as shown in Figure 14.

The rows of $E^{-1}$ are labelled by $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_{\sigma(3)}, \dots, \mathbf{x}_{\sigma(d-2)}, \mathbf{x}_{d-1}, \mathbf{x}_d$ in order, whereas the columns are labelled by the usual ordering $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_d$. The submatrix of $E^{-1}$ restricted to the rows and columns labelled by the variables in $\mathbf{x}_1$ and $\mathbf{x}_2$ is $B_{1,2}^{-1}$ and that labelled by the variables in $\mathbf{x}_{d-1}$ and $\mathbf{x}_d$ is $B_{d-1,d}^{-1}$. For $k \in [3, d-2]$ the submatrix restricted to the rows and columns labelled by $\mathbf{x}_{\sigma(k)}$ is $B_{\sigma(k)}^{-1}$. We infer the following facts:

(1) The space spanned by the first $u_1 - u_2$ (that is $w_1$) rows of $V^{-1}$ is equal to the space spanned by the first $w_1$ rows of $A$, the latter space is $\mathcal{X}_1$.

<footnote>$^{41}$If $\mathcal{V}_1$ and $\mathcal{V}_d$ are the spaces $A^{-1}\mathcal{U}_{d-1,d}$ and $A^{-1}\mathcal{U}_{1,2}$ respectively, then $\mathcal{Y}_1, \mathcal{Y}_{1,2}$ and $\mathcal{Y}_d, \mathcal{Y}_{d-1,d}$ are $\mathcal{X}_d, \mathcal{X}_{d-1,d}$ and $\mathcal{X}_1, \mathcal{X}_{1,2}$ respectively – the proof of this case is similar.</footnote>
<figure><img src="image_20.png" /><figcaption>Figure 14 Matrices $E$ and $E^{-1}$.</figcaption></figure>

(II) The space spanned by the first $u_1$ (that is $w_1 + w_1w_2$) rows of $V^{-1}$ is equal to the space spanned by the first $w_1 + w_1w_2$ rows of $A$, the latter space is $\mathcal{X}_{1,2}$.

(III) The space spanned by the last $u_d$ (that is $w_{d-1} + w_{d-2}w_{d-1}$) rows of $V^{-1}$ is equal to the space spanned by the last $w_{d-1} + w_{d-2}w_{d-1}$ rows of $A$, the latter space is $\mathcal{X}_{d-1,d}$.

(IV) The space spanned by the last $u_d - u_{d-1}$ (that is $w_{d-1}$) rows of $V^{-1}$ is equal to the space spanned by the last $w_{d-1}$ rows of $A$, the latter space is $\mathcal{X}_d$.

(V) For $k \in [3, d-2]$ the space spanned by the rows of $V^{-1}$ that are numbered by $t_{k-1} + 1$ to $t_{k-1} + u_k$ is equal to the space spanned by the rows of $A$ labelled by $\mathbf{x}_{\sigma(k)}$, the latter space is $\mathcal{X}_{\sigma(k)}$. $\quad \blacksquare$

**Claim 50 (restated).** There is a randomized polynomial time algorithm that takes input the bases of the layer spaces $\mathcal{Y}_1, \mathcal{Y}_{1,2}, \mathcal{Y}_3, \dots, \mathcal{Y}_{d-2}, \mathcal{Y}_{d-1,d}, \mathcal{Y}_d$ and with probability at least $1 - \frac{1}{\text{poly}(n)}$ reorders these layer spaces and outputs a width vector $\mathbf{w}'$ such that the reordered sequence of spaces and $\mathbf{w}'$ are:

1. either $\mathcal{X}_1, \mathcal{X}_{1,2}, \mathcal{X}_3, \dots, \mathcal{X}_{d-2}, \mathcal{X}_{d-1,d}, \mathcal{X}_d$ and $(w_1, w_2, \dots, w_{d-1})$ respectively,

2. or $\mathcal{X}_d, \mathcal{X}_{d-1,d}, \mathcal{X}_{d-2}, \dots, \mathcal{X}_3, \mathcal{X}_{1,2}, \mathcal{X}_1$ and $(w_d, w_{d-1}, \dots, w_1)$ respectively.

**Proof.** The algorithm employs evaluation dimension to uncover the permutation $\sigma$. Assume that $\mathcal{Y}_1, \mathcal{Y}_{1,2}, \mathcal{Y}_3, \dots, \mathcal{Y}_{d-2}, \mathcal{Y}_{d-1,d}, \mathcal{Y}_d$ are the spaces $\mathcal{X}_1, \mathcal{X}_{1,2}, \mathcal{X}_{\sigma(3)}, \dots, \mathcal{X}_{\sigma(d-2)}, \mathcal{X}_{d-1,d}, \mathcal{X}_d$ respectively$^{42}$. In this case, the algorithm reorders the spaces to a sequence $\mathcal{X}_1, \mathcal{X}_{1,2}, \mathcal{X}_3, \dots, \mathcal{X}_{d-2}, \mathcal{X}_{d-1,d}, \mathcal{X}_d$ and outputs $\mathbf{w}' = \mathbf{w}$. For every $k \in [3, d-2]$, let $\mathbf{z}_k$ be a set of $\dim(\mathcal{Y}_k)$ many variables. Let $\mathbf{z}_1$ (similarly, $\mathbf{z}_d$) be a set of $\dim(\mathcal{Y}_1)$ (similarly, $\dim(\mathcal{Y}_d)$) variables, and let $\mathbf{z}_2$ (similarly, $\mathbf{z}_{d-1}$) be a set of $\dim(\mathcal{Y}_{1,2}) - \dim(\mathcal{Y}_1)$ (similarly, $\dim(\mathcal{Y}_{d-1,d}) - \dim(\mathcal{Y}_d)$) variables. Finally, let $\mathbf{z} = \mathbf{z}_1 \uplus \dots \uplus \mathbf{z}_d$ be the set of these $n$ fresh variables.

Compute a linear map $\mu$ that maps $\mathbf{x}$ variables to linear forms in $\mathbf{z}$ variables such that the following conditions are satisfied:

(a) For every $k \in [3, d-2]$, the linear forms corresponding$^{43}$ to the basis vectors of $\mathcal{Y}_k$ map to distinct variables in $\mathbf{z}_k$.

(b) The linear forms corresponding to the basis vectors in $\mathcal{Y}_1$ (similarly, $\mathcal{Y}_d$) map to distinct variables in $\mathbf{z}_1$ (similarly, $\mathbf{z}_d$).

<footnote>$^{42}$The proof of the other case is similar.</footnote>

<footnote>$^{43}$Recall, linear forms in $\mathbf{x}$ variables and vectors in $\mathbb{F}^n$ are naturally identified with each other.</footnote>
(c) The linear forms corresponding to the basis vectors in $\mathcal{Y}_{1,2}$ (similarly, $\mathcal{Y}_{d-1,d}$) map to distinct variables in $\mathbf{z}_1 \uplus \mathbf{z}_2$ (similarly, $\mathbf{z}_{d-1} \uplus \mathbf{z}_d$).

Conditions (b) and (c) can be simultaneously satisfied as the basis of $\mathcal{Y}_1$ (similarly, $\mathcal{Y}_d$) is contained in the basis of $\mathcal{Y}_{1,2}$ (similarly, $\mathcal{Y}_{d-1,d}$) by their very constructions in Algorithm 5. As $f = \text{IMM}_{\mathbf{w},d}(A\mathbf{x})$, the map $\mu$ takes $f$ to a polynomial $h(\mathbf{z})$ that is computed by a full rank ABP $A'$ of width $\mathbf{w}$ and length $d$ such that the sets of variables appearing in the $d$ layers of $A'$ from left to right are $\mathbf{z}_1, \mathbf{z}_1 \uplus \mathbf{z}_2, \mathbf{z}_{\sigma^{-1}(3)}, \dots, \mathbf{z}_{\sigma^{-1}(d-2)}, \mathbf{z}_{d-1} \uplus \mathbf{z}_d, \mathbf{z}_d$ in order.

The following observation, the proof of which is given later, helps find $\sigma^{-1}$ incrementally from blackbox access to $h(\mathbf{z})$. Let $\mathbf{y}_2 = \mathbf{z}_1 \uplus \mathbf{z}_2$ and $\mathbf{y}_j = \mathbf{z}_1 \uplus \mathbf{z}_2 \uplus \mathbf{z}_{\sigma^{-1}(3)} \uplus \dots \uplus \mathbf{z}_{\sigma^{-1}(j)}$, for $j \in [3, d-2]$.

**Observation 67.** For every $j \in [2, d-3]$ and $k \in [3, d-2]$ such that $\mathbf{z}_k \not\subset \mathbf{y}_j$,

1. Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k} (h) < |\mathbf{z}_k|$, if $k = \sigma^{-1}(j+1)$, and

2. Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k} (h) > |\mathbf{z}_k|$, if $k \neq \sigma^{-1}(j+1)$.

The proof of the observation also includes an efficient randomized procedure to compute Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k} (h)$.

Finally, the algorithm outputs the reordered layer spaces $\mathcal{Y}_1, \mathcal{Y}_{1,2}, \mathcal{Y}_{\sigma^{-1}(3)}, \dots, \mathcal{Y}_{\sigma^{-1}(d-2)}$, $\mathcal{Y}_{d-1,d}$, $\mathcal{Y}_d$ which is the ordered sequence of spaces $\mathcal{X}_1, \mathcal{X}_{1,2}, \mathcal{X}_3, \dots, \mathcal{X}_{d-2}, \mathcal{X}_{d-1,d}, \mathcal{X}_d$. The width vector $\mathbf{w}'$ can be readily calculated now by inspecting the dimensions:

$$w_1' = \dim(\mathcal{X}_1) = w_1,$$

$$w_2' = \frac{\dim(\mathcal{X}_{1,2}) - w_1}{w_1} = w_2,$$

$$w_k' = \frac{\dim(\mathcal{X}_k)}{w_{k-1}} = w_k, \quad \text{for } k \in [3, d-2],$$

$$w_d' = \dim(\mathcal{X}_d) = w_d, \quad \text{and}$$

$$w_{d-1}' = \frac{\dim(\mathcal{X}_{d-1,d}) - w_d}{w_d} = w_{d-1}.$$

This gives $\mathbf{w}' = \mathbf{w}$.

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

**Proof of Observation 67.** Let $Z_1 \cdot Z_2 \cdots Z_d$ be equal to $A'$, the full rank ABP of width $\mathbf{w} = (w_1, w_2, \dots, w_{d-1})$ computing $h$, where the linear forms in $Z_i$ are in $\mathbf{z}_{\sigma^{-1}(i)}$ variables for $i \in [3, d-2]$, the linear forms in $Z_1, Z_d$ are in variables $\mathbf{z}_1, \mathbf{z}_d$ respectively, and the linear forms in $Z_2, Z_{d-1}$ are in $\mathbf{z}_1 \uplus \mathbf{z}_2, \mathbf{z}_{d-1} \uplus \mathbf{z}_d$ variables respectively.

**Case 1:** Suppose $k = \sigma^{-1}(j+1)$, implying $|\mathbf{z}_k| = w_j w_{j+1}$. Let $G = Z_{j+2} \cdot Z_{j+3} \cdots Z_d$ and the $t$-th entry of $G$ be $g_t$ for $t \in [w_{j+1}]$. As the linear forms in $Z_1, Z_2, \dots, Z_{j+1}$ are $\mathbb{F}$-linearly independent, for every $t \in [w_{j+1}]$ there is a partial evaluation of $h$ at $\mathbf{y}_j \uplus \mathbf{z}_k$ variables that makes $h$ equal to $g_t$. Also, every partial evaluation of $h$ at $\mathbf{y}_j \uplus \mathbf{z}_k$ variables can be expressed as an $\mathbb{F}$-linear combination of $g_1, g_2, \dots, g_{w_{j+1}}$. Hence, from Observation 53 it follows, Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k} (h) = w_{j+1} < |\mathbf{z}_k|$.

**Case 2:** Suppose $k \neq \sigma^{-1}(j+1)$. The variables $\mathbf{z}_k$ appear in the matrix $Z_{\sigma(k)}$, so $|\mathbf{z}_k| = w_{\sigma(k)-1} w_{\sigma(k)}$. Let $G = Z_{\sigma(k)+1} \cdot Z_{\sigma(k)+2} \cdots Z_d$ and the $t$-th entry of $G$ be $g_t$ for $t \in [w_{\sigma(k)}]$. Further, let $P = (p_{lm})_{l \in [w_j], m \in [w_{\sigma(k)-1}]}$ be equal to $Z_{j+1} \cdot Z_{j+2} \cdots Z_{\sigma(k)-1}$. As the linear forms in $Z_1, Z_2, \dots, Z_j$ and $Z_{\sigma(k)}$ are $\mathbb{F}$-linearly independent, there is a partial evaluation of $h$ at the $\mathbf{y}_j \uplus \mathbf{z}_k$ variables that makes $h$ equal to $p_{lm} g_t$ for $l \in [w_j], m \in [w_{\sigma(k)-1}]$ and $t \in [w_{\sigma(k)}]$. By Observation 53, $\{g_t | t \in [w_{\sigma(k)}]\}$ are $\mathbb{F}$-linearly independent; using a proof similar to that of Observation 53 we can show that the polynomials $\{p_{lm} | l \in$
$[w_j], m \in [w_{\sigma(k)-1}]$} are also $\mathbb{F}$-linearly independent. This implies the set of polynomials $\{p_{lm}g_t \mid l \in [w_j], m \in [w_{\sigma(k)-1}] \text{ and } t \in [w_{\sigma(k)}]\}$ are $\mathbb{F}$-linearly independent, as $p_{lm}$ and $g_t$ are on disjoint sets of variables. Since every partial evaluation of $h$ at $\mathbf{y}_j \uplus \mathbf{z}_k$ variables can be expressed as an $\mathbb{F}$-linear combination of the set of polynomials $\{p_{lm}g_t \mid l \in [w_j], m \in [w_{\sigma(k)-1}] \text{ and } t \in [w_{\sigma(k)}]\}$, Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k}(h) = w_j w_{\sigma(k)-1} w_{\sigma(k)} = w_j \cdot |\mathbf{z}_k| > |\mathbf{z}_k|$.

**A randomized procedure to compute Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k}(h)$:** Choose evaluation points $\mathbf{a}_1, \dots, \mathbf{a}_{n^2}$ for the variables $\mathbf{y}_j \uplus \mathbf{z}_k$ independently and uniformly at random from a set $S^{|\mathbf{y}_j \uplus \mathbf{z}_k|} \subset \mathbb{F}^{|\mathbf{y}_j \uplus \mathbf{z}_k|}$ with $|S| = \text{poly}(n)$. Output the dimension of the $\mathbb{F}$-linear space spanned by the polynomials $h(\mathbf{a}_1), \dots, h(\mathbf{a}_{n^2})$ using Claim 24.

We argue that the above procedure outputs Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k}(h)$ with probability at least $1 - \frac{1}{\text{poly}(n)}$. Let Evaldim$_{\mathbf{y}_j \uplus \mathbf{z}_k}(h) = e$. Observe that in both Case 1 and 2, $e \le n^2$. Also, in both the cases $h$ can be expressed as

$$h = \sum_{i \in [e]} f_i(\mathbf{y}_j \uplus \mathbf{z}_k) \cdot q_i, \qquad (25)$$

where $f_i$ and $q_i$ are variable disjoint. The polynomials $q_1, \dots, q_e$ are the polynomials $g_1, \dots, g_{w_{j+1}}$ in Case 1; they are the polynomials $\{p_{lm}g_t \mid l \in [w_j], m \in [w_{\sigma(k)-1}] \text{ and } t \in [w_{\sigma(k)}]\}$ in Case 2. Just as we argue that $q_1, \dots, q_e$ are $\mathbb{F}$-linearly independent, we can show that $f_1, \dots, f_e$ are also $\mathbb{F}$-linearly independent. So, by Claim 24 the rank of the matrix $M = (f_c(\mathbf{a}_r))_{r,c \in [e]}$ is $e$ with high probability. This implies the polynomials $h(\mathbf{a}_1), \dots, h(\mathbf{a}_e)$ are $\mathbb{F}$-linearly independent also with high probability. The correctness of the procedure follows from the observation that the dimension of the $\mathbb{F}$-linear space spanned by $h(\mathbf{a}_1), \dots, h(\mathbf{a}_{n^2})$ is upper bounded by $e$ (from Equation (25)). $\quad$

**► Observation 52 (restated).** If $h$ is computable by a full rank almost set-multilinear ABP of width $\mathbf{w}$ then there is a full rank almost set-multilinear ABP of width $\mathbf{w}$ in canonical form computing $h$.

**Proof.** Suppose $X_1 \cdot X_2 \cdots X_d$ is a full rank almost set-multilinear ABP of width $\mathbf{w} = (w_1, w_2, \dots, w_{d-1})$ computing $h$. Let $X'_1 = (x_1^{(1)} x_2^{(1)} \dots x_{w_1}^{(1)})$ and $X'_d = (x_1^{(d)} x_2^{(d)} \dots x_{w_{d-1}}^{(d)})$. We show there are matrices $X'_2$ and $X'_{d-1}$ satisfying conditions (1b) and (2b) respectively of canonical form (defined in Section 2.4) such that $h = X'_1 \cdot X'_2 \cdot X_3 \cdots X_{d-2} \cdot X'_{d-1} \cdot X'_d$. We prove the existence of $X'_2 = (l'_{ij})_{i \in [w_1], j \in [w_2]}$; the proof for $X'_{d-1}$ is similar. It is sufficient to show that there is such an $X'_2$ satisfying $X_1 \cdot X_2 = X'_1 \cdot X'_2$. Denote the $j$-th entry of the $1 \times w_2$ matrix $X_1 \cdot X_2$ as $X_1 \cdot X_2(j)$. Similarly $X'_1 \cdot X'_2(j)$ represents the $j$-th entry of $X'_1 \cdot X'_2$. Let $g_i$ be the sum of all monomials in $X_1 \cdot X_2(j)$ of the following types: $x_i^{(1)} x_k^{(1)}$ for $k \in [i, w_1]$, and $x_i^{(1)} x_{pq}^{(2)}$ for $p \in [w_1], q \in [w_2]$. Clearly,

$$X_1 \cdot X_2(j) = g_1 + g_2 + \cdots + g_{w_1}.$$

If $l'_{ij} \stackrel{\text{def}}{=} g_i/x_i^{(1)}$ then

$$X_1 \cdot X_2(j) = x_1^{(1)} l'_{1j} + x_2^{(1)} l'_{2j} + \cdots + x_{w_1}^{(1)} l'_{w_1j}.$$

Since $l'_{ij}$ is the $(i, j)$-th entry of $X'_2$, we infer $X_1 \cdot X_2(j) = X'_1 \cdot X'_2(j)$. By definition, $x_k^{(1)}$ does not appear in $l'_{ij}$ for $k < i$, and thus condition (1b) is satisfied by $X'_2$. $\quad$

**► Observation 53 (restated).** Let $X_1 \cdot X_2 \cdots X_d$ be a full rank almost set-multilinear ABP, and $C_k = X_k \cdots X_d$ for $k \in [2, d]$. Let the $l$-th entry of $C_k$ be $h_{kl}$ for $l \in [w_{k-1}]$. Then the polynomials $\{h_{k1}, h_{k2}, \dots, h_{kw_{k-1}}\}$ are $\mathbb{F}$-linearly independent.
**Proof.** Suppose $\sum_{p=1}^{w_k-1} \alpha_p \cdot h_{kp} = 0$ such that $\alpha_p \in \mathbb{F}$ for $p \in [w_{k-1}]$, and not all $\alpha_p = 0$. Assume without loss of generality $\alpha_1 \neq 0$. Since the linear forms in $X_k, \dots, X_d$ are $\mathbb{F}$-linearly independent, there is an evaluation of the variables in $\mathbf{x}_k \oplus \dots \oplus \mathbf{x}_d$ to field constants such that $h_{k1} = 1$ and every other $h_{kp} = 0$ under this evaluation. This implies $\alpha_1 = 0$, contradicting our assumption. ◀

## 7.5 Proof of observation in Section 6

**► Observation 57 (restated).** There are matrices $A_1, \dots, A_{d-1}$ with $A_k \in \text{GL}(w_k)$ for every $k \in [d-1]$, such that $X_1 = Q_1 \cdot A_1$, $X_2(\mathbf{x}_2) = A_1^{-1} \cdot Q_2 \cdot A_2$, $X_{d-1}(\mathbf{x}_{d-1}) = A_{d-2}^{-1} \cdot Q_{d-1} \cdot A_{d-1}$, $X_d = A_{d-1}^{-1} \cdot Q_d$, and $X_k = A_{k-1}^{-1} \cdot Q_k \cdot A_k$ for $k \in [3, d-2]$.

**Proof.** To simplify notations, we write $X_2(\mathbf{x}_2)$, $X_{d-1}(\mathbf{x}_{d-1})$ as $X_2$, $X_{d-1}$ respectively. We have

$$X_1 \cdot X_2 \cdots X_{d-1} \cdot X_d = Q_1 \cdot Q_2 \cdots Q_{d-1} \cdot Q_d = \text{IMM},$$

where the dimensions of the matrices $X_k$ and $Q_k$ are the same, and the set of variables appearing in both $X_k$ and $Q_k$ is $\mathbf{x}_k$, for every $k \in [d]$. Since the linear forms in $X_1$ are $\mathbb{F}$-linearly independent, there is an $A_1 \in \text{GL}(w_1)$ such that $X_1 = Q_1 \cdot A_1$, implying

$$ \begin{aligned} & Q_1 \cdot [A_1 \cdot X_2 \cdots X_{d-1} \cdot X_d - Q_2 \cdots Q_{d-1} \cdot Q_d] = 0 \\ \Rightarrow \quad & X_2 \cdots X_{d-1} \cdot X_d = A_1^{-1} \cdot Q_2 \cdots Q_{d-1} \cdot Q_d, \end{aligned} $$

as the formal variable entries of $Q_1$ do not appear in the matrices $X_k, Q_k$ for $k \in [2, d]$. The rest of the proof proceeds inductively: Suppose for some $k \in [2, d-1]$,

$$X_k \cdots X_{d-1} \cdot X_d = A_{k-1}^{-1} \cdot Q_k \cdots Q_{d-1} \cdot Q_d, \quad \text{where } A_{k-1} \in \text{GL}(w_{k-1}).$$

Let $p_k = \sum_{i=k+1}^d |\mathbf{x}_i|$. Since the linear forms in $X_{k+1}, \dots, X_{d-1}, X_d$ are $\mathbb{F}$-linearly independent, for every $l \in [w_k]$ there is a point $\mathbf{a}_l \in \mathbb{F}^{p_k}$ such that the $w_k \times 1$ matrix $X_{k+1} \cdots X_{d-1} \cdot X_d$ evaluated at $\mathbf{a}_l$ has 1 at the $l$-th position and all its other entries are zero. Let $A_k$ be the $w_k \times w_k$ matrix such that the $l$-th column of $A_k$ is equal to $Q_{k+1} \cdots Q_{d-1} \cdot Q_d$ evaluated at $\mathbf{a}_l$. Then, $X_k = A_{k-1}^{-1} \cdot Q_k \cdot A_k$. As the linear forms in $X_k$ and $Q_k$ are $\mathbb{F}$-linearly independent, it must be that $A_k \in \text{GL}(w_k)$. Putting this expression for $X_k$ in the equation above and arguing as before, we get a similar equation with $k$ replaced by $k+1$. The proof then follows by induction. ◀

## References

1 Scott Aaronson. Arithmetic natural proofs theory is sought. http://www.scottaaronson.com/blog/?p=336, 2008.

2 Manindra Agrawal. Proving Lower Bounds Via Pseudo-random Generators. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, pages 92–105, 2005.

3 Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-Sets for RO-ABP and Sum of Set-Multilinear Circuits. SIAM J. Comput., 44(3):669–697, 2015.

4 Manindra Agrawal and Nitin Saxena. Equivalence of f-algebras and cubic forms. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pages 115–126, 2006.

5 Dana Angluin. Queries and concept learning. Machine Learning., 2(4):319–342, 1988.
6 Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan. New Results on Non-commutative and Commutative Polynomial Identity Testing. In *Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA*, pages 268-279, 2008.

7 Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. *J. ACM*, 47(3):506-530, 2000.

8 Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. In *Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA*, pages 254-257, 1988.

9 Elwyn Berlekamp. Factoring polynomials over finite fields. *Bell System Technical Journal*, 46:1853-1859, 1967.

10 Lenore Blum, Mike Shub, and Steve Smale. On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract). In *29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988*, pages 387-397, 1988.

11 David G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. *Mathematics of Computation*, 36:587-592, 1981.

12 Enrico Carlini. Reducing the number of variables of a polynomial. In *Algebraic geometry and geometric modelling, Mathematics and Visualization, Springer*, pages 237-247, 2006.

13 Zeev Dvir, Rafael Mendes de Oliveira, and Amir Shpilka. Testing equivalence of polynomials under shifts. In *Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I*, pages 417-428, 2014.

14 Michael A. Forbes and Amir Shpilka. Quasip polynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In *54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA*, pages 243-252, 2013.

15 Fulvio Gesmundo. Gemetric aspects of iterated matrix multiplication. *Journal of Algebra*, 461:42-64, 2016.

16 Joshua A. Grochow. *Symmetry and equivalence relations in classical and geometric complexity theory*. PhD thesis, The University of Chicago, 2012.

17 Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam. Efficient Reconstruction of Random Multilinear Formulas. In *IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011*, pages 778-787, 2011.

18 Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam. Reconstruction of depth-4 multilinear circuits with top fan-in 2. In *Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012*, pages 625-642, 2012.

19 Ankit Gupta, Neeraj Kayal, and Youming Qiao. Random Arithmetic Formulas Can Be Reconstructed Efficiently. In *Proceedings of the 28th Conference on Computational Complexity, CCC 2013, Klo Alto, California, USA, 5-7 June, 2013*, pages 1-9, 2013.

20 Johan Håstad. Tensor Rank is NP-Complete. In *Automata, Languages and Programming, 16th International Colloquium, ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings*, pages 451-460, 1989.

21 Joos Heintz and Claus-Peter Schnorr. Testing Polynomials which Are Easy to Compute (Extended Abstract). In *Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA*, pages 262-272, 1980.
22 Erich Kaltofen and Barry M. Trager. Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. In *29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988*, pages 296-305, 1988.

23 Zohar Shay Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In *Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009*, pages 274-285, 2009.

24 Neeraj Kayal. Efficient algorithms for some special cases of the polynomial equivalence problem. In *Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011*, pages 1409-1421, 2011.

25 Neeraj Kayal. Affine projections of polynomials: extended abstract. In *Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012*, pages 643-662, 2012.

26 Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. *Electronic Colloquium on Computational Complexity (ECCC)*, 19:81, 2012.

27 Neerak Kayal, Chandan Saha, and Sébastien Tavenas. An Average-Case Matrix Factorization Problem. Work in progress, 2017.

28 Adam Klivans, Pravesh Kothari, and Igor Carboni Oliveira. Constructing Hard Functions Using Learning Algorithms. In *Proceedings of the 28th Conference on Computational Complexity, CCC 2013, Klo Alto, California, USA, 5-7 June, 2013*, pages 86-97, 2013.

29 Adam Klivans and Amir Shpilka. Learning arithmetic circuits via partial derivatives. In *Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings*, pages 463-476, 2003.

30 Adam Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In *Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece*, pages 216-223, 2001.

31 A.K. Lenstra, H.W.jun. Lenstra, and Lászlo Lovász. Factoring polynomials with rational coefficients. *Math. Ann.*, 261:515-534, 1982.

32 Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. *Chicago J. Theor. Comput. Sci.*, 1997, 1997.

33 Daniel Minahan and Ilya Volkovich. Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. *Electronic Colloquium on Computational Complexity (ECCC)*, 23:171, 2016.

34 Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In *Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA*, pages 410-418, 1991.

35 Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In *Advances in Cryptology - EUROCRYPT'96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding*, pages 33-48, 1996.

36 Alexander A. Razborov and Steven Rudich. Natural proofs. In *Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada*, pages 204-213, 1994.

37 Amir Shpilka. Interpolation of depth-3 arithmetic circuits with two multiplication gates. In *Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007*, pages 284-293, 2007.
38 Amir Shpilka and Ilya Volkovich. Improved Polynomial Identity Testing for Read-Once Formulas. In *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings*, pages 700–713, 2009.

39 Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. *Foundations and Trends in Theoretical Computer Science*, 5(3-4):207–388, 2010.

40 Gaurav Sinha. Reconstruction of real depth-3 circuits with top fan-in 2. In *31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan*, pages 31:1–31:53, 2016.

41 Thomas Thierauf. The isomorphism problem for read-once branching programs and arithmetic circuits. *Chicago J. Theor. Comput. Sci.*, 1998, 1998.

42 Ilya Volkovich. A guide to learning arithmetic circuits. In *Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016*, pages 1540–1561, 2016.