A graph theoretical framework for the strong Gram classification of

arXiv:2010.04691v4 [math.CO] 21 Dec 2021

Appeared in Fundamenta Informaticae 184(1) : 49–82 (2021). 49

Available at IOS Press through:

https://doi.org/10.3233/FI-2021-2092

A Graph Theoretical Framework for the Strong Gram

Classiﬁcation of Non-negative Unit Forms of Dynkin Type A

Jesús Arturo Jiménez González

Instituto de Matemáticas, UNAM, Mexico

[email protected]

Abstract. In the context of signed line graphs, this article in troduces a modiﬁed inﬂation tech-

nique to study strong Gram congruen ce of no n-negative (integral quadratic) unit forms, and uses

it to show that weak and stro ng Gram congruence coincide among positive u nit forms of Dynkin

type A

. The con cept of inverse of a quiver is also intr oduced, and is used to obtain a nd analyze

the Coxeter matr ix of non-negative unit forms of Dynkin type A

. With these tools, connected

principal unit forms of Dynkin type A

are also classiﬁed up to strong congruence.

Keywords: Integral quadratic form, Gr a m congruence, quiver, Dynkin type, Coxeter matrix,

edge-b ipartite graph, signed line graph. 2020 MSC: 1 5A63, 15 A 21, 15B36 , 05C22, 05C50,

05C76, 05B20.

1. Introduction

An integral quadratic form is a homogeneous polynomial q of degree two with integer coefﬁcients,

given usually as qpxq “ x

x for a unique upper triangular matrix

. In case

has only 1’s

as diagonal entries, q is simply called a unit form, and the symmetric matrix G

“

a generalized Cartan matrix (see for instance [3] or [29]). Two unit forms q

and q are said to be

weakly (resp. strongly) Gram congruent, if there is an integer matrix B with detpBq “ ˘1 such that

“ B

B (resp.

“ B

G). Clearly, strong congruence implies weak congruence.

Address of correspondence: Instituto de Matemáticas, Mexico City, Mexico.

Received June 2021; revised November 2021.

50 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

The classiﬁcation of connected positive unit forms up to weak Gram congruence is well known

(see Ovsienko [20], Kosakowska [16] and Simson [23]). Corresponding generalizations to the non-

negative case are also known (see Barot and de la Peña [5, 6], and Simson et al. [26 , 32]). A strong

Gram classiﬁcation of non-negative unit forms is far from been completed (see [28, Problem 2.1paq]

and [29, Problem 1.12] for a speciﬁc formulation of these problems in terms of Coxeter spectra):

Problem A. C lassify all (connected) non-negative unit forms up to strong Gram congruence.

The following problem was posed by Simson in [25, Problems 1.10 and 1.11] (see also [28, Prob-

lem 2.1pbq]):

Problem B. Construct algorithms that compute an integer matrix B with detpBq “ ˘1 that deﬁnes

the strong Gram congruence

“ B

B, in case the quadratic unit forms q and q

are strongly

Gram congruent.

There have been many advances towards the strong classiﬁcation of positive quadratic forms, both

from computational and geometrical points of view. For instance, a classiﬁcation for small cases

(n ď 9), including the exceptional cases E

, E

and E

, as well as all non-simply laced cases, was

presented by Simson et al., cf. [29]. The general case of Dynkin type D

was announced in [28] (see

also [29, §4]), and is solved by Simson in [30].

There is a well known graphical description of quadratic (unit) forms by means of (loop-less)

signed multi-graphs (or bigraphs, as called in the paper following Simson [23]). It is easy to verify

that if qpxq “

p2I ` Aqx, where A is the symmetric adjacency matrix of a loop-less bigraph

(where I denotes the identity matrix of appropriate size), then q is non-negative if and only if the least

eigenvalue of A is greater than or equal to ´2.

Loop-lees bigraphs whose symmetric adjacency matrix has least eigenvalue greater than or equal

to ´2 have attracted the attention of graph theorists since the 1960’s [13, 1, 12, 8], mainly focusing

in their graphical characterization and Laplacian (or Kirchhoff) spectral properties. The connection

of these bigraphs with the classical root systems ADE was established in the seminal work [8] by

Cameron, Goethals, Seidel and Shult in 1976 (see also [34]).

The theory of (loop-lees) bigraphs w ith least eigenvalue ´2, and the theory of quadratic (unit)

forms, have maintained fairly independent roads (see for instance [29] and references therein), per-

haps due to their seemingly different graphical and algebraic goals. The author translated in [14]

the inﬂation techniques into the combinatorial context of (a version of) line digraphs, using the so-

called incidence quadratic form of a quiver (directed multi-graph). Some of the basic concepts in [14]

had already been introduced by Zaslavsky in [37, §3], see also [7, 36]. Here we further explore this

connection. More on the development of the theory of line graph can be found in [9 ].

Motivated by results of Barot [2] and von Höhne [33], the author associated to any quiver Q a

bigraph IncpQq, called incidence graph of Q [14]. This construction has many similarities to the

so-called line digraph (introduced by Harary and Norman [13] in 1961), and is used as an auxiliary

construction for signed line graphs (see [37, 7]). The theory of ﬂations for non-negative unit forms of

Dynkin type A

, in this combinatorial context, was worked out in [14]. Here we propose a modiﬁed

theory of ﬂations that preserves strong Gram congruence of unit forms (Section 3), given a solution of

Problem A for positive unit forms of Dynkin type A

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 51

Theorem A. Any two connected positive unit forms of Dynkin type A

are strongly Gram congruent.

An essentially combinatorial proof of Theorem A is given below (Theorem 3.16), after some

technical preparations. An equivalent result was obtained recently by Simson in [31], in the context

of edge-bipartite graphs and morsiﬁcations of quadratic forms. Recall that a positive unit form is

positive precisely when it is non-negative and has corank zero (see Lemma 2.1pcq below). A connected

non-negative unit form of corank one is called principal. In Section 4 we present a combinatorial

formula for the Coxeter matrix in terms of quiver inverses, whose similarity invariants (for instance,

the characteristic polynomial, called Coxeter polynomial of the unit form), serve as discriminant in

the analogous of Theorem A for principal unit forms (Theorem 4.12):

Theorem B. Two connected principal unit forms of Dynkin type A

are strongly Gram congruent if

and only if they have the same Coxeter polynomial.

A list of the corresponding Coxeter polynomials is given in Remark 4.10. Quiver inverses are

used in Corollary 4.8 to give bounds for the coefﬁcients of the Coxeter matrix associated to non-

negative unit forms q of Dynkin type A

. In Section 2 we collect concepts and general results needed

throughout the paper.

2. Basic notions

The set of integers is denoted by Z, and the canonical basis of Z

by e

, . . . , e

. All matrices have

integer coefﬁcients, and for a n ˆ m matrix A and a n ˆ m

matrix B, the n ˆ pm ` m

q matrix with

columns those of A and B (in this order), is denoted by rA|Bs. In particular, if A

, . . . , A

are the

columns of A, we write A “ rA

| ¨ ¨ ¨ |A

s. The identity n ˆ n matrix is denoted by I

, and simply by

I for appropriate size. The transpose of a matrix A is denoted by A

, and if A is an invertible square

matrix, then A

´tr

denotes pA

´1

. By total (or linear) order we mean a partial order where any two

elements are comparable, and a totally (or linearly) ordered set is one equipped with such order.

2.1. Integral quadratic forms

Let q “ qpx

, . . . , x

q be an integral quadratic form on n ě 1 variables, that is, q is a homogeneous

polynomial of degree two,

qpx

, . . . , x

q “

1ďiďjďn

In case q

“ 1 for i “ 1, . . . , n we say that q is a unit form. The (upper) triangular Gram matrix

associated to an integral quadratic form q is the n ˆ n matrix given by

“ pg

q where g

“ q

for

1 ď i ď j ď n and g

“ 0 for 1 ď j ă i ď n. The symmetric Gram matrix associated to q is given

by G

“

As usual, the form q can be seen as a function q : Z

Ñ Z given by evaluation in the vector of

variables px

, . . . , x

q. N otice that for x “ px

, . . . , x

P Z

we have

qpxq “ x

x “

52 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

For an endom orphism T : Z

Ñ Z

, the integral quadratic form qT is given by qT pxq “ qpT pxqq.

Observe that G

“ T

T (where here as in the rest of the text we identify an endomorphism T

with its square matrix under the ordered canonical basis e

, . . . , e

of Z

). We say that two unit forms

q and q

are weakly congruent if there is an automorphism T of Z

such that q

“ qT (written q

„ q

or q

„

q).

The direct sum q ‘ q

: Z

n`n

Ñ Z of integral quadratic forms q : Z

Ñ Z and q

: Z

Ñ Z is

given by

pq ‘ q

qpx

, . . . , x

n`n

q “ qpx

, . . . , x

q ` q

n`1

, . . . , x

n`n

Observe that

q‘q

“

, which we denote by

‘

. The symmetric bilinear form

associated to an integral quadratic form q : Z

Ñ Z, denoted by qp´|´q : Z

ˆ Z

Ñ Z, is given by

qpx|yq “ qpx ` yq ´ qpxq ´ qpyq,

(notice that qpx|yq “ x

y for any x, y P Z

). The radical radpqq of a unit form q is the set of

vectors x in Z

such that qpx|´q ” 0 (called radical vectors of q). Clearly, radpqq is a subgroup

of Z

, whose rank corkpqq is called corank of q. Alternatively, corkpqq “ n ´ rkpqq, where

rkpqq “ rkpG

q is called rank of q. By root of q we mean a vector x P Z

such that qpxq “ 1.

For convenience, throughout the text we use the notation q

“ q

for i ă j. A unit form q is said

to be connected if for any indices i ‰ j there is a sequence of indices i

, . . . , i

with r ě 1 such that

i “ i

, j “ i

and q

t´1

‰ 0 for t “ 1, . . . , r. R ecall that a unit form q : Z

Ñ Z is called non-

negative (resp. positive) if qpxq ě 0 for any vector x in Z

(resp. qpxq ą 0 for any non-zero vector

x in Z

). A unit form q is called principal if q is non-negative and has corank one, see Simson [21]

and Kosakowska [16]. The following important observation is well known (see for instance [5]), for

convenience here we give a short proof.

Lemma 2.1. For a unit form q the following assertions hold.

a) If q is not connected, then q „ q

‘ q

for unit forms q

and q

b) If q is non-negative and qpxq “ 0, then x is a radical vector of q.

c) The unit form q is positive if and only if q is non-negative and corkpqq “ 0.

Assume now that q is a non-negative unit form, and that q

is a unit form weakly congruent to q.

d) Then q

is non-negative and corkpq

q “ corkpqq.

e) If q is connected, then so is q

Proof:

