Bi-polynomial rank and determinantal complexity

Akihiro Yabe

Graduate School of Information Science and Technology

The University of Tokyo
akihiro [email protected]

March 31, 2015

arXiv:1504.00151v1 [cs.CC] 1 Apr 2015

Abstract
The permanent vs. determinant problem is one of the most important problems
in theoretical computer science, and is the main target of geometric complexity
theory proposed by Mulmuley and Sohoni. The current best lower bound for the
determinantal complexity of the d by d permanent polynomial is d2 /2, due to Mignon
and Ressayre in 2004. Inspired by their proof method, we introduce a natural rank
concept of polynomials, called the bi-polynomial rank. The bi-polynomial rank is re-
lated to width of an arithmetic branching program. We prove that the bi-polynomial
rank gives a lower bound of the determinantal complexity. As a consequence, the
above Mignon and Ressayre bound is improved to (d − 1)2 + 1 over the field of reals.
We show that the computation of the bi-polynomial rank is formulated as a rank
minimization problem. We propose a computational approach for giving a lower
bound of this rank minimization, via techniques of the concave minimization. This
also yields a new strategy to attack the permanent vs. determinant problem.

1 Introduction
The determinant det(A) and the permanent perm(A) of a square matrix A = (ai,j ) of
size d are defined by

X d
Y
det(A) := sign(σ) ai,σ(i) ,
σ∈Sd i=1
d
X Y
perm(A) := ai,σ(i) ,
σ∈Sd i=1

where Sd is the set of permutations on {1, 2, . . . , d}. Determinant is a representative

function which admits efficient computation only with arithmetic operations. On the
other hand, such an efficient computation for permanent is not known. Valiant [17]
proved that the computation of permanent of 0-1 matrices is #P-complete. Therefore,
in contrast to determinant, it is conjectured that permanent cannot be computed in
polynomial time.
The determinantal complexity is a measure for the difficulty of evaluation of polyno-
mials. Let K be a field, and let K[x] = K[x1 , x2 , . . . , xD ] denote the set of polynomials of
variables x1 , x2 , . . . , xD with coefficients in K. By an affine polynomial matrix, we mean
a matrix each of whose entries is an affine polynomial (a linear polynomial including a
constant term).

1
Definition 1.1 (see [10]). The determinantal complexity dc(p) of p ∈ K[x] is defined as
the minimum number n such that there exists an affine polynomial matrix Q ∈ (K[x])n×n
satisfying
p = det(Q).

It is known in [16, 19] that if a polynomial p can be evaluated with number m of

arithmetics, then the determinantal complexity dc(p) is O(mc log m ) for some constant c.
Permanent is regarded as a polynomial of matrix entries. Let permd denote the
permanent polynomial for D = d × d variables of matrix entries. If dc(permd ) = dω(log d)
over K, then permanent cannot be computed by polynomial number of arithmetics on
K. The following is one of the main conjectures in algebraic complexity theory (see [2]).

Conjecture 1.2. Over a field K of characteristic not equal to two, it holds that

dc(permd ) = dω(log d) .

This conjecture implies VPK 6= VNPK , an arithmetic counterpart of P vs. NP

conjecture, since permanent is in VNPK (in fact VNPK -complete) if the characteristic
of K is not equal to two [16].
The current best lower bound for dc(permd ), due to Mignon and Ressayre [10], is
quadratic.

Theorem 1.3 (Mignon and Ressayre [10]). Over a field K of characteristic zero, it
holds that
d2
dc(permd ) ≥ .
2
Improving this bound is one of the most prominent issues in the literature. Cai,
Chen and Li [3] proved that dc(permd ) ≥ (d − 2)(d − 3)/2 over any field K of charac-
teristic not equal to two. Mulmuley and Sohoni [11] proposed a magnificent program,
called geometric complexity theory (GCT), to obtain super-polynomial lower bounds by
utilizing deep techniques of algebraic geometry and representation theory (also, see [6,
Chapter 13]). In the context of GCT, Landsberg, Manivel and Ressayre [7] proved that
the same lower bound d2 /2 holds for the orbit closure version dc of the determinantal
complexity.

Our contribution. We introduce the bi-polynomial rank of a homogeneous polyno-

mial of even degree, and prove that the determinantal complexity is bounded below by
the bi-polynomial rank. Our technique may be viewed as a higher order generalization
of the Hessian rank comparison proof of the above d2 /2 bound (Theorem 1.3) by Mignon
and Ressayre. Let K[x](k) ⊆ K[x] denote the set of homogeneous polynomials of degree
k.

Definition 1.4. The bi-polynomial rank b-rank(p) of p ∈ K[x](2k) is defined as the

minimum number n such that there exist 2n polynomials f1 , f2 , . . . , fn , g1 , g2 , . . . , gn ∈
K[x](k) satisfying
Xn
p= fi gi .
i=1

For p ∈ K[x] and x0 ∈ K D , we define a polynomial px0 by px0 (x) := p(x + x0 ). We

(k)
denote by px0 the degree-k homogeneous part of px0 . The set of points z ∈ K D with
p(z) = 0 is denoted by Zeros(p). Our main result is the following.

2
Theorem 1.5. For a polynomial p ∈ K[x], k ∈ [1, D], and x0 ∈ Zeros(p), it holds that
1
dc(p) ≥ b-rank(p(2k)
x0 ) − 2(k − 1)D
k−1
.
22k−2

We will see in Section 2.2 that every generic polynomial p ∈ K[x](2k) has the bi-
polynomial rank at least k!D k /2(2k)!. This means that the bi-polynomial rank has a
potential to give Ω((d2 )k ) lower bound to dc(permd ) for every k. A direct implication
to the permanent vs. determinant problem is the following.

Corollary 1.6. Let k ≥ 1 be an arbitrary integer. If there exists a sequence of ma-

(2k)
trices Xd ∈ Zeros(permd ) for d = 1, 2, . . . such that b-rank(permd,Xd ) = Ω(d2k ), then
dc(permd ) = Ω(d2k ).

In the case k = 1, our approach sharpens the Hessian approach by Mignon and
Ressayre. We will see in Section 3.1 that Theorem 1.5 directly implies Theorem 1.3.
Furthermore, over the field R, our approach improves the quadratic bound as follows.

Theorem 1.7. Over the field R, it holds that

dc(permd ) ≥ (d − 1)2 + 1.

Bounding b-rank via concave minimization. In the case k ≥ 2, the direct calcula-
tion of the bi-polynomial rank is still difficult. We propose the following computational
procedure to bound the bi-polynomial rank over R. Let Symn and Psdn denote the
sets of real symmetric and positive semidefinite matrices of size n, respectively. Suppose
p ∈ R[x](2k) . We will show that b-rank(p) is at least the half

of the minimum rank of a
D+k−1
matrix of size n = 2sk in Xp ∩ Psdn , where sk := k and Xp is an affine subspace
in Symn explicitly represented by linear equations determined by the coefficients of p;
see the concrete definition in Section 2.1. Thus b-rank(p) is more than r/2 if the sum
µn−r (X) of the smallest n − r eigenvalues of X is positive for all X ∈ Xp ∩ Psdn . It
is known that the function X 7→ µn−r (X) is concave on Symn . A well-known fact in
concave function minimization theory [13] tells us that if we know a polyhedral convex
set P ⊆ Symn containing Xp ∩ Psdn , then the minimum of µn−r is attained by extreme
points of P. Thus, the positivity of µn−r for all these extreme points is a certificate of
b-rank(p) ≥ r/2.

Proposition 1.8. Let p ∈ R[x](2k) , r ∈ N, and n = 2sk . If there exists Y ⊆ Symn

