# A Multivariate to Bivariate Reduction for Noncommutative Rank and Related
Results

V. Arvind The Institute of Mathematical Sciences (HBNI), Chennai, India,
email<EMAIL_ADDRESS>and Chennai Mathematical Institute, Siruseri,
Kelambakkam, India Pushkar S Joglekar Vishwakarma Institute of Technology,
Pune, India, email<EMAIL_ADDRESS>
###### Abstract

We study the _noncommutative rank_ problem, ncRANK, of computing the rank of
matrices with linear entries in $n$ noncommuting variables and the problem of
_noncommutative Rational Identity Testing_ , RIT, which is to decide if a
given rational formula in $n$ noncommuting variables is zero on its domain of
definition.

Motivated by the question whether these problems have _deterministic_
$\mathsf{NC}$ algorithms, we revisit their interrelationship from a parallel
complexity point of view. We show the following results:

  1. 1.

Based on Cohn’s embedding theorem [13, 15] we show deterministic $\mathsf{NC}$
reductions from multivariate ncRANK to bivariate ncRANK and from multivariate
RIT to bivariate RIT.

  2. 2.

We obtain a deterministic $\mathsf{NC}$-Turing reduction from bivariate RIT to
bivariate ncRANK, thereby proving that a deterministic $\mathsf{NC}$ algorithm
for bivariate ncRANK would imply that both multivariate RIT and multivariate
ncRANK are in deterministic $\mathsf{NC}$.

##  1 Introduction

There are two main algorithmic problems of interest in this paper. These are
the _noncommutative Rational Identity Testing problem_ (RIT) and the
_noncommutative rank_ (ncRANK) problem for matrices with linear entries.

The RIT problem is a generalization of multivariate polynomial identity
testing to identity testing of multivariate rational expressions. When the
variables are commuting, rational identity testing and polynomial identity
testing are equivalent problems. On the other hand, if the variables are all
noncommuting, the RIT problem needs different algorithmic techniques as
rational expressions in noncommuting variables are more complicated.
Mathematically, rational expressions over noncommuting variables are quite
well studied. They arise in the construction of the so-called free skew fields
[15]. Hrubes and Wigderson [21] initiated the algorithmic study of RIT for
_rational formulas_ and gave a deterministic polynomial time reduction from
RIT to ncRANK. Subsequently, deterministic polynomial-time algorithms were
obtained independently by Ivanyos et al [23, 22] and by Garg et al [18, 19]
for the RIT problem, in fact they obtain deterministic polynomial time
algorithms for ncRANK, and using Hrubes-Wigderson reduction from RIT to ncRANK
get a polynomial time algorithm for RIT. The Ivanyos et al algorithm is
algebraic and works for fields of all characteristics. The Garg et al
algorithm has an analytic flavor and is for the characteristic zero case.

#### The Edmonds’ Problem and ncRANK

The ncRANK problem is essentially the noncommutative version of the well-known
Edmonds’ problem: determine the rank of a matrix $M$ whose entries are linear
forms in commuting variables (see [23, 19, 6, 9] for more details). A special
case of it is to determine if a square matrix $M$ with linear entries in
commuting variables is _singular_. This is also known as the symbolic
determinant identity testing problem, SDIT. There is an easy randomized
$\mathsf{NC}$ algorithm for it, based on the Polynomial Identity Lemma [4, 28,
30, 16], by randomly substituting scalar values for the variables from the
field (or a suitable extension of it) and evaluating the determinant using a
standard $\mathsf{NC}$ algorithm. However, a deterministic polynomial-time
algorithm for SDIT is an outstanding open problem [6].

Recently, for the RIT problem the first deterministic quasi-$\mathsf{NC}$
algorithm has been obtained [2]. Another recent development — building on the
connection between the noncommutative Edmonds’ problem and identity testing
for noncommutative algebraic branching programs [9] — is a generalization of
the Edmond’s problem to a partially commutative setting with application to
the weighted $k$-tape automata equivalence problem [3].

###  1.1 This paper: overview of results and proofs

With this background, the natural algorithmic questions are whether RIT for
noncommutative rational formulas and ncRANK have deterministic $\mathsf{NC}$
algorithms. We revisit the problems from this perspective and obtain the
following new results.

  * 1.

We show that multivariate RIT for formulas is deterministic $\mathsf{NC}$
reducible to bivariate RIT for formulas. More precisely, given a rational
formula $\Phi(x_{1},x_{2},\ldots,x_{n})$, computing an element of the skew
field $\mathbb{F}{\lparenless}X{\rparengtr}$, where
$X=\\{x_{1},x_{2},\dots,x_{n}\\}$, the deterministic NC reduction replaces
each $x_{i}$ by a formula $\Phi_{i}(x,y)$ computing a polynomial in
$\mathbb{F}\langle x,y\rangle$. Then the resulting rational formula

$\Psi(x,y)=\Phi(\Phi_{1}(x,y),\Phi_{2}(x,y),\dots,\Phi_{n}(x,y))$

has the property that

$\Phi(x_{1},x_{2},\dots,x_{n})\neq 0\textrm{ iff }\Psi(x,y)\neq 0.$

  * 2.

We next show that multivariate ncRANK is deterministic $\mathsf{NC}$ reducible
to bivariate ncRANK. More precisely, given a $d\times d$ linear matrix
$A=A_{0}+\sum_{i=1}^{n}A_{i}x_{i}$ in noncommuting variables
$X=\\{x_{1},x_{2},\ldots,x_{n}\\}$, where the $A_{i}$ are matrices over the
scalar field $\mathbb{F}$, we first give a deterministic NC reduction that
transforms $A$ to a $d\times d$ matrix $B$ whose entries are bivariate
polynomials in $\mathbb{F}\langle x,y\rangle$, where $x$ and $y$ are two
noncommuting variables, where its entries $B[i,j]$ are given by _polynomial
size noncommutative formulas_ , with the property that
$\operatorname{\rm{ncrk}}(A)=\operatorname{\rm{ncrk}}(B)$. Then we examine the
Higman linearization process [21] that transforms $B$ into a matrix
$B^{\prime}$ with linear entries in $x$ and $y$ such that the noncommutative
rank $\operatorname{\rm{ncrk}}(B)$ of $B$ can be easily recovered from
$\operatorname{\rm{ncrk}}(B^{\prime})$. We show that this process can be
implemented in deterministic $\mathsf{NC}$ (the earlier works [21, 22, 23, 19]
only consider its polynomial-time computability).

Additionally, we consider the more general problem $\textrm{ncRANK}_{poly}$ of
computing the noncommutative rank of a matrix whose entries are noncommutative
formulas computing polynomials. We show using our parallel Higman
linearization algorithm that $\textrm{ncRANK}_{poly}$ is also deterministic
$\mathsf{NC}$ reducible to bivariate ncRANK.

Both the multivariate to bivariate reductions, stated above, are crucially
based on a theorem of Cohn [13] (also see [15, Theorem 4.7.3]) which we will
refer to as Cohn’s embedding theorem and describe it later in the
introduction.

  * 3.

Finally, obtaining a deterministic $\mathsf{NC}$ reduction from RIT to ncRANK
turns out to be quite subtle. From the work of Hrubes and Wigderson [21], who
initiated this line of research on RIT, we can only obtain a sequential
deterministic polynomial-time reduction from RIT to ncRANK. However, for our
result we require an $\mathsf{NC}$ reduction. If the given rational formula
has logarithmic depth, then their result already implies an $\mathsf{NC}$
reduction.

Now, in the same paper [21], Hrubes and Wigderson have also shown a _depth
reduction_ result for multivariate noncommutative rational formulas: every
rational formulas of size $s$ is equivalent to a logarithmic depth rational
formula of size $\operatorname{poly}(s)$. Their construction is based on
Brent’s depth reduction result for commutative arithmetic formulas. However,
due to noncommutativity and the presence of inversion gates, the formula
constructed in their proof needs to be different based on whether certain
rational subformulas, arising in the construction procedure, are identically
zero or not. To algorithmize such steps in the construction we need to use RIT
as a subroutine. As RIT has a polynomial-time algorithm [23, 19], the depth-
reduction in [21] also has a polynomial time algorithm.111In the commutative
case, Brent’s result is parallelizable to yield an $\mathsf{NC}$ algorithm.
For noncommutative formulas without inversion gates we can obtain the depth-
reduced formula in $\mathsf{NC}$, as we will observe later in the paper.

As the third result of this paper, building on the Hrubes-Wigderson depth-
reduction construction, we are able to show that, with oracle access to RIT,
rational formula depth reduction can be done in deterministic $\mathsf{NC}$.
Using this we are able to obtain a deterministic $\mathsf{NC}$-Turing
reduction from RIT to ncRANK. Hence, if bivariate ncRANK is in deterministic
$\mathsf{NC}$ we will obtain a deterministic $\mathsf{NC}$ algorithm also for
RIT. We leave open the question whether depth reduction of noncommutative
rational formulas is unconditionally in $\mathsf{NC}$.

We now outline the proof ideas in more detail with some intuitive
explanations.

##  2 Preliminaries

In this section we recall the essential basic definitions and fix the
notation.

Let $\mathbb{F}$ be a (commutative) field222In this paper, $\mathbb{F}$ will
either be the field of rationals or a finite field. and
$X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ be $n$ free noncommuting variables. The
free monoid $X^{*}$ is the set of all monomials in the variables $X$. A
_noncommutative polynomial_ $f(X)$ is a finite $\mathbb{F}$-linear combination
of monomials in $X^{*}$, and the _free noncommutative ring_ $\mathbb{F}\langle
X\rangle$ consists of all noncommutative polynomials.

#### Noncommutative Rational Formulas

An _arithmetic circuit_ computing an element of $\mathbb{F}\langle X\rangle$
is a directed acyclic graph with each indegree $0$ node labeled by either an
input variable $x_{i}\in X$ or some scalar $c\in\mathbb{F}$. Each internal
node $g$ has indegree $2$ and is either a $+$ gate or a $\times$ gate: it
computes the sum (resp. left to right product) of its inputs. Thus, each gate
of the circuit computes a polynomial in $\mathbb{F}\langle X\rangle$ and the
polynomial computed by the circuit is the polynomial computed at the _output
gate_. A _formula_ is restricted to have fanout $1$ or $0$.

When we allow the formulas/circuits to have _inversion gates_ we get _rational
formulas and rational circuits_.

#### The Free Skew Field

We now briefly explain the free skew field construction. The elements of the
free skew field are noncommutative rational functions which are more
complicated than their commutative counterparts. Rational formulas in the
commutative setting can be canonically expressed as ratios of two polynomials.
There is no such canonical representation for noncommutative rational
formulas.

Following Hrubes-Wigderson [21], we use Amitsur’s approach [1] for formally
defining skew fields.333There are other ways to defining free skew fields [1,
5, 27, 10, 11, 12, 15].

It involves defining appropriate notion of equivalence of formulas
(intuitively, two formulas are equivalent if they agree on their _domain of
definition_). The equivalence classes under this equivalence relation are the
elements of the free skew field. We give the formal definitions below.

Let $\mathbb{M}_{k}(\mathbb{F})$ denote the ring of $k\times k$ matrices with
entries from field $\mathbb{F}$. Note that a rational formula $\Phi$ defines a
partial function

$\hat{\Phi}:\mathbb{M}_{k}(\mathbb{F})^{n}\mapsto\mathbb{M}_{k}(\mathbb{F})$

that on input $(a_{1},a_{2},\ldots,a_{n})\in\mathbb{M}_{k}(\mathbb{F})^{n}$
evaluates $\Phi$ by substituting $x_{i}\leftarrow a_{i}$ for $i\in[n]$.
$\hat{\Phi}(a_{1},\ldots,a_{n})$ is undefined if the input to some inversion
gate in $\Phi$ is not invertible in $\mathbb{M}_{k}(\mathbb{F})$.

######  Definition 2.1.

Let $\Phi$ be a rational formula in variables $X$. For each $k\in\mathbb{N}$,
let $\mathcal{D}_{k,\Phi}$ be the set of all matrix tuples
$(a_{1},a_{2},\ldots,a_{n})\in\mathbb{M}_{k}(\mathbb{F})^{n}$ such that
$\hat{\Phi}(a_{1},a_{2},\ldots,a_{n})$ is defined. The _domain of definition_
of $\Phi$ is the union $\mathcal{D}_{\Phi}=\bigcup_{k}\mathcal{D}_{k,\Phi}$.

######  Definition 2.2.

[21]

  * •

A rational formula $\Phi$ is called _correct_ if for every gate $u$ of $\Phi$
the subformula $\Phi_{u}$ has a nonempty domain of definition.

  * •

Correct rational formulas $\Phi_{1},\Phi_{2}$ are said to be _equivalent_
(denoted $\Phi_{1}\equiv\Phi_{2}$) if the intersection
$\mathcal{D}_{\Phi_{1}}\cap\mathcal{D}_{\Phi_{2}}$ of their domains of
definitions is nonempty and they agree on all the points in the intersection.

We note that equivalent formulas need not have the same domain of definition.
For example, $\Phi_{1}=z_{1}z_{2}z_{3}$ and
$\Phi_{2}=(z_{1}z_{2}z_{3}\cdot(z_{2}z_{3}-z_{3}z_{2})^{-1})\cdot(z_{2}z_{3}-z_{3}z_{2})$
are equivalent. However, the domain of definition of $\Phi_{1}$ includes all
matrix tuples, whereas the domain of definition of $\Phi_{2}$ contains only
matrix tuples $(Z_{1},Z_{2},Z_{3})$ such that $Det(Z_{2}Z_{3}-Z_{3}Z_{2})\neq
0$.

The relation $\equiv$ as defined above is an equivalence relation on rational
formulas and the equivalence classes, called _rational functions_ , are the
elements of the skew field $\mathbb{F}{\lparenless}X{\rparengtr}$ [21, 1].

#### Noncommutative Rank

We now recall the notion of rank for matrices over the noncommutative ring
$\mathbb{F}\langle X\rangle$.

######  Definition 2.3 (inner rank).

Let $M$ be a matrix over $\mathbb{F}\langle X\rangle$. Its _inner rank_ is the
least $r$ such that $M$ can be written as a matrix product $M=PQ$ where $Q$
has $r$ rows (and $P$ has $r$ columns).

######  Definition 2.4 (full matrices).

An $n\times n$ square matrix $M$ over $\mathbb{F}\langle X\rangle$ is _full_
if it cannot be decomposed as a matrix product $M=PQ$ where $P$ is $n\times r$
and $Q$ is $r\times n$ for $r<n$. In other words, an $n\times n$ matrix is
called full precisely when its inner rank is $n$.