A more speciﬁc version of paq will be given later in Lemma 2.5. For pbq, take a basic vector e

and

any integer m. If qpxq “ 0 for a vector x, then

0 ď qpmx ` e

q “ mqpx|e

q ` 1.

Since m and i are arbitrary, then qpx|e

q “ 0 and x is a radical vector of q.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 53

For pcq, if q is positive then clearly q is non-negative and radpqq “ 0. Conversely, if q is non-

negative and corkpqq “ 0, then radpqq “ 0. By pbq, for any non-zero vector x we have qpxq ą 0. To

prove pdq consider an automorphism T such that q

“ qT . T hen q

pxq “ qpT pxqq ě 0, that is, q

non-negative. Since

“ T

it is well know n that rkpG

q “ rkpG

q (cf. [19 , § 4.5]), and therefore corkpq

q “ corkpqq.

Finally, to show peq assume that q

“ qT is not connected. By paq we may assume that q

“ q

‘q

for unit forms q

: Z

Ñ Z and q

: Z

Ñ Z (with n “ n

` n

). Let y

, . . . , y

be the columns

of T

´1

. Since q is a unit form, y

is a root of q

for i “ 1 . . . , n. Moreover, if y

(resp. y

) is the

projection of y

into its ﬁrst n

entries (resp. its last n

entries), then

1 “ q

q “ q

q ` q

By pdq, the unit forms q

and q

are non-negative, therefore either q

q “ 1 and q

q “ 0, or

q “ 0 and q

q “ 1. Consider the following partition of the set t1, . . . , nu,

X “ t1 ď i ď n | q

q “ 1u and Y “ t1 ď j ď n | q

q “ 1u.

By pbq, observe that if i P X and j P Y , then y

is a radical vector of q

and y

is a radical vector of

, and therefore

qpe

` e

q “ q

` y

q “ q

` y

q ` q

` y

q “ q

q ` q

q “ 2.

Then qpe

` e

q “ qpe

q ` qpe

q, which implies that q

“ 0 for arbitrary i P X and j P Y (for

“ qpe

q). We need to show that both X and Y are non-empty sets.

We may write

´1

“

0 G

¸˜

“ B

1 B ` C

2 C,

where B and C are respectively n

ˆ n and n

ˆ n matrices. If Y is an empty set, then the columns

of C are radical vectors of q

, and therefore

“ pT

´1

“ B

In particular, rkpqq ď rkpq

q (cf. [19, §4.5]). This is impossible, since by pdq we have rkpqq “

rkpq

q “ rkpq

q ` rkpq

q ą rkpq

q (a similar contradiction can be found assuming that X is an

empty set). This completes the proof, since X ‰ H and Y ‰ H imply that q is non-connected. [\

The example following Remark 2.2 below shows that the non-negativity assumption is necessary

for part peq in Lemma 2.1.

54 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

2.2. Bigraphs and associated unit forms

Let Γ “ pΓ

, Γ

, σq be a bigraph, that is, a m ulti-graph pΓ

, Γ

q together with a sign function

σ : Γ

Ñ t˘1u such that all parallel edges have the same sign (see [23]). As usual, bigraphs are

graphically depicted in the following way: for vertices i and j, an edge a joining i and j with σpaq “ 1

will be denoted by ‚

‚

, and by ‚

‚

if σpaq “ ´1 (this convention is used in [5]

and [14], and is opposite to the one used in [23]). We assume that the set of vertices Γ

is totally

ordered. If Γ has no loop and |Γ

| “ n, the (upper) triangular adjacency matrix

}

Adj

of Γ is the

n ˆ n matrix given by

}

Adj

“

0 d

1,2

1,3

¨ ¨ ¨ d

1,n´1

1,n

0 0 d

2,3

¨ ¨ ¨ d

2,n´1

2,n

0 0 0

. d

3,n´1

3,n

0 0 0 ¨ ¨ ¨ 0 d

n´1,n

0 0 0 ¨ ¨ ¨ 0 0

‹

‚

where |d

| is the number of edges between vertices i ă j, and σpaqd

“ |d

| for any such edge a.

Throughout the text we assume that all bigraphs are loop-less, that is, have no loop.

The (upper) triangular Gram matrix

of Γ is given by

“ I ´

}

Adj

(following the

convention in [23] one gets

“ I `

}

Adj

). The quadratic form associated to a bigraph Γ is given

pxq “ x

x, for any x P Z

that is,

“

. There is a well known bijection between unit forms and loop-less bigraphs (see

for instance [23] and [14]), given by the corresponding triangular (Gram and adjacency) matrices.

Remark 2.2. For a loop-less bigraph Γ, the unit form q

is connected if and only if Γ is a connected

bigraph.

Proof:

Take q

pxq “

1ďiďjďn

, and observe that for any sequence of indices i

, . . . , i

such that

t´1

‰ 0 for t “ 1, . . . , r, there is a sequence of edges a

, . . . , a

in Γ such that a

contains vertices

t´1

and i

(that is, pi

, a

, i

, . . . , i

r´1

, a

, i

q is a walk in Γ). Hence the claim follows. [\

Consider the following connected bigraph Γ with twelve edges, and non-connected bigraph Γ

with six edges,

Γ “

‚

❆

‚

“

‚

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 55

None of the unit forms q

and q

is non-negative, and q

„ q

. Indeed, we have

“

5 2 0 0

2 0 2

2 0

3 2

and G

“

3 0 0

3 2 0 0

0 0 2

0 0

3 2

where for an integer a we take ˆa “ ´a. A direct calculation shows that if B “

1 0 0 0

1 1 0 0

2 0 1 0

2 0 0 1

, then

“ B

2.3. Elementary transformations for unit forms

We consider the following transformations of a unit form q : Z

Ñ Z.

1. Point inversion. Take a subset of indices C Ď t1, . . . , nu and deﬁne the automorphism V

Ñ Z

given by V

q “ ´e

if k P C, and V

q “ e

otherwise. The transformation

is known as point inversion (or sign change) for q, and the unit form qV

is usually referred

to as point inversion of q.

2. Swapping. G iven two indices i ‰ j, consider the transformation S

: Z

Ñ Z

given by

q “ e

, S

q “ e

and S

q “ e

for k ‰ i, j (clearly, S

“ S

). We say that the

unit form qS

is obtained from q by swapping indices i and j.

3. F lation. For two indices i ‰ j, consider the sign ǫ “ sgnpq

q P t`1, 0, ´1u of q

. Take

the linear transformation T

: Z

Ñ Z

given by T

pxq “ x ´ ǫx

, for a (column) vector

x “ px

, . . . , x

in Z

. The transformation T

will be referred to as ﬂation for q.

4. F S-transformation. For our arguments we consider the composition

“ T

, and call it a

F S-(linear) transformation for q if ǫ “ sgnpq

Remark 2.3. Let q be a unit form, with indices i ‰ j.

a) Let T

be a ﬂation for q. Then q

“ qT

is a unit form if and only if |q

| ď 1, and in that case

´ǫ

“ q.

b) Let

be a F S-transformation for q. Then q

“ q

is a unit form if and only if |q

| ď 1, and

in that case q

´ǫ

“ q.

Proof:

To show paq, observe that q

q “ qpe

q “ 1 if k ‰ i, and

q “ qpT

qq “ qpe

´ ǫe

q “ 1 ` pǫ ´ |q

|q.

Since ǫ “ sgnpq

q, it follows that q

q “ 1 if and |q

| ď 1. That T

´ǫ

“ I is clear, since

´ǫ

pxq “ T

px ` ǫx

q “ T

pxq ` ǫx

q “ x ´ ǫx

` ǫx

“ x ,

for any x in Z

