The proof complexity of matrix algebra - Newton Institute, Cambridge 2006

The Proof Complexity of Matrix Algebra
Michael Soltys
McMaster University, Canada
1

1. Quantiﬁed Permutation Frege (with Tim Paterson)
2. Steinitz Exchange Lemma
3. Clow Sequences
2

Quantiﬁed Permutation Frege 3

(∃ab)α ≡ (α(a, b) ∨ α(b, a)) ≡ (α ∨ α(ab)
)
(∀ab)α ≡ (α(a, b) ∧ α(b, a)) ≡ (α ∧ α(ab)
)

QPK
α, Γ → ∆
(∀ab)α , Γ → ∆
Γ → ∆, α
Γ → ∆, (∃ab)α
α, Γ → ∆
(∃ab)α , Γ → ∆
Γ → ∆, α
Γ → ∆, (∀ab)α
α is α or α(ab)
Restriction: for every β ∈ Γ ∪ ∆, (ab) ∈ Aut(β), i.e., β ≡ β(ab)
.

Haj´os Calculus
G¬S, π
g h
EF
S, π
f
−→
Σperm
1 -QPK∗
=
H∗
1
S, π

Haj´os Calculus
Axiom: K4 t
t
t
t

d
dd
Addition Rule: Add any number of vertices and/or edges.
Join Rule:
t
t
t
t

d
dd t
t
t
t

d
dd
=⇒
t
t
t
tt
t
ttj1 j2
j1 j2
i1
i
i2

d
dd
Contraction Rule: Contract two nonadjacent vertices into a
single vertex, and remove the resulting duplicated edges.

We can express k-colorability of graphs in ∃PLA.
Let 0i denote the i × i matrix of zeros.
Let G be a graph, and AG its adjacency matrix. We can state that
G is k-colorable, for any ﬁxed k, as follows:
(∃P)(∃i1, i2, . . . , ik)
bounded by size of AG
[PAGPt
=









0i1 ∗ · · · ∗
∗ 0i2 · · · ∗
...
...
...
...
∗ ∗ ∗ 0ik









]
Let non3col(X) be the negation of this formula with k = 3.
Let HC(X, Y ) be the (LA) formula stating that Y is a HC
derivation of X.
Theorem: ∀PLA HC(X, Y ) → non3col(X).

• ∀PLA HC(X, Y ) → non3col(X)
• H∗
1 p(|σ|) HC(X, Y ) → non3col(X) σ and so
H∗
1 p(|ˆσ|) HC( G¬S , π ) ˆσ → non3col( G¬S ) ˆσ.
• H∗
1 p(|ˆσ|) non3col( G¬S ) ˆσ → S

Steinitz Exchange Lemma 11
We encode a set of vectors {v1, v2, . . . , vn} as a matrix
T = [v1v2 . . . vn].
Steinitz Exchange Theorem (SET): if T is total, and E is
linearly independent, then there exists F ⊆ T, such that |F| = |E|,
and (T − F) ∪ E is total.
∃X, TX = I ∧ (∀Y = 0, EY = 0) → ∃F ⊆ T, |F| = |E| ∧ ∃X, (T − F ∪ E)X = I
So SET is a ΠB
2 formulas of QLA.

Given T, E, the matrix F can be computed in NC2
.
Suppose E = [e1e2] and T = [t1t2t3t4], then consider
[e1e2] [e1e2t1] [e1e2t1t2] [e1e2t1t2t3] [e1e2t1t2t3t4]
Independently for every i = 0, 1, 2, 3, if
rank([e1e2t1 . . . ti]) = rank([e1e2t1 . . . ti+1])
then put ti+1 in F.
Rank can be computed in NC2
with Mulmuley’s algorithm.

Mulmuley’s Algorithma
M is n × n matrix, pM (x) its char. poly. (Berkowitz’s alg.)
Geometric Rank : usual rank.
Algebraic Rank : n − (highest power of x that divides pM (x)).
Claim: RankG(M) = RankG(M2
) ⇒ RankG(M) = RankA(M).
Given M, let M be 