We can also define the rank of a matrix $M$ to be the maximum $r$ such that
$M$ contains an $r\times r$ full submatrix. For matrices over
$\mathbb{F}\langle X\rangle$ these notions of _noncommutative rank_ coincide
as summarized below.444For a ring $R$ in general, a full matrix $R$ need not
be invertible (see [21] for an example).

######  Proposition 2.5.

[15]

Let $M$ be an $n\times n$ matrix over the ring $\mathbb{F}\langle X\rangle$.
Then

  * •

$M$ is a full matrix (that is, $M$ has inner rank $n$) iff it is invertible
over the skew field $\mathbb{F}{\lparenless}X{\rparengtr}$.

  * •

More generally, $M$ has inner rank $r$ iff the largest full submatrix of $M$
is $r\times r$.

#### The Algorithmic Problems of Interest

At this point we formally define the problems of interest in this paper.

  1. 1.

The multivariate RIT problem takes as input a rational formula $\Phi$,
computing a rational function $\hat{\Phi}$ in
$\mathbb{F}{\lparenless}X{\rparengtr}$, and the problem is to check if $\Phi$
is equivalent to $0$? In the bivariate RIT problem $\Phi$ computes a rational
function in $\mathbb{F}{\lparenless}x,y{\rparengtr}$.

  2. 2.

The multivariate ncRANK problem takes as input a matrix $M$ with affine linear
form entries over $X$ and the problem is to determine its noncommutative rank
$\operatorname{\rm{ncrk}}(M)$. Bivariate ncRANK is similarly defined.

  3. 3.

A more general version of ncRANK is $\textrm{ncRANK}_{poly}$ in which the
matrix entries are allowed to be polynomials in $\mathbb{F}\langle X\rangle$
computed by noncommutative formulas. A closely related problem is SINGULAR
where the problem is to test if a square matrix $M$ over $\mathbb{F}\langle
X\rangle$ with entries computed by formulas is singular or not.

#### The complexity class $\mathsf{NC}$ and $\mathsf{NC}$ reductions

The class $\mathsf{NC}$ consists of decision problems that can be solved in
$\operatorname{polylog}(n)$ time with $\operatorname{poly}(n)$ many
processors.555 This model is widely accepted as the right theoretical notion
for efficient parallel algorithms. For two decision problems $A$ and $B$ we
say $A$ is many-one $\mathsf{NC}$ reducible to $B$ if there is a reduction
from $A$ to $B$ that is $\mathsf{NC}$ computable. Similarly, $A$ is
$\mathsf{NC}$-Turing reducible to $B$ if there is an oracle $\mathsf{NC}$
algorithm for $A$ that has oracle access to $B$.

It turns out that SINGULAR and ncRANK are equivalent even under deterministic
$\mathsf{NC}$ reductions. 666As for $M\in\mathbb{F}\langle X\rangle^{m\times
n}$, $\operatorname{\rm{ncrk}}(M)=r$ iff $r$ is a size of a largest sized
invertible minor of $M$, so to compute $\operatorname{\rm{ncrk}}(M)$, it
suffices to test singularity of matrix $UMV$, where $U,V$ are generic $r\times
m,n\times r$ matrices respectively with entries as fresh noncommuting
variables for $r\leq\min(m,n)$. See e.g. [19, Lemma A.3] for details.

#### Cohn’s Embedding Theorem

We now give an outline of Cohn’s embedding theorem and how it gives us the
desired reduction from multivariate to bivariate RIT and also from
multivariate to bivariate ncRANK. However, for multivariate to bivariate
reduction for ncRANK we will require additional $\mathsf{NC}$ algorithms for
formula depth reduction and Higman linearization.

Let $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ be a set of $n$ noncommuting variables,
and let $x,y$ be a pair of noncommuting variables. We first recall the
following well-known fact, observed in the early papers on noncommutative
polynomial identity testing [7, 26]: for noncommutative polynomials in
$\mathbb{F}\langle X\rangle$, the problem of polynomial identity testing (PIT)
is easily reducible to PIT for bivariate noncommutative polynomials in
$\mathbb{F}\langle x,y\rangle$. Indeed, more formally, we have the following
easy to check fact.

######  Fact 2.6.

The map

$x_{i}\mapsto x^{i-1}y,1\leq i\leq n$

extends to an injective homomorphism (i.e. a _homomorphic embedding_) from the
ring $\mathbb{F}\langle X\rangle$ to the ring $\mathbb{F}\langle x,y\rangle$.

However, in order to obtain our multivariate to bivariate reductions, we need
a mapping $\beta:X\to\mathbb{F}\langle x,y\rangle$ which has the following
properties:

  * •

For each $i$, there is a small noncommutative arithmetic formula that computes
$\beta(x_{i})$.

  * •

$\beta$ extends to an injective homomorphism777That is, a homomorphic
embedding., not just from the ring $\mathbb{F}\langle X\rangle$ to
$\mathbb{F}\langle x,y\rangle$, but also to an injective homomorphism from the
skew field $\mathbb{F}{\lparenless}X{\rparengtr}$ to the skew field
$\mathbb{F}{\lparenless}x,y{\rparengtr}$. This will guarantee that for two
rational formulas $\Phi_{1},\Phi_{2}$ computing inequivalent rational
functions in $\mathbb{F}{\lparenless}X{\rparengtr}$ their images
$\beta(\Phi_{1})$ and $\beta(\Phi_{2})$ also compute inequivalent rational
functions in $\mathbb{F}\langle x,y\rangle$.

  * •

Furthermore, in order to get the multivariate to bivariate reduction for
ncRANK, we will additionally require of the map $\beta$ that for any matrix
$M$ over $\mathbb{F}\langle X\rangle$ its image $\beta(M)$, which is a matrix
over $\mathbb{F}\langle x,y\rangle$ obtained by applying $\beta$ to each entry
of $M$, has the same rank as $M$. Such a homomorphic embedding is called an
_honest embedding_ [13]. Here we note that, full matrices over
$\mathbb{F}\langle X\rangle$ are invertible over
$\mathbb{F}{\lparenless}X{\rparengtr}$ [15]. Consequently if one can lift
embedding $\beta$ to one between the corresponding free skew fields, it
enforces $\beta$ to be an honest embedding.

The mapping $x_{i}\mapsto x^{i-1}y$ actually _does not_ extend to an honest
embedding as observed in [13]. Indeed, the rank $2$ matrix
$\left(\begin{array}[]{cc}x_{1}&x_{2}\\\ x_{3}&x_{4}\end{array}\right)$ has
image

$\left(\begin{array}[]{cc}y&xy\\\
x^{2}y&x^{3}y\end{array}\right)=\left(\begin{array}[]{c}1\\\
x^{2}\end{array}\right)\left(\begin{array}[]{cc}y&xy\end{array}\right)$

which is rank $1$. In general, a homomorphic embedding from a ring $R$ to a
ring $R^{\prime}$ is an _honest embedding_ if it maps full matrices over $R$
to full matrices over $R^{\prime}$. We now state Cohn’s embedding theorem.

For polynomials $f,g\in\mathbb{F}\langle x,y\rangle$ let $[f,g]$ denotes the
commutator polynomial $fg-gf$. Cohn’s embedding map $\beta:\mathbb{F}\langle
X\rangle\to\mathbb{F}\langle x,y\rangle$ is defined as follows.

  * •

Let $\beta(x_{1})=y$. For $i\geq 2$, define $\beta(x_{i})=[\beta(x_{i-1}),x]$.

  * •

We can then naturally extend $\beta$ to a homomorphism from $\mathbb{F}\langle
X\rangle$ to $\mathbb{F}\langle y,x\rangle$, and it is easy to check that it
is injective. In fact, we can even assume $|X|$ to be countably infinite.

######  Theorem 2.7 (Cohn’s embedding theorem).

[15, Theorem 7.5.19] The embedding map $\beta:\mathbb{F}\langle
X\rangle\to\mathbb{F}\langle x,y\rangle$ defined above extends to an embedding
between the corresponding skew fields
$\beta:\mathbb{F}{\lparenless}Z{\rparengtr}\to\mathbb{F}{\lparenless}x,y{\rparengtr}$
and hence is an honest embedding.

Cohn’s construction is based on skew polynomial rings, which explains the
appearance of the iterated commutators $\beta(x_{i})=[\beta(x_{i-1}),x]$. We
briefly sketch the underlying ideas in the appendix (see Section 6). For more
details see [13, 15].

##  3 The Reduction from multivariate RIT to bivariate RIT

The reduction follows quite easily from Theorem 2.7. However, we present some
complexity details in this section showing that it is actually a deterministic
$\mathsf{NC}$ reduction. The following lemma is useful to describe the
reduction.

######  Lemma 3.1.

Recall the embedding map $\beta$ defined above. $\beta(z_{0})=y$ and
$\beta(z_{i+1})=[\beta(z_{i}),x]$ are polynomials in $\mathbb{F}\langle
x,y\rangle$ for each $i\geq 0$. Then, for $n\geq 1$ we have

$\beta(z_{n})=\sum_{i=0}^{n}(-1)^{i}{n\choose i}x^{i}yx^{n-i}.$

As a consequence, there is a deterministic $\mathsf{NC}$ algorithm that
constructs a $\operatorname{poly}(n)$-sized formula for $\beta(z_{n})$.

###### Proof.

We will use induction on $n$. The base case follows from the fact that
$\beta(z_{1})=yx-xy$. Inductively assume the claim is true for all $n$. Now,
$\beta(z_{n+1})=[\beta(z_{n}),x]$