. Claim pbq follows from paq. [\

56 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

A composition T “ T

¨ ¨ ¨ T

is called an iterated ﬂation for a unit form q, if taking q

“ q,

then T

is a ﬂation for q

t´1

, and q

“ q

t´1

is a unit form, for t “ 1, . . . , r. In a similar situation,

a composition

T “

¨ ¨ ¨

is called an iterated F S-transformation for q.

2.4. Weak classiﬁcation and strong congruence

The classiﬁcation of positive unit forms up to weak congruence is classical: for n ě 1, the weak

equivalence classes of connected positive unit forms in n variables are in correspondence with the set

of (simply laced) Dynkin types D

, where

“

’

u, if n “ 1, 2, 3,

, D

u, if n “ 4, 5 or n ě 9,

, D

, E

u, if n “ 6, 7, 8,

(called Dynkin graphs on n vertices, see Table 1). The following weak classiﬁcation of connected

non-negative unit forms can be found in [32] (see also [5]). If J Ă t1, . . . , nu is a subset of indices,

denote by τ : Z

Ñ Z

the canonical inclusion. If q : Z

Ñ Z is a unit form, then the compo-

sition q

“ qτ is a unit form called restriction of q, and the unit form q is called extension of q

Simson ﬁxed in [26] (see also [32, Algorithm 3.18]) canonical extensions of connected positive unit

forms, via corresponding connected bigraphs

∆

pcq

for c ě 0 and ∆ a Dynkin graph, which serve as

representatives of weak congruence classes of connected positive unit forms.

Table 1. (Simply lace d) Dynkin graphs with ordered set of vertices.

Notation Graph

pn ě 1q

‚

. . .

‚

n´2

‚

n´1

‚

pn ě 4q

‚

◆

‚

. . .

‚

n´2

‚

n´1

‚

♣

‚

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 57

Theorem 2.4. (Simson-Zaj ˛ac, 2017)

Let q : Z

Ñ Z be a non-negative connected unit form of corank corkpqq “ c. Then there exists an

iterated ﬂation B : Z

Ñ Z

and a unique Dynkin graph ∆ P D

n´c

, denoted by Dynpqq “ ∆ and

called Dynkin type of q, such that the unit form qB is the canonical c-extension of q

∆

. In particular,

two non-negative unit forms q and q

are weakly congruent if and only if they are of the same corank

and of the same Dynkin type.

Two unit forms q and q

are said to be strongly (Gram) congruent, written q

« q or q

q, if

there is an automorphism B such that

“ B

A complete classiﬁcation of strong congruence classes for the exceptional Dynkin types E

, E

and E

is given in [29, 28], as well as for the non-simply laced Dynkin types B

, C

, F

and G

Similar results for the Dynkin type D

were announced in [28] and proved in [30].

Lemma 2.5. Let q : Z

Ñ Z be a unit form. If q is not connected, then q « q

‘ q

for unit

forms q

and q

, and q

‘ q

« q

‘ q

. In particular, strong congruence preserves connectedness of

non-negative unit forms.

Proof:

Assume that q is not connected, and take non-empty sets X and Y such that q

“ 0 for i P X and

j P Y . There is a permutation ρ of the set t1, . . . , nu satisfying

• If i ă j and i, j P X or i, j P Y , then ρpiq ă ρpjq.

• If i P X and j P Y , then ρpiq ă ρpjq.

Let P “ re

´1

p1q

| ¨ ¨ ¨ |e

´1

pnq

s be the permutation matrix associated to the inverse permutation ρ

´1

and consider the product

A “ pa

i“1

“ P

Then a

ρpiqρpjq

“ q

, and by the conditions on the permutation ρ, the matrix A has the following

block-diagonal shape,

A “

0 A

Moreover, A

and A

are upper diagonal matrices with ones in their main diagonals. Taking q

such

that

“ A

(for i “ 1, 2), we get

P “

1 ‘

2 “

‘q

2 ,

as wanted. Swapping the sets X and Y we get q « q

‘ q

The last claim follows by Lemma 2.1peq, since strong congruence implies weak congruence. [\

58 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

2.5. Elementary quiver transformations

A quiver Q “ pQ

, Q

, s, tq consists of (ﬁnite) sets Q

and Q

, whose elements are called vertices

and arrows of Q respectively, and functions s, t : Q

Ñ Q

. We say that the vertices v and w are

source and target of an arrow i respectively, if spiq “ v and tpiq “ w, and display i graphically as

w if v ‰ w. For convenience we consider the set vpiq “ tspiq, tpiqu of vertices incident to i.

An arrow i with spiq “ tpiq is called a loop of Q, and we say that Q is a loop-less quiver if it contains

no loop. Two arrows i and j are said to be parallel if vpiq “ vpjq, and adjacent if vpiq X vpjq ‰ H.

The degree of a vertex v in Q is the number of arrows i in Q such that v P vpiq. A vertex in Q with

degree one is called a leaf, and any arrow i such that vpiq contains a leaf is called a pendant arrow

of Q. Observe that

Q “ pQ

, tvpiqu

iPQ

q is a multi-graph, referred to as underlying graph of Q. We

say that Q is simple, connected or a tree if so is

Q, and walks of Q are also called walks of Q. To be

precise and ﬁx some notation, by walk of Q we mean an alternating sequence of vertices and arrows

in Q of the form,

α “ pv

, i

, v

, . . . , v

ℓ´1

, i

ℓ

, v

ℓ

such that vpi

q “ tv

t´1

, v

u for t “ 1, . . . , ℓ. The notation α “ i

¨ ¨ ¨ i

ℓ

for ǫ

“ ˘1 is also used,

where the symbol i

stands for spi

q “ v

t´1

and tpi

q “ v

, while i

´1

stands for spi

q “ v

and

tpi

q “ v

t´1

(that is, the sign ǫ

denotes the direction in which the arrow i

is found along the walk

α). The non-negative integer ℓ is called length of the walk α, and we call vertex v

(resp. vertex v

ℓ

)

the starting vertex (resp. the ending vertex) of α. A walk with length zero is called a trivial walk.

As usual we omit the exponent `1 in our notation of walks, and abusing notation we set spαq “ v

and tpαq “ v

ℓ

. Observe that the reversed sequence

ℓ

, i

ℓ

, v

ℓ´1

, . . . , v

, i

, v

is also a walk in Q, referred to as reverse walk of α and denoted by α

´1

. With our notation we have

¨ ¨ ¨ i

ℓ

´1

“ i

´ǫ

ℓ

¨ ¨ ¨ i

´ǫ

(in particular spi

´1

q “ tptq and tpi

´1

q “ spiq).

Let Q “ pQ

, Q

q be a quiver (we will usually exclude the source and target functions s and

t from the notation of Q). For a vertex v P Q

, we denote by Q

pvq

the quiver obtained from Q by

removing the vertex v, as well as all arrows containing it (that is, all arrows i with v P vpiq). Similarly,

if i P Q

is an arrow of Q, we denote by Q

piq

the quiver obtained from Q by removing the arrow i.

We will need the following transformations of a loop-less quiver Q “ pQ

, Q

q. Throughout the

text we assume that both sets Q

and Q

are totally ordered.

1. A rrow inversion. Let C be a set of arrows in Q, and take QV

to be the quiver obtained from Q

by inverting the direction of all arrows in C.

2. Swapping. Given two arrows i ‰ j in Q, deﬁne the new quiver QS

as the quiver obtained

from Q by swapping arrows i and j (therefore, swapping their positions in the total ordering of

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 59

3. (Quiver) Flation. Let i and j be adjacent arrows in Q , and choose signs ǫ

and ǫ

such that

α “ i

is a walk in Q. Consider the quiver Q

obtained from Q by replacing i by a new

arrow i

having spi

q “ spαq and tpi

q “ tpαq if ǫ

“ 1, and spi

q “ tpαq and tpi

q “ spαq if

“ ´1. The new arrow i

takes the place of the deleted arrow i in the ordering of Q

. We will

use the notation Q

“ QT

where ǫ “ ´ ǫ

, and say that T

is a ﬂation for the quiver Q. If i

and j are non-adjacent arrows, we take QT

“ Q.

4. F S-transformation. By F S-transformation of a quiver Q with respect to the ordered pair of

different arrows pi, jq, we mean the new quiver Q

given by

“ pQT

The analogous of Remark 2.3 can be stated as follows.

Remark 2.6. Let Q be a loop-less quiver.

a) Let T

be a ﬂation for Q. Then Q

“ QT

is a loop-less quiver if and only if i and j are

non-parallel arrows, and in that case Q

´ǫ

“ Q.

b) Let

be a F S-transformation for Q. Then Q

“ Q

is a loop-less quiver if and only if i and

j are non-parallel arrows, and in that case Q

´ǫ

“ Q.

Moreover, the four types of transform ations described above preserve the number of vertices and

arrows of a quiver, as well as its connectedness if i and j are non-parallel arrows.

Proof:

Let i and j be non-parallel arrows in Q, and notice that by construction the corresponding arrows i

and j

in Q

“ QT

are non-parallel (for i

takes the place of the walk i

of Q, and j

remains

unchanged). Moreover, i and j are adjacent in Q if and only if i

and j

are adjacent in Q

. Noticing

that now pi

´ǫ

is a walk in Q

, then T

´ǫ

is a ﬂation for Q

, and a second application of the

construction above shows that pQ

´ǫ

“ Q (subsequently labels i

and j

are replaced by i and j).

In particular,

´ǫ

“ prQ

´ǫ

“ prQ

´ǫ

“ Q,

since clearly rQ

´ǫ

“ rQ

´ǫ

. This shows paq and pbq.

Now, if Q

is the quiver obtained from Q after applying any of the four types of transformations

above, then Q

“ Q

, and |Q

| “ |Q

|. The claim on connectedness is clear for arrow inversions and

swappings, and follows for T

and

using the arguments above. [\

3. Quivers and their incidence bigraphs

The techniques presented in this section were introduced in a slightly wider context in [14], following

ideas from B arot [2] and von Höhne [33].

60 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

3.1. Incidence quadratic forms

Consider an arbitrary quiver Q with |Q

| “ m vertices and |Q

| “ n arrows, both sets Q

and Q

with ﬁxed total orderings. The (vertex-arrow) incidence matrix of Q is the m ˆ n matrix IpQq with

columns I

“ e

spiq

´e

tpiq

for i P Q

(observe that I

“ 0 if and only if i is a loop in Q), cf. [37]. For a

loop-less quiver Q, it will be useful to consider the incidence function σ

: Q

ˆ Q

Ñ t`1, 0, ´1u

given by

pv, iq “

’

`1, if v is the source of arrow i,

´1, if v is the target of arrow i,

0, otherwise.

Clearly, IpQq “ rσ

pv, iqs

iPQ

vPQ

. For a non-trivial walk α “ i

¨ ¨ ¨

ℓ

in Q, we use the notation

“

ℓ

t“1

. Observe that I

is the telescopic sum

“ ǫ

spi

´ e

tpi

q ` . . . ` ǫ

ℓ

spi

ℓ

´ e

tpi

ℓ

q “ e

spαq

´ e

tpαq

Deﬁnition 3.1. Let Q be a quiver with m ě 1 vertices and n ě 0 arrows.

a) The square matrix G

“ IpQq

IpQq is deﬁned to be the symmetric Gram matrix of Q.

b) Let

be the (unique) upper triangular matrix such that G

“

, called (upper)

triangular Gram matrix of Q.

c) The quadratic form q

: Z

Ñ Z given by

pxq “

IpQq

IpQqx “

||IpQqx||

is deﬁned to be the quadratic form associated to Q.

Notice that the matrix

is the standard matrix morsiﬁcation of q

in the sense of Simson [24].

Remark 3.2. Observe that G

and

do not depend on the order given to the set of vertices Q

Indeed, if Q

is a copy of Q with different ordering of its vertices, there is a permutation m ˆm matrix

P such that IpQ

q “ P IpQq, and therefore IpQ

IpQ

q “ IpQq

P IpQq “ IpQq

IpQq.

To present a graphical description of q

, w e need the following deﬁnition.

Deﬁnition 3.3. Let Q be a loop-less quiver with m ě 1 vertices and n ě 0 arrows. The incidence

(bi)graph IncpQq of a loop-less quiver Q is deﬁned as follows. The set of vertices IncpQq

IncpQq is the set of arrows of Q (that is, IncpQq

“ Q

). The signed edges in IncpQq are given as

follows:

a) Let i and j be adjacent non-parallel arrows in Q. Then the vertices i and j are connected by

exactly one edge a in IncpQq, with sign σpaq given by σpaq “ p´1qσ

pv, iqσ

pv, jq where v

is the (unique) vertex in Q with tvu “ vpiq X vpjq.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 61

b) Let i and j be parallel arrows in Q. Then the vertices i and j are connected by exactly two edges

a and b in IncpQq, with signs given by

σpaq “ p´1qσ

pv, iqσ

pv, jq and σpbq “ p´1qσ

, iqσ

, jq,

where v and v

are the vertices in Q such that vpiq “ tv, v

u “ vpjq. Notice that σpaq “ σpbq.

c) If i and j are non-adjacent arrows in Q, then the vertices i and j are not adjacent in IncpQq.

See [14] for an alternative and more general construction of IncpQq (compare also with the signed line

graph construction in [37, 7]). The following lemma contains a graphical description of the quadratic

form q

Lemma 3.4. For any loop-less quiver Q with n arrows, the quadratic form q

: Z

Ñ Z of Q is a

unit form, and

“ I ´

}

AdjpIncpQqq.

b) q

“ q

IncpQq

c) q

is non-negative.

d) q

is connected if and only if Q is a connected quiver.

Proof:

The non-negativity of q

follows directly from the deﬁnition G

“ IpQq

IpQq. The diagonal

entries of IpQq

IpQq are the squared norms of the columns I

of IpQq. Since Q has no loop, each

column I

“ e

spiq

´ e

tpiq

has squared norm two, which shows that q

is a unit form.

Observe that, by deﬁnition of IncpQq, we have

}

AdjpIncpQqq “

´I

, if i ă j,

0, if i ě j.

In particular, since Q and IncpQq have no loop, we have

2I ´ r

}

AdjpIncpQqq `

}

AdjpIncpQqq

s “ IpQq

IpQq,

that is,

“ I ´

}

