The Linear Span of Uniform Matrix Product States
The variety of uniform matrix product states arises both in algebraic geometry as a natural generalization of the Veronese variety, and in quantum many-body physics as a model for a translation-invariant system of sites placed on a ring. Using methods from linear algebra, representation theory, and...
Saved in:
| Published in: | Symmetry, Integrability and Geometry: Methods and Applications |
|---|---|
| Date: | 2022 |
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2022
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/211805 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | The Linear Span of Uniform Matrix Product States. Claudia De Lazzari, Harshit J. Motwani and Tim Seynnaeve. SIGMA 18 (2022), 099, 18 pages |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860243957597863936 |
|---|---|
| author | De Lazzari, Claudia Motwani, Harshit J. Seynnaeve, Tim |
| author_facet | De Lazzari, Claudia Motwani, Harshit J. Seynnaeve, Tim |
| citation_txt | The Linear Span of Uniform Matrix Product States. Claudia De Lazzari, Harshit J. Motwani and Tim Seynnaeve. SIGMA 18 (2022), 099, 18 pages |
| collection | DSpace DC |
| container_title | Symmetry, Integrability and Geometry: Methods and Applications |
| description | The variety of uniform matrix product states arises both in algebraic geometry as a natural generalization of the Veronese variety, and in quantum many-body physics as a model for a translation-invariant system of sites placed on a ring. Using methods from linear algebra, representation theory, and invariant theory of matrices, we study the linear span of this variety.
|
| first_indexed | 2026-03-21T04:21:24Z |
| format | Article |
| fulltext |
Symmetry, Integrability and Geometry: Methods and Applications SIGMA 18 (2022), 099, 18 pages
The Linear Span of Uniform Matrix Product States
Claudia DE LAZZARI a, Harshit J. MOTWANI b and Tim SEYNNAEVE c
a) Dipartimento di Matematica, Università di Trento,
Via Sommarive 14, 38123 Povo (TN), Italy
E-mail: claudia.delazzari@unitn.it
b) Department of Mathematics: Algebra and Geometry, Ghent University, 9000 Gent, Belgium
E-mail: harshitjitendra.motwani@ugent.be
c) Department of Computer Science, KU Leuven, Celestijnenlaan 200A, 3001 Leuven, Belgium
E-mail: tim.seynnaeve@kuleuven.be
Received June 03, 2022, in final form December 15, 2022; Published online December 21, 2022
https://doi.org/10.3842/SIGMA.2022.099
Abstract. The variety of uniform matrix product states arises both in algebraic geometry
as a natural generalization of the Veronese variety, and in quantum many-body physics as
a model for a translation-invariant system of sites placed on a ring. Using methods from
linear algebra, representation theory, and invariant theory of matrices, we study the linear
span of this variety.
Key words: matrix product states; invariant theory of matrices
2020 Mathematics Subject Classification: 15A69; 20G05; 81P45
1 Introduction
Tensor networks are a powerful tool for the description of tensors living in a high dimensional
space. Since their original conception in quantum many-body physics [1, 15, 24], they have found
a wide range of applications in different fields, such as numerical tensor calculus [2, 9, 17, 23],
algebraic complexity theory [14], graphical models [28], and machine learning [6, 9]. In the
study of these varieties of tensors, some important general results and developments have been
achieved using methods from differential and complex geometry [19], algebraic geometry and
representation theory [3, 4, 5, 7, 8, 18, 21].
In this article, we focus on a particular type of tensor networks: uniform matrix prod-
uct states. From a quantum mechanics perspective, they model translation-invariant physical
systems of sites placed on a ring. The geometry of uniform matrix product states has been
extensively studied [10, 11, 19, 25], but our understanding of them is still far from complete,
and several fundamental mathematical problems remain open.
Our geometric point of view is the following: we fix a tensor space (Cn)⊗d, and consider the set
of all tensors in this space that admit a translation-invariant matrix product state representation,
with a given bond dimension m. After taking the closure of this set, we obtain an algebraic
variety, which we denote by uMPS(m,n, d). The ultimate goal would be to obtain a complete
description of this variety, i.e., to find all defining equations. Phrased in this generality, this
question is likely to be intractable. Indeed, even just determining which linear equations, if any,
vanish on our variety is poorly understood. This is precisely the goal of this paper:
Problem 1.1. Describe the linear span ⟨uMPS(m,n, d)⟩ of the variety uMPS(m,n, d). More
precisely:
� What is the dimension of ⟨uMPS(m,n, d)⟩? (Question 2.4)
mailto:claudia.delazzari@unitn.it
mailto:harshitjitendra.motwani@ugent.be
mailto:tim.seynnaeve@kuleuven.be
https://doi.org/10.3842/SIGMA.2022.099
2 C. De Lazzari, H.J. Motwani and T. Seynnaeve
� For which parameters m,n, d ∈ N does ⟨uMPS(m,n, d)⟩ fill the ambient space? (Ques-
tion 2.6)
� How does ⟨uMPS(m,n, d)⟩ decompose as a GLn-representation? (Question 2.9)
Note that since taking the Zariski closure of any set does not change its linear span, the space
⟨uMPS(m,n, d)⟩ is the linear span of all tensors that admit a uMPS representation with bond
dimension m.
The variety uMPS(m,n, d) does not only arise from tensor networks, it is also a very natural
geometric construction in its own right. Indeed, as we will soon see, uMPS(m,n, d) is the closed
image of the polynomial map that takes as input an n-tuple of m ×m matrices, and outputs
the traces of all d-fold products of the given matrices. In this way, it is a natural generalization
of the classical Veronese variety. Our main Problem 1.1 is therefore equivalent to the following:
Problem 1.2. Let A0, . . . , An−1 be m×m matrices with generic1 entries. Which linear relations
hold among the polynomials
Tr(Ai1 · · ·Aid),
where (i1, . . . , id) ∈ [n]d?
The ring generated by all polynomials Tr(Ai1 · · ·Aid), where the generic matrices are fixed
but we allow d to vary, is known as the trace algebra. In his classical work [27], Procesi described
how to obtain all relations between the generators of this ring in principle. Note however, that
the question we are asking is slightly different: we are only interested in relations between traces
of matrix products of a fixed length d.
This article is divided into three sections. In Section 2, we define the variety of uniform matrix
product states, and describe its natural symmetries. In Section 3, we undertake a computational
study of the space ⟨uMPS(m,n, d)⟩ in the smallest nontrivial case m = n = 2. We describe an
algorithm that can compute this space, viewed as a GL2-representation: more precisely, we
exploit and compute its decomposition into GL2-submodules. Based on this technique, we obtain
a conjectured formula for the character and, in particular, the dimension of the weight spaces,
and consequently of the whole space ⟨uMPS(2, 2, d)⟩. Section 4 contains our main theoretical
results. In Section 4.1, we introduce a powerful method to find linear equations that vanish on
⟨uMPS(m,n, d)⟩, based on the Cayley–Hamilton theorem:
Theorem 4.5. Let A0, . . . , Am, B be m×m matrices. Then for every ℓ ∈ N it holds that∑
σ∈Sm,τ∈Cm+1
sgn(σ) sgn(τ) Tr
(
Aτ(0)B
σ(0)Aτ(1)B
σ(1) · · ·Aτ(m−1)B
σ(m−1)Aτ(m)B
ℓ
)
= 0.
Here Sm is the symmetric group acting on {0, 1, . . . ,m−1}, and Cm+1 is the cyclic group acting
on {0, 1, . . . ,m}.
Theorem 4.5 actually gives nontrivial trace relations, i.e., linear relations that do not follow
either from cyclic permutations or reflections of the factors. As a corollary, we show that, already
for d at least quadratic in the bond dimension m, the linear span ⟨uMPS(m,n, d)⟩ does not fill
its natural ambient space Cycd(Cn), the space of cyclically symmetric tensors; significantly
improving the state of the art. More precisely, the linear span of the space of uniform matrix
product states is a proper subspace of the space of cyclically invariant tensors under the following
conditions:
1More formally: the entries of the Ai are the nm2 variables of a multivariate polynomial ring over C. See also
Definition 3.2.
The Linear Span of Uniform Matrix Product States 3
Corollary 4.6. If n ≥ 3 and d ≥ (m+1)(m+2)
2 , then uMPS(m,n, d) is contained in a proper
linear subspace of the space of cyclically invariant tensors.
In Section 4.2 we study the special case m = n = 2, based on the computations in Sec-
tion 4.1, and, using the trace parametrization, we provide an upper bound on the dimension of
⟨uMPS(2, 2, d)⟩ which is close to optimal. Moreover, we take some first steps towards proving
our conjectured character formulas: in the first cases, i.e., for the first few weights, we can
provide an explicit basis of generators for the weight spaces of the representation, again using
our Cayley–Hamilton technique.
2 Preliminaries
We once and for all fix three parameters m,n, d∈N. We will consider tensors in the space (Cn)⊗d.
The standard basis of Cn will be written as {e0, . . . , en−1}. We abbreviate the set {0, . . . , n− 1}
to [n].
Definition 2.1. The uniform Matrix Product State parametrization is given by the map
ϕ : (Cm×m)n → (Cn)⊗d,
(A0, . . . , An−1) 7→
∑
0≤i1,...,id≤n−1
Tr(Ai1 · · ·Aid) ei1 ⊗ · · · ⊗ eid . (2.1)
We denote the image of this map by uMPS◦(m,n, d). The closure of uMPS◦(m,n, d) in the
Euclidean or equivalently Zariski topology over the complex numbers, is the algebraic variety of
uniform matrix product states, denoted by uMPS(m,n, d).
Remark 2.2. If we think of (Cm×m)n as the space of m × m × n tensors, then the uMPS
parametrization takes a tensor in this space and contracts it d times with itself in a circle; see
Figure 1.
n
m m 7→
· · ·
n n n n
m m m m
d sites
m
Figure 1. Graphical representation of map (2.1) defining uMPS(m,n, d). There are in total d tensors
of order m×m×n, contracted along the respective edges. The parameters m and n are called bond and
physical dimension, respectively. The bond dimensions associated to the edges of the graph represent the
dimension of the vector spaces along which the tensor contraction takes place.
Remark 2.3. An alternative name for uMPS is translation invariant matrix product states with
periodic boundary conditions [10, 25]. The name “uniform matrix product states” is sometimes
reserved for the thermodynamic limit, where the number d of sites approaches infinity. Our
terminology is consistent with [11, 19].
As mentioned in the introduction, the main question we will try to answer in this article is
the following:
Question 2.4. Determine the linear span of uMPS(m,n, d); i.e., the smallest vector subspace
of (Cn)⊗d containing uMPS(m,n, d). In particular: what is the dimension of this space?
4 C. De Lazzari, H.J. Motwani and T. Seynnaeve
2.1 Cyclic and symmetric invariance
The space (Cn)⊗d comes equipped with an action of the symmetric group Sd: for σ ∈ Sd and
ω = v1 ⊗ · · · ⊗ vd ∈ (Cn)⊗d we have
σ · (v1 ⊗ · · · ⊗ vd) = vσ−1(1) ⊗ · · · ⊗ vσ−1(d).
The symmetric group Sd naturally contains the cyclic group Cd and the dihedral group D2d
as subgroups. To be precise: let r, s ∈ Sd be the cyclic permutation and reflection defined
respectively by
r(i) = i+ 1(mod d) and s(i) = d+ 1− i,
then Cd ⊆ Sd is the cyclic subgroup generated by r, and D2d is the subgroup generated by r
and s. The cyclically symmetric tensors and dihedrally symmetric tensors are then the elements
of (Cn)⊗d that are invariant under the action of these subgroups:
Cycd(Cn) :=
{
ω ∈ (Cn)⊗d | σ · ω = ω ∀σ ∈ Cd
}
,
Dihd(Cn) :=
{
ω ∈ (Cn)⊗d | σ · ω = ω ∀σ ∈ D2d
}
.
Note that both are linear subspaces of (Cn)⊗d, and that Dihd(Cn) ⊆ Cycd(Cn), where the
inclusion is strict unless d ≤ 2 or n = 2 and d ≤ 5.
Observation 2.5. The set uMPS(m,n, d) is a subset of the space of cyclically invariant tensors
Cycd(Cn) ⊂ (Cn)⊗d because of the trace invariance under cyclic permutations of the matrices:
given M1, . . . ,Md ∈ Cm×m then
Tr(M1 · · ·Md) = Tr(Mσ(1) · · ·Mσ(d)),
for σ ∈ Cd.
In other words, we can think of uMPS(m,n, d) as a subvariety of the ambient space Cycd(Cn).
As noted in [11, Corollary 3.18], if we fix n and d and let m grow, the space uMPS(m,n, d) will
eventually fill this entire ambient space.
Question 2.6. For fixed n and d, what is the smallestm such that ⟨uMPS(m,n, d)⟩=Cycd(Cm)?
It is known that for m = d, equality holds [11, Proposition 3.11]. On the other hand, it
follows from a dimension count ([11, Theorem 3.14], see also [22]) that if d ≫ m, the inclusion
⟨uMPS(m,n, d)⟩ ⊂ Cycd(Cn) is strict. In Section 4.1 we will prove that already for d = O
(
m2
)
,
we have a strict inclusion.
Observation 2.7. In the case m = n = 2, we have the stronger inclusion
uMPS(2, 2, d) ⊆ Dihd(Cn).
This is a consequence of the identity Tr(Ai1 · · ·Aid) = Tr(Aid · · ·Ai1), which holds for any pair
of 2× 2 matrices A0, A1 and sequence i1, . . . , id with ij ∈ {0, 1}. See [16, Theorem 1.1]
Example 2.8. We consider uMPS(2, 2, 6). For every A0, A1 ∈ C2×2, we have the trace relation
Tr
(
A2
0A
2
1A0A1
)
= Tr
(
A1A0A
2
1A
2
0
)
, that does not come from invariance of trace under cyclic
permutations of the matrices.
The Linear Span of Uniform Matrix Product States 5
2.2 GLn-invariance
The general linear group GLn naturally acts on the space (Cn)⊗d: given g ∈ GLn and ω =
v1 ⊗ · · · ⊗ vd ∈ (Cn)⊗d, we have
g · (v1 ⊗ · · · ⊗ vN ) = (g · v1)⊗ · · · ⊗ (g · vN ).
Clearly, Cycd(Cn) and Dihd(Cn) are invariant under this action. The following computation
shows that uMPS(m,n, d) is invariant under this action as well:
g · ϕ(A1, . . . , An) =
n∑
j1,...,jd=1
Tr(Aj1 · · ·Ajd)
( n∑
i1=1
gi1,j1ei1
)
⊗ · · · ⊗
( n∑
id=1
gid,jdeid
)
=
n∑
j1,...,jd=1
n∑
i1,...,id=1
gi1,j1 · · · gid,jd Tr(Aj1 · · ·Ajd) ei1 ⊗ · · · ⊗ eid
=
n∑
j1,...,jd=1
n∑
i1,...,id=1
Tr(gi1,j1Aj1 · · · gid,jdAjd) ei1 ⊗ · · · ⊗ eid
=
n∑
i1,...,id=1
Tr
[( n∑
j1=1
gi1,j1Aj1
)
· · ·
( n∑
jd=1
gid,jdAjd
)]
ei1 ⊗ · · · ⊗ eid
= ϕ
( n∑
j=1
g1,jAj , . . . ,
n∑
j=1
gn,jAj
)
.
This means that the space ⟨uMPS(m,n, d)⟩ we are interested in is naturally a representa-
tion of GLn. In the remainder of this subsection, we briefly recall what we will use about
representation theory of GLn, and fix notation.
We once and for all fix a torus T ⊂ GLn, consisting of all diagonal matrices; and identify T
with (C∗)n. For λ = (λ0, . . . , λn−1) ∈ Zn and t = diag(t0, . . . , tn−1) ∈ T , we write tλ =
tλ0
0 · · · t
λn−1
n−1 ∈ C∗. Let V be any representation of GLn. For any λ ∈ Zn, the weight space Vλ is
defined as
Vλ =
{
v ∈ V | t · v = tλv ∀t ∈ T
}
.
It is a well-known fact from representation theory that
V =
⊕
λ∈Zn
Vλ
as vector spaces; and that knowing the dimensions of the weight spaces uniquely determines the
representation V up to isomorphism. The polynomial
χV =
∑
λ∈Zn
(dimVλ)tλ
is known as the character of V . If we view our representation as a morphism ρ : GLn → GL(V ),
the character χV is equal to Tr(ρ(diag(t0, . . . , tn−1))).
So we can refine our main Question 2.4 to:
Question 2.9. Let V = ⟨uMPS(m,n, d)⟩, viewed as a GLn-representation. For every weight
λ ∈ Zn, determine the dimension of the weight space Vλ.
6 C. De Lazzari, H.J. Motwani and T. Seynnaeve
2.3 Words, necklaces and bracelets
As a warm-up, let us consider the classical representation V = (Cn)⊗d. Its character is equal
to (t1 + · · ·+ tn)d, and by expanding we find that dimVλ is equal to the multinomial coefficient(
d
λ1,...,λn
)
if
∑
λi
= d, and zero otherwise. We can also see this in terms of coordinates, and this
will be useful later:
Definition 2.10. A word of length d on the alphabet [n] is just an ordered tuple I = (i1, . . . , id),
with ij ∈ [n]. The weight of a word I is a tuple w(I) = (w0, . . . , wn−1) ∈ Zn, where wi is the
number of entries in I that are equal to i.
For every word I = (i1, . . . , id), we can define a vector eI := ei1 ⊗· · ·⊗ eid . The space (Cn)⊗d
has a basis given by the eI , where I runs over all words of length d on the alphabet [n]. In
addition, every eI is a weight vector of weight w(I). So the dimension of the weight space Vλ is
the number of words of weight λ, which is indeed the multinomial coefficient
(
d
λ1,...,λn
)
.
We move on to the subrepresentations Cycd(Cn) and Dihd(Cn), the natural ambient spaces
for uniform matrix product states.
Definition 2.11. A necklace (of length d on the alphabet [n]) is an equivalence class of words,
where two words are equivalent if they agree up to the action Cd. A bracelet (of length d on
the alphabet [n]) is an equivalence class of words, where two words are equivalent if they agree
up to the action D2d. For a fixed necklace or bracelet, all words in the equivalence class clearly
have the same weight; this is the weight of the necklace or bracelet. We denote by N(n, d), resp.
B(n, d), the set of necklaces, resp. bracelets, of length d on [n] and by Nλ(n, d) ⊂ N(n, d), resp.
Bλ(n, d) ⊂ B(n, d), the subset of elements of weight λ ∈ Zn.
To every necklace N ∈ N(n, d), we associate a basis vector eN := 1
d
∑
σ∈Cd
σ · eI , where I is
any representative of N . Then Cycd(Cn) has a basis given by {eN : N ∈ N(n, d)}. Moreover,
eN is a weight vector of weight w(N), hence we find that the dimension of the weight space of
weight λ is given by the number |Nλ(n, d)| of necklaces of weight λ.
Remark 2.12. The number |N(n, d)| of necklaces of length d on [n] can be counted by the
following formula, see for instance [30, Theorem 7.10]:
dim Cycd(Cn) = |N(n, d)| = 1
d
∑
l|d
ϕ(l)n
d
l , (2.2)
where φ is Euler’s totient function. There is also a formula for |Nλ(n, d)| = dim Cycd(Cn)λ: it
is equal to the coefficient of xλ0
0 · · ·x
λn−1
n−1 in the polynomial
1
d
∑
ℓ|d
(
x
d/ℓ
0 + · · ·+ x
d/ℓ
n−1
)ℓ
φ
(
d
ℓ
)
. (2.3)
To every bracelet b ∈ B(n, d), we associate a basis vector eb := 1
2d
∑
σ∈D2d
σ · eI , where I is
a representative of b. Then Dihd(Cn) has a basis given by {eb : b ∈ B(n, d)}, and the dimension
of the weight space of weight λ is given by the number |Bλ(n, d)| of bracelets of weight λ.
Remark 2.13. The number of bracelets of length d on [n] is given by
dim Dihd(Cn) = |B(n, d)| =
1
2
|N(n, d)|+ 1
4
(n+ 1)nd/2 for d even,
1
2
|N(n, d)|+ 1
4
n(d+1)/2 for d odd.
(2.4)
The Linear Span of Uniform Matrix Product States 7
We only state the formula for |Bλ(n, d)| in the case of binary bracelets (i.e. n = 2), as that is
the only case that is relevant to us:
|B(w,d−w)(2, d)| =
1
2d
∑
l| gcd(d,w)
φ(l)
( d
l
w
l
) +
1
2
(d
2 − 1
w−1
2
)
for w odd, 1
2d
∑
l| gcd(d,w)
φ(l)
( d
l
w
l
) +
1
2
( d
2
w
2
)
for w even.
(2.5)
Equations (2.2)–(2.5) can be derived from the Pólya enumeration theorem [26] applied to the
action of the cyclic and the dihedral group, respectively.
3 Computations
In this section, we describe how to computationally answer Question 2.9 for fixed parameters. We
focus on the smallest interesting case m = n = 2. In this case we are dealing with representations
of GL2, so the weights are in Z2. Moreover, the only occurring weights in
(
C2
)⊗d
are tw0 t
d−w
1 for
w = 0, . . . , d. For subrepresentations of
(
C2
)⊗d
, we will abbreviate the weight spaces V(w,d−w)
to Vw. Our goal is to determine the dimension of the weight spaces ⟨uMPS(2, 2, d)⟩w.
All of our dimension counts in this section and the next use the following easy observation.
Observation 3.1. For p1, . . . , pN ∈ C[y1, . . . , ys] polynomials, and X the image of the polyno-
mial map
Cs → CN ,
(y1, . . . , ys) 7→ (p1(y1, . . . , ys), . . . , pN (y1, . . . , ys)),
(3.1)
a linear equation
∑
αixi vanishes on X if and only if the identity
∑
αipi = 0 holds in the
polynomial ring C[y1, . . . , ys]. In particular, the dimension of the linear span of X is equal to
the dimension of the subspace of C[y1, . . . , ys] spanned by the pi’s.
3.1 The trace parametrization
If we directly use Definition 2.1, we see that uMPS(2, 2, d) is the closed image of a polynomial
map C8 → Dihd
(
C2
)
. However, in this specific case there is an alternative parametrization
by C5 instead of C8: the trace parametrization, which appears to be computationally more
efficient in practice. It is based on the connection between uniform matrix product states and
invariant theory of matrices.
Definition 3.2. Let
R = C
[(
akij
)
1≤i,j≤m;1≤k≤n
]
be the polynomial ring in m2n variables, and for k = 0, . . . , n − 1, let Ak :=
(
akij
)
1≤i,j≤m
be generic m × m matrices. The trace algebra Cm,n is the subalgebra of R generated by the
polynomials Tr(Ai1 · · ·Ais), where (i1, . . . , is) runs over all words (or equivalently: necklaces)
in [n].
Remark 3.3. The trace algebra is precisely the subring of R consisting of all elements that are
invariant under simultaneous conjugation:
f ∈ Cm,n ⇐⇒ f
(
P−1A0P, . . . , P
−1An−1P
)
= f(A0, . . . , An−1) ∀P ∈ GLm.
This is known as the first fundamental theorem in the invariant theory of matrices [27, 29].
8 C. De Lazzari, H.J. Motwani and T. Seynnaeve
Proposition 3.4 ([29, Corollary 2]). The trace algebra C2,2 is generated by the following five
polynomials:
Tr(A0), Tr(A1), Tr
(
A2
0
)
, Tr(A0A1), Tr
(
A2
1
)
,
and moreover, there are no polynomial relations between these generators.
Corollary 3.5. For every bracelet b = (b1, . . . , bk), there is a unique polynomial
Pb(T0, T1, T00, T01, T11) ∈ C[T0, T1, T00, T01, T11]
such that for every pair (A0, A1) of 2× 2 matrices, the following equality holds:
Tr(Ab1 · · ·Abk) = Pb
(
Tr(A0),Tr(A1),Tr
(
A2
0
)
,Tr(A0A1),Tr
(
A2
1
))
.
Remark 3.6. If we give the ring C[T0, T1, T00, T01, T11] a grading by putting deg(T0) = deg(T1)
= 1 and deg(T00) = deg(T01) = deg(T11) = 2, then the polynomial Pb is homogeneous of degree
length(b).
The above means that uMPS(2, 2, d) is the image of the polynomial map
ψ : C5 → Dihd
(
C2
)
,
(T0, T1, T00, T01, T11) 7→
∑
b
Pb(T0, T1, T00, T01, T11)eb,
(3.2)
where b runs over all bracelets of length d. This is the trace parametrization.
In order to compute the polynomials Pb, for bracelets of length 3, one verifies that
P000 = −1
2
T 3
0 +
3
2
T0T00, P100 = −1
2
T 2
0 T1 +
1
2
T1T00 + T0T01,
P110 = −1
2
T0T
2
1 +
1
2
T0T11 + T1T01, P111 = −1
2
T 3
1 +
3
2
T1T11.
For bracelets of length ≥ 4, we can inductively use the following identity [29], which holds
for every quadruple (A,B,C,D) of 2× 2 matrices:
2 Tr(ABCD) = Tr(A)(Tr(BCD)− Tr(B) Tr(CD)) + Tr(B)(Tr(CDA)− Tr(C) Tr(DA))
+ Tr(C)(Tr(DAB)− Tr(D) Tr(AB))
+ Tr(D)(Tr(ABC)− Tr(A) Tr(BC))− Tr(AC) Tr(BD)
+ Tr(AB) Tr(CD) + Tr(AD) Tr(BC) + Tr(A) Tr(B) Tr(C) Tr(D).
3.2 Computing the character
The weight space ⟨uMPS(2, 2, d)⟩w is the linear span of the image of the map
C5 → Dihd
(
C2
)
w
,
(T0, T1, T00, T01, T11) 7→
∑
b
Pb(T0, T1, T00, T01, T11)eb,
where b ranges over all bracelets of weight w. By Observation 3.1, we need to compute the
dimension of the linear subspace of C[T0, T1, T00, T01, T11] spanned by the Pb’s. This can be
computed by putting the coefficients of the Pb’s in a matrix and computing its rank.
Putting everything together, we obtain Algorithm 1, which for a given d computes the char-
acter (in particular the dimension) of ⟨uMPS(2, 2, d)⟩. We implemented this algorithm in Sage-
Math [13].
The results are summarized in Table 1, where we write Dw := dim⟨uMPS(2, 2, d)⟩w. For
d < 8, the space ⟨uMPS(2, 2, d)⟩ is equal to the ambient space Dihd
(
C2
)
.
Based on these computations, we make the following conjecture:
The Linear Span of Uniform Matrix Product States 9
Algorithm 1: Linear span of ⟨uMPS(2, 2, d)⟩
Data: d
Result: Character of the representation ⟨uMPS(2, 2, d)⟩
T0 ← Tr(A0); T1 ← Tr(A1); T00 ← Tr
(
A2
0
)
; T01 ← Tr(A0A1); T11 ← Tr
(
A2
1
)
;
for ℓ = 3 to d do
bracelets = bracelets of length ℓ;
for b in bracelets do
P[b] ← Tr(Ab1 · · ·Abℓ), expressed in the Ti;
end
end
for w = 0 to d do
List the monomials yα1 , . . . ,yαt appearing in the P [b], where b ranges over all
bracelets of weight w;
Write P [b] =
∑
j βb,jy
αj ;
Compute the rank of the matrix (βb,j)b,j ;
end
Conjecture 3.7.
dim⟨uMPS(2, 2, d)⟩w
=
1 +
d(v − 1)v
2
− 2(v − 1)v(2v − 1)
3
+ v
⌊
d
2
⌋
− 2v2 + v for w = 2v,
1 +
dv(v + 1)
2
− 2v(v + 1)(2v + 1)
3
for w = 2v + 1.
This would in particular imply:
Conjecture 3.8 (Corollary of Conjecture 3.7).
dim⟨uMPS(2, 2, d)⟩ =
1
192
(
d4 − 4d2 + 192d+ 192
)
for d even,
1
192
(
d4 − 10d2 + 192d+ 201
)
for d odd.
3.3 Higher degree equations
Equations of tensor varieties such as secant varieties of the Segre variety or Veronese variety are
well known to be hard to compute. For uniform matrix product states, Critch and Morton gave
a complete description of the ideal of uMPS(2, 2, 4) and uMPS(2, 2, 5) and several linear equation
of uMPS(2, 2, d) are given for d until 12, cf. [10]. The generators of the ideal of uMPS(2, 2, d)
for d = 4, 5, 6 are given in [11].
Our algorithm from the previous section computes the linear span of uMPS(2, 2, d), which is
equivalent to computing the degree 1 part of its defining ideal. With some small modifications,
one can obtain an algorithm to compute the degree k part of the defining ideal, viewed as
a GL2-representation. In this paper we will only give a brief sketch of this algorithm. For
a more detailed account, including the use of raising operators to speed up the algorithm, we
refer the reader to [12].
We first consider a slightly more general setting: let X be any variety that is given as the
closed image of a homogeneous polynomial map p : Cs → CN as in (3.1), and let I be its
(homogeneous) defining ideal. Suppose that p is compatible with a given GLn-action on Cs
10 C. De Lazzari, H.J. Motwani and T. Seynnaeve
Table 1. Character of ⟨uMPS(2, 2, d)⟩. Since Dw = Dd−w (more generally: for every GL2-represen-
tation V we have that V(b0,b1) = V(b1,b0)), we only list Dw for w ≤
⌈
d
2
⌉
. The dimension of ⟨uMPS(2, 2, d)⟩
equals twice the sum of the Dw’s if d is odd, and twice the sum of the Dw’s minus the last Dw if d is
even.
d D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 dim⟨uMPS(2, 2, d)⟩ dim Dihd
(
C2
)
8 1 1 4 5 7 29 30
9 1 1 4 6 8 40 46
10 1 1 5 7 11 11 61 78
11 1 1 5 8 12 14 82 126
12 1 1 6 9 15 17 20 118 224
13 1 1 6 10 16 20 23 154 380
14 1 1 7 11 19 23 29 29 211 687
15 1 1 7 12 20 26 32 35 268 1224
16 1 1 8 13 23 29 38 41 45 353 2250
17 1 1 8 14 24 32 41 47 51 438 4112
18 1 1 9 15 27 35 47 53 61 61 559 7685
19 1 1 9 16 28 38 50 59 67 71 680 14310
20 1 1 10 17 31 41 56 65 77 81 86 846 27012
and CN . Then for every k ∈ N, the degree k part Ik is naturally a GLn-representation. Fix
a weight w and consider the map
pkw : Cs p−→ CN νk−→ SkCN πw−−→
(
SkCN
)
w
,
where νk is the k’th Veronese embedding and πw is the projection onto the weight space. The
latter map commutes with the action of the torus. Then, the weight space Ik,w ⊆
(
SkCN
)∗
w
is
equal to〈
ℑ(pkw)
〉⊥ ∼= (
SkCN/
〈
ℑ
(
pkw
)〉)∗
,
see for example [20, Proposition 4.4.1.1]. The character of this representation is given by the
difference of the characters of
〈
ℑ
(
pkw
)〉
and SkCN . The latter character can be computed from
the character of CN , and hence we are left to compute the character of
〈
ℑ
(
pkw
)〉
.
In the case X = uMPS(2, 2, d), we can compute the character of
〈
ℑ
(
pkw
)〉
using a minor
modification of Algorithm 1, where in the second loop we replace the collection of polynomials
{P [b] | weight(b) = w} with their k-fold products{ k∏
j=1
P [bj ] |
∑
j
weight(bj) = w
}
.
Using this algorithm, we computed I(uMPS(2, 2, d))2 for d ≤ 10 and I(uMPS(2, 2, d))3 for
d ≤ 9. Our code is available at [13], and our results are summarized in Tables 2 and 3.
4 Results
4.1 Linear relations via Cayley–Hamilton
We recall the classical Cayley–Hamilton theorem. We use this result in order to find linear
equations for uMPS(m,n, d+ k), k ≥ m based on linear equations for uMPS(m,n,N), N =
d, d+ 1, . . . , d+m− 1.
The Linear Span of Uniform Matrix Product States 11
Table 2. Character of I(uMPS(2, 2, d))∗2. Since Dw = D2d−w (again: for every GL2-representation V
we have that V(b0,b1) = V(b1,b0)), we only list Dw for w ≤ d.
d D3 D4 D5 D6 D7 D8 D9 D10
6 0 1 1 2
7 0 1 3 6 7
8 0 5 10 25 32 42
9 1 7 21 48 79 110 119
10 1 14 38 100 176 290 360 408
Table 3. Character of I(uMPS(2, 2, d))∗3. Since Dw = D3d−w, we only list Dw for w ≤
⌈
3d
2
⌉
.
d D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13
6 0 1 2 8 11 17 17
7 0 1 4 15 29 49 67 77
8 0 5 14 51 101 198 292 414 478 532
9 1 7 26 83 191 388 671 1039 1431 1784 1983
Theorem 4.1 (Cayley–Hamilton). Let A ∈ Cm×m be a m ×m complex matrix and pA(λ) =
det(λ Idm − A) its characteristic polynomial. Then pA(A) = 0 where pA(·) is the corresponding
matrix-valued polynomial.
In fact, the only thing we will use is the following statement, which (since deg pA = m)
immediately follows from Theorem 4.1.
Corollary 4.2. Let A ∈ Cm×m. Then Ak, for k ≥ m can be written as a linear combination of
its previous powers.
Lemma 4.3. Let c = (c1, . . . , cs) ∈ Cs be a vector of coefficients and
{
ijℓ
}
1≤ℓ≤d,1≤j≤s
be indices;
with ijℓ ∈ [n]. Assume that for every n-tuple (A0, . . . , An−1) of m×m matrices and every k < m
the following identity holds:
s∑
j=1
cj Tr
(
A
ij1
· · ·A
ijd
Ak
0
)
= 0. (4.1)
Then the same identity holds for arbitrary k ∈ N.
Proof. We use induction on k ≥ m. By Corollary 4.2, Ak
0 can be written as a linear combination
of its previous powers Al
0, for l = 0, . . . ,m− 1. Therefore, we have
s∑
j=1
cj Tr
(
A
ij1
· · ·A
ijd
Ak
0
)
=
s∑
j=1
cj Tr
[
A
ij1
· · ·A
ijd
(m−1∑
l=0
γlA
l
0
)]
=
s∑
j=1
cj
m−1∑
l=0
γl
(
Tr
(
A
ij1
· · ·A
ijd
Al
0
))
=
m−1∑
l=0
γl
( s∑
j=1
cj
(
Tr
(
A
ij1
· · ·A
ijd
Al
0
)))
= 0. ■
12 C. De Lazzari, H.J. Motwani and T. Seynnaeve
The usefulness of Lemma 4.3 stems from the fact that one can find expressions of the
form (4.1) which are trivial for small k, in the sense that they follow from the cyclic invari-
ance of the trace, but nontrivial for large k. We illustrate this in the example below.
Example 4.4. We show that for any 2×2 matrices A0, A1, A2, A3 and any k ≥ 0, the following
identity holds
Tr
(
A1A2A0A3A
k
0
)
+ Tr
(
A2A3A0A1A
k
0
)
+ Tr
(
A3A1A0A2A
k
0
)
= Tr
(
A1A0A2A3A
k
0
)
+ Tr
(
A2A0A3A1A
k
0
)
+ Tr
(
A3A0A1A2A
k
0
)
.
By the above argument, it suffices to show the identity for k = 0 and k = 1. But these both
follow from cyclic invariance of the trace:
Tr(A1A2A0A3) + Tr(A2A3A0A1) + Tr(A3A1A0A2)
= Tr(A1A0A2A3) + Tr(A2A0A3A1) + Tr(A3A0A1A2),
Tr(A1A2A0A3A0) + Tr(A2A3A0A1A0) + Tr(A3A1A0A2A0)
= Tr(A1A0A2A3A0) + Tr(A2A0A3A1A0) + Tr(A3A0A1A2A0).
This immediately gives us a nontrivial linear relation on uMPS(2, 4, d), for d ≥ 6. But we
can also find linear relations on uMPS(2, 2, d). For instance, if we put k = 2, A2 = A2
1 and
A3 = A0A1, we find
Tr
(
A3
1A
2
0A1A
2
0
)
+ Tr
(
A2
1A0A1A0A1A
2
0
)
+ Tr
(
A2
1A
3
0A
2
1A0
)
= Tr
(
A2
1A0A1A
2
0A1A0
)
+ Tr
(
A2
1A
2
0A
2
1A
2
0
)
+ Tr
(
A3
1A
3
0A1A0
)
,
which is the unique linear relation on uMPS(2, 2, 8) that doesn’t follow from dihedral symmetry.
Theorem 4.5. Let A0, . . . , Am, B be m×m matrices. Then for every ℓ ∈ N it holds that∑
σ∈Sm,τ∈Cm+1
sgn(σ) sgn(τ) Tr
(
Aτ(0)B
σ(0)Aτ(1)B
σ(1) · · ·Aτ(m−1)B
σ(m−1)Aτ(m)B
ℓ
)
= 0. (4.2)
Here Sm is the symmetric group acting on {0, 1, . . . ,m−1}, and Cm+1 is the cyclic group acting
on {0, 1, . . . ,m}.
Proof. We will first show the statement for ℓ ∈ {0, 1, . . . ,m − 1}. So let us fix such an ℓ. We
will write
T (σ, τ) := Tr
(
Aτ(0)B
σ(0)Aτ(1)B
σ(1) · · ·Aτ(m−1)B
σ(m−1)Aτ(m)B
ℓ
)
.
Let us write ca for the permutation that cyclically permutes the first a elements. Precisely
ca(i) =
i+ 1 for i < a− 1,
0 for i = a− 1,
i for i > a− 1.
Step 1. For σ ∈ Sm and τ ∈ Cm+1, we define
σ̃ := σ ◦ c−1
σ−1(ℓ)+1
◦ cσ−1(ℓ)+1
m , τ̃ := τ ◦ cσ
−1(ℓ)+1
m+1 .
We have T (σ, τ) = T (σ̃, τ̃).
Indeed, if we write k = σ−1(ℓ), then
T (σ, τ) = Tr
(
Aτ(0)B
σ(0) · · ·Aτ(k)B
σ(k)Aτ(k+1)B
σ(k+1) · · ·Aτ(m−1)B
σ(m−1)Aτ(m)B
σ(k)
)
= Tr
(
Aτ(k+1)B
σ(k+1) · · ·Aτ(m)B
σ(k)Aτ(0)B
σ(0) · · ·Aτ(k−1)B
σ(k−1)Aτ(k)B
σ(k)
)
= T (σ̃, τ̃).
Where for the last step, note that
The Linear Span of Uniform Matrix Product States 13
� k + 1 = ck+1
m+1(0), . . . , m = ck+1
m+1(m− k − 1), 0 = ck+1
m+1(m− k), . . . , k = ck+1
m+1(m),
� k + 1 = c−1
k+1
(
ck+1
m (0)
)
, . . . , m − 1 = c−1
k+1
(
ck+1
m (m − k − 2)
)
, k = c−1
k+1
(
ck+1
m (m − k − 1)
)
,
0 = c−1
k+1
(
ck+1
m (m− k)
)
, . . . , k − 1 = c−1
k+1
(
ck+1
m (m− 1)
)
.
Step 2. Note that the assignment
Sm × Cm+1 → Sm × Cm+1,
(σ, τ) 7→ (σ̃, τ̃)
is an involution. Indeed, we have
σ̃−1(ℓ) = c−σ−1(ℓ)−1
m
(
cσ−1(ℓ)+1
(
σ−1(ℓ)
))
= c−σ−1(ℓ)−1
m (0) = m− σ−1(ℓ)− 1.
So, again writing k = σ−1(ℓ),
˜̃σ = σ̃ ◦ c−1
σ̃−1(ℓ)+1
◦ cσ̃−1(ℓ)+1
m = σ ◦ c−1
k+1 ◦ c
k+1
m ◦ c−1
m−k ◦ c
m−k
m = σ.
To see the last equality:
� for i < k: c−1
k+1
(
ck+1
m
(
c−1
m−k
(
cm−k
m (i)
)))
= c−1
k+1
(
ck+1
m
(
c−1
m−k(m − k + i)
))
= c−1
k+1
(
ck+1
m (m −
k + i)
)
= c−1
k+1(i+ 1) = i,
� for i = k: c−1
k+1
(
ck+1
m
(
c−1
m−k(cm−k
m (k))
))
= c−1
k+1
(
ck+1
m
(
c−1
m−k(0)
))
= c−1
k+1
(
ck+1
m (m− k− 1)
)
=
c−1
k+1(0) = k,
� for i > k: c−1
k+1
(
ck+1
m
(
c−1
m−k(cm−k
m (i))
))
= c−1
k+1
(
ck+1
m
(
c−1
m−k(i−k)
))
= c−1
k+1
(
ck+1
m (i−k−1)
)
=
c−1
k+1(i) = i.
And furthermore ˜̃τ = τ ◦ ck+1
m+1 ◦ c
m−k
m+1 = τ .
Step 3. Note that
sgn(σ̃) sgn(τ̃) = (−1)k+(k+1)(m−1)+(k+1)m sgn(σ) sgn(τ) = − sgn(σ) sgn(τ).
From Step 1 we have that T (σ, τ) = T (σ̃, τ̃). There will be cancellations of terms in (4.2) as
sgn(σ̃) sgn(τ̃) = − sgn(σ) sgn(τ) from Step 3. Finally using Step 2 we ensure that all terms will
cancel out therefore establishing the given identity for 0 ≤ l ≤ m − 1. Now using Lemma 4.3,
we conclude that the given identity (4.2) holds for all l ∈ N. ■
Corollary 4.6. If n ≥ 3 and d ≥ (m+1)(m+2)
2 , then uMPS(m,n, d) is contained in a proper
linear subspace of the space of cyclically invariant tensors.
Proof. Let ℓ ≥ m and let Sm+1 denote the symmetric group acting on {0, 1, . . . ,m− 1, ℓ}. As
the trace is invariant under cyclic permutations, for every τ ∈ Cm+1,
Tr
(
Aτ(0)B
σ(0)Aτ(1)B
σ(1) · · ·Aτ(m−1)B
σ(m−1)Aτ(m)B
ℓ
)
can be written as
Tr
(
A0B
σ′(0)A1B
σ′(1) · · ·Am−1B
σ′(m−1)AmB
σ′(ℓ)
)
fixing all positions of Ai’s and permuting Bj ’s according to some σ′ ∈ Sm+1. If for a moment
we identify {0, 1, . . . ,m− 1, ℓ} with [m], we have σ′ = σ ◦ τ−1. Therefore, we can rewrite (4.2)
as follows:∑
σ∈Sm+1
sgn(σ) Tr
(
A0B
σ(0)A1B
σ(1) · · ·Am−1B
σ(m−1)AmB
σ(ℓ)
)
= 0. (4.3)
14 C. De Lazzari, H.J. Motwani and T. Seynnaeve
Let X0, X1, X2 be m ×m matrices, and in (4.3) substitute A0 = X0, B = X1, and Ai = X2
for i = 1, . . . ,m. Note that even after that substitution, the ternary bracelets corresponding
to the (m + 1)! terms in (4.3) are all distinct. Hence no two terms will cancel, and we get
a nontrivial linear relation on uMPS(m, 3, d), where d = 1 + 2 + · · ·+ (m− 1) + ℓ+ (m+ 1) ≥
1 + 2 + · · ·+ (m+ 1) =
(
m+2
2
)
. ■
Remark 4.7. With a bit more care, one can also get nontrivial relations on uMPS(m, 2, d) in
this way. For instance if we take ℓ = m and in (4.3) we substitute A0 = X0X
m+1
1 X0, B = X1,
and Ai = X0 for i = 1, . . . ,m, one verifies that again no terms cancel, and hence we found
a nontrivial linear relation on uMPS(m, 2, d), where d =
(
m+3
2
)
.
4.2 Linear equations for uMPS(2, 2, d)
From the trace parametrization, we can give an upper bound on dim⟨uMPS(2, 2, d)⟩.
Theorem 4.8. For every d ∈ N, we have the inequality
dim⟨uMPS(2, 2, d)⟩ ≤
1
192
(d+ 6)(d+ 4)2(d+ 2) for d even,
1
192
(d+ 7)(d+ 5)(d+ 3)(d+ 1) for d odd.
Proof. It follows from (3.2) and Remark 3.6 that dim⟨uMPS(2, 2, d)⟩ can be at most the number
of degree d monomials in C[T0, T1, T00, T01, T11]. Counting these monomials gives the above
formula. ■
Note that asymptotically for d → ∞, the above bound agrees with our conjectured formula
in Conjecture 3.8.
As in the previous section, we abbreviate “weight λ = (w, d − w) ∈ Z2” to “weight w”. In
the rest of this section, we provide a proof of Conjecture 3.7 in the cases of weight w = 0, 1, 2, 3.
Consider the parametrization of uMPS(2, 2, d) in coordinates
ϕ :
(
C2×2
)2 → Dihd
(
C2
)
,
(A0, A1) 7→
(
Tr
(
Ad
0
)
,Tr
(
Ad−1
0 A1
)
, . . . ,Tr
(
Ad
1
))
.
It is in particular a polynomial map in the unknown entries of the matrices A0, A1 ∈ C2×2, that
we denote by
A0 =
(
a1 a2
a3 a4
)
, A1 =
(
b1 b2
b3 b4
)
.
We will write
Ti1...id := Tr(Ai1 . . . Aid) ∈ C[a1, . . . , b4]d and Ww := ⟨Tb : b ∈ Bw(2, d)⟩.
By Observation 3.1, we have
dim⟨uMPS(2, 2, d)⟩w = dimWw.
The proof of the cases w = 0, 1, 2, 3 consists in determining that a basis of the vector space Ww
is given by a number of elements that coincides with our conjectured dimension. In order to do
this, we guess a set of generators {Tb} of the cardinality prescribed by the conjectured dimension.
The guess of the Tb’s is based on determining a specific subset of the set of binary bracelets of
weight w, of the proper cardinality. Then, we prove that the generators are linearly independent
for a fixed choice of matrices A0 and A1.
The cases w = 0 and w = 1 are easy:
The Linear Span of Uniform Matrix Product States 15
Proposition 4.9. The space W0 is a 1-dimensional vector space generated by the polynomial
T0,...,0 = Tr
(
Ad
0
)
. The space W1 is a 1-dimensional vector space generated by the polynomial
T10...0 = Tr
(
A1A
d−1
0
)
.
Proof. If w = 0 then b = (0 . . . 0) ∈ B0(2, d) is the only binary bracelet of weight zero, and if
w = 1 then b = (10 . . . 0) ∈ B1(2, d) is the only binary bracelet of weight 1. ■
We now turn to the case w = 2. Then Conjecture 3.7 states that dimWw =
⌊
d
2
⌋
. But
⌊
d
2
⌋
is exactly the number B2(2, d) of generators Tb of Ww; hence we need to show that they are
linearly independent.
Proposition 4.10. The polynomials {Tb : b ∈ B2(2, d)} are linearly independent.
Proof. Note that
W2 =
〈
T10i10d−2−i | i = 0, . . . ,
⌊
d
2
⌋
− 1
〉
.
If we make the substitutions
A1 =
(
0 1
1 0
)
, A0 =
(
1 0
0 x
)
,
our generators Tb become
T10i10d−2−i = Tr
(
A1A
i
0A1A
d−2−i
0
)
= xi + xd−2−i, i = 0, . . . ,
⌊
d
2
⌋
− 1. (4.4)
Since for the given choice of A0, A1 the polynomials (4.4) are
⌊
d
2
⌋
linearly independent polyno-
mials, the same holds for a generic choice of matrices. ■
Finally, we prove the case w = 3. In this case our conjectured formula states that dimWw =
d− 3. Consider the following subset of B3(2, d):
B̃3 := {b ∈ B3(2, d) : b contains 11 or 101} ⊂ B3(2, d).
Lemma 4.11. The cardinality of B̃3 equals d− 3.
Proof. The cardinality of B̃3 is the sum of the number of binary bracelets of weight 3 contain-
ing 11 and the number of binary bracelets of weight 3 containing 101 but not 11, that are
⌈
d−2
2
⌉
and
⌈
d−5
2
⌉
respectively. Therefore the cardinality of B̃3 is⌈
d− 2
2
⌉
+
⌈
d− 5
2
⌉
= d− 3. ■
In order to prove the case w = 3 we need to show that
{
Tb : b ∈ B̃3
}
is a basis of W3. We
first show linear independence:
Lemma 4.12. The polynomials
{
Tb : b ∈ B̃3
}
are linearly independent.
Proof. We will show that the polynomials are linearly independent even after the following
substitution:
A1 =
(
0 1
1 1
)
, A0 =
(
1 0
0 x
)
.
16 C. De Lazzari, H.J. Motwani and T. Seynnaeve
Then W3 is spanned by the following polynomials:
fb := T110b10d−b−3 = xb + xd−b−3 + 2xd−3, b ∈
{
0, . . . ,
⌊
d− 3
2
⌋}
,
gb := T1010b10d−b−4 = xb+1 + xd−b−3 + xd−4 + xd−3, b ∈
{
1, . . . ,
⌊
d− 4
2
⌋}
.
We now simply have to put the coefficients of these polynomials in a matrix and show it has
full rank. For d even the matrix of coefficients is given by
S =
1 . . . 3
1 1 2
1 1 2
...
. . . . .
. ...
0 1 1 2
0 0 1 0 . . . 2 1
0 1 1 1 1
...
. . . . .
. ...
0 . . . 2 . . . 0 1 1
and for d odd, given by
S =
1 . . . 0 3
1 0 1 2
1 1 0 2
...
. . . . .
. ...
...
1 1 0 2
2 0 2
0 0 1 0 . . . 0 2 1
0 1 0 1 1 1
. . . . .
. ...
...
0 0 1 1 0 1 1
.
By elementary row operations, we can reduce the left upper part to a diagonal matrix of or-
der
⌊
d−1
2
⌋
. The left lower part is filled with zeros. The (rectangular) right lower block of
dimension
⌊
d−4
2
⌋
×
⌊
d−2
2
⌋
can be put in the following upper triangular forms, for d even and odd
respectively,
0 . . . −1 2 −1
... −1 1 1 −1
. .
.
. .
.
0 1 −1
−1 1
...
...
...
2 0 . . . 0 1 1
→
2 0 . . . 1 1
0 2 3 −1
. . . 5 −3
...
...
...
0 . . . 0 2 ∗ ∗
0 . . . 0 ∗ ∗
for d even,
0 . . . −1 2 −1
... −1 1 1 −1
. .
.
. .
.
0 1 −1
...
...
...
−1 1 −1
1 0 . . . 0 1 0
→
1 0 . . . 0 1 0
0 1 0 . . . 0 2 −1
... 0
. . . 3 −2
...
...
0 1 ∗ ∗
0 ∗ ∗
for d odd.
The Linear Span of Uniform Matrix Product States 17
Both the obtained blocks have rank
⌊
d−4
2
⌋
. We have that the rank of S is
⌊
d−1
2
⌋
+
⌊
d−4
2
⌋
= d−3,
and this concludes the proof. ■
We finish our proof by showing that
{
Tb : b ∈ B̃3
}
spans W3:
Lemma 4.13. Every polynomial T10a10b10c = Tr
(
A1A
a
0A1A
b
0A1A
c
0
)
, with 1 < a ≤ b ≤ c,
a+ b+ c = d− 3 is an element of the linear span
〈
Tb : b ∈ B̃3
〉
.
Proof. Notice that the elements of B3(2, n) \ B̃3 can be written without loss of generality in
the form
10a10b10c, with 1 < a ≤ b ≤ c.
We use induction on a. If a = 0 and a = 1 then
(
10a10b10c
)
∈ B̃3 and we are done. If we
substitute A1 → A1A
a−1
0 , A2 → A1A
b
0 and A3 → A1 in the equation given by Theorem 4.5, we
get
Tr
(
A1A
a−1
0 A1A
b+1
0 A1A
c
0
)
+ Tr
(
A1A
b
0A1A0A1A
a+c−1
0
)
+ Tr
(
A2
1A
a
0A1A
b+c
0
)
= Tr
(
A1A
a
0A1A
b
0A1A
c
0
)
+ Tr
(
A1A
b+1
0 A2
1A
a+c−1
0
)
+ Tr
(
A1A0A1A
a−1
0 A1A
b+c
0
)
.
Reordering the summands, we obtain
T10a10b10c =
(
T10b1010a+c−1 + T110a10b+c − T10b+1110a+c−1 − T1010a−110b+c
)
+ T10a−110b+110c .
All terms in the parenthesis have as subscript an elements of B̃3, and the last term is in
〈{
Tb : b ∈
B̃3
}〉
by the induction hypothesis. This concludes the proof. ■
Acknowledgements
The third author would like to thank Alessandra Bernardi, Jaros law Buczyński, Joseph Lands-
berg, and Frank Verstraete for many helpful discussions. The second author is supported
by FWO grants (G023721N and G0F5921N) and UGent BOF grants (BOF21/DOC/182 and
STA/201909/038).
References
[1] Affleck I., Kennedy T., Lieb E.H., Tasaki H., Valence bond ground states in isotropic quantum antiferro-
magnets, in Condensed Matter Physics and Exactly Soluble Models, CMS Conf. Proc., Springer, Berlin,
1988, 253–304.
[2] Bachmayr M., Schneider R., Uschmajew A., Tensor networks and hierarchical tensors for the solution of
high-dimensional partial differential equations, Found. Comput. Math. 16 (2016), 1423–1472.
[3] Barthel T., Lu J., Friesecke G., On the closedness and geometry of tensor network state sets, Lett. Math.
Phys. 112 (2022), 72, 33 pages, arXiv:2108.00031.
[4] Bernardi A., De Lazzari C., Fulvio G., Dimension of tensor network varieties, Comm. Cont. Math., to
appear, arXiv:2101.03148.
[5] Buczyńska W., Buczyński J., Micha lek M., The Hackbusch conjecture on tensor formats, J. Math. Pures
Appl. 104 (2015), 749–761, arXiv:1501.01120.
[6] Chen J., Cheng S., Xie H., Wang L., Xiang T., Equivalence of restricted Boltzmann machines and tensor
network states, Phys. Rev. B 97 (2018), 085104, 16 pages, arXiv:1701.04831.
[7] Christandl M., Gesmundo F., França D.S., Werner A.H., Optimization at the boundary of the tensor network
variety, Phys. Rev. B 103 (2021), 195139, 9 pages, arXiv:2006.16963.
[8] Christandl M., Lucia A., Vrana P., Werner A.H., Tensor network representations from the geometry of
entangled states, SciPost Phys. 9 (2020), 042, 31 pages, arXiv:1809.08185.
https://doi.org/10.1007/978-3-662-06390-3_19
https://doi.org/10.1007/s10208-016-9317-9
https://doi.org/10.1007/s11005-022-01552-z
https://doi.org/10.1007/s11005-022-01552-z
https://arxiv.org/abs/2108.00031
https://doi.org/10.1142/S0219199722500596
https://arxiv.org/abs/2101.03148
https://doi.org/10.1016/j.matpur.2015.05.002
https://doi.org/10.1016/j.matpur.2015.05.002
https://arxiv.org/abs/1501.01120
https://doi.org/10.1103/PhysRevB.97.085104
https://arxiv.org/abs/1701.04831
https://doi.org/10.1103/PhysRevB.103.195139
https://arxiv.org/abs/2006.16963
https://doi.org/10.21468/scipostphys.9.3.042
https://arxiv.org/abs/1809.08185
18 C. De Lazzari, H.J. Motwani and T. Seynnaeve
[9] Cichocki A., Lee N., Oseledets I., Phan A.H., Zhao Q., Mandic D.P., Tensor networks for dimensionality
reduction and large-scale optimization: Part 1. Low-rank tensor decompositions, Found. Trends Mach.
Learn. 9 (2016), 249–429, arXiv:1809.08185.
[10] Critch A., Morton J., Algebraic geometry of matrix product states, SIGMA 10 (2014), 095, 10 pages,
arXiv:1210.2812.
[11] Czapliński A., Micha lek M., Seynnaeve T., Uniform matrix product states from an algebraic geometer’s
point of view, Adv. in Appl. Math. 142 (2023), 102417, 25 pages, arXiv:1904.07563.
[12] De Lazzari C., Algebraic, geometric and numerical methods for tensor network varieties, Ph.D. Thesis,
University of Trento, 2022.
[13] De Lazzari C., Motwani H.J., Seynnaeve T., The linear span of uniform matrix product states, GitHub
repository, 2022, available at https://github.com/harshitmotwani2015/uMPS/.
[14] Dvir Z., Malod G., Perifel S., Yehudayoff A., Separating multilinear branching programs and formulas, in
STOC’12 – Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012,
615–623.
[15] Fannes M., Nachtergaele B., Werner R.F., Finitely correlated states on quantum spin chains, Comm. Math.
Phys. 144 (1992), 443–490.
[16] Greene J., Traces of matrix products, Electron. J. Linear Algebra 27 (2014), 716–734.
[17] Hackbusch W., Tensor spaces and numerical tensor calculus, Springer Ser. Comput. Math., Vol. 56, Springer,
Cham, 2019.
[18] Hackl L., Guaita T., Shi T., Haegeman J., Demler E., Cirac J.I., Geometry of variational methods: dynamics
of closed quantum systems, SciPost Phys. 9 (2020), 048, 100 pages, arXiv:2004.01015.
[19] Haegeman J., Mariën M., Osborne T.J., Verstraete F., Geometry of matrix product states: metric, parallel
transport, and curvature, J. Math. Phys. 55 (2014), 021902, 50 pages, arXiv:1210.7710.
[20] Landsberg J.M., Tensors: geometry and applications, Grad. Stud. Math., Vol. 128, Amer. Math. Soc.,
Providence, RI, 2012.
[21] Landsberg J.M., Qi Y., Ye K., On the geometry of tensor network states, Quantum Inf. Comput. 12 (2012),
346–354, arXiv:1105.4449.
[22] Navascues M., Vertesi T., Bond dimension witnesses and the structure of homogeneous matrix product
states, Quantum 2 (2018), 50, 15 pages, arXiv:1509.04507.
[23] Oseledets I.V., Tensor-train decomposition, SIAM J. Sci. Comput. 33 (2011), 2295–2317.
[24] Östlund S., Rommer S., Thermodynamic limit of density matrix renormalization, Phys. Rev. Lett. 75 (1995),
3537–3540, arXiv:cond-mat/9503107.
[25] Perez-Garcia D., Verstraete F., Wolf M.M., Cirac J.I., Matrix product state representations, Quantum Inf.
Comput. 7 (2007), 401–430, arXiv:quant-ph/0608197.
[26] Pólya G., Read R.C., Combinatorial enumeration of groups, graphs, and chemical compounds, Springer,
New York, 1987.
[27] Procesi C., The invariant theory of n× n matrices, Adv. Math. 19 (1976), 306–381.
[28] Robeva E., Seigal A., Duality of graphical models and tensor networks, Inf. Inference 8 (2019), 273–288,
arXiv:1710.01437.
[29] Sibirskii K.S., Algebraic invariants of a system of matrices, Sib. Math. J. 9 (1968), 115–124.
[30] Stanley R.P., Algebraic combinatorics: walks, trees, tableaux, and more, Undergrad. Texts Math., Springer,
New York, 2013.
http://doi.org/10.1561/2200000059
http://doi.org/10.1561/2200000059
https://arxiv.org/abs/1809.08185
https://doi.org/10.3842/SIGMA.2014.095
https://arxiv.org/abs/1210.2812
https://doi.org/10.1016/j.aam.2022.102417
https://arxiv.org/abs/1904.07563
https://github.com/harshitmotwani2015/uMPS/
https://doi.org/10.1145/2213977.2214034
https://doi.org/10.1007/BF02099178
https://doi.org/10.1007/BF02099178
https://doi.org/10.13001/1081-3810.1999
https://doi.org/10.1007/978-3-030-35554-8
https://doi.org/10.21468/scipostphys.9.4.048
https://arxiv.org/abs/2004.01015
https://doi.org/10.1063/1.4862851
https://arxiv.org/abs/1210.7710
https://doi.org/10.1090/gsm/128
https://arxiv.org/abs/:1105.4449
https://doi.org/10.22331/q-2018-01-31-50
https://arxiv.org/abs/1509.04507
https://doi.org/10.1137/090752286
https://doi.org/10.1103/PhysRevLett.75.3537
https://arxiv.org/abs/cond-mat/9503107
http://hdl.handle.net/1854/LU-8589272
http://hdl.handle.net/1854/LU-8589272
https://arxiv.org/abs/quant-ph/0608197
https://doi.org/10.1007/978-1-4612-4664-0
https://doi.org/10.1016/0001-8708(76)90027-X
https://doi.org/10.1093/imaiai/iay009
https://arxiv.org/abs/1710.01437
https://doi.org/10.1007/BF02196663
https://doi.org/10.1007/978-1-4614-6998-8
1 Introduction
2 Preliminaries
2.1 Cyclic and symmetric invariance
2.2 GLn-invariance
2.3 Words, necklaces and bracelets
3 Computations
3.1 The trace parametrization
3.2 Computing the character
3.3 Higher degree equations
4 Results
4.1 Linear relations via Cayley–Hamilton
4.2 Linear equations for uMPS(2,2,d)
References
|
| id | nasplib_isofts_kiev_ua-123456789-211805 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1815-0659 |
| language | English |
| last_indexed | 2026-03-21T04:21:24Z |
| publishDate | 2022 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | De Lazzari, Claudia Motwani, Harshit J. Seynnaeve, Tim 2026-01-12T10:11:58Z 2022 The Linear Span of Uniform Matrix Product States. Claudia De Lazzari, Harshit J. Motwani and Tim Seynnaeve. SIGMA 18 (2022), 099, 18 pages 1815-0659 2020 Mathematics Subject Classification: 15A69; 20G05; 81P45 arXiv:2204.10363 https://nasplib.isofts.kiev.ua/handle/123456789/211805 https://doi.org/10.3842/SIGMA.2022.099 The variety of uniform matrix product states arises both in algebraic geometry as a natural generalization of the Veronese variety, and in quantum many-body physics as a model for a translation-invariant system of sites placed on a ring. Using methods from linear algebra, representation theory, and invariant theory of matrices, we study the linear span of this variety. The third author would like to thank Alessandra Bernardi, Jaroslaw Buczyński, Joseph Landsberg, and Frank Verstraete for many helpful discussions. The second author is supported by FWO grants (G023721N and G0F5921N) and UGent BOF grants (BOF21/DOC/182 and STA/201909/038). en Інститут математики НАН України Symmetry, Integrability and Geometry: Methods and Applications The Linear Span of Uniform Matrix Product States Article published earlier |
| spellingShingle | The Linear Span of Uniform Matrix Product States De Lazzari, Claudia Motwani, Harshit J. Seynnaeve, Tim |
| title | The Linear Span of Uniform Matrix Product States |
| title_full | The Linear Span of Uniform Matrix Product States |
| title_fullStr | The Linear Span of Uniform Matrix Product States |
| title_full_unstemmed | The Linear Span of Uniform Matrix Product States |
| title_short | The Linear Span of Uniform Matrix Product States |
| title_sort | linear span of uniform matrix product states |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/211805 |
| work_keys_str_mv | AT delazzariclaudia thelinearspanofuniformmatrixproductstates AT motwaniharshitj thelinearspanofuniformmatrixproductstates AT seynnaevetim thelinearspanofuniformmatrixproductstates AT delazzariclaudia linearspanofuniformmatrixproductstates AT motwaniharshitj linearspanofuniformmatrixproductstates AT seynnaevetim linearspanofuniformmatrixproductstates |