$\displaystyle=$ $\displaystyle\sum_{i=0}^{n}(-1)^{i}{n\choose
i}x^{i}yx^{n-i+1}-\sum_{j=0}^{n}(-1)^{j}{n\choose j}x^{j+1}yx^{n-j}~{}\text{by
induction hypothesis}$ $\displaystyle=$ $\displaystyle
yx^{n+1}+\sum_{i=1}^{n}(-1)^{i}{n\choose
i}x^{i}yx^{n-i+1}+\sum_{i=1}^{n+1}(-1)^{i}{n+1-1\choose i-1}x^{i}yx^{n+1-i}$
$\displaystyle=$ $\displaystyle
yx^{n+1}+\sum_{i=1}^{n}(-1)^{i}~{}~{}\left[{n+1-1\choose i}+{n+1-1\choose
i-1}\right]~{}~{}x^{i}yx^{n-i+1}+(-1)^{n+1}x^{n+1}y$ $\displaystyle=$
$\displaystyle yx^{n+1}+(-1)^{n+1}x^{n+1}y+\sum_{i=1}^{n}(-1)^{i}{n+1\choose
i}x^{i}yx^{n+1-i}~{}~{}\text{from Pascal's identity}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n+1}(-1)^{i}{n+1\choose i}x^{i}yx^{n+1-i}$

This completes the inductive proof.

As the binomial coefficients can be computed in $\mathsf{NC}$ using Pascal’s
identity, the expression for $\beta(z_{n})$ obtained above immediately implies
an $\mathsf{NC}$ algorithm for construction of a $\operatorname{poly}(n)$
sized formula for $\beta(z_{n})$. $\Box$

######  Theorem 3.2.

The multivariate RIT problem is deterministic $\mathsf{NC}$ (in fact,
logspace) reducible to bivariate RIT. More precisely, given as input a
rational formula $\Phi$ computing an element of
$\mathbb{F}{\lparenless}X{\rparengtr}$, $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$
there is a deterministic $\mathsf{NC}$ algorithm that computes a rational
formula $\Psi$ computing an element of
$\mathbb{F}{\lparenless}x,y{\rparengtr}$ such that $\Phi$ is nonzero in its
domain of definition iff $\Psi$ is nonzero in its domain of definition.

###### Proof.

We can identify $\mathbb{F}{\lparenless}X{\rparengtr}$ with
$\mathbb{F}{\lparenless}z_{0},z_{1},\ldots,z_{n-1}{\rparengtr}$. Let
$\Phi_{i}(x,y)$ be the $\operatorname{poly}(i)$ size noncommutative formula
computing the nested commutator $\beta(z_{i})$ for each $i$. In the rational
formula $\Phi$, for each $i$ we replace the input $z_{i}$ to $\Phi$ by
$\Phi_{i}(x,y)$. The new formula we obtain is

$\Psi(x,y)=\Phi(\Phi_{1}(x,y),\Phi_{2}(x,y),\ldots,\Phi_{n-1}(x,y)).$

By Theorem 2.7, $\Psi(x,y)\neq 0$ on its domain of definition iff
$\Phi(z_{0},z_{1},\ldots,z_{n-1})$ is nonzero on its domain of definition.
Furthermore, because $\beta$ is an embedding, it is guaranteed that if $\Phi$
has a nontrivial domain of definition then $\Psi$ also has a nontrivial domain
of definition.

As computation of $\Psi$ from $\Phi$ involves only replacing the $z_{i}$ by
$\Phi_{i}$, the reduction is clearly logspace computable. $\Box$

##  4 Reduction from $n$-variate $\textrm{ncRANK}_{poly}$ to $2$-variate
ncRANK

In this section we give a deterministic $\mathsf{NC}$ reduction from
$n$-variate $\textrm{ncRANK}_{poly}$ to bivariate ncRANK. The basic idea of
the reduction is as follows. Given a polynomial matrix888We can assume it is a
square matrix without loss of generality. $M\in\mathbb{F}\langle
X\rangle^{m\times m}$ such that each entry of $M$ is computed by formula of
size at most $s$. We will use Cohn’s embedding theorem 2.7 to get a matrix
$M_{1}$ with _bivariate_ polynomial entries such that each entry of $M_{1}$ is
computed by a $\operatorname{poly}(n,s)$ size noncommutative formula and
$\operatorname{\rm{ncrk}}(M)=\operatorname{\rm{ncrk}}(M_{1})$. Notice that
$M_{1}$ is an instance of bivariate $\textrm{ncRANK}_{poly}$. Next, we need to
give an $\mathsf{NC}$ reduction transforming $M_{1}$ to an instance of
bivariate ncRANK (which will be a matrix with linear entries in $x$ and $y$).

In order to do this transformation in $\mathsf{NC}$, we will first apply the
depth-reduction algorithm of Lemma 4.2 to get matrix $M_{2}$ whose entries are
$\operatorname{poly}(n,s)$ size log-depth formulas that compute the same
polynomials as the corresponding entries of $M_{1}$. Then we apply Higman
Linearization to $M_{2}$ to obtain a bivariate linear matrix $M_{3}$. For this
we will use our parallel algorithm for Higman Linearization described in
Theorem 4.4. From the properties of Higman linearization we can easily recover
$\operatorname{\rm{ncrk}}(M_{2})$ from $\operatorname{\rm{ncrk}}(M_{3})$. In
what follows, first we give a deterministic $\mathsf{NC}$ algorithm for the
depth reduction of noncommutative formulas and Higman linearization process.
We conclude the section by giving an $\mathsf{NC}$ reduction from multivariate
to bivariate ncRANK using above $NC$ algorithms combined with Cohn’s embedding
theorem 2.7.

###  4.1 Depth reduction for noncommutative formulas without divisions

In the commutative setting Brent [8] obtained a deterministic $\mathsf{NC}$
algorithm to transform a given _rational_ formula (which may have division
gates) to a log-depth rational formula. In the noncommutative setting, Hrubes
and Wigderson [21] proved the _existence_ of log-depth _rational_ formula
equivalent to any given rational formula. Their proof is based on [8].
However, it is not directly algorithmic as explained in the introduction. We
will discuss it in more detail in Section 5. However, it turns out that, if
the noncommutative formula doesn’t have division gates then the depth
reduction is quite easy and we obtain a simple deterministic $\mathsf{NC}$
algorithm for it that computes a log-depth noncommutative formula equivalent
to the given noncommutative formula. The proof is based Brent’s commutative
version. We just highlight the distinctive points arising in the
noncommutative version in the proof presented in the appendix.

We introducing some notation. Let $\Phi$ be a noncommutative arithmetic
formula computing a polynomial in $\mathbb{F}\langle
x_{1},x_{2},\ldots,x_{n}\rangle$. Let $\hat{\Phi}$ denote the polynomial
computed by $\Phi$. For a node $v\in\Phi$, let $\Phi_{v}$ denote the
subformula of $\Phi$ rooted at node $v$, so $\hat{\Phi_{v}}$ is the polynomial
computed by the subformula rooted at $v$. For a node $v\in\Phi$, let
$\Phi_{v\leftarrow z}$ be a formula obtained from $\Phi$ by replacing the sub-
formula $\Phi_{v}$ by single variable $z$. For a node $v\in\Phi$, let
$wt(v)=|\Phi_{v}|$ denote the number of nodes in the subformula rooted at $v$.
By size of formula $\Phi$ we refer to number of gates in $\Phi$.

######  Lemma 4.1.

Given a formula $\Phi$ of size $s$ computing a noncommutative polynomial
$f\in\mathbb{F}\langle x_{1},x_{2},\ldots,x_{n}\rangle$ there is an
$\mathsf{NC}$ algorithm to obtain an equivalent formula $\Phi^{\prime}$ for
$f$ with depth $O(\log s)$.

The proof of the lemma is in the appendix.

######  Remark 4.2.

In Lemma , we avoid using the depth-reduction approach for noncommutative
rational formulas in [21]. This is because it can introduce inversion gates
even if the original formula has no inversion gates. Instead, we directly
adapt ideas from Brent’s construction for commutative formulas to obtain the
NC algorithm. We note here that Nisan’s seminal work [24] also briefly
mentions noncommutative formula depth reduction (but not its parallel
complexity or even in an algorithmic context).

Higman linearization which is sometimes called Higman’s trick was first used
by Higman in [20]. Cohn extensively used Higman Linearization in his
factorization theory of free ideal rings. Given a matrix with noncommutative
polynomials as its entries, Higman linearization process transforms it into a
matrix with linear entries. This transformation process has several nice
properties such as: it preserves fullness of the matrix (that is the input
polynomial matrix is full rank iff final linear matrix is full rank), it
preserves irreducibility of the matrix, etc.

We first describe a single step of the linearization process applied to a
single noncommutative polynomial, which easily generalizes to matrices with
polynomial entries. Given an $m\times m$ matrix $M$ over $\mathbb{F}\langle
X\rangle$ such that $M[m,m]=f+g\times h$, apply the following:

  * •

Expand $M$ to an $(m+1)\times(m+1)$ matrix by adding a new last row and last
column with diagonal entry $1$ and remaining new entries zero:

$\left[\begin{array}[]{c|c}M&0\\\ \hline\cr 0&1\end{array}\right].$

  * •

Then the bottom right $2\times 2$ submatrix is transformed as follows by
elementary row and column operations

$\left(\begin{array}[]{cc}f+gh&0\\\
0&1\end{array}\right)\rightarrow\left(\begin{array}[]{cc}f+gh&g\\\
0&1\end{array}\right)\rightarrow\left(\begin{array}[]{cc}f&g\\\
-h&1\end{array}\right)$

Given a polynomial $f\in\mathbb{F}\langle X\rangle$ by repeated application of
the above step we will finally obtain a _linear matrix_
$L=A_{0}+\sum_{i=1}^{n}A_{i}x_{i}$, where each $A_{i},0\leq i\leq n$ is an
$\ell\times\ell$ over $\mathbb{F}$, for some $\ell$. The following theorem
summarizes its properties.

######  Theorem 4.3 (Higman Linearization).

[15] Given a polynomial $f\in\mathbb{F}\langle X\rangle$, there are matrices
$P,Q\in\mathbb{F}\langle X\rangle^{\ell\times\ell}$ and a linear matrix
$L\in\mathbb{F}\langle X\rangle^{\ell\times\ell}$ such that

$P\left(\begin{array}[]{c|c}f&0\\\ \hline\cr
0&I_{\ell-1}\end{array}\right)~{}Q=~{}L$ (1)

with $P$ upper triangular, $Q$ lower triangular, and the diagonal entries of
both $P$ and $Q$ are all $1$’s. (Hence, $P$ and $Q$ are both invertible over
$\mathbb{F}{\lparenless}X{\rparengtr}$, moreover entries of $P^{-1}$ and
$Q^{-1}$ are in $\mathbb{F}\langle X\rangle$).

Instead of a single $f$, we can apply Higman linearization to a matrix of
polynomials $M\in\mathbb{F}\langle X\rangle^{m\times m}$ to obtain a linear
matrix $L$ such that $P(M\oplus I_{k})Q=L$ for invertible matrices $P,Q$. Garg
et al. [19] gave polynomial time algorithm to carry out Higman linearization
for polynomial matrix whose entries are given by noncommutative formulas. We
will give an $\mathsf{NC}$ algorithm to implement this transformation.

######  Theorem 4.4.

Let $A\in\mathbb{F}\langle X\rangle^{n\times n}$ be a polynomial matrix such
that each entry of $A$ is given by a noncommutative formula of size at most
$s$. Then there is a deterministic $\mathsf{NC}$ algorithm (with parallel time
complexity $\operatorname{poly}(\log s,\log n)$) to compute invertible upper
and lower triangular matrices $P,Q\in\mathbb{F}\langle
X\rangle^{\ell\times\ell}$ with all diagonal entries $1$ and a linear matrix
$L\in\mathbb{F}\langle X\rangle^{\ell\times\ell}$ such that
$P~{}\left(\begin{array}[]{c|c}A&0\\\ \hline\cr
0&I_{k}\end{array}\right)~{}Q=L$, where $\ell=n+k$ and $k$ is $O(n^{2}\cdot
s)$. All the entries of $P,Q$ are computable by algebraic branching programs
of size $\operatorname{poly}(n,s)$. Moreover $ncrk(A)+k=ncrk(L)$, hence the
rank of $A$ is easily computable from the rank of $L$.

The proof of the above theorem is in the appendix.

Using Theorem 2.7, Lemma 4.2 and Theorem 4.4 we get a deterministic
$\mathsf{NC}$ reduction from multivariate ncRANK to bivariate ncRANK.

######  Theorem 4.5.

There is a deterministic $\mathsf{NC}$ reduction from the multivariate ncRANK
problem to the bivariate ncRANK problem.

##  5 $\mathsf{NC}$ Reduction from RIT to bivariate ncRANK

In this section we give an $\mathsf{NC}$-Turing reduction from RIT to
bivariate ncRANK. That is, we design an $\mathsf{NC}$ algorithm for RIT
assuming we have an oracle for bivariate ncRANK. Hrubes and Wigderson in [21]
give a polynomial time reduction from RIT to ncRANK problem [21, Theorem 2.6].
Also they show that for any given rational formula $\Phi$ there is a log-depth
rational formula that is equivalent to $\Phi$ [21, Proposition 4.1].

Our key contribution here is to use Cohn’s embedding theorem to transform RIT
problem to the _bivariate_ case. Then we parallelize the Hrubes-Wigderson
reduction from RIT to ncRANK. In fact, if the input rational formula is
already logarithmic depth then the Hrubes-Wigderson reduction from RIT to
ncRANK can be implemented in $\mathsf{NC}$. In this section we design an
$\mathsf{NC}$ algorithm for depth reduction of rational formulas (possibly
with division gates) assuming $\mathsf{NC}$ oracle for bivariate ncRANK.999 It
is an interesting problem to devise an $\mathsf{NC}$ algorithm for rational
formula depth reduction without oracle access to singularity test. Indeed, the
construction of an equivalent log-depth rational formula, as described in
[21], does not appear to be directly parallelizable, as its description
crucially requires rational formula identity testing.101010The overall proof
in [21] is based on the Brent’s depth-reduction of commutative rational
formulas [8]. In the commutative case addressed by Brent, it turns out that
the construction procedure does not require oracle access to identity testing
and he obtains an $\mathsf{NC}$ algorithm for obtaining the depth-reduced
formula.

We show that, indeed, the depth-reduction proof in [21] can be parallelized
step by step. However, there are some key points where our algorithmic proof
is different. Firstly, to solve the RIT instance arising in the depth-
reduction proof, we need to recursively depth-reduce the corresponding
subformula and then apply Hrubes-Wigderson reduction from RIT to ncRANK on the
constructed log-depth subformula. Secondly, we need to handle an important
case arising in the proof (namely, the case (2) in the description of the
Normal-Form procedure in the proof of the Lemma 5.3 in the Appendix) which was
not significant for the existential argument in [21]. In fact to handle this
case, we require an argument based on Brent’s commutative formula depth
reduction [8].

In the detailed proof of Lemma 5.3 given in the Appendix, we first sketch our
$\mathsf{NC}$ algorithm for depth reduction of rational formula assuming
oracle access to bivariate ncRANK. We highlight and elaborate the key steps
where our proof differs from [21]. We need to reproduce some parts of their
proof for completeness, for these parts we just sketch the argument and refer
to [21] for the details. Using this depth reduction algorithm we give an
$\mathsf{NC}$ Turing reduction from RIT to bivariate ncRANK, which is a main
result of this section.

###  5.1 Depth reduction for noncommutative formulas with inversion gates

The following is a consequence of results in [21] and [17].

######  Theorem 5.1 ([21], [17]).

Let $\Phi$ be a rational formula of size $s$ computing a _non-zero_ rational
function in $\mathbb{F}{\lparenless}X{\rparengtr}$. If the field $\mathbb{F}$
is sufficiently large and $k>2s$ then, at a matrix tuple
$(M_{1},M_{2},\ldots,M_{n})$ chosen uniformly at random from $M_{k\times
k}(\mathbb{F})^{n}$, the matrix $\hat{\Phi}(M_{1},\ldots,M_{n})$ is
nonsingular with "high" probability.

If $\mathbb{F}$ is small then we can pick the random matrices over a suitable
extension field, and by “high” probability we mean, say, $1-2^{-\Omega(s+n)}$.

Let $\Phi_{1}$ and $\Phi_{2}$ be correct rational formulas of size at most $s$
computing rational functions in $\mathbb{F}{\lparenless}X{\rparengtr}$. By
Theorem 5.1 and a union bound argument, for a random matrix substitution
$(M_{1},M_{2},\ldots,M_{n})$ from $M_{k\times k}(\mathbb{F})^{n}$, inputs to
all the inversion gates in $\Phi_{1}$ and $\Phi_{2}$ simultaneously evaluate
to non-singular matrices with "high" probability. Hence, for $k$ sufficiently
large we have
$\mathcal{D}_{k,\Phi_{1}}\cap\mathcal{D}_{k,\Phi_{2}}\neq\emptyset$. It
follows that a random matrix tuple is in
$\mathcal{D}_{k,\Phi_{1}}\cap\mathcal{D}_{k,\Phi_{2}}$ with high probability.

By Theorem 5.1 and the definition of correct rational formulas (Definition
2.2), it follows that if $\Phi_{1}$ and $\Phi_{2}$ are size $s$ correct
formulas that are _not_ equivalent then for a random matrix substitution of
dimension $k>2s$ both $\Phi_{1}$ and $\Phi_{2}$ are defined and they disagree
with high probability. As noted in Section 2, equivalent formulas need not
have the same domain of definition.

Lemma 5.3 is the main technical result of this section. It describes an
$\mathsf{NC}$ algorithm for depth-reduction of correct formulas assuming an
oracle for bivariate ncRANK. The next lemma is useful for establishing
equivalences of formulas arising in the proof of Lemma 5.3. Suppose $\Phi$ is
a rational formula computing the rational function $\hat{\Phi}$. For a gate
$v$ in formula $\Phi$, $\Phi_{v}$ denotes the subformula rooted at $v$. The
formula $\Phi_{v\leftarrow
z}\in\mathbb{F}{\lparenless}X\cup\\{z\\}{\rparengtr}$ is obtained from $\Phi$
by replacing subformula $\Phi_{v}$ with fresh variable $z$.

######  Lemma 5.2 (local surgery).

Let $\Phi$ be a correct rational formula and $v$ be a gate in $\Phi$. Suppose
$\Psi$ is a correct rational formula equivalent to $\Phi_{v}$. Let
$\Psi^{\prime}=(A\cdot z+B)\cdot(C\cdot z+D)^{-1}$ is a formula equivalent to
$\Phi_{v\leftarrow z}$ such that $A,B,C,D$ are correct formulas which do not
depend upon $z$ and $\hat{C}\cdot\hat{\Delta}+\hat{D}\neq 0$ for any formula
$\Delta$ such that $\Phi_{v\leftarrow\Delta}$ is correct. Let $\Phi^{\prime}$
denote the rational formula obtained by replacing $z$ in $\Psi^{\prime}$ by
$\Psi$. Then $\Phi^{\prime}$ is correct and it is equivalent to $\Phi$.

###### Proof.

From the definitions of $\Phi_{v}$ and $\Phi_{v\leftarrow z}$ it follows that
$\Phi=\Phi_{v\leftarrow\Phi_{v}}$. As $\Phi$ is correct, from the properties
of formulas $C,D$ as stated in the lemma it follows that
$\hat{C}\hat{\Phi_{v}}+\hat{D}\neq 0$. Which implies
$\hat{C}\hat{\Psi}+\hat{D}\neq 0$ as $\Psi\equiv\Phi_{v}$. This shows that the
formula $\Phi^{\prime}=(A\cdot\Psi+B)\cdot(C\cdot\Psi+D)^{-1}$ is correct. Now
let $\tau=(M_{1},\ldots,M_{n})$ is a matrix tuple in
$\mathcal{D}_{\Phi}\cap\mathcal{D}_{\Phi^{\prime}}$, the intersection of
domains of definition of $\Phi$ and $\Phi^{\prime}$. This implies
$\tau\in\mathcal{D}_{\Phi_{v}}$ as
$\mathcal{D}_{\Phi}\subseteq\mathcal{D}_{\Phi_{v}}$, $\Phi_{v}$ being
subformula of $\Phi$. Similarly, $\tau\in\mathcal{D}_{\Psi}$ as
$\mathcal{D}_{\Phi^{\prime}}\subseteq\mathcal{D}_{\Psi}$, $\Psi$ being a
subformula of $\Phi^{\prime}$. So
$\tau\in\mathcal{D}_{\Phi_{v}}\cap\mathcal{D}_{\Psi}$. As
$\Phi_{v}\equiv\Psi$, it follows that $\Phi_{v}(\tau)=\Psi(\tau)$. As
$\tau\in\mathcal{D}_{\Phi}$. It implies that
$(M_{1},M_{2},\ldots,M_{n},\Phi_{v}(\tau))=(\tau,\Phi_{v}(\tau))\in\mathcal{D}_{\Phi_{v\leftarrow
z}}$. Similarly, as $\tau\in\mathcal{D}_{\Phi^{\prime}}$, it follows that
$(\tau,\Psi(\tau))\in\mathcal{D}_{\Psi^{\prime}}$. As
$\Phi_{v}(\tau)=\Psi(\tau)$, it implies

$(\tau,\Phi_{v}(\tau))=(\tau,\Psi(\tau))\in\mathcal{D}_{\Phi_{v\leftarrow
z}}\cap\mathcal{D}_{\Psi^{\prime}}$

As $\Phi_{v\leftarrow z}\equiv\Psi^{\prime}$, this implies $\Phi_{v\leftarrow
z}(\tau,\Phi_{v}(\tau))=\Psi^{\prime}(\tau,\Psi(\tau))$. But
$\Phi_{v\leftarrow z}(\tau,\Phi_{v}(\tau))=\Phi(\tau)$ and
$\Psi^{\prime}(\tau,\Psi(\tau))=\Phi^{\prime}(\tau)$. So we get
$\Phi(\tau)=\Phi^{\prime}(\tau)$ for any
$\tau\in\mathcal{D}_{\Phi}\cap\mathcal{D}_{\Phi^{\prime}}$. Thus proving
$\Phi\equiv\Phi^{\prime}$. $\Box$

######  Lemma 5.3.

Given a _correct_ formula $\Phi$ of size $s$ computing a rational function
$f\in\mathbb{F}{\lparenless}X{\rparengtr}$, for sufficiently large $s$ and
absolute constants $c,b$

  1. 1.

we give an $\mathsf{NC}$ algorithm, with oracle access to bivariate ncRANK,
that outputs a correct formula $\Phi^{\prime}$ of depth at most $c\log_{2}s$
which is equivalent to $\Phi$.

  2. 2.

If a variable $z$ occurs in $\Phi$ at most once then we give an $\mathsf{NC}$
algorithm, with bivariate ncRANK as oracle, that constructs _correct_ rational
formulas $A,B,C,D$ which do not depend on $z$ with depth at most
$c\log_{2}s+b$ and the formula $\Phi^{\prime}=(A\cdot z+B)\cdot(C\cdot
z+D)^{-1}$ is equivalent to $\Phi$. Moreover, the rational function
$\hat{C}\hat{\Psi}+\hat{D}\neq 0$ for any formula $\Psi$ such that
$\Phi_{z\leftarrow\Psi}$ is correct.

The proof of the above lemma is given in the appendix.

#### Hrubes-Wigderson reduction from RIT to ncRANK

Now we recall the polynomial-time reduction from RIT to ncRANK from [21,
Theorem 2.6]. Given a rational formula $\Phi$ their reduction outputs an
invertible linear matrix $M$ in the variables $X$.111111Notice that the
entries of $M^{-1}$ are elements of the skew field
$\mathbb{F}{\lparenless}X{\rparengtr}$ Their reduction ensures that the top
right entry of $M^{-1}$ is $\hat{\Phi}$, the rational function computed by the
formula $\Phi$. It turns out that if $\Phi$ is already of logarithmic depth
then their reduction can be implemented in $\mathsf{NC}$.

######  Theorem 5.4 ([21]).

Let $\Phi$ be a rational formula of size $s$ and depth $O(\log s)$ computing a
rational expression in $\mathbb{F}{\lparenless}X{\rparengtr}$ there is an
$\mathsf{NC}$ algorithm to construct an invertible linear matrix $M_{\Phi}$
such that the top right entry of $M_{\Phi}^{-1}$ is $\hat{\Phi}$.

###### Proof.

We only briefly sketch the $\mathsf{NC}$ algorithm. Their reduction
recursively constructs the matrix $M_{\Phi}$, using the formula structure of
$\Phi$.

Given a formula $\Phi$ we can compute the sizes of all its subformulas in
$\mathsf{NC}$ using a standard pointer doubling algorithm. This allows us to
estimate the dimensions of matrices $M_{\Phi_{v}}$ for subformulas $\Phi_{v}$
for each gate $v$ of $\Phi$. We can also compute in $\mathsf{NC}$ the precise
location for placement of the sub-matrices $M_{\Phi_{v}}$ inside the matrix
$M_{\Phi}$ following their construction. Assuming that $\Phi$ is already of
logarithmic depth, there are only $O(\log s)$ nested recursive calls for this
recursive procedure. This ensures that the overall process can be implemented
in $\mathsf{NC}$. $\Box$

After constructing linear matrix $M_{\Phi}$ such that the top right entry of
$M_{\Phi}^{-1}$ is $\hat{\Phi}$, define matrix $M^{\prime}$ as
$M^{\prime}=\left(\begin{array}[]{cc}v^{T}&M_{\Phi}\\\ 0&-u\end{array}\right)$

where $u,v$ are $1\times k$ vectors, such that $u=(1,0,\ldots,0)$ and
$v=(0,0,\ldots,0,1)$ where $k$ is the dimension of the matrix $M_{\Phi}$. It
follows that $\hat{\Phi}\neq 0$ iff $M^{\prime}$ is invertible in the skew
field $\mathbb{F}{\lparenless}X{\rparengtr}$ (see e.g. [18, Proposition
3.29]). So we have the following theorem.

######  Theorem 5.5 ([21]).

Let $\Phi$ be a rational formula of size $s$ and depth $O(\log s)$ computing a
rational expression in $\mathbb{F}{\lparenless}X{\rparengtr}$ then there is an
$\mathsf{NC}$ algorithm to construct a linear matrix $M$ such that
$\hat{\Phi}\neq 0$ iff $M$ is invertible in the skew field
$\mathbb{F}{\lparenless}X{\rparengtr}$.

Now, from Lemma 5.3, Theorem 5.5, and Theorem 3.2, we obtain an $\mathsf{NC}$
Turing reduction from multivariate RIT to bivariate ncRANK.

######  Theorem 5.6.

There is a deterministic $\mathsf{NC}$ Turing reduction from RIT problem to
ncRANK problem for bivariate linear matrices.

#### Concluding Remarks.

Motivated by the question whether RIT and ncRANK have deterministic
$\mathsf{NC}$ algorithms, we show that multivariate RIT is
$\mathsf{NC}$-reducible to bivariate RIT and multivariate ncRANK is
$\mathsf{NC}$-reducible to bivariate ncRANK. RIT is known to be polynomial-
time reducible to ncRANK, and indeed that is how the polynomial-time algorithm
for RIT works, by reducing to ncRANK and solving ncRANK. We show that RIT is
deterministic $\mathsf{NC}$-Turing reducible to ncRANK. We prove this by
showing that noncommutative rational formula depth reduction is
$\mathsf{NC}$-Turing reducible to ncRANK. The main open problem is to obtain
deterministic $\mathsf{NC}$ algorithms for bivariate ncRANK and bivariate RIT.
We also leave open finding an unconditional $\mathsf{NC}$ algorithm for depth-
reduction of noncommutative rational formulas.

## References

  * [1] S. A. Amitsur.  Rational identities and applications to algebra and geometry.  Journal of Algebra, 3:304–359, 1966.
  * [2] V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay.  Black-box identity testing of noncommutative rational formulas in deterministic quasipolynomial time.  CoRR, abs/2309.1564, 2023. In STOC 2024, to appear.
  * [3] V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay.  Trading determinism for noncommutativity in Edmonds’ problem.  CoRR, abs/2404.07986, 2024.
  * [4] Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja.  Randomized polynomial-time identity testing for noncommutative circuits.  Theory Comput., 15:1–36, 2019.
  * [5] G. M. Bergman.  Skew fields of noncommutative rational functions, after Amitsur.  Sé Schü–Lentin–Nivat, Paris, 1970.
  * [6] Markus Bläser, Gorav Jindal, and Anurag Pandey.  A deterministic PTAS for the commutative rank of matrix spaces.  Theory Comput., 14(1):1–21, 2018.
  * [7] Andrej Bogdanov and Hoeteck Wee.  More on noncommutative polynomial identity testing.  In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 92–99, 2005.
  * [8] Richard P. Brent.  The parallel evaluation of general arithmetic expressions.  J. ACM, 21(2):201–206, 1974.
  * [9] Abhranil Chatterjee and Partha Mukhopadhyay.  The noncommutative edmonds’ problem re-visited.  CoRR, abs/2305.09984, 2023.
  * [10] P. M. Cohn.  The embedding of fir in skew fields.  Proceedings of the London Mathematical Society, 23:193–213, 1971\.
  * [11] P. M. Cohn.  Universal skew fields of fractions.  Sympos. Math., 8:135–148, 1972.
  * [12] P. M. Cohn.  Free Rings and their Relations.  London Mathematical Society Monographs. Academic Press, 1985.
  * [13] P. M. Cohn.  An embedding theorem for free associative algebras.  Mathematica Pannonica, 1(1):49–56, 1990.
  * [14] P. M. Cohn.  Introduction to Ring Theory.  Springer, 2000.
  * [15] P. M. Cohn.  Free Ideal Rings and Localization in General Rings.  New Mathematical Monographs. Cambridge University Press, 2006.
  * [16] Richard A. DeMillo and Richard J. Lipton.  A probabilistic remark on algebraic program testing.  Inf. Process. Lett., 7(4):193–195, 1978.
  * [17] Harm Derksen and Visu Makam.  Polynomial degree bounds for matrix semi-invariants.  CoRR, abs/1512.03393, 2015.
  * [18] Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson.  A deterministic polynomial time algorithm for non-commutative rational identity testing.  CoRR, abs/1511.03730, 2015.
  * [19] Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson.  Operator scaling: Theory and applications.  Found. Comput. Math., 20(2):223–290, 2020.
  * [20] Graham Higman.  The units of group-rings.  Proceedings of the London Mathematical Society, s2-46(1):231–248, 1940.
  * [21] Pavel Hrubes and Avi Wigderson.  Non-commutative arithmetic circuits with division.  Theory Comput., 11:357–393, 2015.
  * [22] Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam.  Non-commutative edmonds’ problem and matrix semi-invariants.  Comput. Complex., 26(3):717–763, 2017.
  * [23] Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam.  Constructive non-commutative rank computation is in deterministic polynomial time.  Comput. Complex., 27(4):561–593, 2018.
  * [24] 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. ACM, 1991.
  * [25] Sanguthevar Rajasekaran and John H. Reif, editors.  Handbook of Parallel Computing - Models, Algorithms and Applications.  Chapman and Hall/CRC, 2007.
  * [26] Ran Raz and Amir Shpilka.  Deterministic polynomial identity testing in non-commutative models.  Comput. Complex., 14(1):1–19, 2005.
  * [27] L. H. Rowen.  Polynomial identities in ring theory, Pure and Applied Mathematics.  Academic Press Inc., Harcourt Brace Jovanovich Publishers, New York, 1980\.
  * [28] Jacob T. Schwartz.  Fast probabilistic algorithms for verification of polynomial identities.  J. ACM, 27(4):701–717, 1980.
  * [29] James C. Wyllie.  Complexity of Parallel Computation, PhD Thesis.  Cornell University, 1979.
  * [30] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Edward W. Ng, editor, Symbolic and Algebraic Computation, EUROSAM ’79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, volume 72 of Lecture Notes in Computer Science, pages 216–226. Springer, 1979.

Appendix

##  6 Cohn’s Embedding Theorem

Let $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ be a set of $n$ noncommuting variables,
and let $x,y$ be a pair of noncommuting variables. The goal of Cohn’s
construction [13] is to obtain an honest embedding from $\mathbb{F}\langle
X\rangle\to\mathbb{F}\langle x,y\rangle$. Indeed, his construction gives an
honest embedding map even for a countable set of variables
$X=\\{x_{1},x_{2},\ldots\\}$.

The first point is that the free noncommutative rings $\mathbb{F}\langle
X\rangle$ and $\mathbb{F}\langle x,y\rangle$ have both enough
structure121212Technically, both these rings are semifir [13, 15]. that
guarantees the following.

######  Lemma 6.1.

If a homomorphic embedding $\phi:\mathbb{F}\langle
X\rangle\to\mathbb{F}\langle x,y\rangle$ can be extended to a homomorphic
embedding
$\phi:\mathbb{F}{\lparenless}X{\rparengtr}\to\mathbb{F}{\lparenless}x,y{\rparengtr}$
then, in fact, $\phi$ is an honest embedding.

The reason for this is basically, that if an $n\times n$ $M$ over
$\mathbb{F}\langle X\rangle$ is a full matrix then it is invertible with an
inverse $M^{-1}$ over the skew field $\mathbb{F}{\lparenless}X{\rparengtr}$.
Thus, it suffices to find a homomorphic embeddings that extends to one between
the corresponding free skew fields.

Cohn solved this problem of finding such an embedding [15, Theorem 4.7.3] by
an ingenious construction using skew polynomial rings.

#### Skew Polynomial Rings

We recall the definition of skew polynomial rings and state some basic
properties (details can be found in Cohn’s text [14, Chapter 1.1]). Let $R$ be
an _integral domain_ 131313That means $R$ is a, possibly noncommutative, ring
with unity $1$ and without zero divisors. and let $\sigma:R\to R$ be a ring
_endomorphism_. Let

$A=\\{x^{n}a_{n}+x^{n-1}a_{n-1}+\ldots+a_{0}\mid\textrm{ each }a_{i}\in R\\}$

be the set of all formal univariate polynomials in the indeterminate $x$ which
is assumed to not commute with elements of $R$. Addition of elements in $A$
can be defined component-wise as usual. The multiplication operation is
defined with a "twist" to it, using the ring endomorphism $\sigma$, which we
briefly explain below.

A _$\sigma$ -derivation_ on $R$ is defined as an additive homomorphism
$\delta:R\to R$ such that

$\delta(ab)=\sigma(a)\delta(b)+\delta(a)b\textrm{ for all }a,b\in R.$

We define

$ax=x\sigma(a)+\delta(a),\textrm{ for all }a\in R,$

which extends to ring multiplication in $A$. Under these operations the set
$A$ is the _skew polynomial ring_ denoted $R[x;\sigma,\delta]$. If the
$R$-endomorphism $\sigma$ is the identity map $1$ and $\delta=0$ in this
definition, then we obtain the univariate polynomial ring $R[x]$ in which the
variable $x$ commutes with elements of $R$.

Following Cohn’s construction in his embedding theorem, we consider skew
polynomial rings of the form $R[x;1,\delta]$, where the endomorphism
$\sigma=1$. We refer to $\delta$ as a derivation and we have:

$\displaystyle\delta(ab)$ $\displaystyle=$ $\displaystyle
a\delta(b)+\delta(a)b\textrm{ for all }a,b\in R,\textrm{ and}$ (2)
$\displaystyle ax$ $\displaystyle=$ $\displaystyle xa+\delta(a),\textrm{ for
all }a\in R.$ (3)

#### Cohn’s Construction

We now describe the construction, adding some details to the rather terse
description in [15].

We set the integral domain $R$ to be $\mathbb{F}\langle X\rangle$ for
$X=\\{x_{1},x_{2},\ldots,\\}$. Consider the map $\delta:X\mapsto X$ defined as

$\delta(x_{i})=x_{i+1}.$

The map $\delta$ naturally extends to a unique derivation on
$\mathbb{F}\langle X\rangle$ as follows. For scalars $a\in\mathbb{F}$, we
define $\delta(ax_{i})=a\delta(x_{i})$, by linearity. Next, define $\delta$ on
all monomials in $X^{*}$. Let
$\delta(x_{i}x_{j})=\delta(x_{i})x_{j}+x_{i}\delta(x_{j})$. In general, for a
degree-$\ell$ monomial $m=x_{i_{1}}x_{i_{2}}\ldots x_{i_{\ell}}$ we define

$\delta(m)=\delta(x_{i_{1}}x_{i_{2}}\ldots
x_{i_{k}})x_{i_{k+1}}x_{i_{k+2}}\ldots x_{i_{\ell}}+x_{i_{1}}x_{i_{2}}\ldots
x_{i_{k}}\delta(x_{i_{k+1}}x_{i_{k+2}}\ldots x_{i_{\ell}}).$

It is easy to verify that the above definition of $\delta(m)$ is independent
of $k\in[\ell]$. We now extend this definition to the entire ring
$\mathbb{F}\langle X\rangle$ by linearity. By an easy induction on the degree
of polynomials in $\mathbb{F}\langle X\rangle$ we obtain the following.

######  Lemma 6.2.

The mapping $\delta$ defined above is a derivation on the ring
$R=\mathbb{F}\langle X\rangle$.

Let $H=R[x;1,\delta]$ be the skew polynomial ring defined by the derivation
$\delta$ described above. By definition, $\delta$ satisfies Equations 2 and 3.
Therefore, putting $a=x_{i}$ in Equation 3, for each $i\geq 1$ we have

$x_{i+1}=x_{i}x-xx_{i}=[x_{i},x],$

This actually gives a homomorphic embedding from the ring $\mathbb{F}\langle
X\rangle$ to the bivariate ring $\mathbb{F}\langle x,y\rangle$. To see this,
we define a map $\beta:X\mapsto\mathbb{F}\langle x,y\rangle$ as follows:

  * •

Let $\beta(x_{1})=y$. For $i\geq 2$, let $\beta(x_{i})=[\beta(x_{i-1}),x]$.

  * •

We can then naturally extend $\beta$ to a homomorphism from $\mathbb{F}\langle
X\rangle$ to $\mathbb{F}\langle x,y\rangle$, and it is easy to check that it
is injective.

Hence we have

######  Theorem 6.3.

[15, Theorem 4.5.3] $\beta$ is a homomorphic embedding from $\mathbb{F}\langle
X\rangle$ to $\mathbb{F}\langle x,y\rangle$.

Furthermore, by the definition of $\delta$, the elements of the skew
polynomial ring $R[x;1,\delta]$ are also polynomials in the ring
$\mathbb{F}\langle x,y\rangle$. Indeed, the map $\beta$ can be extended to an
isomorphism from the ring $R[x;1,\delta]$ to $\mathbb{F}\langle x,y\rangle$ as
follows: for $f=x^{n}a_{n}+x^{n-1}a_{n-1}+\ldots+a_{0}\in R[x;1,\delta]$
define
$\beta(f)=x^{n}\beta(a_{n})+x^{n-1}\beta(a_{n-1})+\ldots+x\beta(a_{1})+\beta(a_{0})$.

######  Theorem 6.4.

[15, Theorem 4.5.3] $\beta$ is a homomorphic embedding from $\mathbb{F}\langle
X\rangle$ to $\mathbb{F}\langle x,y\rangle$. Furthermore, $\beta$ is an
isomorphism from $R[x;1,\delta]$ to $\mathbb{F}\langle x,y\rangle$.

Using properties of the field of fractions of the skew polynomial ring
$R[x;1,\delta]$ Cohn shows that $\beta$ extends to an embedding between the
skew fields.

######  Theorem 6.5 (Cohn’s embedding theorem).

The embedding map $\beta:\mathbb{F}\langle X\rangle\to\mathbb{F}\langle
x,y\rangle$ extends to an embedding
$\beta:\mathbb{F}{\lparenless}X{\rparengtr}\to\mathbb{F}{\lparenless}x,y{\rparengtr}$
which implies that $\beta$ is an honest embedding.

#### Proof of Lemma 4.2

###### Proof.

First we describe a recursive construction to compute a formula
$\Phi^{\prime}$ equivalent to $\Phi$ and inductively prove that the depth of
$\Phi^{\prime}$ is $c\log_{2}s$ for an absolute constant $c$. Then we analyze
the parallel time complexity of the construction and prove that it can be
implemented in $\mathsf{NC}$.

Let $A_{\Phi}$ be $s\times s$ matrix such that for gates $u,v\in\Phi$,
$(u,v)^{th}$ entry of $A_{\Phi}$ is $1$ if gate $v$ is a descendent of gate
$u$. Using the well-known pointer doubling strategy (see e.g. [29], [25]) we
can compute matrix $A_{\Phi}$ in $\mathsf{NC}$. So by adding elements in each
row of $A_{\Phi}$, we can compute $wt(u)$ (that is the number of descendants
of gate $u\in\Phi$) in $\mathsf{NC}$. Let $v$ be a gate in $\Phi$ such that
$\frac{s}{3}\leq wt(v)<\frac{2s}{3}$. Such a gate always exists by a standard
argument. Since we can compute the number of descendants of a gate in
$\mathsf{NC}$, we can also find such a gate $v$ in $\mathsf{NC}$, by simply
having a processor associated to each gate to check the above inequalities.
Now we are ready to describe recursive construction of $\Phi^{\prime}$.

  1. 1.

In $\mathsf{NC}$ find a gate $v$ in $\Phi$ such that $\frac{s}{3}\leq
wt(v)<\frac{2s}{3}$.

  2. 2.

Let $r=v_{0}$ be the root of $\Phi$ and $v_{1},v_{2},\ldots,v_{\ell-1}$ be
gates on $r$ to $v$ path in $\Phi$. Let $v=v_{\ell}$. For $1\leq i\leq\ell$,
let $u_{i}$ denote a sibling of $v_{i}$. Let $S_{1}$ be collection of all
indices $j$ such that $1\leq j\leq\ell$, $v_{j}$ is a product gate and is a
right child of its parent. Similarly let $S_{2}$ be collection of all indices
$j$ such that $1\leq j\leq\ell$, $v_{j}$ is a product gate and is a left child
of its parent. Define formula $\Psi_{1}=\prod_{j\in S_{1}}\Phi_{u_{j}}$. The
product is computed using sequence of multiplication gates, starting with
$\Phi_{u_{j}}$ for the first $u_{j}$ (one with smallest index $j\in S_{1}$)
each multiplication gate multiplies the product so far from right by
$\Phi_{u_{j}}$ for the next gate $u_{j}$, $j\in S_{1}$, along the root to $v$
path. Similarly define formula $\Psi_{2}=\prod_{j\in S_{2}}\Phi_{u_{j}}$. Let
$\Psi_{3}$ be a formula obtained from $\Phi$ by replacing subformula
$\Phi_{v}$ by zero.

  3. 3.

Recursively in parallel compute log-depth formulas
$\Psi_{1}^{\prime},\Psi_{2}^{\prime},\Psi_{3}^{\prime},\Phi_{v}^{\prime}$
equivalent to $\Psi_{1}$, $\Psi_{2}$, $\Psi_{3}$ and $\Phi_{v}$ respectively.

  4. 4.

Define formula $\Phi^{\prime}$ as
$(\Psi_{1}^{\prime}\cdot\Phi_{v}^{\prime})\cdot\Psi_{2}^{\prime}+\Psi_{3}$.

From the definitions of $\Psi_{1},\Psi_{2}$ and $\Psi_{3}$ it is clear that
the polynomial computed by $\Phi$ equals
$(\hat{\Psi_{1}}\cdot\hat{\Phi_{v}})\cdot\hat{\Psi_{2}}+\hat{\Psi_{3}}$, where
$\hat{\Psi_{1}},\hat{\Psi_{1}},\hat{\Psi_{1}},\hat{\Phi_{v}}$ are the
polynomials computed by $\Psi_{1}$, $\Psi_{2}$, $\Psi_{3}$ and $\Phi_{v}$
respectively. Hence, $\Phi^{\prime}$, defined in Step 4, is equivalent to
$\Phi$.

Let $d(s)$ denote the upper bound on the depth of the formula output by the
above procedure if size $s$ formula is given to it as input. We use induction
on the size $s$ to prove that $d(s)\leq c\log_{2}s$. As $\Psi_{1},\Psi_{2}$
are disjoint subformulas of $\Phi_{v\leftarrow z}$, clearly we have
$|\Psi_{1}|+|\Psi_{2}|\leq|\Phi_{v\leftarrow z}|$. Since
$|\Phi_{v}|\geq\frac{s}{3}$, it implies
$|\Psi_{1}|,|\Psi_{2}|\leq|\Phi_{v\leftarrow z}|\leq\frac{2s}{3}$. From the
definition of $\Psi_{3}$, it is clear that $|\Psi_{3}|\leq|\Phi_{v\leftarrow
z}|\leq\frac{2s}{3}$. So the size of each formula $\Psi_{1}$, $\Psi_{2}$,
$\Psi_{3}$ and $\Phi_{v}$ is upper bounded by $\frac{2s}{3}$. Hence,
inductively, for each of the formulas
$\Psi_{1}^{\prime},\Psi_{2}^{\prime},\Psi_{3}^{\prime},\Phi_{v}^{\prime}$ the
depth is upper bounded by $c\log_{2}\frac{2s}{3}$. As $\Phi^{\prime}$ is
obtained from
$\Psi_{1}^{\prime},\Psi_{2}^{\prime},\Psi_{3}^{\prime},\Phi_{v}^{\prime}$
using two multiplications and an addition as in Step 4, it follows that the
depth of $\Phi^{\prime}=d(s)\leq c\log_{2}\frac{2s}{3}+3$. Choosing
$c\geq\frac{3}{(\log_{2}3-1)}$ we get $d(s)\leq c\log_{2}\frac{2s}{3}+3\leq
c\log_{2}s$. This completes the induction, proving that the depth of
$\Phi^{\prime}$ is at most $c\log_{2}s$.

Let $t(s)$ denotes parallel time complexity of the above procedure. Since
Steps 1, 2, 4 can be implemented in $\mathsf{NC}$ they together take $(\log
s)^{k}$ parallel time for an absolute constant $k$. As all the recursive calls
in Step 3 are processed in parallel, we have the recurrence $t(s)\leq
t(2s/3)+(\log s)^{k}$. Hence, $t(s)\leq(\log s)^{(k+1)}$. This shows that the
above procedure can be implemented in $\mathsf{NC}$, completing the proof of
the theorem. $\Box$

#### Proof of Theorem 4.4

###### Proof.

By Lemma 4.2 we have an $\mathsf{NC}$ algorithm to convert every entry of $A$
to a log-depth formula. We will first describe parallel algorithm for Higman
linearization of single polynomial $f$ given by noncommutative log-depth
formula $\Phi$. Higman linearization of a polynomial matrix can be handled
similarly.

######  Claim 6.6.

Given a noncommutative formula $\Phi$ of size $s$ and depth $O(\log s)$
computing a polynomial $f$ in $\mathbb{F}\langle X\rangle$. We can compute
Higman linearization of $f$ in deterministic $\mathsf{NC}$. More precisely, we
can compute a linear matrix $L_{\Phi}\in\mathbb{F}\langle
X\rangle^{(s+1)\times(s+1)}$, invertible upper and lower triangular matrices
$P$,$Q$ $\in\mathbb{F}\langle X\rangle^{(s+1)\times(s+1)}$ with all diagonal
entries $1$ such that $P(f\oplus I_{s})Q=L_{\Phi}$. All the entries of $P,Q$
are computable by algebraic branching programs of size
$\operatorname{poly}(s)$. Moreover, $f\not\equiv 0$ iff $L_{\Phi}$ is a full
noncommutative rank matrix.

###### Proof.

The basic idea is to compute the Higman linearization recursively in parallel.
Since the formula size is known and for every $+$ or $\times$ gate in $\Phi$
we need to add a new row and column for the Higman process, we know exactly
the dimension of the final matrix $L$ and the precise location for placement
of the submatrices inside $L$, corresponding to each subformula of $\Phi$. To
obtain Higman linearization of $\Phi$ we recursively in parallel compute
Higman linearization of the subformulas rooted at the left and the right child
of the root. Based on whether at root of $\Phi$ we have a $+$-gate or a
$\times$-gate, we appropriately compose Higman linearizations of the sub-
formulas rooted at the left and the right child of the root. As depth of
$\Phi$ is logarithmic, there are only $O(\log s)$ nested recursive calls, this
ensures that the overall process can be implemented in $\mathsf{NC}$.

We now give the details of the inductive proof.

Let $r$ be the root of $\Phi$, and $g$ and $h$ be the polynomials computed at
the left and right child of $r$, respectively. If $r$ is a $\times$-gate, the
matrix obtained after the first step of the Higman Linearization is

$\left(\begin{array}[]{cc}1&g\\\
0&1\end{array}\right)\left(\begin{array}[]{cc}g\cdot h&0\\\
0&1\end{array}\right)\left(\begin{array}[]{cc}1&0\\\
-h&1\end{array}\right)~{}=~{}\left(\begin{array}[]{cc}0&g\\\
-h&1\end{array}\right)$

If $r$ is a $+$-gate, we do not explicitly deal with it, as we are eventually
interested only in _linearizing_ the matrix. Nevertheless, for the $+$-gate
case we carry out following step.141414This facilitates the presentation and
calculation of parallel placement of linear submatrices corresponding to the
recursive calls inside the final Higman linearized matrix for $f$.

$\left(\begin{array}[]{cc}1&g\\\
0&1\end{array}\right)\left(\begin{array}[]{cc}g+h&0\\\
0&1\end{array}\right)\left(\begin{array}[]{cc}1&0\\\
-1&1\end{array}\right)~{}=~{}\left(\begin{array}[]{cc}h&g\\\
-1&1\end{array}\right)$

It reduces computing Higman linearization of $g+h$ to computing it for $g$ and
for $h$.

We can in $\mathsf{NC}$ compute the size of sub-tree rooted at any gate of
$\Phi$. Let $s_{1}$ and $s_{2}$ be sizes of the left and right sub-trees of
the root $r$. Let $w=-h$ if $r$ is a $\times$-gate and is equal to $h$ when
$r$ is a $+$-gate. Suppose we compute Higman linearization of $g$ and $w$
recursively in parallel. More precisely, we obtain invertible upper and lower
triangular matrices $P_{g},Q_{g}\in\mathbb{F}\langle
X\rangle^{(s_{1}+1)\times(s_{1}+1)}$ respectively, with all diagonal entries
$1$ and linear matrix $L_{g}\in\mathbb{F}\langle
X\rangle^{(s_{1}+1)\times(s_{1}+1)}$ such that $P_{g}~{}(g\oplus
I_{s_{1}})~{}Q_{g}=L_{g}$. The entries of $P_{g},Q_{g}$ are given by ABPs of
size $\operatorname{poly}(s_{1})$. Similarly, we obtain invertible upper and
lower triangular matrices $P_{w},Q_{w}\in\mathbb{F}\langle
X\rangle^{(s_{2}+1)\times(s_{2}+1)}$ respectively, with all diagonal entries
$1$ and linear matrix $L_{w}\in\mathbb{F}\langle
X\rangle^{(s_{2}+1)\times(s_{2}+1)}$ such that $P_{w}~{}(w\oplus
I_{s_{2}})~{}Q_{w}=L_{w}$. The entries of $P_{w},Q_{w}$ are given by ABPs of
size $\operatorname{poly}(s_{2})$. Let $R_{g}\in\mathbb{F}\langle
X\rangle^{1\times s_{1}}$ be a row matrix obtained by dropping $(1,1)^{th}$
entry from the first row of $P_{g}$. Similarly, column matrix $C_{g}$ is
obtained by dropping$(1,1)^{th}$ entry from the first column of $Q_{g}$.
Analogously, define row and column matrices $R_{w}$ and $C_{w}$. Let
$P_{g}^{\prime},Q_{g}^{\prime}$ denote bottom right $s_{1}\times s_{1}$ blocks
of matrices $P_{g}$ and $Q_{g}$ respectively. Similarly, let
$P_{w}^{\prime},Q_{w}^{\prime}$ denote bottom right $s_{2}\times s_{2}$ blocks
of matrices $P_{w}$ and $Q_{w}$ respectively. So we have,

$L_{g}=\left(\begin{array}[]{cc}1&R_{g}\\\
0&P_{g}^{\prime}\end{array}\right)\left(\begin{array}[]{cc}g&0\\\
0&I_{s_{1}}\end{array}\right)\left(\begin{array}[]{cc}1&0\\\
C_{g}&Q_{g}^{\prime}\end{array}\right)=\left(\begin{array}[]{cc}g+R_{g}C_{g}&R_{g}Q_{g}^{\prime}\\\
P_{g}^{\prime}C_{g}&P_{g}^{\prime}Q_{g}^{\prime}\end{array}\right)$

Similarly, we have

$L_{w}=\left(\begin{array}[]{cc}1&R_{w}\\\
0&P_{w}^{\prime}\end{array}\right)\left(\begin{array}[]{cc}w&0\\\
0&I_{s_{2}}\end{array}\right)\left(\begin{array}[]{cc}1&0\\\
C_{w}&Q_{w}^{\prime}\end{array}\right)=\left(\begin{array}[]{cc}w+R_{w}C_{w}&R_{w}Q_{w}^{\prime}\\\
P_{w}^{\prime}C_{w}&P_{w}^{\prime}Q_{w}^{\prime}\end{array}\right)$

Now we are ready to define matrices $P,Q,L$ using matrices
$P_{g},Q_{g},P_{w},Q_{w}$ so that $P(f\oplus I_{s})Q=L$.

  * •

$r$ is $\times$-gate

After the first step of Higman linearization on $f$ the matrix obtained is
$\left(\begin{array}[]{cc}0&g\\\ w&1\end{array}\right)$.

When we obtain Higman linearization for $g$, $w$ recursively, these
polynomials sit at $(1,1)^{th}$ entry of $g\oplus I_{s_{1}}$ and $w\oplus
I_{s_{2}}$ respectively. Whereas in the matrix above, the polynomials $g,w$
sit at $(1,2)^{th},(2,1)^{th}$ entries respectively. Now we define block
matrices $\tilde{P_{g}},\tilde{P_{w}}$ and $\tilde{Q_{g}},\tilde{Q_{w}}$ for
performing row and column operations, respectively, on the appropriate rows
and columns of the matrix, taking into account the location of $g$ and $h$.
Whenever we are carrying out linearization for $g$ it keeps the block
corresponding to linearization of $h$ intact and vice-versa. Define
$\tilde{P_{g}},\tilde{P_{w}}$ as

$\tilde{P_{g}}=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
0&1\end{array}&\begin{array}[]{cc}R_{g}&0\\\ 0&0\end{array}\\\ \hline\cr
0&\begin{array}[]{cc}P_{g}^{\prime}&0\\\
0&I_{s_{2}}\end{array}\end{array}\right),\tilde{P_{w}}=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
0&1\end{array}&\begin{array}[]{cc}0&0\\\ 0&R_{w}\end{array}\\\ \hline\cr
0&\begin{array}[]{cc}I_{s_{1}}&0\\\
0&P_{w}^{\prime}\end{array}\end{array}\right)$