0 Mt
M 0


Clearly, rankG(M) = 1
2 rankG(M ).
M = M · diag(1, y, y2
, . . . , y2n−1
); rankG(M ) = rankG((M )2
).
Here y is an indeterminate, and M is a matrix over the ﬁeld F(y).
aParallel Linear Algebra, by Joachim von zur Gathen, chapter in Synthesis
of Parallel Algorithms.


0 Mt
M 0


2 rankG(M ).
M = M · diag(1, y, y2
, . . . , y2n−1
).


0 Mt
M 0


2 rankG(M ).
M = M · diag(1, y, y2
, . . . , y2n−1
).
y is an indeterminate, and M is a matrix over the ﬁeld F(y).

SET can be shown with PolyTime concepts.
Can it be shown with NC2
concepts?

SET proves in QLA the following principles
1. (∃B = 0)[AB = I ∨ AB = 0],
2. The columns of an n × (n + 1) matrix are linearly dependent,
3. Every matrix has an annihilating polynomial,
4. AB = I ⊃ BA = I,
5. Existence of An
, and the Cayley-Hamilton Thm.

QLA can prove the existence of powers of a matrix from SET.
Let POW(A, n) be the formula:
∃ X0X1 . . . Xn (∀i ≤ n)[X0 = I ∧ (i n ⊃ Xi+1 = Xi ∗ A)]
Show QLA (∃B = 0)[AB = I ∨ AB = 0] ⊃ POW(A, n).

Let N be the n2
× n2
matrix consisting of n × n blocks which are all
zero except for (n − 1) copies of A above the diagonal zero blocksa
.
Then Nn
= 0, and (I − N)−1
= I + N + N2
+ . . . + Nn−1
=








I A A2
. . . An−1
0 I A . . . An−2
...
...
...
0 0 0 . . . I








.
Set C = I − N.
Show that if CB = 0, then B = 0, using induction on the rows of
B, starting with the bottom row.
Using (∃B = 0)[CB = I ∨ CB = 0], conclude that there is a B such
that CB = I.
aA taxonomy of problems with fast parallel algorithms, by Stephen Cook.

Let N be the n2
× n2
.
Then Nn
= 0, and (I − N)−1
= I + N + N2
+ . . . + Nn−1
=








I A A2
. . . An−1
0 I A . . . An−2
...
...
...
0 0 0 . . . I








.
Set C = I − N.
that CB = I.

Let N be the n2
× n2
.
Then Nn
= 0, and (I − N)−1
= I + N + N2
+ . . . + Nn−1
=








I A A2
. . . An−1
0 I A . . . An−2
...
...
...
0 0 0 . . . I








.
Set C = I − N.
that CB = I. Finally, show that B = I + N + N2
+ · · · + Nn−1
.

Strong Linear Independence (SLI)
if {v1, . . . , vm} are n × 1, non-zero, linearly dependent vectors, then
there exists a 1 ≤ k m such that
{
lin. indep.
v1, . . . , vk, vk+1
lin. dep.
, vk+2, . . . , vm}

Csanky’s algorithm (NC2
) for computing the characteristic poly. of
a matrix uses
’s
symmetric polynomials:
s0 = 1,
sk =
1
k
k
i=1
(−1)i−1
sk−itr(Ai
)
pA(x) := s0xn
− s1xn−1
+ s2xn−2
− · · · ± snx0
.

Theorem: QLA proves the Cayley-Hamilton Thm. from SET
and SLI.
The 12 steps proof :
(1) pA is the characteristic polynomial of the matrix A as
computed by Csanky’s algorithm.
(2) Let W = {ei, Aei, . . . , An
ei}.
(3) By SET, W must be linearly dependent.
(4) By SLI there exists a k ≤ n such that
W0 = {ei, Aei, . . . , Ak−1
ei} is linearly independnet and k is the
largest such index.