satisfying the following property, then b-rank(p) > r/2.
(i) Xp ∩ Psdn ⊆ conv(Y).
(ii) µn−r (Y ) > 0 for all Y ∈ Y.

It should be noted that this approach is essentially an outer approximation algo-

rithm [5, 15] in the concave minimization.

(2k)
Related work. The bi-polynomial rank b-rank(px0 ) can be interpreted as the mini-
(2k)
mum width of the kth layer of an arithmetic branching program (ABP) computing px0 .
Since the determinant polynomial of a matrix of size n has an ABPq
with width at most
(2k)
n2 [8], it directly follows that a simple but weaker bound dc(p) ≥ b-rank(px0 ). We
include the detailed discussion in Section 2.3. Our bound shows the possibility to prove
(4)
dc(permd ) = Ω(d4 ) by considering forth derivatives permd,Xd of permd , which seems
significantly simpler than considering eighth derivatives.

3
 Our proof method of Theorem 1.5 is first considering a normal form of an affine
polynomial matrix Q, and then constructing an ABP of det(Q)(2k) with small width
using an exhaustive construction of low-degree terms. Such an exhaustive construction
implicitly appears in the area of depth reduction of arithmetic circuits [19].
Nisan [12] considered the rank of a matrix defined by partial derivatives of non-
commutative determinant, and proved an exponential lower bound of the size of ABP of
non-commutative determinant. This implies an exponential lower bound of the size of
non-commutative formulas for determinant. We consider the bi-polynomial rank, which
is width of ABP, and formulate the bi-polynomial rank as the minimum matrix-rank over
an affine subset of matrices. Therefore our approach may be viewed as a commutative
analogue of Nisan’s approach.
The difficulty of lower bound problems come from that of proving non-existence of
certain objects. The essential idea in GCT [11] is to flip the non-existence of embeddings
into the existence of representation-theoretical obstructions. Our approach might yield
a comparable optimization-theoretic flip strategy for the permanent vs. determinant
problem: for proving dc(permd ) = Ω(d2k ),

find Xd ∈ Zeros(permd ), a polyhedron Pd containing Xp ∩ Psdn for p =

(2k)
permd,Xd , and r = O(d2k ) such that µn−r (P ) > 0 holds for all extreme
points P of Pd .

Though much still remains to be unsettled, we hope that our approach will bring a new
inspiration and trigger a new attack to this extremely difficult lower bound issue.

Organization. In Section 2, we prove basic properties of the bi-polynomial rank.

In Section 2.1, we introduce a formulation of the bi-polynomial rank as the minimum
matrix-rank over an affine subspace of matrices. In Section 2.2, we prove that generic
polynomials p ∈ K[x](2k) have the bi-polynomial rank at least D k /(2k)!. In Section 2.3,
we discuss a relation between the bi-polynomial rank and ABP. In Section 3, we consider
lower bounds of dc(permd ) from the bi-polynomial rank for the case k = 1. In Section 3.1,
we demonstrate that the bi-polynomial rank generalizes the Hessian rank, and give an
alternative and conceptually simpler proof of Theorem 1.3. In Section 3.2, we prove
dc(permd ) ≥ (d − 1)2 + 1 over the real field (Theorem 1.7). In Section 4, we prove
Proposition 1.8, and propose an approach for the permanent vs. determinant problem
based on the bi-polynomial rank, the rank minimization, and the concave minimization
for k ≥ 2. In Section 5, we prove Theorem 1.5, the main result of this paper.

2 Basic properties of b-rank

2.1 Rank minimization for b-rank
To consider the calculation of the bi-polynomial rank, we formulate the bi-polynomial
rank as the minimum matrix-rank over an affine subspace of matrices. This formulation
is a basis for discussions in subsequent sections.
Let Matn (K) be the set of square matrices of size n over the field K. For a nonneg-
ative integer k, let Ik (= Ik,D ) denote the set of D-tuples (i1 , i2 , . . . , iD ) of nonnegative
integers such that the sum i1 + i2 + · · · + iD is equal to k. For I = (i1 , i2 , . . . , iD
) ∈ Ik , let
xI denote the monomial xi11 xi22 · · · xiDD . We define sk (= sk,D ) := |Ik | = D+k−1 k , and con-
sider that sk -dimensional vectors u = (uI )I∈Ik and matrices Q = (qI,J )I,J∈I P k of size sk
are indexed by elements of Ik . Then their products are written as (Qu)I = J∈Ik qI,J uJ .
Let v(x) := (xI )I∈Ik be the sk -dimensional vector which consists of monomials.

4
Theorem 2.1. For p ∈ K[x](2k) , b-rank(p) is equal to the optimum value of the following
problem:

Minimize rank(Q)
subject to p(x) = v(x)⊤ Qv(x),
Q ∈ Matsk (K).

Proof. Suppose that Qopt attains the optimum value. First we prove thatPb-rank(p) ≤
rank(Qopt ). Let r := rank(Qopt ). We can represent Qopt as a sum Qopt = ri=1 f i g ⊤ i of
rank one matrices f i g ⊤
i , where f i and g i are s k -dimensional vectors for i = 1, 2, . . . , r.
Then we have
Xr
p(x) = v(x)⊤ Qopt v(x) = (f ⊤ ⊤
i v(x))(g i v(x)).
i=1

Choosing 2r polynomials f1 , f2 , . . . , fr , g1 , g2 , . . . , gr ∈ K[x](k) as fi (x) = f ⊤

i v(x) and
⊤
gi (x) = g i v(x) for i = 1, 2, . . . , r, we have b-rank(p) ≤ r = rank(Qopt ).
Next, we show that b-rank(p) ≥ rank(Qopt ). Set n := b-rank(p). From the P definition,
(k) n
there exist 2n polynomials
P f1 , f2 , . .I. , fn , g1 , g2 , . . . , gn ∈ K[x] such that p = i=1 fi gi .
Suppose that fi (x) = I∈Ik fi,I x , for fi,I ∈ K, where i = 1, 2, . . . , n. Then we can
represent polynomials fi by inner product of sk -dimensional vectors as fi (x) = f ⊤ i v(x),
where f i := (fi,I )I∈Ik . Also, we can represent gi as gi (x) = g ⊤ i v(x) where gi :=
(gi,I )I∈Ik . Then we have
n
X n
X
p(x) = (f ⊤ ⊤
i v(x))(g i v(x)) = v(x)⊤ (f i g ⊤
i )v(x).
i=1 i=1
P
Defining Q0 := ni=1 f i g ⊤ ⊤
i , it follows that v(x) Q0 v(x) = p(x). Thus Q0 satisfies the
constraints, and we have b-rank(p) = n ≥ rank(Q0 ) ≥ rank(Qopt ).

Observe that the feasible region of the above problem is an affine subspace of the
set of matrices. We give similar formulations over symmetric and positive semidefinite
matrices over R.

Corollary 2.2. For p ∈ R[x](2k) , b-rank(p) is at least the half of the optimum value of
the following problem:

Minimize rank(Q)
subject to p(x) = v(x)⊤ Qv(x),
Q ∈ Symsk .

Proof. Consider the optimum solution Q′ ∈ Matn (R) of the corresponding optimiza-
tion problem in Theorem 2.1. Then it holds that b-rank(p) = rank(Q′ ). Since Q =
(Q′ + Q′⊤ )/2 is a feasible solution of the above problem and rank(Q′ ) ≥ rank(Q)/2, the
statement holds.

Corollary 2.3. For p ∈ R[x](2k) , b-rank(p) is at least the half of the optimum value of
the following problem:

Minimize rank(Q+ ) + rank(Q− )

subject to p(x) = v(x)⊤ (Q+ − Q− )v(x),
Q+ , Q− ∈ Psdsk .