Similarly, define $\tilde{Q_{g}},\tilde{Q_{w}}$ as

$\tilde{Q_{g}}=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
0&1\end{array}&0\\\ \hline\cr\begin{array}[]{cc}0&C_{g}\\\
0&0\end{array}&\begin{array}[]{cc}Q_{g}^{\prime}&0\\\
0&I_{s_{2}}\end{array}\end{array}\right),\tilde{Q_{w}}=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
0&1\end{array}&0\\\ \hline\cr\begin{array}[]{cc}0&0\\\
C_{w}&0\end{array}&\begin{array}[]{cc}I_{s_{1}}&0\\\
0&Q_{w}^{\prime}\end{array}\end{array}\right)$

$\tilde{P_{g}},\tilde{Q_{g}}$ carry out linearization of $g$,
$\tilde{P_{w}},\tilde{Q_{w}}$ carry out linearization of $w$. Define
$P_{1}=\left(\begin{array}[]{cc}1&g\\\ 0&1\end{array}\right)\oplus
I_{s_{1}+s_{2}}$ and $Q_{1}=\left(\begin{array}[]{cc}1&0\\\
w&1\end{array}\right)\oplus I_{s_{1}+s_{2}}$, which would carry out the first
step of linearization.

Finally, define $P=\tilde{P_{w}}\tilde{P_{g}}P_{1}$. We can see that
$P=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&g\\\
0&1\end{array}&\begin{array}[]{cc}R_{g}&0\\\ 0&R_{w}\end{array}\\\ \hline\cr
0&\begin{array}[]{cc}P_{g}^{\prime}&0\\\
0&P_{w}^{\prime}\end{array}\end{array}\right)$. Similarly, define
$Q=\tilde{Q_{w}}\tilde{Q_{g}}Q_{1}=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
w&1\end{array}&0\\\ \hline\cr\begin{array}[]{cc}0&C_{g}\\\
C_{w}&0\end{array}&\begin{array}[]{cc}Q_{g}^{\prime}&0\\\
0&Q_{w}^{\prime}\end{array}\end{array}\right)$