AdjpIncpQqq. Therefore q

“ q

IncpQq

By construction, the incidence bigraph IncpQq is connected if and only if Q is connected. Then

the last claim follows from Remark 2.2. [\

3.2. The rank of an incidence matrix

The following result is well known (cf. [37]), and easy to prove.

Lemma 3.5. For a connected loop-less quiver Q we have rkpIpQqq “ |Q

| ´ 1.

62 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

Proof:

Assume ﬁrst that Q is a tree (that is, that |Q

| “ |Q

|´1), and proceed by induction on m “ |Q

| (the

cases m ď 2 are clear). Assume that m ą 2 and take a vertex v in Q with degree one. Then there is a

unique arrow i in Q containing v, and the restriction Q

pvq

is a tree. By induction hypothesis, the set of

columns tI

| j P Q

´ tiuu is linearly independent. Notice that v does not belong to the support of

for j ‰ i, which implies that the whole set tI

jPQ

is linearly independent, which completes the

induction step.

Assume now that Q is an arbitrary connected quiver with n arrows, and choose a spanning tree Q

of Q. By the ﬁrst part of the proof, the set of columns tI

u with j P Q

is linearly independent. In

particular rkpIpQqq ě m ´ 1. Take now an arrow i P Q

´ Q

, and let v and w be respectively the

source and target of i. Then there is a (unique) walk α “ i

¨ ¨ ¨ i

ℓ

in Q

with starting vertex v and

ending vertex w. We have

“

ℓ

i“1

“ e

spαq

´ e

tpαq

“ e

´ e

“ I

which shows that rkpIpQqq ď m ´ 1, hence the result. [\

Corollary 3.6. For a connected loop-less quiver Q we have corkpq

q “ |Q

| ´ |Q

| ` 1.

Proof:

Since q

is a non-negative unit form in |Q

| variables and rkpG

q “ rkpIpQqq (see for instance [38]),

by the lemma above we have the result (for corkpqq “ n ´ rkpG

q). [\

3.3. Connection between the elementary transformations of Q and q

Lemma 3.7. Let Q be a loop-less quiver with arrows i ‰ j. Then, for ǫ P t`1, 0, ´1u, the linear

transformation T

is a ﬂation for q

if and only if T

is a quiver ﬂation for Q.

Proof:

Take q “ q

. Recall that T

is a ﬂation for q if ǫ “ sgnpq

q. O n the other hand, T

is a ﬂation for Q

if ǫ “ ´ǫ

, where i

is a walk of Q, when the arrows i and j are adjacent, and ǫ “ 0 otherwise.

Using Lemma 3.4, w e simply compute q

for each of the cases in Deﬁnition 3.3:

a) Assume vpiq X vpjq “ tv u. Then q

“ σ

pv, iqσ

pv, jq, and i

´σ

pv,iq

pv,jq

is a walk of Q.

Therefore sgnpq

q “ σ

pv, iqσ

pv, jq “ ´ǫ

b) Assume vpiqXvpjq “ tv, wu. Then |q

| “ 2 and sgnpq

q “ σ

pv, iqσ

pv, jq “ σ

pw, iqσ

pw, jq.

As before, i

´σ

pv,iq

pv,jq

is a walk of Q, and sgnpq

q “ σ

pv, iqσ

pv, jq “ ´ǫ

c) If i and j are non-adjacent, then q

“ 0 and ǫ “ 0.