5
Proof. Since any symmetric matrix Q ∈ Symn can be uniquely represented as the differ-
ence Q = Q+ − Q− of the two positive semidefinite matrices Q+ , Q− ∈ Psdn satisfying
rank(Q) = rank(Q+ ) + rank(Q− ), the statement follows from Corollary 2.2.

For p ∈ R[x](2k) , we define Xp as the set of pairs (Q+ , Q− ) of sk × sk matrices

satisfying linear equation p(x) = v(x)⊤ (Q+ − Q− )v(x). By the embedding
 
Q+ O
(Q+ , Q− ) 7→ .
O Q−
we regard Xp as an affine subspace of Sym2sk . Then Xp ∩ Psd2sk is the feasible region of
the optimization problem in Corollary 2.3.

2.2 b-rank of generic polynomials

The inequality in Theorem 1.5 is nontrivial only if the bi-polynomial rank is larger
than 22k−1 (k − 1)D k−1 . We are going to show that for D ≫ k and a generic poly-
nomial, this condition holds. Here we suppose that K is an algebraically closed field
of characteristic zero. We use the terminologies in Section 2.1. Observe that poly-
nomials in K[x](2k) are determined by s2k coefficients, and therefore we regard that a
homogeneous
P polynomial p ∈ K[x](2k) is a point in K s2k , under the correspondence
p(x) = I∈I (2k) aI xI 7→ (aI )I∈I (2k) ∈ K s2k . Then the set of polynomials p satisfying
D D
b-rank(p) ≤ r are characterized in terms of algebraic geometry, as follows.
Theorem 2.4. Let S := {q ∈ K[x](2k) | b-rank(q) ≤ r} ⊆ K s2k . Then the Zariski
closure S is an irreducible variety having dimension at most r(2sk − r).
2 2
Proof. We identify Matsk (K) with K sk . Let Zr := {X ∈ K sk | rank(X) ≤ r}. Zr is
called the determinantal variety, and it is known that Zr is an irreducible variety of
2
dimension r(2sk − r) (see, e.g., [4]). We define π : K sk → K s2k by
X
(π(X))H := XI,J (I, J ∈ Ik , H ∈ I2k ).
I,J:I+J=H

This π is a linear projection. For q ∈ K[x](2k) , Theorem 2.1 shows that b-rank(q) ≤ r if
2
and only if there exists X ∈ K sk such that rank(X) ≤ r and π(X) = q. Thus it follows
that S = π(Zr ). As the Zariski closure of the linear projection of the irreducible variety
Zr , S = π(Zr ) is irreducible and its dimension is at most r(2sk − r).

From Theorem 2.4, we can obtain a lower bound of the bi-polynomial rank for generic
polynomials.
Proposition 2.5. For a polynomial p ∈ C[x](2k) with algebraically independent coeffi-
cients over Q, it holds that b-rank(p) ≥ k!D k /2(2k)!.

Proof. Let r := b-rank(p) and Sr := {q ∈ C[x](2k) | b-rank(q) ≤ r} ⊆ Cs2k . From

Theorem 2.4, Sr is an irreducible variety of dimension at most r(2sk − r). Since Zr and
hence S r is defined over Q and p has no algebraic relation over Q in its coefficients,
p ∈ Sr implies that Sr must be Cs2k . Comparing the dimensions, it must holds that
r(2sk − r) ≥ s2k . This implies r 2 − 2sk r + s2k ≤ 0 and
  
k!D k
q
2 s2k s2k
r ≥ sk − sk − s2k ≥ sk 1 − 1 − 2 = ≥ .
2sk 2sk 2(2k)!
√
In the second inequality, we use the fact that 1 − x ≤ 1 − x/2 for x ≤ 1.

6
 This lower bound is asymptotically tight if k is a constant.
Proposition 2.6. For any polynomial p ∈ K[x](2k) , it holds that b-rank(p) ≤ sk ≤ D k .
This proposition immediately follows from Lemma 5.6.

2.3 b-rank and arithmetic branching program

We here discuss a relation between the bi-polynomial rank and an arithmetic branching
program (ABP). We show that the following weaker statement than Theorem 1.5 easily
follows from known facts on an ABP of determinant.
Proposition 2.7. For a polynomial p ∈ K[x], k ∈ N, and x0 ∈ K D \ Zeros(p), it holds
that
q
(2k)
dc(p) ≥ b-rank(px0 ).
We omit the case x0 ∈ Zeros(p) for the simplicity of the proof. We use the following
lemma which is a variation of Lemma 5.1.
Lemma 2.8. Let p ∈ K[x] with dc(p) = n. Then, for all x0 ∈ K D \ Zeros(p), there exist
a linear polynomial matrix A ∈ (K[x])n×n and α ∈ R such that px0 (x) = α det(A(x)+I).
Proof. From the definition of the determinantal complexity, there exists an affine poly-
nomial matrix Q ∈ (K[x])n×n such that p = det(Q). In particular, given any x0 ∈ K D \
Zeros(p) it follows that px0 (x) = det(Q(x + x0 )). Define α := det(Q(x0 )) = px0 (0) 6= 0.
Since Q is an affine polynomial matrix, we can represent Q(x + x0 ) = L(x) + Q(x0 )
where L ∈ (K[x])n×n is a linear polynomial matrix. We have
det(Q(x + x0 )) = α det(Q(x0 )−1 )det(L(x) + Q(x0 )) = αdet(Q(x0 )−1 L(x) + I).
Since Q(x0 )−1 L(x) is also a linear polynomial matrix, we define A(x) := Q(x0 )−1 L(x),
and then the statement follows.
We formally define an ABP discussed in Section 1.
Definition 2.9 (Nisan [12], see also [14]). An (homogeneous) arithmetic branching
program (ABP) over K[x] is a layered graph with n + 1 layers as follows. The layers
are labeled by 0, 1, . . . , n. The edges of the graph go from layer i to layer i + 1. Every
edge e is labeled by a (homogeneous) linear polynomial ℓe ∈ K[x]. Layer 0 has only
one vertex called the source, and layer n has only one vertex called the sink. For every
directed path from the source to the sink γ = (e1 , e2 , . . . , en ), define the polynomial
P fγ
associated to γ as fγ = ℓe1 ℓe2 · · · ℓen . The polynomial computed by ABP is γ fγ .
For an ABP A, we define the width wk (A) of layer k as the number of vertices in the
layer k. Given a homogeneous polynomial f with degree at least k, we denote by wk (f )
the minimum wk (A) over ABPs A which compute f .
The following is an easy observation.
Fact 2.10. For f ∈ K[x](2k) , it holds that b-rank(f ) ≤ wk (f ).
Proof. Suppose that an ABP A computes f . Let V be the set of vertices in the layer k
of A. For v ∈ V , let Rv and R′v be the sets of path from the source to v and from v to
the sink, respectively. Then it holds that
  
X X X
f=  fγ   fγ ′  .
v∈V γ∈Rv γ ′ ∈Rv

Therefore we have b-rank(f ) ≤ |V | = wk (f ).

7
 The next statement is a well-known result.

Theorem 2.11 (Mahajan and Vinay [8]). Let A ∈ (K[x])n×n be a linear polynomial
matrix, and r ∈ [1, n − 2]. Then there exists an ABP A over K[x] such that A computes
the coefficient of λn−r in det(A(x) + λI) and satisfying wk (A) ≤ n2 for all k ∈ [1, r − 1].

Then Proposition 2.7 is proved as follows.