As $P_{g}^{\prime}$ and $P_{w}^{\prime}$ are bottom right blocks of the upper
triangular matrices $P_{g}$ and $P_{w}$, it follows that $P_{g}^{\prime}$,
$P_{w}^{\prime}$, and hence also $P$ is invertible, and also upper triangular
with all diagonal entries $1$. Similarly, $Q$ is invertible and lower
triangular with all diagonal entries $1$. As $P,Q$ are realized as a matrix
product as defined above and entries of $P_{g},Q_{g}$ and $P_{w},Q_{w}$ are
given by ABPs of size $\operatorname{poly}(s_{1}),\operatorname{poly}(s_{2})$
respectively, we can construct ABPs of $\operatorname{poly}(s)$ size for
entries of $P$ and $Q$ in $\mathsf{NC}$.

Now, define $L_{\Phi}=P(f\oplus
I_{s})Q=\left(\begin{array}[]{c|c}\begin{array}[]{cc}0&g+R_{g}C_{g}\\\
w+R_{w}C_{w}&1\end{array}&\begin{array}[]{cc}R_{g}Q_{g}^{\prime}&0\\\
0&R_{w}Q_{w}^{\prime}\end{array}\\\
\hline\cr\begin{array}[]{cc}0&P_{g}^{\prime}C_{g}\\\
P_{w}^{\prime}C_{w}&0\end{array}&\begin{array}[]{cc}P_{g}^{\prime}Q_{g}^{\prime}&0\\\
0&P_{w}^{\prime}Q_{w}^{\prime}\end{array}\end{array}\right)$