(5) Ak
ei can be written as a linear combination of the vectors in
W0.
Let c1, . . . , ck be the coeﬃcients of this linear combination, so that
if g(x) = xk
+ c1xk−1
+ · · · + ck, then g(A)ei = 0.
(6) Let Ag be the k × k companion matrix of g,










0 0 0 . . . 0 −ck
1 0 0 . . . 0 −ck−1
0 1 0 . . . 0 −ck−2
...
...
...
0 0 0 . . . 1 −c1











(7) LAP proves pAg = g, and so LAP proves (pAg (A))ei = 0.
(8) Extend W0 to B = W0 ∪ {ej1 , . . . , ejn−k
}.
Existence of B follows from SET:
let T = B0 = the standard basis,
let E = W0, which is linearly independent,
let F = B0 − {ej1 , . . . , ejn−k
},
so B = (T − F) ∪ E.
A ∼


Ag E1
0 E2



(9) LAP proves that if C1 ∼ C2 then pC1 (x) = pC2 (x)
(tr(A) = tr(PAP−1
), since tr(AB) = tr(BA)).
(10) LAP proves that if
C =


C1 ∗
0 C2


then pC(x) = pC1 (x) · pC2 (x).
(11) ∴ pA(A)ei = (pAg (A) · pE(A))ei = pE(A) · (pAg (A)ei) = 0.
(12) This is true for all ei in the standard basis, and so pA(A) = 0.

Clow Sequences 31
det(A) =
σ∈Sn
sgn(σ)
n
i=1
aiσ(i).


1 2 3 4 5
3 5 4 1 2


Cycle cover representation of permutations

Clow Sequences 32
A clowa
(closed walk) is a walk (w1, . . . , wl) starting from vertex w1
and ending at the same vertex, where any (wi, wi+1) is an edge in
the graph.
Vertex w1 is the least-numbered vertex in the clow, and it is called
the head of the clow. We also require that the head occur only once
in the clow. This means that there is exactly one incoming edge
(wl, w1) and one outgoing edge (w1, w2) at w1.
A clow sequence is a sequence of clows (C1, . . . , Ck) with two
properties: (i) the sequence is ordered by heads:
head(C1) . . . head(Ck)
and (ii) the total number of edges, counted with multiplicity, adds
to n.
aDeterminant: Combinatorics, Algorithms, and Complexity, by M. Mahajan
and V. Vinay.

Clow Sequences 33
7 8 9 10 11 12 13 14 15
Clow (8, 11, 10, 12, 9, 10, 14)

Clow Sequences 34
det(A) =
C is a
clow sequence
sign(C)w(C)
=
C is a
clow sequence
with head of 1st clow 1
sgn(C)w(C)
=
C is a
clow sequence
with preﬁx property
sgn(C)w(C)
C = (C1, . . . , Ck) has the preﬁx property if ∀i k the total length
of C1, . . . , Ci−1 is at least head(Ci) − 1.

Clow Sequences 35
det(A) =
C is a
clow sequence
sign(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)

Clow Sequences 36
det(A) =
C is a
clow sequence
sign(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)

Clow Sequences 37
det(A) =
C is a
clow sequence
sign(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)

Clow Sequences 38
det(A) =
C is a
clow sequence
sign(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)
=
C is a
clow sequence
sgn(C)w(C)

Clow Sequences 39
A is n × n.
Deﬁne layered, directed, acyclic graph HA with three special
vertices: s, t+, t−
such that
det(A) =
ρ:s;t+
w(ρ) −
ρ:s;t−
w(ρ)
weight of path ρ is the product of weights of the edges appearing
on it.
Main Idea: s ; t+ (s ; t−) paths will be in 1-1 correspondence
with clow sequences of positive (negative) sign.