Proof of Proposition 2.7. By Lemma 2.8, there exists a linear polynomial matrix A ∈
(2k)
(K[x])n×n and α ∈ R such that px0 (x) = α det(A(x) + I). Then px0 is equal to the
coefficient of λn−2k in α det(A(x) + λI). Then by Theorem 2.11, there exists an ABP
(2k)
A with wk (A) ≤ n2 which computes px0 (x)(2k) . By Fact 2.10, we have b-rank(px0 ) ≤
(2k)
wk (px0 ) ≤ wk (A) ≤ n2 = dc(p)2 .

3 Lower bounds of dc(permd ) by b-rank: case k = 1

Considering the case k = 1 in Theorem 1.5, we obtain lower bounds of dc(permd ) by the
bi-polynomial rank. We define Σd ∈ Zeros(permd ) as follows:
 
1 ··· ··· 1
 .. . . . . .. 
 . . . . 
Σd := 
 .. . .
.

 . . 1 1 
1 ··· 1 1 − d

This is the same matrix appearing in the proof of Theorem 1.3 in [10].

3.1 Mignon-Ressayre bound from b-rank

This section is devoted to the demonstration of the bi-polynomial rank as an extention
of Hessian rank. We give an alternative proof of the result of Mignon and Ressayre
(Theorem 1.3). By using the bi-polynomial rank, Theorem 1.3 immediately follows from
Theorem 1.5 as follows.

An alternative proof of Theorem 1.3. For any p ∈ K[x] and x0 ∈ Zeros(p), we have
 
(2) 1 X ∂2 
px0 (x) = xi xj p  .
2 ∂xi ∂xj x=x0
1≤i,j≤D
 
∂2 
We define the Hessian Hp,x0 = (hi,j ) of p at x0 by hi,j := ∂xi ∂xj p
 . By definition,
x=x0
(2) P PD m
b-rank(px0 ) is equal to the minimum number n of bilinear forms ( D m
l=1 bl xl )( l=1 cl xl )
(2)
(m = 1, 2, . . . , n) whose sum is equal to px0 . We define
Pthe rank one matrices Am = (am i,j )
m m m n
for m = 1, 2, . . . , n, by ai,j := bi cj . Let A := m=1 Am , and then it holds that
(2) 1
A + A⊤ = Hp,x0 . Therefore we have b-rank(px0 ) ≥ rank(A) ≥ 2 rank(Hp,x0 ). By
Theorem 1.3, by putting k = 1 it holds that
1
dc(p) ≥ b-rank(p(2)
x0 ) ≥ rank(Hp,x0 ).
2
In the case of p = permd , Mignon and Ressayre proved rank(Hpermd ,Σd ) = d2 . Thus
Theorem 1.3 follows from our Theorem 1.5.

8
3.2 Lower bound of dc(permd ) over the field R
Theorem 1.7 improves the current best lower bound given by Mignon and Ressayre.
We present the proof in this section. Given a symmetric matrix, we denote by a tuple
(n+ , n− , n0 ) the signature of the matrix, that is, the number of positive, negative, zero
eigenvalues, respectively. If symmetric matrices S and S ′ have the same signature, we
denote S ∼ S ′ . By Sylvester’s law of inertia, S ∼ S ′ if and only if S ∼ T ST ⊤ for a
nonsingular matrix T . We use the next lemma.

Lemma 3.1. Let Q ∈ Matn (R), Qsym := Q + Q⊤ , and (n+ , n− , n0 ) be the signature of
Qsym . Then it holds that rank(Q) ≥ max{n+ , n− }.

Proof. Let λ1 , λ2 , . . . , λn+ be the positive eigenvalues of Qsym , and v 1 , v 2 , . . . , v n+ be

the corresponding eigenvectors which are orthogonal to each other. Let V+ ⊆ Rn be
the
Pn+n+ -dimensional subspace spanned by v1 , v 2 , . . . , v n+ . For any nonzero vector u =
i=1 ai v i ∈ V+ where a1 , a2 , . . . , an+ ∈ R, it holds that

n+ n+
X X
⊤ ⊤
2u Qu = u Qsym u = a2i v ⊤
i Qv i = a2i λi > 0.
i=1 i=1

The above inequality shows that Qu 6= 0 for all nonzero vectors u in n+ -dimensional
space V+ , and therefore rank(Q) ≥ n+ . The same argument is also true for eigenvectors
with negative eigenvalues, and it holds that rank(Q) ≥ n− .

The proof of Theorem 1.7 is given as follows.

Proof of Theorem 1.7. From Theorem 1.5, for k = 1 we obtain that dc(permd ) ≥
(2)
b-rank(permd,Σd ) over R. We consider that a matrix A = (a(i,j),(i′ ,j ′ ) ) of size d2 is
indexed by pairs of integers (i, j), (i′ , j ′ ) where i, j, i′ , j ′ ∈ [1, d]. Since
 2 
(2) 1 X ∂ permd 
permd,Σd (x) = xi,j xi′ ,j ′ ,
2 ∂xi,j ∂xi′ ,j ′ x=Σd
′ ′i,j,i ,j ∈[1,d]

we define the Hessian matrix H = (h(i,j),(i′ ,j ′ ) ) of permd at Σd by the following equation.

 
∂ 2 permd 
h(i,j),(i′ ,j ′ ) = h(i′ ,j ′ ),(i,j) := .
∂xi,j ∂xi′ ,j ′ x=Σd

The corresponding optimization problem in Theorem 2.1 is equal to the following.

Minimize rank(Q)
subject to Q + Q⊤ = H,
Q ∈ Matd2 (R).

Let Qopt be an optimum solution of the above problem. By Theorem 2.1 we have
(2)
b-rank(permd,Σd ) = rank(Qopt ). Let (n+ , n− , n0 ) be the signature of H ∈ Symd2 . Since
Qopt + Q⊤
opt = H by Lemma 3.1 it follows that rank(Qopt ) ≥ n− . Therefore we obtain

(2)
dc(permd ) ≥ b-rank(permd,Σd ) = rank(Qopt ) ≥ n− .

9
 We are going to prove n− = (d − 1)2 + 1. As in [10], H can be calculated as
 
O B ··· B C
. .. 
 B . . . . . . ..

 . 

.
 .. . . . O B
H = (d − 3)!  ,
 C  
 B ··· B O C 
C ··· C C O
where B and C are the following matrices of size d:
 
0 −2 · · · −2 d − 2  
 . . .. ..  0 1
··· 1
 −2 .. .. . .   . . .. 

..
  1 0 . . 
B= . ..  , C = (d − 2)  .
 . 0 −2 d − 2   .. . . . . 
   . . . 1 
 −2 · · · −2 0 d−2 
1 ··· 1 0
d − 2 ··· d − 2 d − 2 0
Let Sd be the symmetric matrix of size d defined as follows.
 
0 1 ··· 1
 . . .. 
 1 0 . . 
Sd :=  .. .. ..
.

 . . . 1 
1 ··· 1 0
Then it holds that B ∼ −Sd and C ∼ Sd . Let Id be the identity matrix of size d. The
signature of Sd is (1, d − 1, 0), since the rank of the matrix (Sd + Id ) is one with the
nonzero eigenvalue d. Define a nonsingular matrix T of size d2 as follows.
 
Id O ··· ··· O
 .. .. .. 
 O Id . . . 
 
T := 
 .
.. .. .. .. ..  .
. . . . 
 
 O O ··· Id O 
1 1 1
− d−2 CB −1 − d−2 CB −1 · · · − d−2 CB −1 Id

Then H ∼ T HT ⊤ , where
 
O B ··· O O
 . . .. .. 
 B O . . . 
 
T Qsym T ⊤ .
=  .. . . . . . . B
 .
 O 

 B ··· B O O 
d−1
O · · · · · · O − d−2 CB −1 C