Clearly, $L_{\Phi}$ is linear as $L_{g}$ and $L_{w}$ are linear. Note that we
do not need to compute $L_{\Phi}$ as a product $P(f\oplus I_{s})Q$. If we
explicitly know linear entries of $L_{g},L_{w}$ (which we do know recursively)
we can explicitly compute linear entries of $L_{\Phi}$.

  * •

$r$ is $+$-gate

This case is handled similarly. In case of $+$-gate, the matrix obtained after
first step is $\left(\begin{array}[]{cc}w&g\\\ -1&1\end{array}\right)$. So to
ensure the Higman linearized matrices of $g$ and $w$ are correctly placed
inside the Higman linearized matrix for $f$ we define $P,Q$ as

$P=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&g\\\
0&1\end{array}&\begin{array}[]{cc}R_{g}&R_{w}\\\ 0&0\end{array}\\\ \hline\cr
0&\begin{array}[]{cc}P_{g}^{\prime}&0\\\
0&P_{w}^{\prime}\end{array}\end{array}\right),Q=\left(\begin{array}[]{c|c}\begin{array}[]{cc}1&0\\\
-1&1\end{array}&0\\\ \hline\cr\begin{array}[]{cc}0&C_{g}\\\
C_{w}&0\end{array}&\begin{array}[]{cc}Q_{g}^{\prime}&0\\\
0&Q_{w}^{\prime}\end{array}\end{array}\right)$

and define $L_{\Phi}$ as

$L_{\Phi}=P(f\oplus
I_{s})Q=\left(\begin{array}[]{c|c}\begin{array}[]{cc}w+R_{w}C_{w}&g+R_{g}C_{g}\\\
-1&1\end{array}&\begin{array}[]{cc}R_{g}Q_{g}^{\prime}&R_{w}Q_{w}^{\prime}\\\
0&0\end{array}\\\ \hline\cr\begin{array}[]{cc}0&P_{g}^{\prime}C_{g}\\\
P_{w}^{\prime}C_{w}&0\end{array}&\begin{array}[]{cc}P_{g}^{\prime}Q_{g}^{\prime}&0\\\
0&P_{w}^{\prime}Q_{w}^{\prime}\end{array}\end{array}\right)$

Clearly, any entry of $L_{\Phi}$ is a scalar or some entry of $L_{g}$ or
$L_{w}$, so $L_{\Phi}$ is linear. Again, entries of $L_{\Phi}$ can be computed
explicitly, given the matrices $L_{g}$ and $L_{w}$ explicitly. This completes
the Case 2.

As $P,Q$ are invertible, it implies $\operatorname{\rm{ncrk}}(f\oplus
I_{s})=\operatorname{\rm{ncrk}}(L)$, which implies $L$ is full iff
$f\not\equiv 0$. This proves the claim.

$\Box$

In the general case, we need to Higman linearize an $n\times n$ polynomial
matrix $A$. We will in parallel compute Higman linearization matrices for each
entry of $A$ using the $\mathsf{NC}$ algorithm described in the above claim.
Let $M_{i,j}$ be $(s_{i,j}+1)\times(s_{i,j}+1)$ linear matrix corresponding to
$(i,j)^{th}$ entry for $1\leq i,j\leq n$. That is
$M_{i,j}=P_{i,j}(A_{i,j}\oplus I_{s_{i,j}})Q_{i,j}$ where $P_{i,j},Q_{i,j}$
are invertible upper and lower triangular matrices respectively. We have
polynomial sized ABPs for entries of $P_{i,j}$ and $Q_{i,j}$.

Let $M_{i,j}^{\prime}$ denote $s_{i,j}\times s_{i,j}$ bottom right block of
$M_{i,j}$. Let $R_{i,j}$ denote $1\times s_{i,j}$ row matrix obtained by
dropping first entry of first row of $M_{i,j}$. Similarly, let $C_{i,j}$ be
$s_{i,j}\times 1$ column matrix obtained by dropping first entry of the first
column of $M_{i,j}$. Then, the matrix $L$ is a $2\times 2$ block matrix such
that

  1. 1.

The top left block of $L$ is $n\times n$ and for $1\leq i,j\leq n$,
$(i,j)^{th}$ entry of the block is $(1,1)^{th}$ entry of $M_{i,j}$.

  2. 2.

The top right block of $L$ is the matrix