Clow Sequences 40
Vertices of HA: {s, t+, t−} together with
{[p, h, u, i] : p ∈ {0, 1} (parity), h, u ∈ [n], 0 ≤ i ≤ n − 1}
Meaning of the vertices: if a path ρ (starting from s) reaches a
vertex [p, h, u, i], this indicates that in the clow sequence being
constructed along this path:
• p is the parity of the quantity “n+(the number of components
already constructed),”
• h is the head of the clow currently being constructed,
• u is the vertex that the current clow has reached,
• and i is the number of edges traversed so far (in this and
preceding clows).
Finally, a path from s to t+ (t−) corresponds to a clow sequence of
positive (negative) parity.

Clow Sequences 41
The edges of HA:
Edge Condition Weight
(s, [b, h, h, 0]) h ∈ [n] and b = parity of n 1
([p, h, u, i] , [p, h, v, (i + 1)]) v h and (i + 1) n auv
([p, h, u, i] , [¯p, h , h , (i + 1)]) h h and (i + 1) n auh
([1, h, u, (n − 1)] , t+) auh
([0, h, u, (n − 1)] , t−) auh

Clow Sequences 42


a11 a12
a21 a22


[0,1,1,0]
[0,1,1,1]
[0,2,1,1]
[0,1,2,1]
[0,2,2,1]
[0,1,1,1]
[0,2,1,1]
[0,1,2,1]
[0,2,2,1]
[0,2,1,0] [0,1,2,0]
[0,2,2,0]
[0,1,1,0] [0,2,1,0][0,1,2,0] [0,2,2,0]
t- t+
s

Clow Sequences 43
For u, v, i ∈ [n] and p ∈ {0, 1} (Initialize values to 0)
V [p, u, v, (i − 1)] ← 0
V [t+] ← 0 and V [t−] ← 0
b ← parity of n
For u ∈ [n] (Set selected values at layer 0 to 1)
V [b, u, u, 0] ← 1
For i = 0 to (n − 2) (Process outgoing edges from each layer)
For u, v ∈ [n] such that u ≤ v and p ∈ {0, 1}
For w ∈ {u + 1, . . . , n}
V [p, u, w, (i + 1)] ← V [p, u, w, (i + 1)] + V [p, u, v, i] · avw
V [¯p, w, w, (i + 1)] ← V [¯p, w, w, (i + 1)] + V [p, u, v, i] · avu
For u, v ∈ [n] such that u ≤ v and p ∈ {0, 1}
V [t+] ← V [t+] + V [1, u, v, (n − 1)] · avu
V [t−] ← V [t−] + V [0, u, v, (n − 1)] · avu
Return V [t+] − V [t−]

Clow Sequences 44
• Running time: O(n4
)-many edges in HA, and one addition and
one multiplication per edge.
• Space: at each stage only the values of two adjacent layers are
required, so O(n2
) entries; each N many bits.
• To compute (pA)i, we sum over clow sequences of (n − i) many
edges: add ti
+, ti
−, for each i, and connect ti
+, ti
− to the
(n − i)-th layer.
• If V (ti
+) − V (ti
−) = 0, then i ≤ rankA, and rankA ≤ rankG, we
can conclude that the matrix has rank at least i.

Clow Sequences 45
• Pruning of HA: paths going through vertices of the form
[p, h, u, i] with h i + 1
cannot correspond to cycle covers (once h becomes a head, at
least (h − 1) edges should have been visited in the preceding
cycle).
• Prefix Property: Extend the prefix property to all the
coefficients,
(pA)i = (−1)n−i
C is an
(n − i)-clow sequence
sgn(C)w(C)
• Berkowitz’s algorithm computes over clows with the prefix
property . . .

The proof complexity of matrix algebra - Newton Institute, Cambridge 2006

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (17)

Similar to The proof complexity of matrix algebra - Newton Institute, Cambridge 2006

Similar to The proof complexity of matrix algebra - Newton Institute, Cambridge 2006 (20)

Recently uploaded

Recently uploaded (20)

The proof complexity of matrix algebra - Newton Institute, Cambridge 2006