This completes the proof. [\

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 63

Proposition 3.8. Let Q be a loop-less quiver, and consider an elementary transformation A P tV

, S

u for Q (with C a subset of arrows, and arrows i ‰ j) with corresponding elementary linear

transformation A P tV

, S

, T

u. Then

IpQAq “ IpQqA and q

“ q

Proof:

Notice that the claims for A “ V

or A “ S

follow directly from the deﬁnitions, thus we only need

to show the claims for A “ T

If i and j are non-adjacent arrows, there is nothing to prove. Assume that i and j are adjacent

arrows, say vpiq “ tv, wu and vpjq “ tv, w

u. Let I

, I

, . . . be the columns of the (vertex-arrow)

incidence matrix IpQ

q where Q

“ Q T

. By deﬁnition (see 2.5), the new arrow i

in Q

satisﬁes

vpi

q “ tw , w

u, and I

“ I

for any arrow k P Q

´ tiu. M oreover, observe that

pv, iqI

“ σ

pv, iqI

´ σ

pv, jqI

, that is, I

“ I

´ σ

pv, iqσ

pv, jqI

On the other hand, T

is a ﬂation for q

if ǫ “ sgnppq

q. Hence, using Lemma 3.4 we get

ǫ “ σ

pv, iqσ

pv, jq. Take I

“ IpQqT

with columns I

, I

, . . . Then, for k P Q

we have

“ IpQqT

IpQqe

“ I

, if k ‰ i,

IpQqpe

´ ǫe

q “ I

´ ǫI

, if k “ i.

Therefore I

“ I

for all k, which completes the proof (cf. also [14, Proposition 5.2pbq and Re-

mark 5.2]).

For the claims on quadratic forms, taking q “ q

and q

“ q

, we have

“ IpQAq

IpQAq “ A

IpQq

IpQqA “ A

that is, q

“ qA. [\

Remark 3.9. For a subset C of arrows in Q we have

where V

is the point inversion of 2.3 over the indices determined by C.

Proof:

Take q “ q

, q

“ q

and V “ V

. Notice that V

T V is an upper (or lower) triangular matrix if

and only if so is T . This observation and the equality G

“ V

V show that

“ V

V , that

is, q

q. [\

64 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

3.4. Admissibility

The following observation justiﬁes our considerations on F S-transformations.

Lemma 3.10. Let qpxq “

1ďiďjďn

be a unit form, and take indices i ‰ j such that |q

| ď 1.

Consider the F S-transformation

T “

for q, and take q

“ q

T . Then q

q if and only if

“ 0 “ q

for any integer k such that i ă k ă j or j ă k ă i.

Proof:

Assume that i ă j. Consider the m atrix

partitioned in the following way, where q

i,‚

“ pq

i,i`1

, . . . ,

i,j´1

q and q

‚,j

“ pq

i`1,j

, . . . , q

j´1, j

“

A y

0 1 q

i,‚

0 0 G

‚,j

0 0 0 1 z

0 0 0 0 G

‹

‚

and where G

, G

and G

are upper triangular (square) matrices w ith all diagonal entries equal to 1,

with matrices A, B, C and vectors y

, y

, z

of appropriate size. Observe that the composition

has the following shape,

“

´ y

A y

0 2 ´ ǫq

i,‚

´ ǫ z

´ z

0 ´q

‚,j

0 ´ǫ 0 1 z

0 0 0 0 G

‹

‚

Swapping the i-th and j-th columns and rows of the matrix above, we get

“

A y

´ y

0 1 0 ´ǫ z

0 q

‚,j

´q

‚,j

0 q

´ ǫ q

i,‚

2 ´ ǫq

´ z

0 0 0 0 G

‹

‚

Now, since ǫ “ sgnpq

q and |q

| ď 1, then q

´ ǫ “ 0 (and 2 ´ ǫq

“ 1, as already argued in

Remark 2.3paq). We conclude by observing that

T is an upper triangular matrix if and only if

i,‚

“ 0 and q

‚,j

“ 0. The case j ă i can be shown in a similar way. [\

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 65

A F S-transformation

for q such that q

q will be called q-admissible.

For an arrow i P Q

in a loop-less quiver Q, consider the set Q

piq of all arrows in Q adjacent to

arrow i, that is, Q

piq “ tj P Q

| j ‰ i and vpiq X vpjq ‰ Hu. We say that two arrows i ‰ j in Q

are Q-admissible (or that

is Q-asmissible) if we have

k R Q

piq Y Q

pjq, for any arrow k with i ă k ă j or j ă k ă i.

Corollary 3.11. Let Q be a loop-less quiver with arrow s i ‰ j, and consider the ﬂation

T “

for

Q, and the corresponding F S-transformation

T “

for q

. Then

T is q

-admissible if and only if

T is Q-admissible, and in that case

Proof:

Take q

pxq “

1ďiďjďn

. By Lemma 3.10 , the transformation

T is q

admissible if and only if

“ 0 “ q

for all k such that i ă k ă j or j ă k ă i. Correspondingly, using Lemma 3.4 and the

deﬁnition of incidence graph IncpQq, this means that

k R Q

piq Y Q

pjq, for any arrow k with i ă k ă j or j ă k ă i,

that is,

T is q

admissible if and only if

T is Q -admissible. [\

3.5. Iterated transformations

Recall that by iterated F S-(linear) transformation

T for q we mean a composition of the form

T “

¨ ¨ ¨

such that

is a F S-transformation for q

t´1

, where q

“ q and we take recursively

“ q

t´1

, and such that each q

is a unit form for t “ 1, . . . , r. If each

is q

t´1

-admissible,

we say that

T is a q-admissible iterated F S-(linear) transformation. In this case we have q

An iterated F S-transformation

T of a loop-less quiver Q is a concatenation

T “

¨ ¨ ¨

of F S-transformations such that if we take inductively Q

“ Q and Q

“ Q

t´1

, then the pair of

arrows i

and j

are not parallel in Q

t´1

for t “ 1, . . . , r. The expression Q

T denotes the ﬁnal (loop-

less) quiver Q

. If in each step t, the F S-transformation

is Q

t´1

-admissible, then the iterated

F S-transformation

T is called Q-admissible. By deﬁnition and Corollary 3.11,

T is Q-admissible if

and only if

T is q

admissible, and in that case

Notice that if

T is a Q-admissible iterated F S-transformation, and

is a Q

T -admissible iterated

F S-transformation, then the concatenation

is a Q-admissible iterated F S-transformation.

Recall that a maximal (quiver) star S

with n arrows is a tree quiver with n ` 1 vertices (and

arbitrary direction of its arrows), such that there exists a vertex v

incident to all arrows of the quiver

66 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

(called center of the star). One of our m ain combinatorial problems is to show that any tree quiver

can be brought to a maximal star via an admissible iterated F S-transformation. We need the following

key preliminary observation.

Lemma 3.12. For any maximal (quiver) star S and any vertex v P S

, there exists a S-admissible

iterated F S-transformation

T such that S

T is a maximal star having v as its center.

Proof:

Let 1, . . . , n be the arrows of the maximal star S, all of them having in common the center of the star

, and assume n ě 2. The rest of vertices v

, . . . , v

of S are enumerated such that v

is incident to

the arrow t for t “ 1, . . . , n. We show that the following is a S-admissible iterated F S-transformation,

W “

2,1

3,2

¨ ¨ ¨

n,n´1

For t “ 1, . . . , n, take Q

to be the tree quiver with same set of vertices than S, given by

●

t`1

✉

“

. v

t´1

✇

❏

(the direction of arrows, not shown in the diagram, is irrelevant for the proof). Then Q

“ S, and

clearly

t`1,t

is a Q

-admissible F S-transformation (admissibility holds since t ` 1 and t are consec-

utive arrows). Observe that Q

t`1

“ Q

t`1,t

, and thus by deﬁnition Q

“ SW. Notice also that Q

is a maximal star with center the vertex v

, that W is a Q

-admissible iterated F S-transformation, and

that the ﬁrst arrow 1 in Q

joins the vertices v

and v

. In particular, the quiver pSWqW is a maximal

star with center v

, w hose ﬁrst arrow joins vertices v

and v

Now, if v “ v

is the original center of the star, there is nothing to do. If v “ v

for some

1 ď t ď n, then we may repeat the above construction t times to get a maximal star SW

with center

the vertex v

, as wanted, where W

denotes the concatenation of t copies of W. [\

Proposition 3.13. For any tree quiver Q with selected vertex v, there exists a Q-admissible iterated

F S-transformation

T such that Q

T is a maximal star with center the vertex v.

Proof:

We proceed by induction on the number of arrows n “ |Q

| of the tree Q. For n “ 1 there is nothing

to show. For n “ 2 the tree Q is a star, and we may change the position of its center as in the Lemma

above. Hence, we may assume that n ě 3 and that the claim holds for all trees with less than n arrows.

Let n be the maximal arrow in Q (relative to the total order ď in Q

) and take vpnq “ tv, wu. Let

be the quiver obtained from Q by deleting the arrow n. Then Q

is the disjoint union of exactly two

tree quivers, one containing vertex v and denoted by Q

, and one containing vertex w and denoted by

. The sets Q

and Q

inherit the total order from Q

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 67

Observe that, by the maximality of n, any Q

-admissible iterated F S-transformation is also Q-

admissible, and similarly for Q

. We distinguish two cases:

Case 1. Assume ﬁrst that |Q

| “ 1 (that is, that w is a leaf in Q). By induction hypothesis, we may

assume that Q

is a maximal star with center v. Then Q is a maximal star. We proceed analogously if

| “ 1.

Case 2. Assume that |Q

| ą 1 and |Q

| ą 1, and that the second largest arrow n ´ 1 in Q belongs to

. By induction hypothesis, we may assume that Q

is a maximal star with center v. In particular,

n ´ 1 and n are adjacent arrows and n ´ 1 is a pendant arrow in Q. Then

n´1,n

is a Q-admissible

F S-transformation, and the maximal arrow n in Q

“ Q

n´1,n

is a pendant arrow in Q

. Apply then

Case 1 to the tree quiver Q

To complete the proof, use the Lemma above to change the center of the resulting maximal star,

as desired. [\

Remark 3.14. For a loop-less quiver Q, all Q-admissible iterated F S-transformations are reversible.

To be precise, if

T “

¨ ¨ ¨

is a Q-admissible iterated F S-transformation and Q

“ Q

T , then

´1

:“

´ǫ

¨ ¨ ¨

´ǫ

is a Q

-admissible F S-transformation, and Q “ Q

´1

Proof:

The claim follows inductively from Remark 2.6pbq. [\

3.6. Strong congruence among posi tive unit forms of Dynkin type A

The following proposition is one of the goals in [14] (see [14, Theorem 5.5pcq and Corollary 6.6]).

Here we give a short proof. For c ě 0, deﬁne the canonical c-extension linear quiver

ÝÑ

pcq

as a

quiver obtained from the linear quiver

ÝÑ

“

ÝÑ

p0q

“ v

. . . v

n`1

by adding c

arrows from v

n`1

to v

ÝÑ

pcq

“ v

. . . v

n´1

n`1

n`c

n`1

¨¨¨

Observe that the incidence graph of

ÝÑ

pcq

is the canonical c-vertex extension

pcq

of Dynkin type

, as deﬁned by Simson in [26, Deﬁnition 2.2],

Incp

ÝÑ

pcq

q “

pcq

Proposition 3.15. Let q be a connected non-negative unit form of Dynkin type A

. Then there is a

connected loop-less quiver Q such that q “ q

68 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

Proof:

By Theorem 2.4, there is an iterated ﬂation T “ T

¨ ¨ ¨ T

for q such that qT “ q

pcq

is the

canonical c-extension of q

(for c ě 0 the corank of q, see [26, 32]).

Take Q as the unique quiver satisfying

IpQq “ Ip

ÝÑ

pcq

´1

and notice that for any x P Z

we have

pxq “

IpQq

IpQqx “

´tr

ÝÑ

pcq

ÝÑ

pcq

´1

x “

“ q

pcq

´1

xq “ qpxq,

that is, q “ q

. [\

Now we are ready to prove one of the main Gram classiﬁcation results of the paper.

Theorem 3.16. Let q be a connected positive unit form of Dynkin type A

. If q

is a unit form with

„ q, then there exists a composition of q-admissible iterated F S-linear transformations and sign

changes B, such that

Proof:

Let Q be a tree quiver such that q “ q

as in Proposition 3.15. By Proposition 3.13, there is a Q-

admissible iterated F S-transformation

T such that Q

T is a maximal star. Take an arrow inversion V

such that S “ Q

T V has all arrows pointing away from the star center. Denote by

T the F S-linear

transformation for q corresponding to

T , and by V the point inversion corresponding to V, so that

qT V “ q

, by P roposition 3.8.

Now, if q

„ q then q

is a connected positive unit form (by Lemma 2.1). As before, there

is a composition of q

-admissible iterated F S-linear transformations T

, and a point inversion V

such that q

“ q

“ qT V . Considering the linear transform ation B “ T V pV

´1

, by

Corollary 3.11 and Remark 3.9 we have q

q, which completes the proof. [\

4. Combinatorial Coxeter analysis of unit forms of Dynkin type A

We begin this section giving some combinatorial deﬁnitions, in particular the notion of inverse of a

quiver, w hich will be used for the Coxeter analysis of non-negative unit forms of Dynkin type A

. Let

Q “ pQ

, Q

, s, tq be a loop-less quiver, with a ﬁxed total ordering ď of its arrows, and consider the

sets

pv, iq “ tj P Q

| j ă i and v P vpiq X vpjq u,

for each vertex v and each arrow i of Q.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 69

Deﬁnition 4.1. Let α “ i

¨ ¨ ¨ i

ℓ

be a non-trivial walk of Q.

a) We say that the walk α is minimally decreasing if

t`1

“ max Q

, i

q, for t “ 0, . . . , ℓ ´ 1.

b) If α is minimally decreasing, we say that α is left complete if whenever βα is minimally

decreasing for some walk β, then β is a trivial walk. Similarly, α is right complete if whenever

αβ is minimally decreasing for some walk β, then β is a trivial walk. A left and right complete

minimally decreasing walk will be called structural (decreasing) walk.

We will mainly consider the following particular minimally decreasing walks. For an arrow i with

there are exactly two right complete minimally descending walks starting with arrow i, one starting at

vertex sptq and denoted by α

q, and one starting at vertex tpiq and denoted by α

´1

q. To be

precise, if

q “ pv

´1

, i

, v

, i

, v

, . . . , v

ℓ´1

, i

ℓ

, v

ℓ

then v

´1

“ spiq, i

“ i, i

t`1

“ max Q

, i

q for t “ 0, . . . , ℓ ´ 1, and Q

ℓ

, i

ℓ

q “ H.

Similarly, if

´1

q “ pv

´1

, i

, v

, i

, v

, . . . , v

ℓ´1

, i

ℓ

, v

ℓ

then v

´1

“ tpiq, i

“ i, i

t`1

“ max Q

, i

q for t “ 0, . . . , ℓ ´ 1, and Q

ℓ

, i

ℓ

q “ H. For a

vertex v we denote by α

pvq the unique structural decreasing walk starting at v.

Consider dually the minimally increasing walks α

˘1

q and α

pvq.

Deﬁnition 4.2. Deﬁne a new quiver Q

“ pQ

, Q

, s

, t

q having the same set of vertices Q

“ Q

than Q, and the same number of arrows |Q

| “ |Q

|, and such that each arrow i in Q corresponds to

an arrow i

in Q

, given by

q “ tpα

´1

qq, and t

q “ tpα

qq.

The order of the set of arrows of Q

corresponds to the order in Q

(that is, i

ď j

in Q

if and only

if i ď j in Q

The quiver Q

deﬁned above will be referred to as inverse quiver of Q , and we will use the

notation Q

´1

“ Q

(we will drop the asterisk ˚ on arrows of Q

´1

when the context allows it).

Proposition 4.4 below, for which w e need the following technical result, justiﬁes our deﬁnitions.

4.1. A technical lemma

Recall that the columns of the (vertex-arrow) incidence matrix IpQq of Q are denoted by I

“ spiq ´

tpiq P Z

for an arrow i of Q. The columns of IpQ

´1

q will be denoted by I

´1

for an arrow i of

the inverse quiver Q

´1

. For convenience, we consider the function x´, ´y : Q

ˆ Q

Ñ Z given by

xi, jy “ I

for arrows i and j in Q.

70 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

Lemma 4.3. Let Q be a loop-less quiver. Deﬁne an auxiliary function Ξ : Q

ˆ Q

Ñ Z

, given

for a vertex v and an arrow k of Q by,

Ξpv, kq “

iPQ

pv,kq

´1

xi, ky

|xi, ky|

where as usual the sum is zero when the set of indices is empty. Then the following assertions hold:

a) If j “ max Q

pv, kq and vpjq “ tv, wu, then Ξpv, kq “

xj,ky

|xj,ky|

´ Ξpw, jqs.

b) For any arrow k with vpkq “ tv, wu we have Ξpv, kq ` Ξpw, kq “ I

´ I

´1

In particular, for any arrow k in Q the following recursive formula for I

´1

holds,

´1

“ I

iăk

´1

xi, ky.

Proof:

We proceed by induction on the totally ordered arrows Q

. Observe that if k is minimal in Q

, then

Ξpspkq, kq “ 0 “ Ξptpkq, kq and I

´1

“ I

, therefore all claims hold in this case. For simplicity, for

adjacent arrows j and k we take

σpj, kq “

xj, ky

|xj, ky|

P t˘1u.

To verify paq for an arrow k, assume that pbq is satisﬁed for all arrows smaller than k. Then, since

j “ max Q

pv, kq, we have Q

pv, kq “ tju Y Q

pv, jq, and therefore

Ξpv, kq “ I

´1

σpj, kq `

iPQ

pv,jq

´1

σpi, kq

“ I

´1

σpj, kq `

iPQ

pv,jq

´1

σpi, jqσpj, kq (1)

“ σpj, kq

”

´1

` Ξpv, jq

“ σpj, kq

”

´1

` I

´ I

´1

´ Ξpw, jq

(2)

“ σpj, kq rI

´ Ξpw, jqs ,

where the equality (1) holds since σpi, jqσpj, kq “ σpi, kq whenever vpiq X vpjq X vpkq ‰ H, and

the equality (2) holds applying pbq to the arrow j.

To show pbq, assume the claim holds for all arrows smaller than k, and that paq holds for all arrows

smaller than or equal to k. Consider the minimally descending walk α “ α

´1

q of i

“ k as in the

deﬁnition above,

α “ i

¨ ¨ ¨ i

(in particular, ǫ

“ ´1 since tpkq “ v

´1

). For simplicity, for such a walk and for t “ 1, . . . , r deﬁne

σpi

, i

t´1

, . . . , i

, i

q “ p´1q

t`1

, i

t´1

y xi

t´1

, i

t´2

y ¨ ¨ ¨ xi

, i

|xi

, i

t´1

y xi

t´1

, i

t´2

y ¨ ¨ ¨ xi

, i

P t˘1u.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 71

Applying recursively paq we get Ξpv

, i

q “

t“1

σpi

, . . . , i

q. H owever, since spi

q “ v

, we

have σpi

, . . . , i

q “ ´σpv

, i

q “ ǫ

, and therefore the above expression for Ξpv

, i

q is a telescopic

sum, that is,

Ξpv

, i

q “ I

` . . . ` I

“ e

´ e

ξpv

Proceeding similarly for Ξpw

, i

q, where w

“ tpi

q, we ﬁnd that

Ξpw

, i

q “ e

ξpw

´ e

Since our deﬁnition of I

´1

is I

´1

“ e

ξpv

´ e

ξpw

, these equations yield the result,

Ξpv

, i

q ` Ξpw

, i

q “ e

´ e

ξpv

` e

ξpw

´ e

“ I

´ I

´1

Now, to verify the last claim, for an arrow k with vpkq “ tv, wu consider the sets

X “ Q

pv, kq ´ Q

pw, kq, Y “ Q

pw, kq ´ Q

pv, kq and Z “ Q

pv, kq X Q

pw, kq.

Then, applying pbq, we get

´1

“ I

iPQ

pv,kq

´1

σpi, kq ´

iPQ

pw,kq

´1

σpi, kq

“ I

iPXYY

´1

xj, ky

|xj, ky|

` 2

iPZ

´1

xj, ky

|xj, ky|

“ I

iăk

´1

xi, ky,

where the last equality holds since |xi, ky| “ 1 if i P X Y Y , and |xi, ky| “ 2 if i P Z (observe that

Z is the set of arrows smaller than k that are parallel to k), and xi, ky “ 0 if i R X Y Y Y Z. This

completes the proof. [\

4.2. Gram matrices of a quiver and its inverse

We recall that the inverse quiver of a loop-less quiver Q is given in Deﬁnition 4.2, and is denoted by

´1

Proposition 4.4. Let Q be a loop-less quiver with inverse quiver Q

´1

and upper triangular Gram

matrices

and

´1

. Then

IpQ

´1

q “ IpQq

´1

and

´1

“ I.

Proof:

Take G “

and let A be the (upper) triangular adjacency matrix

}

AdjpIncpQqq of the incidence

bigraph IncpQq of Q (hence G ` G

“ IpQq

IpQq “ 2I ´ pA ` A

q, cf. 3.1). We proceed by

induction on the number of arrows m “ |Q

| of Q (the claim is trivial for m “ 1). Let 1, . . . , m

be the ordered arrows of Q, and denote by

Q the quiver obtained from Q by removing the maximal

72 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

arrow m. Notice that, by maximality, the inverse

´1

is obtained from Q

´1

by removing its maximal

arrow. Then

Qq “ rI

| ¨ ¨ ¨ |I

m´1

s, and G “

G ´V

0 1

where

G “

and V is the column vector of size m´1 given by V “ pxt, myq

m´1

t“1

(since G “ I´A,

cf. Lemma 3.4). Observe that

´1

“

´1

0 1

therefore, by induction hypothesis,

IpQqG

´1

“ rIp

Qq|I

´1

0 1

“ rIp

´1

|Ip

´1

V ` I

“ rIp

´1

q|I

` Ip

´1

qV s.

We have shown in Lemma 4.3 that

` Ip

´1

qV “ I

m´1

t“1

´1

xt, my “ I

´1

that is, IpQqG

´1

“ rIp

´1

q|I

´1

s “ IpQ

´1

q, as wanted.

Now we show that

´1

“ I. By the ﬁrst claim, observe that

´1

“ G

´1

“ IpQ

´1

IpQ

´1

“

´tr

IpQq

´1

“

´tr

´1

“

´tr

´1

“

´tr

´1

This completes the proof since both

´1 and

´1

are upper triangular matrices. [\

As consequence we have the following important observation.

Corollary 4.5. For a loop-less quiver Q the following assertions hold.

a) The inverse quiver Q

´1

has no loop, and

Q “ pQ

´1

b) The quiver Q is connected if and only if Q

´1

is connected.

c) Inverses commute with arrow inversions, that is, if C is a set of arrows in Q, and C

is the set

of corresponding arrows in Q

´1

, then pQV

´1

“ Q

´1

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 73

Proof:

For paq, if Q

´1

has a loop, then its (vertex-arrow) incidence matrix IpQ

´1

q has a zero column, say

“ 0. Then the i-th diagonal entry of G

´1

“ IpQ

´1

IpQ

´1

q is zero. But G

´1

“

´1

´tr

which means that the i-th diagonal entry of

´1

is zero. This is impossible since

´1

is invertible. It

follows that the inverse quiver Q

´1

has no loop. Now, applying Proposition 4.4, we obtain

IppQ

´1

q “ IpQ

´1

“ rIpQq

´1

“ IpQq,

that is, Q “ pQ

´1

. This completes the proof of paq.

For pbq, notice that the construction of the inverse Q

´1

involves only vertices and arrows inside

the connected components of Q, that is, if Q “ Q

Y Q

, then

´1

“ pQ

´1

Y pQ

´1

Using paq, this show s that Q is connected if and only if so is Q

´1

For pcq, by applying Propositions 3.8 and 4.4 we obtain

IppQV

´1

q “ IpQV

´1

“ IpQqV

´1

“ IpQq

´1

´tr

“ IpQ

´1

“ IpQ

´1

Here we use the equalities

“V

(cf. Remark 3.9) and V

´tr

“V

. Clearly IppQV

´1

q“

IpQ

´1

q implies pQV

´1

“ Q

´1

. This ﬁnishes the proof of pcq. [\

4.3. A combinatorial formula for the Coxeter matrix

The Coxeter matrix associated to a unit form q on n variables is the n ˆ n matrix given by

“ ´

´1

The characteristic polynomial of Φ

, given by ϕ

pλq “ det pIλ ´ Φ

q, is called Coxeter polynomial

of q. The Coxeter nu mber c

of q is the minimal natural number m such that Φ

“ I, if such number

exists, and c

“ 8 otherwise (cf. [29] for these and related deﬁnitions). The following result may be

found in [29, Proposition 4.2] in a wider context.

Lemma 4.6. Let q and q

be unit forms. If q

q, then

“ B

´tr

In particular, ϕ

pλq “ ϕ

pλq and c

“ c

Proof:

By hypothesis we have

“ B

B, therefore

´1

“ B

´1

´tr

, and

“ ´

´1

“ ´pB

BqpB

´1

´tr

q “ B

´tr

Finally, both the characteristic polynomial and the order of a square matrix are similarity invariants,

therefore the remaining two equalities hold. [\

74 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

We now give a combinatorial expression for the Coxeter matrix of some unit forms.

Theorem 4.7. For a loop-less quiver Q, the following formula for the Coxeter matrix Φ

of the unit

form q

holds,

“ I ´ IpQq

IpQ

´1

Proof:

By Proposition 4.4 we have

I ´ IpQq

IpQ

´1

q “ I ´ IpQq

IpQq

´1

“ I ´ G

´1

“ I ´ p

´1

“ I ´ I ´

´1

“ ´

´1

“ Φ

since

“

. [\

We deﬁne the C oxeter matrix Φ

of a loop-less quiver Q as

“ I ´ IpQq

IpQ

´1

The Coxeter polynomial of q

, denoted by ϕ

pλq, is also referred to as Coxeter polynomial of Q.

Corollary 4.8. Let q : Z

Ñ Z be a connected non-negative unit form of Dynkin type A

n´c

(with

c the corank of q). Then the entries c

of the Coxeter matrix Φ

“ pc

i,j“1

of q are bounded as

follows.

´ δ

| ď 2, for i, j “ 1, . . . , n,

where δ

“ 1 if i “ j and δ

“ 0 otherwise. Moreover,

a) If q is principal (that is, of corank one) and |q

| ď 1 for all i, j “ 1, . . . , n, then |c

| ď 2 for

i, j “ 1, . . . , n.

b) If q is positive, then |c

| ď 1 for i, j “ 1, . . . , n.

Proof:

By Proposition 3.15, there is a connected loop-less quiver Q such that q “ q

. If I

and I

´1

denote

respectively the columns of the (vertex-arrow ) incidence matrices IpQq and IpQ

´1

q, then the pi, jq-th

entry d

of the matrix Φ

´ I is d

“ ´I

´1

. In particular,

| ď 2 and ´ 2 ď d

ď 0, for i, j “ 1, . . . , n.

Hence the general claim follows since d

` δ

“ c

, by T heorem 4.7.

Let q be a principal unit form. By Corollary 3.6, w e see that the connected quiver Q satisﬁes

| “ |Q

| (that is, Q is a 1-tree quiver). Assume, to the contrary, that there is an arrow i such that

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 75

´1

“ ´2, that is, i and its corresponding arrow i

in the inverse quiver Q

´1

are parallel arrows

with opposite directions, say

spiq “ v “ t

q and tpiq “ w “ s

where Q “ pQ

, Q

, s, tq and Q

´1

“ pQ

, Q

, s

, t

q. Let α “ α

´1

q and β “ α

q be the

minimally descending walks starting with arrow i, as given after Deﬁnition 4.1. Then

spαq “ tpiq “ s

q “ tpαq and spβq “ spiq “ t

q “ tpβq,

that is, both α and β are closed walks. Since Q is a 1-tree and α ‰ β (for spαq ‰ spβq), and both α

and β are minimally descending walks, we conclude that α “ i

and β “ i

´ǫ

. In particular

| “ 2, which proves the claim paq.

Assume now that q is a positive unit form. Again by Corollary 3.6, we see that the connected

quiver Q is a tree. Assume that i and j are arrows in Q such that v

q “ vpjq. Let α “ i

¨ ¨ ¨ i

and β “ j

¨ ¨ ¨ j

be as before, where i “ i

“ j

. In this situation, observe that there are signs

ǫ, η P t˘1u such that the following is a non-trivial closed walk in Q,

¨ ¨ ¨ j

´ǫ

¨ ¨ ¨ i

´ǫ

which is impossible since Q is a tree. This shows that |c

| ď 1 for i ‰ j.

Finally, for any arrow i in Q with corresponding arrow i

in Q

´1

, w e may argue as above to show

that if vpiqXv

q ‰ 0, then either spiq “ s

q or tpiq “ t

q. This shows that d

“ ´I

´1

t´2, ´1, 0u, and in particular c

“ d

` 1 P t´1, 0, 1u, which completes the proof of pbq. [\

4.4. Extended maximal stars

Recall that a 1-tree quiver is a connected quiver Q with |Q

| “ |Q

|. By maximal 1-star we mean

a 1-tree quiver

S such there is a vertex v P

(called center of the star) incident to all arrows of

Notice that there is exactly one pair of parallel arrows in

S, say ℓ ă m. In that case, if the maximal

1-star quiver

S has n ` 1 arrows and 1 ď ℓ ă m ď n ` 1, we use the notation

S “

ℓ,m

For instance, the cases

ℓ,5

for 1 ď ℓ ă 5, with corresponding inverses shown underneath, have the

following shapes,





⑧



❄



⑧



❄



⑧



❄



⑧

⑧

⑧



❄

⑧

76 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

We now generalize Lemma 3.12 and Proposition 3.13 to maximal 1-stars.

Lemma 4.9. Let

S be a maximal 1-star quiver.

a) For an arbitrary vertex v of

S, there is a

S-admissible iterated F S-transformation

T such that

T is a maximal 1-star with center v.

b) If

S “

ℓ,m

and

“

ℓ

, then q

« q

if and only if

´ ℓ

q “ pm ´ ℓq or pm

´ ℓ

q ` pm ´ ℓq “ n ` 1.

Proof:

Let

“ t1, . . . , n, n ` 1u be the arrows of the maximal 1-star

S, all of them having in common the

center of the star v

, and assume n ą 3. Take

S “

ℓ,m

for arrows 1 ď ℓ ă m ď n`1, and enumerate

the non-central vertices of

S so that v

is incident to arrow t for t “ 1, . . . , m ´ 1, and to arrow t ` 1

for t “ m, . . . , n.

To prove paq it is enough to show, as in Lemma 3.12, that there is a

S-admissible iterated F S

transformation

T such that

T is a maximal 1-star with center v

, and such that the vertex v

incident to the minimal arrow of

T . We distinguish three cases:

Case 1. Assume ﬁrst that ℓ ą 1. We use the following iterated F S-transformation,

W “

2,1

3,2

¨ ¨ ¨

n`1,n

As in Lemma 3.12, a direct computation shows

ℓ,m

W “

ℓ´1,m´1

where now v

is the star center of

SW, and the ﬁrst arrow of

SW is joining vertices v

and v

Case 2. Assume now that ℓ “ 1 and m ą 2, and consider the following iterated F S transformation,

“

2,1

3,2

¨ ¨ ¨

m´1,m´2

m`1,m

¨ ¨ ¨

n`1,n

obtained from W by omitting the transformation

m,m´1

. Notice similarly that

1,m

W “

m´1,n`1

Indeed, the quiver Q :“

2,1

3,2

¨ ¨ ¨

m´1,m´2

has the following shape,

❖

m`1

. v

m´1

m´2

♦

n`1

▼

The arrows m and m ´ 1 are parallel in Q, therefore we omit

m,m´1

to avoid loops (see Remark 2.6).

However,

m`1,m

¨ ¨ ¨

n`1,n

is a Q-admissible iterated F S-transformation, and one can directly com-

pute

1,m

“ Q

m`1,m

¨ ¨ ¨

n`1,n

“

m´1,n`1

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 77

Moreover, since m ą 2, both vertices v

and v

are incident to the minimal arrow of

Case 3. Assume now that ℓ “ 1 and m “ 2. Take

M “

n,n`1

n´1,n

¨ ¨ ¨

1,2

and M

“

n´1,n

¨ ¨ ¨

1,2

and observe that Q

“

n´1

has the following shape,

“ v

❖

n`1

❖

n´1

n´2

“ v

❖

n`1

❖

♦

n´1



Notice also that Q

“

1,n`1

is a maximal 1-star with center v

, and such that v

is incident to the

minimal arrow of Q

Take now

T to be the transformation W, W

or M

n´1

in cases 1, 2 and 3 respectively, and

observe that we have

ℓ,m

T “

ℓ´1,m´1

, if ℓ ą 1,

m´1,n`1

, if ℓ “ 1 .

(3)

By the above,

T is a maximal 1-star with center v

and such that v

is incident to the minimal arrow

T , which shows the inductive step to complete the proof of paq.

To show pbq, if

´ ℓ

q “ pm ´ ℓq or pm

´ ℓ

q ` pm ´ ℓq “ n ` 1,

then by Corollary 3.11 and equation (3) we have q

« q

. For the converse, assume that q

« q

Using equation (3), we may also assume that m “ n ` 1 “ m

, and that 1 ď ℓ, ℓ

n`1

. In this case,

consider the shape of the Coxeter polynomial of

S (see remark below), must have ℓ “ ℓ

. Hence the

result. [\

Remark 4.10. A direct calculation using the description of Coxeter matrices in Theorem 4.7 yields

the following Coxeter polynomial for a maximal 1-star

S “

ℓ,m

pλq “ pλ

m´ℓ

´ 1qpλ

pn`1q´pm´ℓq

´ 1q.

Therefore, Lemma 4.9pbq may be reinterpreted as follows:

b’) Two maximal 1-star quivers are strongly Gram congruent if and only if they have the same

Coxeter polynomial.

Results of this kind for posets may be found in [11].

78 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

Proposition 4.11. Let Q be a 1-tree quiver. Then for any vertex v in Q there is a Q-admissible iterated

F S-transformation

T such that Q

T is a maximal 1-star w ith center the vertex v.

Proof:

We proceed as in Proposition 3.13, that is, by induction on the number n “ |Q

| of arrows in Q. For

n “ 1, 2 the tree Q is a 1-star, and we may change the position of its center as in the Lemma above.

Hence, we may assume that n ě 3 and that the claim holds for all 1-trees with less than n arrows.

Let n be the maximal arrow in Q (relative to the total order ď in Q

) and take vpnq “ tv, wu.

Let Q

be the quiver obtained from Q by deleting the arrow n. The set Q

inherits a total order

from Q

. Observe that, by the maximality of n, any Q

-admissible iterated F S-transformation is also

Q-admissible. We distinguish two cases:

Case 1. Assume ﬁrst that Q

is a connected quiver. Then Q

is a (0´)tree, and we may use Proposi-

tion 3.13 to assume that Q

is a maximal star with center v. Since vpnq “ tv, wu, then Q is a maximal

1-star.

Case 2. Assume now that Q

is not connected. Then Q

is the disjoint union of exactly two connected

quivers, one containing vertex v and denoted by Q

, and one containing vertex w and denoted by Q

Subcase 2.1. Assume ﬁrst that |Q

| “ 1. T hen Q

is a 1-tree, and by induction hypothesis we

may assume that Q

is a maximal 1-star with center v. Hence Q is a maximal star, and we proceed

analogously if |Q

| “ 1.

Subcase 2.2. Assume now that |Q

| ą 1 and |Q

| ą 1, and that the second largest arrow n ´ 1 in

Q belongs to Q

. Since Q is a 1-tree, either Q

is a 0-tree or a 1-tree w ith less than n arrows. Thus,

by Proposition 3.13 or induction hypothesis respectively, we may assume that Q

is a maximal c-star

with center v for c “ 0 or c “ 1. First, if n ´ 1 is a pendant arrow in Q

, then n is a pendant arrow in

“ Q

n´1,n

, and we may apply Case 1 above to the 1-tree quiver Q

. Second, if n ´ 1 has a parallel

arrow j in Q

, then the arrows j, n ´ 1 and n form a cycle in Q

, and we may apply Case 1 above to

the 1-tree quiver Q

To complete the proof, use Lemma 4.9paq to change the center of the resulting 1-star as desired. [\

We end this section with the second main classiﬁcation result of the paper.

Theorem 4.12. Two (connected) principal unit forms of Dynkin type A

are strongly Gram congruent

if and only if they have the same Coxeter polynomial.

Proof:

Since Coxeter polynomials are strong Gram invariants (Lemma 4.6), we only need to show sufﬁ ciency:

assume q and q

are principal unit forms in n ` 1 variables, both of Dynkin type A

and same Coxeter

polynomial. By Proposition 3.15, there are connected 1-tree quivers Q and Q

such that q “ q

and

“ q

. By Proposition 4.11, there is a Q-admissible iterated F S-transformation

T and a maximal

1-star

ℓ,m

(for some n ě 1 and 1 ď ℓ ă m ď n ` 1), such that Q

T “

ℓ,m

. By Lemma 4.9pbq and

Remark 4.10, we may assume that m “ n ` 1 and 1 ď ℓ ď

n`1

is such that

pλq “ ϕ

ℓ,n`1

pλq “ pλ

ℓ

´ 1qpλ

n`1´ℓ

´ 1q.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 79

Proceeding similarly for q

, since ϕ

“ ϕ

, we ﬁnd a Q

-admissible iterated F S-transformation

with Q

“

ℓ,n`1

“ Q

T , hence q « q

by Corollary 3.11. [\

Concluding remarks and future work

We stress that the proof of all preparatory results towards the main theorems (the elementary quiver

transformations, Lemmas 3.12, 4.9, Propositions 3.13, 4.11, and most importantly, Proposition 3.15)

are completely constructive, and can be easily implemented in any programming language of general

use. In particular, one may follow the proofs of Theorems 3.16 and 4.12 to ﬁnd algorithmic solutions

to Problem B in terms of iterated F S-transformations, for the case of non-negative unit forms of

Dynkin type A

of corank zero or one.

It seems to be a good idea to consider quadratic forms q : Z

Ñ Z having symmetric Gram matrix

factorized as

“ I

for a n ˆ m matrix I with “special” properties, for instance, one having columns in the root systems

as given in [8, Deﬁnitions 3.1 and 3.2]. Any such quadratic form is clearly non-negative. Here we

consider the root system A

given in [8, Deﬁnition 3.1], that is, matrices I such that for each column

(for i “ 1, . . . , n) there are signs S , T P t˘1u and indices s, t P t1, . . . , nu satisfying

i) Ie

“ Se

` T e

ii) S ‰ T .

iii) s ‰ t.