$\left(\begin{array}[]{cccc}R_{1,1}~{}R_{1,2}~{}\ldots
R_{1,n}&{}{}\hfil&{}{}\hfil&{}{}\hfil\\\ {}{}\hfil&R_{2,1}~{}R_{2,2}~{}\ldots
R_{2,n}&{}{}\hfil&{}{}\hfil\\\ {}{}\hfil&{}{}\hfil&\ddots&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&{}{}\hfil&R_{n,1}~{}R_{n,2}~{}\ldots
R_{n,n}\end{array}\right)$

  3. 3.

The bottom left block of $L$ is the matrix $[B_{1}B_{2}\ldots B_{n}]^{T}$
where for $1\leq i\leq n$, $B_{i}$ is the matrix

$\left(\begin{array}[]{cccc}C_{i,1}&{}{}\hfil&{}{}\hfil&{}{}\hfil\\\
{}{}\hfil&C_{i,2}&{}{}\hfil&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&\ddots&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&{}{}\hfil&C_{i,n}\end{array}\right)$

  4. 4.

The bottom right block of $L$ is a matrix
$\left(\begin{array}[]{cccc}D_{1}&{}{}\hfil&{}{}\hfil&{}{}\hfil\\\
{}{}\hfil&D_{2}&{}{}\hfil&{}{}\hfil\\\ {}{}\hfil&{}{}\hfil&\ddots&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&{}{}\hfil&D_{n}\end{array}\right)$ where $D_{i}$ is a
matrix
$\left(\begin{array}[]{cccc}M_{i,1}^{\prime}&{}{}\hfil&{}{}\hfil&{}{}\hfil\\\
{}{}\hfil&M_{i,2}^{\prime}&{}{}\hfil&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&\ddots&{}{}\hfil\\\
{}{}\hfil&{}{}\hfil&{}{}\hfil&M_{i,n}^{\prime}\end{array}\right)$

All unspecified entries in the above matrices are zero. As done in the proof
of Claim 6.6, we can easily define invertible upper and lower triangular
matrices $P$ and $Q$ such that $P(A\oplus I_{k})Q=L$. Also we can obtain ABPs
computing entries of $P,Q$ from ABPs for the entries of the matrices
$P_{i,j},Q_{i,j}$, $1\leq i,j\leq n$. Since $P,Q$ are invertible, it implies
that $\operatorname{\rm{ncrk}}(L)$ is equal to
$\operatorname{\rm{ncrk}}(A\oplus I_{k})$ which is equal to
$\operatorname{\rm{ncrk}}(A)+k$. Clearly, the dimension of the bottom right
block of $L$ is $O(n^{2}\cdot s)$ which implies similar bound on $k$. This
completes the proof of the theorem. $\Box$

#### Proof of Lemma 5.3

###### Proof.

We give a recursive construction for both the parts and prove the correctness
by induction on $s$, the size of the formula $\Phi$.

Depth-reduce($\Phi$)
Input: A correct formula $\Phi$ of size $s$ computing a rational function in
$\mathbb{F}{\lparenless}X{\rparengtr}$.
Output: A correct formula $\Phi^{\prime}$ of depth at most $c\log_{2}s$ such
that $\Phi\equiv\Phi^{\prime}$.

  1. 1.

Find a gate $v\in\Phi$ such that $\frac{s}{3}<wt(v)\leq\frac{2s}{3}$.

  2. 2.

In Parallel construct formulas $\Psi$, $\Delta$ such that $\Psi=\text{Depth-
Reduce}(\Phi_{v})$ and $\Delta=\text{Normal-Form}(\Phi_{v\leftarrow z},z)$.

  3. 3.

Obtain formula $\Phi^{\prime}$ from $\Delta$ by replacing $z$ in $\Delta$ by
$\Psi$.

  4. 4.

Output $\Phi^{\prime}$.

Normal-Form($\Phi$, $z$)
Input: A correct formula $\Phi$ of size $s$ computing a rational function in
$\mathbb{F}{\lparenless}X{\rparengtr}$ and a variable $z\in\Phi$ which appears
at most once in $\Phi$
Output: A correct formula $\Phi^{\prime}$ which is of the form

$\Phi^{\prime}=(Az+B)(Cz+D)^{-1}$

where $A,B,C$ and $D$ are correct rational formulas which do not depend on $z$
with depth at most $c\log_{2}s+b$. Moreover, the rational function
$\hat{C}\hat{\Psi}+\hat{D}\neq 0$ for any formula $\Psi$ such that
$\Phi_{z\leftarrow\Psi}$ is correct.

Let $v_{1},v_{2},\ldots,v_{\ell}=z$ be gates on the path from root $r$ of
$\Phi$ to the leaf gate $z$, such that $v_{j}$ is not an inverse gate. So
parent of each $v_{j}$ has two children, and let $u_{i}$ denote the sibling of
$v_{i}$. Use pointer doubling based parallel algorithm (as mentioned in the
proof of Lemma 4.2) to compute $wt(u_{i})$ and $wt(v_{i})$ for all
$i\in[\ell]$. We call gate $v_{i}$ for $i\in[\ell]$ as a _balanced_ gate if
$wt(\Phi_{v_{i}}),wt(\Phi_{v_{i}\leftarrow z^{\prime}})\leq\frac{5s}{6}$. Now
we consider two cases.

  1. 1.

There exist a balanced gate $v_{i}$:

    1. (a)

Let $v=v_{i}$. In parallel compute formulas $\Psi_{1},\Psi_{2}$ such that

$\displaystyle\Psi_{1}$ $\displaystyle=$
$\displaystyle(A_{1}z^{\prime}+B_{1})(C_{1}z^{\prime}+D_{1})^{-1}=\text{Normal-
Form}(\Phi_{v\leftarrow z^{\prime}},z^{\prime})$ $\displaystyle\Psi_{2}$
$\displaystyle=$ $\displaystyle(A_{2}z+B_{2})(C_{2}z+D_{2})^{-1}=\text{Normal-
Form}(\Phi_{v},z)$

    2. (b)

Define formulas $A,B,C,D$ as $A_{1}\cdot A_{2}+B_{1}\cdot C_{2}$, $A_{1}\cdot
B_{2}+B_{1}\cdot D_{2}$, $C_{1}\cdot A_{2}+D_{1}\cdot C_{2}$ and $C_{1}\cdot
B_{2}+D_{1}\cdot D_{2}$ respectively.

    3. (c)

Let $\Phi^{\prime}=(A\cdot z+B)\cdot(C\cdot z+D)^{-1}$

    4. (d)

Output $\Phi^{\prime}$ and halt

  2. 2.

There does not exist a balanced gate:
In this case, we can prove that there is a unique $i\in[\ell]$ such that
$wt(u_{i})>\frac{s}{6}$.

    1. (a)

Let $v$ be parent of the gate $v_{i}$.

    2. (b)

In Parallel find formulae $\Psi_{1},\Psi_{2},\Psi_{3},\Psi_{4}$ such that

$\displaystyle\Psi_{1}$ $\displaystyle=$
$\displaystyle(A_{1}z^{\prime}+B_{1})(C_{1}z^{\prime}+D_{1})^{-1}=\text{Normal-
Form}(\Phi_{v\leftarrow z^{\prime}},z^{\prime})$ $\displaystyle\Psi_{2}$
$\displaystyle=$ $\displaystyle(A_{2}z+B_{2})(C_{2}z+D_{2})^{-1}=\text{Normal-
Form}(\Phi_{v_{i}},z)$ $\displaystyle\Psi_{3}$ $\displaystyle=$
$\displaystyle\text{Depth-Reduce}(\Phi_{u_{i}})$ $\displaystyle\Psi_{4}$
$\displaystyle=$ $\displaystyle(Az+B)(Cz+D)^{-1}=\text{Normal-
Form}(\Phi^{\prime\prime},z)$

where $\Phi^{\prime\prime}$ is obtained by replacing sub-tree rooted at
$u_{i}$ by $0$ in $\Phi$.

    3. (c)

Using the algorithm of Theorem 5.5 check if $\hat{\Psi_{3}}\equiv 0$ in
$\mathsf{NC}$ with oracle access to bivariate ncRANK. If $\hat{\Psi_{3}}\equiv
0$ then output $\Psi_{4}$ and halt.

    4. (d)

If $\hat{\Psi_{3}}\not\equiv 0$ then let $\Phi^{\prime}=(A\cdot
z+B)\cdot(C\cdot z+D)^{-1}$, where

$A=\begin{cases}A_{1}A_{2}+B_{1}C_{2}+A_{1}\hat{\Psi_{3}}C_{2}&\text{ if
$v_{i}$ is a $+$-gate}\\\ A_{1}\hat{\Psi_{3}}A_{2}+B_{1}C_{2}&\text{if $v_{i}$
is a $\times$-gate and is a right child of $v$}\\\
A_{1}A_{2}+B_{1}\hat{\Psi_{3}}^{-1}C_{2}&\text{if $v_{i}$ is a $\times$-gate
and is a left child of $v$}\end{cases}$
$B=\begin{cases}A_{1}B_{2}+B_{1}D_{2}+A_{1}\hat{\Psi_{3}}D_{2}&\text{ if
$v_{i}$ is a $+$-gate}\\\ A_{1}\hat{\Psi_{3}}B_{2}+B_{1}D_{2}&\text{if $v_{i}$
is a $\times$-gate and is a right child of $v$}\\\
A_{1}B_{2}+B_{1}\hat{\Psi_{3}}^{-1}D_{2}&\text{if $v_{i}$ is a $\times$-gate
and is a left child of $v$}\end{cases}$
$C=\begin{cases}C_{1}A_{2}+D_{1}C_{2}+C_{1}\hat{\Psi_{3}}C_{2}&\text{ if
$v_{i}$ is a $+$-gate}\\\ C_{1}\hat{\Psi_{3}}A_{2}+D_{1}C_{2}&\text{if $v_{i}$
is a $\times$-gate and is a right child of $v$}\\\
C_{1}A_{2}+D_{1}\hat{\Psi_{3}}^{-1}C_{2}&\text{if $v_{i}$ is a $\times$-gate
and is a left child of $v$}\end{cases}$
$D=\begin{cases}C_{1}B_{2}+D_{1}D_{2}+C_{1}\hat{\Psi_{3}}D_{2}&\text{ if
$v_{i}$ is a $+$-gate}\\\ C_{1}\hat{\Psi_{3}}B_{2}+D_{1}D_{2}&\text{if $v_{i}$
is a $\times$-gate and is a right child of $v$}\\\
C_{1}B_{2}+D_{1}\hat{\Psi_{3}}^{-1}D_{2}&\text{if $v_{i}$ is a $\times$-gate
and is a left child of $v$}\end{cases}$

    5. (e)

Output $\Phi^{\prime}$ and halt.

Case 2 above is not explicitly dealt with in [21] as their focus is on the
_existence_ of a log-depth formula equivalent to $\Phi$. In contrast to that,
in our case we want to _algorithmically construct_ log-depth formula
$\Phi^{\prime}$ equivalent to $\Phi$. This makes the details of Case 2 crucial
as the construction of $\Phi^{\prime}$ in Case 2 depends on whether
$\hat{\Phi_{u_{i}}}\equiv 0$ or not. To solve this RIT instance we need to
recursively compute log-depth formula $\Psi_{3}$ equivalent to $\Phi_{u_{i}}$
and then invoke algorithm of theorem 5.5 to carry out RIT test in NC with
oracle access to bivariate ncRANK, as in Step (c).

We first prove the correctness of both the algorithms described above using
induction on $s$, then we analyze the parallel complexity of both the
algorithms. We will choose appropriate constants $c,b$ during the proof.

#### Correctness of the algorithm Depth-Reduce

We know that there exists a gate $v\in\Phi$ such that
$\frac{s}{3}<wt(v)\leq\frac{2s}{3}$. As in proof of Lemma 4.2 we can find such
a gate $v$ as required by Step 1 of the Depth-Reduce algorithm. Clearly, the
formulas $\Phi_{v}$ and $\Phi_{v\leftarrow z}$ are of size at most $2s/3$.
Using inductive assumption, we can construct a correct formula $\Psi$ such
that depth of $\Psi$ is at most $c\log_{2}\frac{2s}{3}$ and
$\Psi\equiv\Phi_{v}$. Again using inductive assumption we can construct
correct formulas $A,B,C,D$ (which do not depend on $z$) of depth at most
$c\log_{2}\frac{2s}{3}+b$ such that the formula $\Delta=(A\cdot
z+B)\cdot(C\cdot z+D)^{-1}$ is equivalent to $\Phi_{v\leftarrow z}$. Since
$\Phi$ is equal to the formula obtained from $\Phi_{v\leftarrow z}$ by
replacing $z$ by $\Phi_{v}$ and $\Phi$ is correct so from inductive assumption
it follows that $\hat{C}\hat{\Phi_{v}}+\hat{D}\neq 0$.

As $\Psi\equiv\Phi_{v}$, $\Delta\equiv\Phi_{v\leftarrow z}$ and
$\hat{C}\hat{\Phi_{v}}+\hat{D}\neq 0$ from Lemma 5.2 it follows that
$\Phi^{\prime}$ is correct and $\Phi^{\prime}\equiv\Phi$. Since
$\Phi^{\prime}=(A\cdot\Psi+B)\cdot(C\cdot\Psi+D)^{-1}$ we get that depth of
$\Phi^{\prime}$ is at most $c\log_{2}\frac{2s}{3}+b+4$. By choosing constant
$c\geq\frac{b+4}{(\log_{2}3-1)}$, we get that the depth of $\Phi^{\prime}$ is
at most $c\log_{2}s$. Completing the inductive argument for the correctness
proof of the algorithm Depth-Reduce.

#### Correctness of the algorithm Normal-Form

