Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let me start with a question for which I know the answer. Consider a symmetric integral $n\times n$ matrix $A=(a_{ij})$ such that $a_{ii}=2$, and for $i\ne j$ one has $a_{ij}=0$ or $-1$. One can encode such a matrix by a graph $G$: it has $n$ vertices, and two vertices $i,j$ are connected by an edge iff $a_{ij}=-1$.

Question 1: Which graphs correspond to positive definite $A$?

Answer 1: (Classical, well-known, and easy) $G$ is a disjoint union of $A_n$, $D_n$, $E_n$. (http://en.wikipedia.org/wiki/Root_system)

Now let me put a little twist to this. Let us also allow $a_{ij}=+1$ for $i\ne j$, and encode this by putting a broken edge between $i$ and $j$ (or an edge of different color, if you prefer).

Real question: Which of these graphs correspond to positive definite $A$?


Let me add some partial considerations which do not quite go far enough. (Some of these were in the helpful Gjergji's answer.)

(1) Consider the set $R$ of shortest vectors in $\mathbb Z^n$; they have square 2. Reflections in elements $r\in R$ send $R$ to itself, and $R$ spans $\mathbb Z^n$ since it contains the standard basis vectors $e_i$. By the standard result about root lattices, $\mathbb Z^n$ is then a direct sum of the $A_n$, $D_n$, $E_n$ root lattices, and one can restrict to the case of a single direct summand.

Hence, the question equivalent to the following: what are the graphs corresponding to all possible bases of $\mathbb R^n$ in which the basis vectors are roots?

The case of $R=A_n$ is relatively easy. The roots are of the form $f_a-f_b$, with $a,b \in (1,\dots,n+1)$. Every collection $e_i$ corresponds to an oriented spanning tree on the set $(1,\dots,n+1)$. The 2-colored graph is computed from that tree. I don't see a clean description of the graphs obtained via this procedure, but it is something.

For $D_n$, similarly, a basis is described by an auxiliary connected graph $S$ on $n$ vertices with $n$ edges whose ends are labeled $+$ or $-$. The graph $G$ is computed from $S$.

And for $E_6,E_7,E_8$ there are of course only finitely many cases, but for me the emphasis is on MANY, very many.

So has anybody done this? Is there a table in some paper or book which contains all the 2-colored graphs obtained this way, or -- better still -- a clean characterization of such graphs?

(2) There is a notion of "weakly positive quadratic forms" used in the cluster algebra theory (see for example the first pages of LNM 1099 (Tame Algebras and Integral Quadratic Forms) by Ringel. And there is some kind of classification theory for them. Maybe I am mistaken, but this seems to be quite different: a quadratic form $q$ is "weakly positive" if $q\ge 0$ on the first quadrant $\mathbb Z_{\ge0}^n$. So there is no direct relation to my question, it seems.

share|improve this question
    
I know $K_n$ is the complete graph and $C_n$ is a cycle graph and I am assuming that $E_n$ is the empty graph. What are $A_n$ and $D_n$? –  Robby McKilliam Sep 2 '10 at 6:13
2  
@Robby, no, these are "Dynkin diagrams." See, e.g., en.wikipedia.org/wiki/Root_system –  Gerry Myerson Sep 2 '10 at 7:02
1  
Possibly a start could be the description of unit positive definite sincere quadratic forms given in "Sincere weakly positive unit quadratic forms" by M.V. Zeldich (Canadian Mathematical Society, Conference proceedings, Vol 14, 1993). Parts of it can be previewed here books.google.com/… –  Gjergji Zaimi Sep 2 '10 at 12:30
1  
"Clearly, the standard basis vectors $e_i$ are roots (they have square 2), and generate the lattice $Z^n.$ By the standard result about root lattices, $Z^n$ is then a direct sum of the $A_n, D_n, E_n$ root lattices, and one can restrict to the case of a single direct summand." I cannot follow this at all: by definition, a root lattice is spanned by a root system, which is a finite set $R$ of vectors invariant under reflections in the hyperplanes orthogonal to the vectors from $R.$ So what is the root system associated with the matrix $A$? –  Victor Protsak Sep 2 '10 at 15:13
1  
@Victor: let $R$ be the set of all integral elements of $Z^n$ of square 2. Then $R$ is finite, spans $Z^n$ (because it contains $e_i$), and reflections in the elements $r\in R$ send $R$ to itself. It follows that $R$ is a reduced root system, a direct sum of $A_n,D_n,E_n$. So after changing a $\mathbb Z$-basis, we get one of the ADE graphs. In the original basis $e_i$, the graph may not be ADE. My question is: what is it? –  VA. Sep 2 '10 at 15:25
add comment

2 Answers

I have studied a closely related problem (but never published the results and my notes are messy). Consider a set $\mathcal S$ of roots in a simply laced root system. Associate to $\mathcal S$ the graph with edges given by pairs of distinct, non-opposite roots which are not orthogonal. (In other terms, forget the colouring of the edges in your graph.)

Up to 8 vertices you get all graphs in this way. For more than 8 vertices, there are graphs which are not of this form. (There are some necessary conditions related to the Arf invariant of an associated quadratic form over $\mathbb F_2$. One works of course only with connected components.)

The trick, if I remember correctly, is to work modulo $2$ and to show that in certain situations, one can "lift" a solution into (projective) subsets of roots.

More precisely, one can define invertible combinatorial moves (chirurgies) on graphs which come from transformations on subsets contained in root systems (and which amount to convections in symplectic spaces over $\mathbb F_2$).

For at most eight vertices, one can then look at the equivalence classes of such moves and show that each equivalence class contains a member realizable by a suitable subset of roots (in a uniquely defined minimal simply laced root-system). In particular, every graph with at most $8$ vertices has a a certain "root-type".

share|improve this answer
    
That is very interesting. This sort of implies that there is little hope for a nice classification. On the other hand, graphs for the $A_n$ and $D_n$ lattices do have a clear structure, and in the $E_6$, $E_7$, $E_8$ cases there are only finitely many graphs. –  VA. Sep 3 '10 at 13:28
    
Do you really get all graphs with ≤8 vertices, as you say? For example, consider the graph on 5 vertices with the edges 12,13,14,15,23,24,25. How do you get that? What is the root system? –  VA. Sep 20 '10 at 12:52
    
Take the elements $(1,1,0,0)$, $(1,0,1,0)$, $(1,0,0,1)$, $(1,0,0,-1)$, $(0,1,1,0)$ of the root system $D_4$. –  Roland Bacher Sep 22 '10 at 11:55
    
They are linearly dependent, so the quadratic form is not positive definite. This may work for the problem you investigated but not for my question. Indeed, I think that there is no positive definite form for this graph, for any way of putting solid and broken edges. –  VA. Sep 23 '10 at 7:41
    
The quadratic form is the usual scalar product of $\mathbb R^4$. These five vectors define five roots contained in the root system $D_4$ so it is obvious that they are linearly dependent but this has no relation with the quadratic form which is always non-negative but not necessarily positive-definite. However I answered your question with respect to the framework of my answer which is related but not identical with the framework of your question. –  Roland Bacher Sep 23 '10 at 8:00
add comment

In "Cluster algebras of finite type and positive symmetrizable matrices" by Barot, Geiss and Zelevinsky we can see that positive definite quasi-Cartan matrices (defined the same as Cartan matrices but relaxing the condition of non-positivity of elements off the diagonal) actually come from positive definite Cartan matrices. That is, each positive definite quasi-Cartan matrix is equivalent to a positive definite Cartan matrix, where equivalence in the symmetric case is defined as $A\sim B$ if there is a matrix $E$ with determinant $\pm 1$ so that $A=E^TBE$. This is proved in proposition 2.9.

This means that the graphs you are looking for are classified up to the equivalence relation above. Since a such a matrix $E$ as above can be constructed easily for the case of trees for example this means that all trees that answer your question are also ADE.

A classification result that includes the trees example above is given in "Sincere weakly positive unit quadratic forms" by M.V. Zeldich (Canadian Mathematical Society, Conference proceedings, Vol 14, 1993) and again, this classification contains graphs that are obtained from ADE by some modifications, and the resulting graphs are described with 2-colored edges.

share|improve this answer
    
Gjergji, thanks for the answer but no, these are observations are obvious, known to me, and don't go very far. Yes, $e_i$ are roots and generate the lattice, so the lattice is of $ADE$ type. From there, it is a long step, unclear to me, to classify the 2-colored graphs. For trees, it is trivial to get rid of $+1$. "Weakly positive" quad. forms are not positive definite; they are $\ge0$ on the first quadrant $\mathbb N^n$. –  VA. Sep 2 '10 at 11:33
    
Gjergji, Are you referring to a paper entitled "Sincere weakly positive unit quadratic forms"? Where can I see 'this classification'? I would like to check it out. Can you give a reference? –  VA. Sep 2 '10 at 11:40
    
@VA: Sorry I keep writing nonsense here. I will try to be more careful. :P –  Gjergji Zaimi Sep 3 '10 at 14:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.