Indeed, matrices with these three conditions are precisely the (vertex-arrow) incidence matrices of

loop-less quivers, and Proposition 3.15 asserts that the corresponding quadratic forms are precisely

the non-negative unit forms with all components of Dynkin type A

Assume, additionally, that A is a Z-invertible matrix morsiﬁcation of q with integer coefﬁcients

(in the sense of Simson [24]). As in the proof of Theorem 4.7, the Coxeter matrix Φ

“ ´A

´1

A admits the following expression,

“ I

´ I

´1

In an upcoming paper [15], we show that the similarity invariants of Φ

correspond to the orthogonal

invariants of the matrix

“ I

´ IA

´1

which turns out to be an orthogonal matrix, producing in this way many important strong Gram in-

variants of A. The particular case when IA

´1

satisﬁes again conditions pi ´ iiiq above has special

combinatorial features, as illustrated in Section 4.2 when A is the standard morsiﬁcation of q. In

this case, IA

´1

is precisely the incidence matrix of the inverse of the quiver with incidence matrix

I. Although successful for coranks zero and one, we do not know whether the technique of F S-

transformations used in Lemmas 3.12 and 4.9 can be generalized to higher coranks (even corank two).

80 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

As in the proofs of Propositions 3.13 and 4.11, and Theorems 3.16 and 4.12, such a generalization