In case (1) we know that there exists a balanced gate $v=v_{i}$. We have
$wt(\Phi_{v}),wt(\Phi_{v\leftarrow z^{\prime}})\leq\frac{5s}{6}$. So by
inductive assumption we know that the formulas $A_{j},B_{j},C_{j},D_{j}$ for
$j\in\\{1,2\\}$ are correct, and their depths are at most
$c\log_{2}\frac{5s}{6}+b$. Now using compositionality of the z-normal forms as
in Proposition 4.1 of [21] it follows that the formula $\Phi^{\prime}=(A\cdot
z+B)\cdot(C\cdot z+D)^{-1}$ is equivalent to $\Phi$ where $A,B,C,D$ are
$A_{1}\cdot A_{2}+B_{1}\cdot C_{2}$, $A_{1}\cdot B_{2}+B_{1}\cdot D_{2}$,
$C_{1}\cdot A_{2}+D_{1}\cdot C_{2}$ and $C_{1}\cdot B_{2}+D_{1}\cdot D_{2}$
respectively. Also, clearly the depth of $A,B,C,D$ is at most
$c\log_{2}\frac{5s}{6}+b+2$. By choosing
$c\geq\frac{2}{(\log_{2}6-\log_{2}5)}$ it follows that the depths of formulas
$A,B,C,D$ are at most $c\log_{2}s+b$. To complete the inductive proof we need
to prove that $\hat{C}\hat{\pi}+\hat{D}\neq 0$ for any formula $\pi$ such that
$\Phi_{z\leftarrow\pi}$ is correct. Let $\pi$ be such that
$\Phi_{z\leftarrow\pi}$ is correct. For simplicity lets denote formulas
$\Phi_{v}$ and $\Phi_{v\leftarrow z^{\prime}}$ by $\alpha$ and $\beta$
respectively. Since $\Phi_{z\leftarrow\pi}$ is correct, it implies
$\alpha_{z\leftarrow\pi}$ is correct as $\alpha$ is a subformula of $\Phi$. So
by inductive assumption $\hat{C_{2}}\hat{\pi}+\hat{D_{2}}\neq 0$. Since
$\Phi_{z\leftarrow\pi}$ is correct, $\beta$ being a subformula of $\Phi$ it
also implies $\beta_{z^{\prime}\leftarrow\gamma}$ is correct where
$\gamma=(A_{2}\cdot\pi+B_{2})\cdot(C_{2}\cdot\pi+D_{2})^{-1}$. By inductive
assumption we get

$\displaystyle\hat{C_{1}}\hat{\gamma}+D_{1}$ $\displaystyle\neq$
$\displaystyle 0~{}\text{which implies}$
$\displaystyle\hat{C_{1}}[(\hat{A_{2}}\cdot\hat{\pi}+\hat{B_{2}})\cdot(\hat{C_{2}}\cdot\hat{\pi}+\hat{D_{2}})^{-1}]+D_{1}$
$\displaystyle\neq$ $\displaystyle 0~{}\text{which implies}$
$\displaystyle\hat{C_{1}}(\hat{A_{2}}\cdot\hat{\pi}+\hat{B_{2}})+\hat{D_{1}}(\hat{C_{2}}\cdot\hat{\pi}+\hat{D_{2}})$
$\displaystyle\neq$ $\displaystyle
0~{}\text{as}~{}\hat{C_{2}}\hat{\pi}+\hat{D_{2}}\neq 0$
$\displaystyle\text{So}~{}(\hat{C_{1}}\hat{A_{2}}+\hat{D_{1}}\hat{C_{2}})\hat{\pi}+(\hat{C_{1}}\hat{B_{2}}+\hat{D_{1}}\hat{D_{2}})$
$\displaystyle\neq$ $\displaystyle 0~{}\text{which implies}$
$\displaystyle\hat{C}\hat{\pi}+\hat{D}$ $\displaystyle\neq$ $\displaystyle 0$

This completes the proof for case 1.

Next we argue that case 1 and case 2 together cover all the possibilities. To
see this, we will argue that if there does not exist a unique $u_{i}$ with
$wt(u_{i})\geq\frac{s}{6}$ then there must exist a balanced gate. There are
two possibilities: either for every gate $u_{i}$, $wt(u_{i})\leq\frac{s}{6}$
or there are two or more gates $u_{i}$’s with $wt(u_{i})>\frac{s}{6}$ If for
every $i\in[\ell]$, $wt(u_{i})\leq\frac{s}{6}$, we find smallest $j$ such that
$\sum_{i=1}^{j}wt(u_{i})>\frac{s}{6}$. Clearly
$\sum_{i=1}^{j}wt(u_{i})\leq\frac{2s}{6}$, which implies
$wt(\Phi_{v}),wt(\Phi_{v\leftarrow z^{\prime}})\leq\frac{5s}{6}$ for
$v=v_{i+1}$. So $v$ is balanced. If there are two or more $u_{i}$’s such that
$wt(u_{i})>\frac{s}{6}$ then $v$ be parent of gate $u_{i}$ such that $i$ is a
largest index with $wt(u_{i})>\frac{s}{6}$. Clearly $v$ is a balanced gate.
This proves that case 1, 2 together cover all possibilities.

Assume that there is a unique $i\in[\ell]$ such that $wt(u_{i})>\frac{s}{6}$.
We first apply Depth-Reduce on formula $\Phi_{u_{i}}$ and get a log-depth
formula $\Psi_{3}$ equivalent to $\Phi_{u_{i}}$, we carry out this depth
reduction to efficiently test if $\Phi_{u_{i}}\equiv 0$?. We will give details
on this later when we figure out the parallel time complexity of the
algorithm. Now when $\Phi_{u_{i}}\equiv\Psi_{3}\equiv 0$, clearly formula
$\Phi\equiv\Phi^{\prime\prime}$ where $\Phi^{\prime\prime}$ is a formula
obtained from $\Phi$ by replacing sub-formula rooted at $u_{i}$ by $0$. As
$wt(u_{i})>\frac{s}{6}$, we have $|\Phi^{\prime\prime}|\leq\frac{5s}{6}$. So
by inductive assumption, the correct sub-formulas $A,B,C,D$ of $\Psi_{4}$
obtained by recursive call $\text{Normal-Form}(\Phi^{\prime\prime},z)$ have
depth at most $c\log_{2}\frac{5s}{6}+b\leq c\log_{2}s+b$ and
$\Psi_{4}\equiv\Phi^{\prime\prime}\equiv\Phi$. So it follows,
$\Phi_{z\leftarrow\pi}\equiv\Phi^{\prime\prime}_{z\leftarrow\pi}$.
Consequently $\Phi_{z\leftarrow\pi}$ is correct iff
$\Phi^{\prime\prime}_{z\leftarrow\pi}$ is correct. So from inductive
hypothesis it follows that $\hat{C}\hat{\pi}+\hat{D}\neq 0$ for any formula
$\pi$ such that $\Phi_{z\leftarrow\pi}$ is correct. This proves the
correctness of Normal-form procedure when $\Phi_{u_{i}}\equiv 0$.

Now let $\Phi_{u_{i}}\not\equiv 0$. Let $v$ be the parent of $u_{i}$. Below we
discuss the case when $v$ is $\times$-gate and $u_{i}$ is a right child of
$v$.

We have $\Psi_{2}\equiv\Phi_{v_{i}}\equiv(A_{2}\cdot z+B_{2})\cdot(C_{2}\cdot
z+D_{2})^{-1}$. Let $h_{1}=A_{2}\cdot z+B_{2}$ and $h_{2}=C_{2}\cdot
z+D_{2})$. So $\Phi_{v_{i}}\equiv h_{1}\cdot h_{2}^{-1}$. Now as $v$ is
$\times$-gate and $v_{i},u_{i}$ are left and right children of $v$
respectively. So we get $\Phi_{v}\equiv h_{1}h_{2}^{-1}\Phi_{u_{i}}\equiv
h_{1}h_{2}^{-1}\Psi_{3}$. We have $\Psi_{1}\equiv\Phi_{v\leftarrow
z^{\prime}}=(A_{1}z^{\prime}+B_{1})(C_{1}z^{\prime}+D_{1})^{-1}$. So we get

$\displaystyle\Phi$ $\displaystyle\equiv$
$\displaystyle(~{}A_{1}\cdot(h_{1}h_{2}^{-1}\Psi_{3})+B_{1})\cdot(~{}C_{1}\cdot(h_{1}h_{2}^{-1}\Psi_{3})+D_{1})^{-1}$
$\displaystyle\equiv$ $\displaystyle(A_{1}\cdot
h_{1}+B_{1}\cdot\Psi_{3}^{-1}h_{2})\cdot
h_{2}^{-1}\Psi_{3}\cdot[~{}(C_{1}\cdot
h_{1}+D_{1}\cdot\Psi_{3}^{-1}h_{2})\cdot h_{2}^{-1}\Psi_{3}~{}]^{-1}$
$\displaystyle\equiv$ $\displaystyle(A_{1}\cdot
h_{1}+B_{1}\cdot\Psi_{3}^{-1}h_{2})\cdot
h_{2}^{-1}\Psi_{3}\cdot\Psi_{3}^{-1}h_{2}~{}\cdot(C_{1}\cdot
h_{1}+D_{1}\cdot\Psi_{3}^{-1}h_{2})^{-1}$ $\displaystyle\equiv$
$\displaystyle(A_{1}\cdot h_{1}+B_{1}\cdot\Psi_{3}^{-1}h_{2})\cdot(C_{1}\cdot
h_{1}+D_{1}\cdot\Psi_{3}^{-1}h_{2})^{-1}$

By substituting values of $h_{1},h_{2}$ and simplifying we get that
$\Phi\equiv(A\cdot z+B)\cdot(C\cdot z+D)^{-1}$ where $A,B,C,D$ are $A_{1}\cdot
A_{2}+B_{1}\cdot\Psi_{3}^{-1}\cdot C_{2}$, $A_{1}\cdot
B_{2}+B_{1}\cdot\Psi_{3}^{-1}\cdot D_{2}$, $C_{1}\cdot
A_{2}+D_{1}\cdot\Psi_{3}^{-1}\cdot C_{2}$ and $C_{1}\cdot
B_{2}+D_{1}\cdot\Psi_{3}^{-1}\cdot D_{2}$ respectively as defined in Step
2(d).

As $wt(u_{i})>\frac{s}{6}$, clearly $|\Phi_{v_{i}}|,|\Phi_{v\leftarrow
z^{\prime}}|\leq\frac{5s}{6}$. Since

$\displaystyle\Psi_{1}$ $\displaystyle=$
$\displaystyle(A_{1}z^{\prime}+B_{1})(C_{1}z^{\prime}+D_{1})^{-1}=\text{Normal-
Form}(\Phi_{v\leftarrow z^{\prime}},z^{\prime})$ $\displaystyle\Psi_{2}$
$\displaystyle=$ $\displaystyle(A_{2}z+B_{2})(C_{2}z+D_{2})^{-1}=\text{Normal-
Form}(\Phi_{v_{i}},z)$

So by inductive assumptions the sub-formulas $A_{1},B_{1},C_{1},D_{1}$ of
$\Psi_{1}$ and the sub-formulas $A_{2},B_{2},C_{2},D_{2}$ of $\Psi_{2}$ are
correct and have depths at most $c\log_{2}\frac{5s}{6}+b$. As
$\Psi_{3}=\text{Depth-Reduce}(\Phi_{u_{i}})$ and $|\Phi_{u_{i}}|<s$ by
inductive assumption we get that the depth of $\Psi_{3}$ is at most
$c\log_{2}s$. Clearly $c\log_{2}\frac{5s}{6}+b\leq c\log_{2}s$ for
$c\geq\frac{b}{\log_{2}6-\log_{2}5)}$. So from expressions for $A,B,C,D$ it
follows that the depth of $A,B,C,D$ is at most depth of $\Psi_{3}$ plus $4$.
Which implies that the depth of $A,B,C,D$ is at most $c\log_{2}s+4\leq
c\log_{2}s+b$ if the constant $b\geq 4$. This gives us the desired bound on
the depth of $A,B,C,D$. To summarize if we choose constant $b\geq 4$ and
choose constant $c$ such that it satisfies all the lower bounds required in
different steps of the above proof, we will get the desired bound on the depth
of $A,B,C,D$. We can show that $\hat{C}\hat{\pi}+\hat{D}\neq 0$ for any
formula $\pi$ such that $\Phi_{z\leftarrow\pi}$ is correct. The proof is
similar to one for Case (1), we additionally need to take into account
$\times$-gate at $v$ while composing z-Normal forms $\Psi_{1}$ and $\Psi_{2}$.
We skip the details.

When $v$ is a $v$ is a $\times$-gate and $u_{i}$ is a left child of $v$, the
composition of z-normal forms is easy as we do not need an oracle access for
RIT as in the case discussed above when $u_{i}$ is the right child. In the
commutative case we can by default assume that $u_{i}$ is the left child.
Precisely for this reason Brent’s construction [8] is independent of whether
$\Phi_{u_{i}}\equiv 0$ or not. We skip the details of cases when $v$ is a
$+$-gate or $v$ is $\times$-gate and $u_{i}$ is the left child which can be
handled similar to case (1). This proves the correctness of the procedure
Normal-Form.

Next we analyze the parallel time complexity of both the procedures. Let
$t_{1}(s),t_{2}(s)$ denote the parallel time complexities of the procedures
Depth-Reduce and Normal-Form respectively. The step (1) of the Depth reduce
procedure can be implemented in $\mathsf{NC}$ so it has parallel time
complexity $(\log_{2}s)^{k}$ for some absolute constant $k$. As both the
formulas $\Phi_{v}$ and $\Phi_{v\leftarrow z}$ have sizes at most $2s/3$, the
parallel time complexity of step (2) is at most
$\max(t_{1}(2s/3),t_{2}(2s/3))$. So we get the following recurrence for
$t_{1}(s)$.

$t_{1}(s)\leq(\log_{2}s)^{a}+\max\left(~{}t_{1}\left(\frac{2s}{3}\right)~{},~{}t_{2}\left(\frac{2s}{3}~{}\right)\right)$

where $a$ is an absolute constant. Now we obtain recurrence for $t_{2}(s)$. In
Case (1) of Normal-Form when there exist a balanced gate $v_{i}$, we can find
such a gate in $\mathsf{NC}$. Both the formulas $\Phi_{v}$ and
$\Phi_{v\leftarrow z^{\prime}}$ have the sizes at most $5s/6$ so step 1(a)
takes parallel time $\max(t_{1}(5s/6),t_{2}(5s/6))$. In case (2) the formulas
$\Phi_{v\leftarrow z^{\prime}}$, $\Phi_{v_{i}}$ and $\Phi^{\prime\prime}$ all
have sizes at most $5s/6$ and formula $\Phi_{u_{i}}$ has size at most $s-1$.
So collectively we get the following recurrence for $t_{2}(s)$

$\displaystyle t_{2}(s)$ $\displaystyle\leq$
$\displaystyle(\log_{2}s)^{b}+\max\left(~{}t_{1}\left(\frac{5s}{6}\right)~{},~{}t_{2}\left(\frac{5s}{6}~{}\right)~{},~{}t_{1}(s-1)\right)$
$\displaystyle\leq$
$\displaystyle(\log_{2}s)^{b}+\max\left(~{}t_{2}\left(\frac{5s}{6}~{}\right)~{},~{}t_{1}(s)\right)$

for an absolute constant $b$. The upper bound
$t_{1}(s),t_{2}(s)\leq(\log_{2}s)^{c}$ for sufficiently large constant $c$
follows from an easy induction. Hence both the procedures can be implemented
in deterministic $\mathsf{NC}$.

$\Box$