Let H ′ be the upper-left principal submatrix of T HT ⊤ of size d(d − 1), which is repre-
sented as follows.  
O B ··· B
 .. . 
 B O . .. 
Q′ =  .. . . ..
.

 . . . B 
B ··· C O
Denote by (l+ , l− , l0 ) and (m+ , m− , m0 ) the signatures of (−CB −1 C) and H ′ , respec-
tively. Then it holds that n− = l− +m− . Since −CB −1 C ∼ −(BC −1 )(CBC)(BC −1 )⊤ =

10
−B ∼ Sd , l− is equal to d − 1. On the other hand, it holds that H ′ = Sd−1 ⊗ C, where
⊗ denote the Kronecker product. Since the set of eigenvalues of Sd−1 ⊗ B consists of
the products of all pair of eigenvalues of Sd−1 and B, the signature of Sd−1 ⊗ B is
(2d − 3, (d − 2)(d − 1) + 1, 0). Therefore we have n− = (d − 1) + ((d − 2)(d − 1) + 1) =
(d − 1)2 + 1.

4 Toward strong lower bounds via concave minimization

We formulate the bi-polynomial rank as the minimum matrix-rank over an affine sub-
space of matrices in Section 2.1. Unfortunately, few results are known for giving the-
oretical lower bounds for the rank minimization problem. In our case, the calculation
of such a minimum rank is still difficult for k ≥ 2. We propose an approach to bound
the minimum rank below by using the framework of the concave minimization. In this
section, we fix the field K = R.

4.1 Concave minimization for bounding minimum rank below

The object of the concave minimization is to minimize a concave function over a convex
set. This setting is studied in the area of global optimization [13]. We use this framework
to obtain lower bounds of the minimum rank over a subset of positive semidefinite
matrices.
As in Section 1, for Y ∈ Symn and l ∈ [1, n], we denote by µl (Y ) the sum of the small-
est l eigenvalues of Y . For X ⊆ Symn , we define rank(X ) := minX∈X rank(X). Then
the next statement is immediate from the definition of positive semidefinite matrices.

Lemma 4.1. Let X ⊆ Psdn , and r ∈ N. Then rank(X ) > r if and only if µn−r (X) > 0
for all X ∈ X .

This statement suggests the way to solve the rank minimization problem over positive
semidefinite matrices by minimizing µl over the feasible region. The computation of µl
is formulated as the optimum solution of a semidefinite programming.

Proposition 4.2 (See [1, Section 4.1]). Let A ∈ Symn and l ∈ [1, n]. Then µl (A) is
equal to the optimum value of the following problem:

Minimize tr(AX)
subject to tr(X) = l,
X, I − X ∈ Psdn .

Proof. Since A is a symmetric matrix, A is diagonalizable by some orthogonal matrix V ,

as V AV ⊤ =: Ã. Let X̃ := V XV ⊤ , and then the replacement of A, X by Ã, X̃ does not
change the optimum value. Therefore, without loss of generality, we can assume that A
is a diagonal matrix with diagonal entries λ1 ≤ λ2 ≤ · · · ≤ λn . Then the optimum value
is attained by such X that the firstP
l diagonal entries are 1, and the other entries are 0.
It holds that the optimum value is li=1 λi = µl (A).

For latter use, we prepare the next statement.

Corollary 4.3. Let Y ∈ Symn . Then µl (Y ) is at least lz − tr(Z) for Z ∈ Psdn and
z ∈ R satisfying (Y + Z − zI) ∈ Psdn .

11
Proof. Observe that the following optimization problem is the dual of the problem in
Proposition 4.2.

Maximize lz − tr(Z)
subject to z ∈ R,
Z, Y + Z − zI ∈ Psdn .

By the weak duality of semidefinite programming, for any feasible solution (Z, z) ∈
Psdn × R, the objective value lz − tr(Z) is at most µl (Y ).

The concavity of µl is proved as follows.

Corollary 4.4 (See [1, Section 4.1]). For l ∈ [1, n], µl : Symn → R is a concave
function.

Proof. Let X, Y ∈ Symn . Denote by prb(Y ) the optimization problem in Proposition 4.2
for Y . Then an optimum solution of prb( X+Y
2 ) is a feasible solution of both prb(X) and
prb(Y ), and therefore the optimum value of prb( X+Y
2 ) is at least the average of optimum
values of prb(X) and prb(Y ). By Proposition 4.2, this indicates that 21 (µl (X)+µl (Y )) ≤
µl ( X+Y
2 ).

In the theory of the concave minimization, the outer approximation approach [5, 15]
(see also [13]) obtain a lower bound of the minimum of a given concave function by
approximating the feasible region from outside. Given a set Y ⊆ Symn , we denote by
conv(Y) the convex hull of Y. In general, given a concave function f over Y, it holds
that minY ∈Y f (Y ) = minY ∈conv(Y) f (Y ). Therefore the next statement holds.

Theorem 4.5. Let X ⊆ Psdn and r ∈ N. If there exists Y ⊆ Symn satisfying the
following property, then rank(X ) > r.
(i) X ⊆ conv(Y).
(ii) µn−r (Y ) > 0 for all Y ∈ Y.

Proof. Since µn−r is a concave function, 0 < minY ∈Y µn−r (Y ) = minY ∈conv(Y) µn−r (Y ) ≤
minX∈X µn−r (X). By Lemma 4.1, µn−r (X) > 0 for all X ∈ X implies rank(X ) > r.

To utilize Theorem 4.5 for lower bounds of the bi-polynomial rank, we prove Propo-
sition 1.8.

Proof of Proposition 1.8. By Corollary 2.3, b-rank(p) ≥ 21 rank(Xp ∩ Psdn ). Then by

Theorem 4.5, rank(Xp ∩ Psdn ) > r, and therefore the statement holds.

Corollary 4.3 may help the verification µn−r (Y ) > 0 as follows.

Corollary 4.6. Let p ∈ K[x](2k) and r ∈ N. If there exists Y ⊆ Xp satisfying the

following property, then b-rank(p) > r/2.
(i) Xp ∩ Psd2sk ⊆ conv(Y).
(ii) For all (Y1 , Y2 ) ∈ Y, there exists (Z1 , Z2 , z) ∈ Psdsk × Psdsk × R such that
(Y1 + Z1 − zI), (Y2 + Z2 − zI) ∈ Psdsk and (2sk − r)z − tr(Z1 + Z2 ) > 0.

Proof. The statement directly follows from Proposition 1.8 and Corollary 4.3.

12
4.2 An explicit representation of Xperm(2k)
d,Σd

The previous section discusses a general framework for giving lower bounds of the bi-
polynomial rank. In the framework, to calculate b-rank(p) of p ∈ K[x](2k) , we consider
the minimum of the concave function µ2sk −r over Xp ∩ Psd2sk . Our final target is to
(2k)
obtain lower bounds of dc(permd ). In this section, we fix p = permd,Σd , and give an
explicit representation of a projection Z2k of Xp . p is a multilinear polynomial, and to
2
extract this feature, we define the subset Jk,d2 := Ik,d2 ∩ {0, 1}d of d2 -tuples. Define
d′ := d − 1. Observe that Σd has good symmetry except for dth row/column. For
I = (i1,1 , i1,2 , . . . , id′ ,d′ ) ∈ Jk,d′ 2 , we define ι(I) ∈ Jk,d2 by the insertion of zeros into the
entries not in Jk,d′ 2 . More concretely,

ι(i1,1 , i1,2 , . . . , id′ ,d′ ) := (i1,1 , . . . , i1,d−1 , 0, i2,1 , . . . , id′ ,d′ , 0, . . . , 0).