would imply the Coxeter spectral determination of strong Gram classes of non-negative unit forms of

Dynkin type A

, as in the positive and principal case. In an upcoming work, we approach such strong

classiﬁcation with a matricial method.

A different direction is to omit conditions piiq and piiiq on I, that is, to consider simply “incidence

matrices” as in [37]. In a future work we show that the corresponding quadratic forms include not only

non-negative semi-unit forms of Dynkin type A

, but also those of Dynkin type D

, as well as the

Euler form of important classes of algebras (for instance, gentle algebras of ﬁnite global dimension).

Moreover, the results of 4.3 and [15] can be extended to unimodular morsiﬁcations of quadratic forms

with Gram matrix factorized by “incidence matrices”, potentially facilitating their Coxeter spectral

analysis.

In some sense, the matrix I exposes internal properties of I

I. The straightforward constructions

and considerations of the paper work in support of this claim.

References

[1] A igner M. On the Linegraph of a Directed Graph, Math. Zeitschr. 1967. 102:56–61.

doi:10.1007/BF01110285.

[2] Barot M. A cha racterization of positive unit forms, Bol. Soc. M at. Mexicana 1999. 5(1):87-93.

ISSN:1405-213X, ID:124439229.

[3] Barot M, Geiss C, and Zelevinsky A . Cluster algebras o f ﬁnite type and positive symmetrizable matrices.