Let tk be the cardinality of Jk,d′ 2 . Then we define the projection π : Symsk → Symtk by
1
π(Y )I,J := αYι(I),ι(J) for I, J ∈ Jk,d′ 2 , where α := − 2k(d−2k−1)! is a constant. We define
Z2k ⊆ Symtk × Symtk as a projection of Xp as follows:

Z2k := {(π(X+ ), π(X− )) | (X+ , X− ) ∈ Xp }.

Then it holds that

rank(Z2k ∩ Psd2tk ) ≤ rank(Xp ∩ Psd2sk )

≤ rank(Z2k ∩ Psd2tk ) + (sk − tk ),

where sk − tk = O(d2k−2 ). Hence rank(Xp ∩ Psd2sk ) = Ω(d2k ) if and only if rank(Z2k ∩

Psd2tk ) = Ω(d2k ). We are going to give an explicit representation of Z2k . In p, no mono-
mial with repetition of a row/column index appear. To express this, we classify J2k,d′ 2
into H1 and H0 as follows. We define H1 as the set of tuples (H1,1 , H1,2 , . . . , Hd′ ,d′ ) ∈
Pd′ Pd′ ′
J2k,d′ 2 satisfying j ′ =1 Hi,j ′ ≤ 1 and i′ =1 Hi′ ,j ≤ 1 for i, j ∈ [1, d ], and H0 :=
J2k,d′ 2 \ H1 . Then Z2k is given as the set of pairs (U, V ) of matrices in Symtk satis-
fying linear equations for all H ∈ J2k,d′ 2 :
(
X 1, H ∈ H1
(uI,J − vI,J ) =
I,J∈Jk,d′ 2
0, H ∈ H0
I+J=H

Observe that this affine space Z2k is represented by simple linear equations with coeffi-
cients in {0, ±1}.

5 Proof of Theorem 1.5

A linear polynomial matrix over x1 , x2 , . . . , xD of size n is an n × n matrix A(x) =
(ai,j (x)) ∈ (K[x])n×n , where each element ai,j (x) is a (homogeneous) linear polynomial
for 1 ≤ i, j ≤ n. Denote by Λrn the diagonal matrix of size n with diagonal entries
(0, . . . , 0, 1, . . . , 1). For α, β ∈ Z with α ≤ β, we denote {α, α + 1, . . . , β} by [α, β].
| {z }
r

Lemma 5.1. Let p ∈ K[x] with dc(p) = n. Then, for all x0 ∈ Zeros(p), there exist a
linear polynomial matrix A ∈ (K[x])n×n and r ∈ [0, n − 1] such that px0 (x) = det(A(x) +
Λrn ).

13
Proof. From the definition of the determinantal complexity, there exists an affine polyno-
mial matrix Q ∈ (K[x])n×n such that p = det(Q). In particular, given any x0 ∈ Zeros(p)
it follows that px0 (x) = det(Q(x + x0 )). Observe that det(Q(x0 )) = px0 (0) = 0 and
rank(Q(x0 )) ≤ n − 1. Let r ∈ [0, n − 1] be the rank of Q(x0 ). Then there exist nonsingu-
lar matrices S, T of size n such that SQ(x0 )T = Λrn and det(ST ) = 1. Since Q is an affine
polynomial matrix, we can represent Q(x + x0 ) = L(x) + Q(x0 ) where L ∈ (K[x])n×n is
a linear polynomial matrix. We have
det(Q(x + x0 )) = det(L(x) + Q(x0 )) = det(S(L(x) + Q(x0 ))T ) = det(SL(x)T + Λrn ).
Since SL(x)T is also a linear polynomial matrix, we define A(x) := SL(x)T , and then
the statement follows.

Given a linear polynomial matrix A ∈ (K[x])n×n , k ∈ N and r ∈ [0, n − 1], we define

pA,k,r (x) := (det(A(x) + Λrn ))(k) .
P
Then it holds that det(A(x)+Λrn ) = nk=n−r pA,k,r (x). The next statement is the essence
of our result.
Proposition 5.2. For A ∈ (K[x])n×n , it holds that b-rank(pA,2k,n−1 ) ≤ n+2(k−1)D k−1 .
The proof of Proposition 5.2 is given in the next section. By this proposition, the
following statement holds.
Lemma 5.3. (i) For r ∈ [n − 2k, n − 1], it holds that b-rank(pA,2k,r ) ≤ 2n−r−1 (n + 2(k −
1)D k−1 ).

(ii) For r = n − 2k, it holds that b-rank(pA,2k,r ) ≤ 2k
k .

Proof. (i), let i := n − r. We prove the statement by the induction on i. The case
i = 1 directly follows from Proposition 5.2. Suppose that for i ≤ 2k − 1, the statement
holds. Denote by A′ ∈ K[x]n−1×n−1 the linear polynomial matrix obtained by deleting
the (i + 1)th row and column of A. Since determinant is a bi-linear form, we have
(n−1)−i
det(A(x) + Λnn−i ) = det(A(x) + Λnn−(i+1) ) + det(A′ (x) + Λn−1 ),
and therefore pA,2k,n−(i+1) = pA,2k,n−i − pA′ ,2k,(n−1)−i . By inductive hypothesis, we have

b-rank(pA,2k,n−(i+1)) ≤ b-rank(pA,2k,n−i ) + b-rank(pA′ ,2k,(n−1)−i )

≤ 2i−1 (n + 2(k − 1)D k−1 ) + 2i−1 ((n − 1) + 2(k − 1)D k−1 ) ≤ 2i (n + 2(k − 1)D k−1 ).
Therefore the statement (i) holds.
(ii) We have
pA,2k,n−2k (x) = (det(A(x) + Λnn−2k ))(2k) = det(A2k (x)),
where A2k is the leading principal submatrix of A of size 2k. Given I ⊆ [1, 2k] with
|I| = k, we denote by BI the square submatrix of A2k consisting of rows and columns
corresponding to indices I and [1, k], respectively. Also, we denote by BI¯(x) the square
submatrix of A2k (x) with row and column indices [1, 2k] \ I and [k + 1, 2k], respectively.
Then the following is an elementary formula for determinant.
X
det(A2k ) = sign(I)det(BI ) · det(BI¯),
I⊆[1,2k]:|I|=k

where sign(I) ∈ {1, −1}. Since
det(BI ), det(BI¯) ∈ K[x](k) for all I ⊆ [1, 2k] with |I| = k,
we have b-rank(pA,2k,r ) ≤ 2k
k .

14
 We give a proof of Theorem 1.5.

Proof of Theorem 1.5. Suppose that dc(p) = n. By Lemma 5.1, for all x0 ∈ Zeros(p),
there exist a linear polynomial matrix A ∈ (K[x])n×n and r ∈ [0, n − 1] such that
(2k)
px0 (x) = det(A(x) + Λrn ). Then px0 (x) = (det(A(x) + Λrn ))(2k) = pA,2k,r . If r < n − 2k
(2k)
or n = 1, then pA,2k,r = 0 and b-rank(px0 ) = 0. The statement is trivial in this case,
and we assume that r ∈ [n − 2k, n − 1] and n ≥ 2. By Lemma 5.3 it holds that
 
2k−2 2k
b-rank(pA,2k,r ) ≤ max{2 (n + 2(k − 1)D k−1
), } ≤ 22k−2 (n + 2(k − 1)D k−1 ),
k


since k ≤ D, n ≥ 2, and 2k k
k ≤ (2k) ≤ 2
2k−2 (n + 2(k − 1)D k−1 ). Therefore it holds

that
1
2k−2
b-rank(p(2k)
x0 ) − 2(k − 1)D
k−1
≤ n = dc(p).
2

Proof of Proposition 5.2

We denote pA,k,n−1 := (det(A(x) + Λnn−1 ))(k) by pA,k for notational simplicity. Let us
define the following notions about clows and cycles on a vertex set. The former is a
terminology of Mahajan and Vinay [8].

• Let Vn := [1, n], and we call elements of Vn as vertices.

• A clow (standing for closed walk) on Vn is an ordered tuple of vertices hv1 , v2 , . . . , vl i

such that v1 < vi for i = 2, . . . , l. The vertex v1 is referred to as the head of c,
and l is called the length of c. If all vertices v1 , v2 , . . . , vl are distinct, the clow is
particularly called a cycle. Note that hvi is a cycle for all v ∈ Vn .

• Given a clow c = hv1 , v2 , . . . , vl i and a linear polynomial matrix A(x) := (ai,j (x)) ∈
Q
(K[x])n×n , ac ∈ K[x](l) is defined as ac := li=1 avi ,vi+1 , with identification vl+1 =
v1 .

• A clow sequence C = (c1 , c2 , . . . , cm ) is an ordered tuple of clows c1 , . . . , cm , where

the head of ci is strictly less than the head of cj if i < j. The size ℓ(C) of C is
defined by ℓ(C) := m.

• We denote by C n,k the set of clow sequences C on Vn such that the sum of length of
all clows in C is k. The subset Cn,k ⊆ C n,k consists of vertex disjoint clow sequences
C ′ where each clow in C ′ is a cycle. Since every element C ′ of Cn,k includes exactly
k distinct vertices, we call C ′ as a cycle k-cover.

• The sign of C ∈ C n,k is defined as (−1)n+ℓ(C) .

• We denote by C n,k,1 ⊆ C n,k the set of clow sequences which includes the vertex
1 ∈ Vn . Also, Cn,k,1 ⊆ C n,k,1 is defined as the set of cycle k-covers which include
the vertices 1 ∈ Vn . Given C ∈ C n,k,1 , we denote by c1 the unique clow in C which
includes the vertex 1.

• Given a linear polynomial matrix A(x) = (ai,j (x)) ∈ (K[x])n×n and a clow se-
quence C = (c1 , c2 , . . . , cℓ(C) ) ∈ C n,k , we define a polynomial aC ∈ K[x](k) by
Qℓ(C)
aC := i=1 aci .

15
Lemma 5.4. Given a linear polynomial matrix A ∈ (K[x])n×n , it holds that
X
pA,k (x) = (−1)n−k sign(C)aC
C∈Cn,k

P
Proof. We expand det(A(x) + Λnn−1 ) = ni=1 pA,i (x) with respect to ai,j (x). Given U
with {1} ⊆ U ⊆ Vn , AU is defined as the principal submatrix of A consisting of rows
and columns having indices in U . Since determinant is a multilinear function and Λnn−1
has nonzero entries which is equal to 1 only on diagonal, it follows that
X n
X X
det(A(x) + Λrn ) = det(AU (x)) = det(AU (x)). (5.1)
U :{1}⊆U ⊆Vn k=1 U :|U |=k
{1}⊆U ⊆Vn

For U ⊆ Vn , denote by Cn,U ⊆ Cn,|U | the set of cycle |U |-covers which include all vertices
in U . Since elements in Cn,U consist of vertices in U , we can regard them as cycle |U |-
covers on U . Let SU be the set of permutations on the finite set U . Observe that there is
a natural one-to-one correspondence between permutations Q σ ∈ SU and cycle |U |-covers
C ∈ Cn,U , satisfying sign(σ) = (−1) n−|U | sign(C) and i∈U ai,σ(i) = aC . Therefore from
the definition of determinant it follows that
X Y X
det(AU ) = sign(σ) ai,σ(i) = (−1)n−|U | sign(C)aC . (5.2)
σ∈SU i∈U C∈Cn,U

By (5.1), (5.2), we obtain

n
X X X
det(A(x) + Λrn ) = (−1)n−k sign(C)aC (x)
k=1 U :|U |=k C∈Cn,U
{1}⊆U ⊆Vn
n
X X n
X
= (−1)n−k sign(C)aC (x) = (−1)n−k pA,k,r (x).
k=1 C∈Cn,k,n−r k=1

The second equation holds since Cn,k,n−r is the disjoint union of Cn,U over U satisfying
{1} ⊆ U ⊆ Vn and |U | = k. Therefore it holds that pA,k = (det(A(x) + Λrn ))(k) =
(−1)n−k pA,k,r (x).

The following lemma was essentially given in [18, Section 3], and proved in full detail
in [8, 9].

Lemma 5.5. It holds that

X
pA,k = (−1)n−k sign(C)aC .
C∈C n,k,1

Proof. Since Cn,k,1 ⊆ C n,k,1 , by the definition of pA,k,1 it is enough to show that
X
sign(C)aC (x) = 0. (5.3)
C∈C n,k,1 \Cn,k,1

Observe that C ∈ C n,k,1 is not in Cn,k,1 if and only if C has a repetition of vertices.
Suppose that C = (c1 , c2 , . . . , cm ) ∈ C n,k,1 have a repetition of vertices. Let l ≤ m be
the maximum number such that (cl , . . . , cm ) has a repetition but (cl+1 , . . . , cm ) does not.

16
Let cl = hv1 , v2 , . . . , vi i and vj be the first element in cl which is either (1) equal to one
of vt where 1 < t < j, or (2) equal to an element in one of cl+1 , . . . , cm . Precisely one of
them will occur.
In the case (1), let hut , ut+1 , . . . , uj−1 i be the clow obtained by cyclically reorder-
ing the vertex sequence vt , vt+1 . . . , vj−1 (these vertices are all distinct and there is a
unique minimum element). We replace cl by two clows hv1 , . . . , vt−1 , vj , . . . , vi i and
hut , . . . , uj−1 i, which are made by separation around vt .
In the case (2), let c′ = hu1 , . . . , us−1 , vj , us+1 , . . . , ui′ i be the clow including vj . We
replace cl and c′ by the single clow hv1 , . . . , vj , us+1 , . . . , ui′ , u1 , . . . , us−1 , vj , vj+1 , . . . , vi i,
which is constructed by the insertion of c′ into c around the common vertex vt . It can
be verified that the procedures (1) and (2) are inverses of each other, which result in
a one-to-one correspondence in clow sequences with repetition. If C ∈ C n,k,1 \Cn,k,1
is converted to C ′ ∈ C n,k,1 \Cn,k,1 by the above procedure, then aC (x) = aC ′ (x) and
sign(C) = − sign(C ′ ). Thus the equation (5.3) holds.


The number of polynomials needed to span K[x](k) as a K-vector space is D+k−1 k ,
D+k−1

and we define sk := k . The following is a general property of polynomials.

Lemma 5.6. For p ∈ K[x](k) and m ≤ k, there exist 2s Pmmpolynomials f1 , f2 , . . . , fsm ∈

K[x](m) and g1 , g2 , . . . , gsm ∈ K[x](k−m) such that p = si=1 fi gi .
PD
Proof. Let Pm := {xj11 xj22 · · · xjDD | j1 , j2 , . . . , jD ∈ Z+ , l=1 jl = m} be the set of
monomials with degree m. Take distinct fi ∈ Pm for i = 1, 2, . . . , sm . Since P meach term
in p is divisible by at least one of fi , we can obtain a decomposition p = si=1 fi gi .

For t = 1, 2, . . . , 2k, let qA,2k,t ∈ K[x](2k) be defined by

X
qA,2k,t := sign(C)aC ,
C∈C n,2k,1
|c1 |=t

where c1 is the unique clow in C including

P2k the vertex 1, and |c1 | is the length of c1 .
Then it holds that pA,2k = (−1) n−2k
t=1 qA,2k,t . Let Ft be the set of clows with length
t which include the vertex 1 ∈ Vn .

Lemma 5.7. (i) For t = 2k, it holds that b-rank(qA,2k,2k ) ≤ n − 1.

(ii) For t = 1, 2, . . . , 2k−1, let t′ := min{t, 2k−t}. Then it holds that b-rank(qA,2k,t) ≤
sk−t′ .
P
Proof. (i) We have qA,2k,2k = (−1)n+1 c∈F2k ac . For v = 2, 3, . . . , n, let F2k,v ⊆ F2k
be the set of clows whose (k + 1)th vertices are equal to v. Note that the (k + 1)th
vertex of a clow c ∈PF is one P of {2, 3, . . . , n}, since the head of c is 1. Then we have
qA,2k,2k = (−1)n+1 v∈[2,n] c∈F2k,v ac . Let Rv and R′v be the sets of k + 1 vertex
sequences R = (1, u2 , u3 , . . . , uk , v) and R′ = (v, u′2 , u′3 . . . , u′k , 1), respectively, such that
Q
u2 , u3 , . . . , um , u′2 , u′3 , . . . , u′k+1 ∈ {2, 3, . . . , n}. We define aR := ki=1 aui ,ui+1 for R =
(u1 , u2 , . . . , uk+1 ) in Rv or R′v . Then there is a one-to-one correspondence between F2k,v
and Rv × R′v by the following correspondence

F2k,v ∋ h1, u2 , u3 , . . . , uk , v, uk+2 , uk+3 , . . . , u2k i

7→ ((1, u2 , u3 , . . . , uk , v), (v, uk+2 , uk+3 , . . . , u2k , 1)) ∈ Rv × R′v .

17
Therefore it holds that
! 
X X X
ac = aR  aR′  .
c∈Fk,v R∈Rv R′ ∈R′v
P P
Therefore it holds that b-rank(qA,2k,2k ) ≤ v∈[2,n] b-rank( c∈Fk,v ac ) ≤ n − 1.
(ii) Let G2k−t ⊆ C n,2k−t be the set of clow sequences which do not include the vertex
1 ∈ Vn . Observe that a clow sequence C ∈ C n,2k,1 with |c1 | = t is uniquely determined
by a pair of a clow c1 ∈ Ft and a clow sequence C ′ ∈ Gk−t . Furthermore, both can be
chosen independently. Therefore we have
! 
X X
qA,2k,t = ac  − sign(C ′ )aC ′  .
c∈Ft C ′ ∈G2k−t
P P
One of polynomial ( c∈Ft ac ) and (− C ′ ∈G2k−t sign(C ′ )aC ′ ) has degree t′ , and we de-
note it by α1 . The other is denoted by α2 . If t′ = k, we already have the decomposition
qA,2k,t = α1 α2 , and b-rank(qA,2k,t ) = 1 ≤ sk−t′ . Otherwise, by Lemma 5.6 there exist
′
sk−t′ polynomials β1 , β2 , . . . , βsk−t′ ∈ K[x](k−t ) and γ1 , γ2 , . . . , γsk−t′ ∈ K[x](k) such that
Psk−t′
α2 = i=1 βi γi . Then we have
sk−t′
X
qA,2k,t = (α1 βi ) · γi ,
i=1

and b-rank(qA,2k,t ) ≤ sk−t′ .

P2k
Proof of Proposition 5.2. By definition, pA,2k = (−1)n−2k t=1 qA,2k,t . By Lemma 5.7,
it holds that
2k
X k−1
X
b-rank(pA,2k ) ≤ b-rank(qA,2k,t) ≤ (n − 1) + 2 st ≤ n + 2(k − 1).
t=1 t=1

Acknowledgements
We are deeply grateful to Hiroshi Hirai, Kyo Nishiyama, Jun Tarui and Takeshi Tokuyama
for helpful comments improving the presentation of this paper. We are indebted to
Susumu Ariki for suggesting a formulation of the bi-polynomial rank, whereas our orig-
inal formulation was based on tensors of higher-order differentials, and was quite com-
plicated. We appreciate Hiroshi Hirai for pointing out the relation between our original
approach and the theory of the concave minimization. This work evolved from discus-
sions of monthly GCT seminars. We thank all the members (S. Ariki, N. Enomoto,
H. Hirai, H. Matsumoto, K. Nishiyama, J. Tarui and T. Tokuyama) of the seminar.
The author is supported by the ELC project (Grant-in-Aid for Scientific Research on
Innovative Areas MEXT Japan), and is partially supported by KAKENHI(26330023).

References
[1] F. Alizadeh. Interior point methods in semidefinite programming with applications
to combinatorial optimization. SIAM Journal on Optimization, 5(1):13–51, 1995.

18
 [2] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, vol-
ume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Prin-
ciples of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collabo-
ration of Thomas Lickteig.

[3] J. Cai, Xi Chen, and D. Li. Quadratic lower bound for permanent vs. determinant
in any characteristic. Computational Complexity, 19(1):37–56, 2010.

[4] J. Harris. Algebraic Geometry, volume 133 of Graduate Texts in Mathematics.

Springer-Verlag, New York, 1995. A first course, Corrected reprint of the 1992
original.

[5] Jr. J. E. Kelley. The cutting-plane method for solving convex programs. Journal
of the Society for Industrial and Applied Mathematics, 8:703–712, 1960.

[6] J. M. Landsberg. Tensors: geometry and applications, volume 128 of Graduate

Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.

[7] J. M. Landsberg, L. Manivel, and N. Ressayre. Hypersurfaces with degenerate duals

and the geometric complexity theory program. Commentarii Mathematici Helvetici,
88(2):469–484, 2013.

[8] M. Mahajan and V. Vinay. Determinant: combinatorics, algorithms, and complex-

ity. Chicago Journal of Theoretical Computer Science, page Article 5, 1997.

[9] M. Mahajan and V. Vinay. Determinant: old algorithms, new insights. SIAM
Journal on Discrete Mathematics, 12(4):474–490, 1999.

[10] T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent
problem. International Mathematics Research Notices, (79):4241–4253, 2004.

[11] K. D. Mulmuley and M. Sohoni. Geometric complexity theory. I. An approach to

the P vs. NP and related problems. SIAM Journal on Computing, 31(2):496–526,
2001.

[12] N. Nisan. Lower bounds for non-commutative computation. in: Proceedings of the
23rd ACM Symposium on Theory of Computing, ACM Press, 410–418, 1991.

[13] P. M. Pardalos and J. B. Rosen. Methods for global concave minimization: a

bibliographic survey. SIAM Review, 28(3):367–379, 1986.

[14] A. Shpilka and A. Yehudayoff. Arithmetic circuits: a survey of recent results and
open questions. Foundations and Trends in Theoretical Computer Science, 5(3-
4):207–388 (2010), 2009.

[15] H. Tuy. On outer approximation methods for solving concave minimization prob-
lems. Technical Report 108, Forschungsschwerpunkt Dynamische Systeme Univer-
sität Bremen, West Germany, 1983.

[16] L. G. Valiant. Completeness classes in algebra. in: Conference Record of the

Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979),
249–261. ACM, New York, 1979.

[17] L. G. Valiant. The complexity of computing the permanent. Theoretical Computer

Science, 8(2):189–201, 1979.

19
[18] L. G. Valiant. Why is Boolean complexity theory difficult? in: Boolean function
complexity (Durham, 1990), volume 169 of London Math. Soc. Lecture Note Ser.,
84–94. Cambridge Univ. Press, Cambridge, 1992.

[19] L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation

of polynomials using few processors. SIAM Journal on Computing, 12(4):641–644,
1983.

20