J. London Math. Soc., 2006. 73(3):545–564. doi:10.1112/S0024610706022769.

[4] Barot M, Jiménez González JA, and de la Peña JA. Quadratic Forms: Combinatorics and Numeri-

cal Results, Alg e bra and Applications, Vol. 25 Springer Nature Switzerland AG 20 18. ISBN-1 3:978-

3030056261, 10:3030056260.

[5] Barot M, and de la Peña JA. The Dynkin type of a non-negative unit form, Expo. Math. 1999. 17:339–

348.

[6] Barot M , and de la Peña JA. Root-induced integral quadratic forms, L inear Algebra Appl. 2006.

412(2):291–302. doi:10.1016/j.la a .2005.06. 030.

[7] Belardo F, Li Marzi EM, and Simi

c SK. Signed line graph s with least eigenvalue ´2: The star comp le-

ment technique, Discrete Applied Mathematics 2016. 207:2 9–38. doi:10.1016 /j. dam.2016.02.018.

[8] Cameron PJ, Goethals JM, Seidel JJ, and Shult EE. Line graphs, Root Systems, and Elliptic Ge ometry,

J. Algebra 1976. 43(1):305–327. doi:10.1016/0021 -8693(76)90162-9.

[9] Cavaleri M, D’Angelo D, and Donno A. Characterizations of line graphs in signed and gain graphs.

2021. arXiv:2101.09677v2 [math.CO]

[10] Cvetkovi

c D, Rowlinson P, and Simi

c S. Spectral Generalizations of Line Graphs, On

graphs with least eigenvalue ´2, Cambridge University Press, 2004. ISBN:9780511751752.

doi:10.1017/CBO9780511751752.

[11] G ˛asiorek M, Simson D, and Zaj ˛ac K. Algorithmic computatio n of principal posets

using Maple and Py thon. Algebra and Discrete M a th. 2014. 17(1):33–69. URL

http://dspace.nbuv.gov.ua/handle/123456789/152339.

J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative 81

[12] Geller D, and Harary F. Arrow diagrams are line diagrams, SIAM J. Appl. Math., 1968 . 16(6):1141–

1145. URL https://www.jstor.org/stable/2099532.

[13] Harary F, and Norman RZ. Some properties of line d igraphs, Rend. Circ. Mat. Palermo 1961. 9:161–

168. doi:10.1007/BF02854581.

[14] Jiménez González JA. Incidence graphs and non-negative integral quadratic forms. Journal of Algebra

2018. 513:208–245. do i:10.1016/j.jalgebra.2018.07.020.

[15] Jiménez González JA. Coxeter invaria nts for non-negative unit forms of Dynkin type A

. 2020.

arXiv:2010.09991v1 [math.CO].

[16] Kosakowska J. Inﬂation algorithms for po sitive and principal edge-bipartite graphs and unit quadratic

forms, Fund. Inform. 2012. 119(2):149–162, doi.org/10.3233/FI-2012-731.

[17] Makuracki B, and Mróz A. Root systems and inﬂations of non-negative quasi-Cartan matrices, Linear

Algebra Appl. 2019. 580:128–165. doi:10.1016/j.laa.2019.06.006.

[18] Makuracki B, and Simson D. A Gram cla ssiﬁcation of principal Cox-regular edge-bipartite graphs via

inﬂation algo rithm , Discrete Appl. Math. 2019. 253:25–36. doi:10.1 016/j.dam.2017.10.033.

[19] Meyer CD. Matrix Analysis and Applied Linear Algebra. Philadelphia, SIAM, 2000.

ISBN:9780898714548. doi:10.1137 /1.9780898719512.

[20] Ovsienko SA. Integral weakly positive forms, in: Schur Matrix Problems and Quadratic Forms (Rus-

sian), in: Inst. Mat. Akad. Nauk USSR, Preprint 7 8.25, 1978 pp. 3–17.

[21] Simson D. Mesh algorithms for so lv ing principal Diophantine equations, sand-glass tubes and tori of

roots. Fund. Inform., 2011. 109(4):425–462. doi:10.3233/FI-20 11-520.

[22] Simson D. Mesh geometries of root orb its of integral quadratic forms, J. Pure Appl. Algebras 2011.

215(1):13–34. doi:10.1016/j.jpaa.2010.02.029.

[23] Simson D. A Coxeter Gram classiﬁca tion of positive simply lac e d edge-bipartite graphs. SIAM J. D is-

crete Math., 2013. 27(2):827–854. doi:10.1137/110843721.

[24] Simson D. Algorithms determining matrix morsiﬁcations, Weyl orbits, Coxeter polynomials and mesh

geometries of roots for Dynkin diagrams, Fund. Inform. 2013. 123:447–490.

[25] Simson D. A framework for Cox e te r spectral analysis of edge-bipartite graphs, their rational mo rsiﬁ-

cations and mesh geometries of root orbits, Fund. Inform. 2013. 124(3):309–338. doi:10.3233/FI-2013-

836.

[26] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classiﬁcation

of edge-bipa rtite graphs I. A Gram classiﬁcation. Fund. Inform., 2016. 145(1):19–48. doi:10.3233/FI-

2016-1345.

[27] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classiﬁcation

of edge-bipa rtite graphs II. Isotropy mini-groups. Fund. Inform., 2 016. 145(1):4 9–80. doi:10. 3233/FI-

2016-1346.

[28] Simson D. A Coxeter spectral classiﬁcation of positive edge-bipartite graphs I. Dynkin types B

, C

, G

, E

. Linear Algebra Appl. 2018. 557:105–133. doi:10.10 16/J.LAA.2018.07.013.

[29] Simson D. A computational technique in Coxeter spectral study of symme trizable integer Cartan matri-

ces. Linear Algebra Appl., 2020. 586(3):190–238 . doi:10.1016/j.laa.20 19.10.015.

82 J. A. Jiménez González / A Graph Theoretical Framework for the Strong Gram Classiﬁcation of Non-negative

[30] Simson D. A Coxeter spectral classiﬁcation of positive edge-bipartite graphs II. Dynkin type D

. Linear

Algebra and its Applications 2021. 612:223–272. doi:10.101 6/j.laa.2020.11.001.

[31] Simson D. Weyl orbits of matrix morsiﬁcations and a Coxeter spe ctral classiﬁcation of p ositive signed

graphs and quasi-Cartan matrices of Dynkin type A

. Preprint.

[32] Simson D, and Zaj ˛ac K. Inﬂation a lgorithm for loop-free non-negative edge-bipartite graph s of corank

at least two, Linear Algebra Appl. 2017. 524:109–152. doi:10.1016/j.laa.2017.02.021.

[33] von Höhne H-J. On weakly positive unit forms, Com ment. Math. Helvetici 198 8. 63:312–336.

doi:10.1007/BF02566771.

[34] Zaslavsky T. The geometry of root systems and signed graphs, Amer. Math. Monthly 1981. 88(2 ):88–

105. doi:10.2307/2321133.

[35] Zaslavsky T. Signed graphs, Discrete Applied Mathematics. North-Holland Publishing Compa ny 19 82.

4(1):4 7–74. doi:10.1016/0166-218X(82)90033-6.

[36] Zaslavsky T. Line graphs of switching classes, Report of the XVIIIth O.S.U. Denison Maths Conference

(Granville, Ohio, 1984), pp. 2–4 . Dept. of Math., Ohio State Univ., Columbus, Ohio, 1984.

[37] Zaslavsky T. Matrices in the theory of signed simple graphs, in: Advances in Discrete Mathematics

and Applications: Mysore, 2008, in Ramanujan Math. Soc. Lect. Notes Ser., Vol. 13, Ramanujan Math.

Soc., Mysore, 201 0, pp. 207–229.

[38] Zhang F. Matrix Theory: Basic Results and Techniques, 2nd Ed. Springer 1999. ISBN:978-1-4757-

5797-2.